Paper Info
Title
High-dimensional similarity search using data-sensitive space partitioning
Abstract
Nearest neighbor search has a wide variety of applications. Unfortunately, the majority of search methods do not scale well with dimensionality. Recent efforts have been focused on finding better approximate solutions that improve the locality of data using dimensionality reduction. However, it is possible to preserve the locality of data and find exact nearest neighbors in high dimensions without dimensionality reduction. This paper introduces a novel high-performance technique to find exact k-nearest neighbors in both low and high dimensional spaces. It relies on a new method for data-sensitive space partitioning based on explicit data clustering, which is introduced in the paper for the first time. This organization supports effective reduction of the search space before accessing secondary storage. Costly Euclidean distance calculations are reduced through efficient processing of a lightweight memory-based filter. The algorithm outperforms sequential scan and the VA-File in high-dimensional situations. Moreover, the results with dynamic loading of data show that the technique works well on dynamic datasets as well.
Year
DOI
Venue
2006
10.1007/11827405_72
DEXA
Keywords
Field
DocType
high-dimensional similarity search,exact k-nearest neighbor,dynamic loading,explicit data,search space,data-sensitive space,nearest neighbor search,search method,effective reduction,dynamic datasets,data-sensitive space partitioning,dimensionality reduction,similarity search,data clustering,k nearest neighbor,nearest neighbor,euclidean distance
Space partitioning,Data mining,Dimensionality reduction,Search algorithm,Computer science,Euclidean distance,Full table scan,Algorithm,Curse of dimensionality,Cluster analysis,Nearest neighbor search
Conference
Volume
ISSN
ISBN
4080
0302-9743
3-540-37871-5
Citations 
PageRank 
References 
2
0.35
17
Authors
2
Name
Order
Citations
PageRank
Sachin Kulkarni11518.87
Ratko Orlandic211623.50