ÍslenskaenEnglish

Aðilar að Skemmunni

Leit eftir:


SkýrslaHáskólinn í Reykjavík>Tölvunarfræðideild>Reykjavik University Technical Report Computer Science. RUTR-CS>

Vinsamlegast notið þetta auðkenni þegar þið vitnið til verksins eða tengið í það: http://hdl.handle.net/1946/7525

Titlar
  • en

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

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

Útgáfa
Júlí 2007
Útdrættir
  • en

    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.

  • Á 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.

Birtist í

RUTR-CS07001

ISSN

1670-5777

Birting
4.2.2011


Skrár
NafnRaðanlegtStærðRaðanlegtAðgangurHækkandiLýsingRaðanlegtSkráartegund
RUTR-CS07001.pdf454KBOpinn Heildartexti PDF Skoða/Opna