NDLI: Efficient and accurate nearest neighbor and closest pair search in high-dimensional space

Please wait, while we are loading the content...

ACM Transactions on Database Systems (TODS) : Volume 42

ACM Transactions on Database Systems (TODS) : Volume 41

ACM Transactions on Database Systems (TODS) : Volume 40

ACM Transactions on Database Systems (TODS) : Volume 39

ACM Transactions on Database Systems (TODS) : Volume 38

ACM Transactions on Database Systems (TODS) : Volume 37

ACM Transactions on Database Systems (TODS) : Volume 36

ACM Transactions on Database Systems (TODS) : Volume 35

Issue 4, November 2010

Issue 3, July 2010

A survey of B-tree locking techniques

Continuous online index tuning in moving object databases

Privacy-aware location data publishing

Improving XML search by generating and utilizing informative result snippets

Efficient and accurate nearest neighbor and closest pair search in high-dimensional space

Views and queries: Determinacy and rewriting

Towards a logical reconstruction of a theory for locally closed databases

Issue 2, April 2010

Issue 1, February 2010

ACM Transactions on Database Systems (TODS) : Volume 34

ACM Transactions on Database Systems (TODS) : Volume 33

ACM Transactions on Database Systems (TODS) : Volume 32

ACM Transactions on Database Systems (TODS) : Volume 31

ACM Transactions on Database Systems (TODS) : Volume 30

ACM Transactions on Database Systems (TODS) : Volume 29

ACM Transactions on Database Systems (TODS) : Volume 28

ACM Transactions on Database Systems (TODS) : Volume 27

ACM Transactions on Database Systems (TODS) : Volume 26

ACM Transactions on Database Systems (TODS) : Volume 25

ACM Transactions on Database Systems (TODS) : Volume 24

ACM Transactions on Database Systems (TODS) : Volume 23

ACM Transactions on Database Systems (TODS) : Volume 22

ACM Transactions on Database Systems (TODS) : Volume 21

ACM Transactions on Database Systems (TODS) : Volume 20

ACM Transactions on Database Systems (TODS) : Volume 19

ACM Transactions on Database Systems (TODS) : Volume 18

ACM Transactions on Database Systems (TODS) : Volume 17

ACM Transactions on Database Systems (TODS) : Volume 16

ACM Transactions on Database Systems (TODS) : Volume 15

ACM Transactions on Database Systems (TODS) : Volume 14

ACM Transactions on Database Systems (TODS) : Volume 13

ACM Transactions on Database Systems (TODS) : Volume 12

ACM Transactions on Database Systems (TODS) : Volume 11

ACM Transactions on Database Systems (TODS) : Volume 10

ACM Transactions on Database Systems (TODS) : Volume 9

ACM Transactions on Database Systems (TODS) : Volume 8

ACM Transactions on Database Systems (TODS) : Volume 7

ACM Transactions on Database Systems (TODS) : Volume 6

ACM Transactions on Database Systems (TODS) : Volume 5

ACM Transactions on Database Systems (TODS) : Volume 4

ACM Transactions on Database Systems (TODS) : Volume 3

ACM Transactions on Database Systems (TODS) : Volume 2

ACM Transactions on Database Systems (TODS) : Volume 1

Efficient and accurate nearest neighbor and closest pair search in high-dimensional space

Content Provider	ACM Digital Library
Author	Yi, Ke Sheng, Cheng Tao, Yufei Kalnis, Panos
Copyright Year	2010
Abstract	Nearest Neighbor (NN) search in high-dimensional space is an important problem in many applications. From the database perspective, a good solution needs to have two properties: (i) it can be easily incorporated in a relational database, and (ii) its query cost should increase $\textit{sublinearly}$ with the dataset size, regardless of the data and query distributions. Locality-Sensitive Hashing (LSH) is a well-known methodology fulfilling both requirements, but its current implementations either incur expensive space and query cost, or abandon its theoretical guarantee on the quality of query results. Motivated by this, we improve LSH by proposing an access method called the Locality-Sensitive B-tree (LSB-tree) to enable fast, accurate, high-dimensional NN search in relational databases. The combination of several LSB-trees forms a $\textit{LSB-forest}$ that has strong quality guarantees, but improves dramatically the efficiency of the previous LSH implementation having the same guarantees. In practice, the LSB-tree itself is also an effective index which consumes linear space, supports efficient updates, and provides accurate query results. In our experiments, the LSB-tree was faster than: (i) iDistance (a famous technique for exact NN search) by two orders of magnitude, and (ii) MedRank (a recent approximate method with nontrivial quality guarantees) by one order of magnitude, and meanwhile returned much better results. As a second step, we extend our LSB technique to solve another classic problem, called Closest Pair (CP) search, in high-dimensional space. The long-term challenge for this problem has been to achieve $\textit{subquadratic}$ running time at very high dimensionalities, which fails most of the existing solutions. We show that, using a LSB-forest, CP search can be accomplished in (worst-case) time significantly lower than the quadratic complexity, yet still ensuring very good quality. In practice, accurate answers can be found using just two LSB-trees, thus giving a substantial reduction in the space and running time. In our experiments, our technique was faster: (i) than distance browsing (a well-known method for solving the problem exactly) by several orders of magnitude, and (ii) than D-shift (an approximate approach with theoretical guarantees in low-dimensional space) by one order of magnitude, and at the same time, outputs better results.
Starting Page	1
Ending Page	46
Page Count	46
File Format	PDF
ISSN	03625915
e-ISSN	15574644
DOI	10.1145/1806907.1806912
Volume Number	35
Issue Number	3
Journal	ACM Transactions on Database Systems (TODS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2010-07-30
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Locality-sensitive hashing Closest pair search Nearest neighbor search
Content Type	Text
Resource Type	Article
Subject	Information Systems

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Efficient and accurate nearest neighbor and closest pair search in high dimensional space.

Quality and efficiency in high dimensional nearest neighbor search

Reverse Nearest Neighbors Search in High Dimensions using Locality-Sensitive Hashing

Reverse Nearest Neighbors Search in High Dimensions using Locality-Sensitive Hashing

CLSH: Cluster-based Locality-Sensitive Hashing

Diverse Yet Efficient Retrieval using Locality Sensitive Hashing

Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem

Query-Adaptive Reciprocal Hash Tables for Nearest Neighbor Search

Robust and efficient locality sensitive hashing for nearest neighbor search in large data sets.

Efficient and accurate nearest neighbor and closest pair search in high-dimensional space

Similar Documents

Efficient and accurate nearest neighbor and closest pair search in high dimensional space.

Quality and efficiency in high dimensional nearest neighbor search

Reverse Nearest Neighbors Search in High Dimensions using Locality-Sensitive Hashing

Reverse Nearest Neighbors Search in High Dimensions using Locality-Sensitive Hashing

CLSH: Cluster-based Locality-Sensitive Hashing

Diverse Yet Efficient Retrieval using Locality Sensitive Hashing

Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem

Query-Adaptive Reciprocal Hash Tables for Nearest Neighbor Search

Robust and efficient locality sensitive hashing for nearest neighbor search in large data sets.

Efficient and accurate nearest neighbor and closest pair search in high-dimensional space