2011 FastApproximateSimilaritySearch

• (Aoyama et al., 2011) ⇒ Kazuo Aoyama, Kazumi Saito, Hiroshi Sawada, and Naonori Ueda. (2011). “Fast Approximate Similarity Search based on Degree-reduced Neighborhood Graphs.” In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2011) Journal. ISBN:978-1-4503-0813-7 doi:10.1145/2020408.2020576

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222011%22+Fast+Approximate+Similarity+Search+based+on+Degree-reduced+Neighborhood+Graphs
• http://dl.acm.org/citation.cfm?id=2020408.2020576&preflayout=flat#citedby

Quotes

Author Keywords

• Algorithms; approximate algorithm; graph and tree search strategies; index structure; neighborhood graph; performance; [[search process; similarity search; theory

Abstract

This paper presents a fast approximate similarity search method for finding the most similar object to a given query object from an object set with a dissimilarity with a success probability exceeding a given value. As a search index, the proposed method utilizes a degree-reduced k-nearest neighbor (k-DR) graph constructed from the object set with the dissimilarity, and explores the k-DR graph along its edges using a greedy search (GS) algorithm starting from multiple initial vertices with parallel processing. In the graph-construction stage, the structural parameter k of the k-DR graph is determined so that the probability with which at least one search trial of those with multiple initial vertices succeeds is more than the given success probability. To estimate the greedy-search success probability, we introduce the concept of a basin in the k-DR graph. The experimental results on a real data set verify the approximation scheme and high search performance of the proposed method and demonstrate that it is superior to E2LSH in terms of the expected search cost.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2011 FastApproximateSimilaritySearch	Naonori Ueda Kazuo Aoyama Kazumi Saito Hiroshi Sawada			Fast Approximate Similarity Search based on Degree-reduced Neighborhood Graphs				10.1145/2020408.2020576		2011