Publications
Detailed Information
A Fast k-Nearest Neighbor Search Using Query-Specific Signature Selection
Cited 0 time in
Web of Science
Cited 3 time in Scopus
- Authors
- Issue Date
- 2016-03-07
- Citation
- CIKM’15, October 19–23, 2015, Melbourne, Australia
- Abstract
- k-nearest neighbor (k-NN) search aims at nding k points
nearest to a query point in a given dataset. k-NN search is
important in various applications, but it becomes extremely
expensive in a high-dimensional large dataset. To address
this performance issue, locality-sensitive hashing (LSH) is
suggested as a method of probabilistic dimension reduction
while preserving the relative distances between points. How-
ever, the performance of existing LSH schemes is still in-
consistent, requiring a large amount of search time in some
datasets while the k-NN approximation accuracy is low.
In this paper, we target on improving the performance of
k-NN search and achieving a consistent k-NN search that
performs well in various datasets. In this regard, we pro-
pose a novel LSH scheme called Signature Selection LSH
(S2LSH). First, we generate a highly diversi ed signature
pool containing signature regions of various sizes and shapes.
Then, for a given query point, we rank signature regions of
the query and select points in the highly ranked signature
regions as k-NN candidates of the query. Extensive experi-
ments show that our approach consistently outperforms the
state-of-the-art LSH schemes.
- Files in This Item:
- There are no files associated with this item.
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.