Name
Title | ||
|---|---|---|
MLR-Index: An Index Structure for Fast and Scalable Similarity Search in High Dimensions |
Abstract | ||
|---|---|---|
High-dimensional indexing has been very popularly used for performing similarity search over various data types such as multimedia (audio/image/video) databases, document collections, time-series data, sensor data and scientific databases. Because of the curse of dimensionality , it is already known that well-known data structures like kd-tree, R-tree, and M-tree suffer in their performance over high-dimensional data space which is inferior to a brute-force approach linear scan . In this paper, we focus on an approximate nearest neighbor search for two different types of queries: r-Range search and k-NN search . Adapting a novel concept of a ring structure, we define a new index structure MLR-Index (Multi-Layer Ring-based Index) in a metric space and propose time and space efficient algorithms with high accuracy. Evaluations through comprehensive experiments comparing with the best-known high-dimensional indexing method LSH show that our approach is faster for a similar accuracy, and shows higher accuracy for a similar response time than LSH . |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-02279-1_12 | SSDBM |
Keywords | Field | DocType |
high dimensions,time-series data,approximate nearest neighbor search,scalable similarity search,r-range search,well-known data structure,various data type,high accuracy,k-nn search,index structure,high-dimensional data space,sensor data,similarity search,data type,high dimensional data,kd tree,data structure,time series data,indexation | Locality-sensitive hashing,Data mining,Data structure,Computer science,Best bin first,Ball tree,Search engine indexing,Curse of dimensionality,Cover tree,Nearest neighbor search,Database | Conference |
Volume | ISSN | Citations |
5566 | 0302-9743 | 1 |
PageRank | References | Authors |
0.34 | 18 | 7 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rahul Malik | 1 | 30 | 2.92 |
| Sangkyum Kim | 2 | 178 | 10.54 |
| Xin Jin | 3 | 503 | 24.30 |
| Chandrasekar Ramachandran | 4 | 73 | 4.42 |
| Jiawei Han | 5 | 43085 | 3824.48 |
| Indranil Gupta | 6 | 1837 | 143.92 |
| Klara Nahrstedt | 7 | 7941 | 636.63 |