Browse

A Fast k-Nearest Neighbor Search Using Query-Specific Signature Selection

Cited 0 time in Web of Science Cited 2 time in Scopus
Authors
Park, Youngki; Hwang, Heasoo; Lee, Sang-goo
Issue Date
2016-03-07
Citation
CIKM’15, October 19–23, 2015, Melbourne, Australia
Keywords
k-nearest neighbor searchlocality sensitive hashing
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.
URI
http://hdl.handle.net/10371/95640
DOI
https://doi.org/10.1145/2806416.2806632
Files in This Item:
There are no files associated with this item.
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Computer Science and Engineering (컴퓨터공학부)Journal Papers (저널논문_컴퓨터공학부)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse