MLR-index: An index structure for fast and scalable similarity search in high dimensions

Rahul Malik, Sangkyum Kim, Xin Jin, Chandrasekar Ramachandran, Jiawei Han, Indranil Gupta, Klara Nahrstedt

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationScientific and Statistical Database Management - 21st International Conference, SSDBM 2009, Proceedings
Pages167-184
Number of pages18
DOIs
StatePublished - Aug 27 2009
Event21st International Conference on Scientific and Statistical Database Management, SSDBM 2009 - New Orleans, LA, United States
Duration: Jun 2 2009Jun 4 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5566 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other21st International Conference on Scientific and Statistical Database Management, SSDBM 2009
CountryUnited States
CityNew Orleans, LA
Period6/2/096/4/09

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'MLR-index: An index structure for fast and scalable similarity search in high dimensions'. Together they form a unique fingerprint.

  • Cite this

    Malik, R., Kim, S., Jin, X., Ramachandran, C., Han, J., Gupta, I., & Nahrstedt, K. (2009). MLR-index: An index structure for fast and scalable similarity search in high dimensions. In Scientific and Statistical Database Management - 21st International Conference, SSDBM 2009, Proceedings (pp. 167-184). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5566 LNCS). https://doi.org/10.1007/978-3-642-02279-1_12