Viðburðir eftir árum


PhD defense: Herwig Lejsek - A Scalable Disk-Based High-Dimensional Index

  • 6.5.2015, 10:00 - 12:00

HerwigWhen:  May 6th, from 10:00-10:45 
Where:  M 104
Title:  A Scalable Disk-Based High-Dimensional Index 
PhD student:  Herwig Lejsek
Advisor:  Dr. Björn Þór Jónsson (Reykjavík University)

Thesis committee:  Dr. Laurent Amsaleg (Research Scientist, IRISA-CNRS, France), Dr. Yngvi Björnsson (Professor, Reykjavik University).

Thesis Examiner: Dr. Shin´ichi Satoh (Professor, National Institute of Informatics, Japan. 

Abstract:
This thesis presents the NV-tree (Nearest Vector tree), which addresses thespecific problem of efficiently and effectively finding the approximate k-nearest neighbors within large collections of high-dimensional data points.The NV-tree is a very compact index, as only six bytes are kept in the indexfor each high-dimensional descriptor. It thus scales extremely well whenindexing large collections of high-dimensional descriptors. The NV-tree efficientlyproduces results of good quality, even at such a large scale that theindices can no longer be kept entirely in main memory. We demonstrate thiswith extensive experiments presenting results from various collection sizesfrom 36 million up to nearly 30 billion SIFT (Scale Invariant Feature Transform)descriptors.We also study the conditions under which a nearest neighbour search providesmeaningful results. Following this analysis we compare the NV-tree toLSH (Locality Sensitive Hashing), the most popular method for -distancesearch, showing that the NV-tree outperforms LSH when it comes to theproblem of nearest neighbour retrieval. Beyond this analysis we also discusshow the NV-tree index can be used in practise in industrial applicationsand address two frequently overlooked requirements: dynamicity—the abilityto cope with on-line insertions of new high-dimensional items into theindexed collection—and durability—the ability to recover from crashes andavoid losing the indexed data if a failure occurs. As far as we know, no othernearest neighbor algorithm published so far is able to cope with all threerequirements: scale, dynamicity and durability.




Vinsamlegast athugið að á viðburðum Háskólans í Reykjavík (HR) eru teknar ljósmyndir og myndbönd sem notuð eru í markaðsstarfi HR. Hægt er að nálgast frekari upplýsingar á ru.is eða með því að senda tölvupóst á netfangið: personuvernd@ru.is
//
Please note that at events hosted at Reykjavik University (RU), photographs and videos are taken which might be used for RU marketing purposes. Read more about this on our ru.is or send an e-mail: personuvernd@ru.is