Can I read HD-index: pushing the scalability-accuracy boundary for approximate kNN search in high-dimensional spaces on EtoBox?

HD-index: pushing the scalability-accuracy boundary for approximate kNN search in high-dimensional spaces by Akhil Arora; Sakshi Sinha; Piyush Kumar; Arnab Bhattacharya is a Computer Science article available to read on EtoBox.

What is HD-index: pushing the scalability-accuracy boundary for approximate kNN search in high-dimensional spaces about?

Nearest neighbor searching of large databases in high-dimensional spaces is inherently difficult due to the curse of dimensionality. A flavor of approximation is, therefore, necessary to practically solve the problem of nearest neighbor search. In this paper, we propose a novel yet simple indexing scheme, __HD-Index__ , to solve the problem of __approximate k-nearest neighbor queries__ in massive high-dimensional databases. HD-Index consists of a set of novel hierarchical structures called __RDB-trees__ built on Hilbert keys of database objects. The leaves of the RDB-trees store distances of database objects to reference objects, thereby allowing efficient pruning using distance filters. In addition to triangular inequality, we also use Ptolemaic inequality to produce better lower bounds. Experiments on massive (up to billion scale) high-dimensional (up to 1000+) datasets show that HD-Index is __effective, efficient__ , and __scalable.__

Who reads HD-index: pushing the scalability-accuracy boundary for approximate kNN search in high-dimensional spaces?

Author

Akhil Arora; Sakshi Sinha; Piyush Kumar; Arnab Bhattacharya

Publisher

ACM

Published

2018

Language

EN

Field

Computer Science (Physical Sciences)