EnglishisÍslenska

Member institutions

Search in


ReportReykjavík University>Tölvunarfræðideild>Reykjavik University Technical Report Computer Science. RUTR-CS>

Please use this identifier to cite or link to this item: http://hdl.handle.net/1946/7525

Titles
  • NV-tree: An Efficient Disk-Based Index for Approximate Search in Very Large High-Dimensional Collections

  • is

    NV-tréð: Hraðvirkur diskamiðaður vísir fyrir nálgunarleit í stórum margvíðum gagnasöfnum

Published
July 2007
Abstracts
  • Over the last two decades much research effort has been spent on nearest neighbor search in high-dimensional data sets. Most approaches yet published have, however, only been tested on rather small collections. When large collections have been considered, high-performance environments have been used, in particular systems with a large main memory. Accessing data on disk has largely been avoided, because disk operations are considered to be too slow. It has been shown, however, that using large amounts of memory is generally not an economic choice. Therefore, we propose the NV-tree, which is a very efficient disk-based data structure that can give good approximate answers to nearest neighbor queries with a single disk operation, even for very large collections of high-dimensional data. Using a single NV-tree, the returned results have high recall, but contain a number of false positives. By combining two of three NV-trees, most of these false positives can be avoided while retaining the high recall. Finally, we compare the NV-tree to Locality Sensitive Hashing, a popular method for e-distance search. We show that they return results of similar quality, but the NV-tree uses many fewer disk reads.

  • is

    Á síðustu tveimur áratugum hefur mikil vinna verið lögð í leit að næsta nágranna í margvíðum gagnasöfnum. Flestar virtar aðferðir hafa þó aðeins verið prófaðar á fremur smáum gagnasöfnum. Þegar stór söfn hafa verið skoðuð, hefur sérlega öflugur vélbúnaður verið notaður, einkum kerfi með stóru innra minni. Markmið hefur verið að forðast diskavinnslu, þar sem hún hefur verið talin of hægvirk. Það hefur þó verið sýnt fram á að notkun mjög mikils innra minni er ekki hagkvæm. Þess vegna setjum við fram NV-tréð, sem er mjög hraðvirk diskamiðuð gagnagrind sem gefur góða nálgun við næsta nágranna með einum diskalestri, jafnvel í mjög stórum söfnum af margvíðum gögnum. Með einu NV-tré fást niðrustöður með góðum skilum, en þær innihalda einnig mörg röng svör. Með því að nota tvö eða þrjú NV-tré má sía burtu flest þessara röngu svara án þess að fækka réttu svörunum. Að lokum berum við NV-tréð saman við LSH, sem er vinsæl hökkunaraðferð fyrir e-fjarlægðar fyrirspurnir. Við sýnum að báðar aðferðir geta skilað álíka góðum svörum, en að NV-tréð notar miklu færri diskalesara.

Appeared in

RUTR-CS07001

ISSN

1670-5777

Issued Date
04/02/2011


Artifacts
Name[Sortable]Size[Sortable]Visibility[Sortable]Description[Sortable]Format
RUTR-CS07001.pdf454KBOpen Complete Text PDF View/Open