TY - GEN
T1 - MLR-index
T2 - 21st International Conference on Scientific and Statistical Database Management, SSDBM 2009
AU - Malik, Rahul
AU - Kim, Sangkyum
AU - Jin, Xin
AU - Ramachandran, Chandrasekar
AU - Han, Jiawei
AU - Gupta, Indranil
AU - Nahrstedt, Klara
N1 - Funding Information:
The work was supported in part by the U.S. NSF grants CNS-0520182, IIS-0513678, IIS-0842769, CAREER CNS-0448246, ITR CMS-0427089 and Air Force Office of Scientific Research MURI award FA9550-08-1-0265. Any opinions, findings, and conclusions expressed here are those of the authors and do not necessarily reflect the views of the funding agencies.
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=69049102406&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=69049102406&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-02279-1_12
DO - 10.1007/978-3-642-02279-1_12
M3 - Conference contribution
AN - SCOPUS:69049102406
SN - 3642022782
SN - 9783642022784
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 167
EP - 184
BT - Scientific and Statistical Database Management - 21st International Conference, SSDBM 2009, Proceedings
Y2 - 2 June 2009 through 4 June 2009
ER -