poster

Optimal incremental multi-step nearest-neighbor search

Authors:

Ming Zhang,

Reda Alhajj,

Jon RokneAuthors Info & Claims

GIS '08: Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems

Article No.: 75, Pages 1 - 4

https://doi.org/10.1145/1463434.1463520

Published: 05 November 2008 Publication History

Get Access

Abstract

The distance measures used to determine the dissimilarities between high-dimensional feature vectors are often expensive to compute. To reduce the number of expensive distance calculations in the search process, Korn, et al [5] proposed a multi-step algorithm, which involves two stages: filtering and refinement. This algorithm was later improved by Seidl and Kriegel [8] to produce optimal-sized candidate set in the filtering stage; the improved algorithm is said to be filtering optimal, but can not produce the result incrementally in the refinement stage. In this paper, we propose an extended version of the algorithm that can produce the nearest neighbors incrementally in an optimal way. Our algorithm is both filtering and refinement optimal, and well serves real applications. We proved the optimality of the proposed extended algorithm.

References

[1]

I. Assent, A. Wenning, T. Seidl. "Approximation techniques for indexing the Earth Mover's Distance in multimedia databases." Proc. of IEEE ICDE, 2006.

Digital Library

Google Scholar

[2]

S. Berchtold, D. Keim, and H. P. Kriegel. "The X-tree: an index structure for high-dimensional data." Proc. ofVLDB, pp. 28--39, 1996.

Digital Library

Google Scholar

[3]

F. Hillier and G. Lieberman. Introduction to Linear Programming. McGraw-Hill, 1990.

Google Scholar

[4]

H. V. Jagadish, B. C. Ooi, K. L. Tan, C. Yu, and R. Zhang. "iDistance: An adaptive B+-tree based indexing method for nearest neighbor search." ACM TODS, 30(2):364--397, 2005.

Digital Library

Google Scholar

[5]

F. Korn, N. Sidiropoulos, C. Faloutsos, E. Siegel and Z. Protopapas, "Fast Nearest Neighbor Search in Medical Image Databases." Proc. of VLDB, pp. 215--226, 1996.

Digital Library

Google Scholar

[6]

H. P. Kriegel, P. Kröger, P. Kunath and M. Renz. "Generalizing the Optimality of Multi-step k-Nearest Neighbor Query Processing." Proc. of SSTD, pp. 75--92, July 2007.

Digital Library

Google Scholar

[7]

Y. Rubner, C. Tomasi and L. Guibas. "The Earth Mover's Distance as a Metric for Image Retrieval." International Journal of Computer Vision, 40(2):99--121, 2000.

Digital Library

Google Scholar

[8]

T. Seidl, H. P. Kriegel. "Optimal Multi-Step k-Nearest Neighbor Search." Proc. of ACM-SIGMOD, pp. 154--165, 1998.

Digital Library

Google Scholar

[9]

J. Venkateswaran, D. Lachwani, T. Kahveci, and C. Jermaine. "Reference-based indexing of sequences databases." Proc. of VLDB, pp. 906--917, 2006.

Digital Library

Google Scholar

Cited By

View all

Beecks CBerrendorf M(2018)Optimal k-Nearest-Neighbor Query Processing via Multiple Lower Bound Approximations2018 IEEE International Conference on Big Data (Big Data)10.1109/BigData.2018.8622493(614-623)Online publication date: Dec-2018
https://doi.org/10.1109/BigData.2018.8622493
Zhang MAlhajj R(2011)Effectiveness of NAQ-tree in handling reverse nearest-neighbor queries in high-dimensional metric spaceKnowledge and Information Systems10.1007/s10115-011-0405-531:2(307-343)Online publication date: 8-May-2011
https://doi.org/10.1007/s10115-011-0405-5
Zhang MAlhajj RRokne J(2010)Effectiveness of optimal incremental multi-step nearest neighbor searchExpert Systems with Applications: An International Journal10.1016/j.eswa.2010.02.14137:8(6018-6027)Online publication date: 1-Aug-2010
https://dl.acm.org/doi/10.1016/j.eswa.2010.02.141

Index Terms

Optimal incremental multi-step nearest-neighbor search
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Unsupervised learning
        Cluster analysis
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Effectiveness of optimal incremental multi-step nearest neighbor search

The development of techniques that facilitate effective similarity search is important for many applications such as multi-media databases, content-based image retrieval, molecular biology, medical imaging, and object recognition, among others. Two of ...
A fast nearest neighbor search algorithm by nonlinear embedding
CVPR '12: Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)

We propose an efficient algorithm to find the exact nearest neighbor based on the Euclidean distance for large-scale computer vision problems. We embed data points nonlinearly onto a low-dimensional space by simple computations and prove that the ...
Improvements of TLAESA nearest neighbour search algorithm and extension to approximation search
ACSC '06: Proceedings of the 29th Australasian Computer Science Conference - Volume 48

Nearest neighbour (NN) searches and k nearest neighbour (k-NN) searches are widely used in pattern recognition and image retrieval. An NN (k-NN) search finds the closest object (closest k objects) to a query object. Although the definition of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GIS '08: Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems

November 2008

559 pages

ISBN:9781605583235

DOI:10.1145/1463434

Program Chairs:
Walid G. Aref
Purdue University
,
Mohamed F. Mokbel
University of Minnesota
,
Markus Schneider
University of Florida

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Poster

Conference

GIS '08

Sponsor:

Microsoft
SIGSPATIAL

GIS '08: 16th International Symposium on Advances in Geographic Information Systems

November 5 - 7, 2008

California, Irvine

Acceptance Rates

Overall Acceptance Rate 257 of 1,238 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
150
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Beecks CBerrendorf M(2018)Optimal k-Nearest-Neighbor Query Processing via Multiple Lower Bound Approximations2018 IEEE International Conference on Big Data (Big Data)10.1109/BigData.2018.8622493(614-623)Online publication date: Dec-2018
https://doi.org/10.1109/BigData.2018.8622493
Zhang MAlhajj R(2011)Effectiveness of NAQ-tree in handling reverse nearest-neighbor queries in high-dimensional metric spaceKnowledge and Information Systems10.1007/s10115-011-0405-531:2(307-343)Online publication date: 8-May-2011
https://doi.org/10.1007/s10115-011-0405-5
Zhang MAlhajj RRokne J(2010)Effectiveness of optimal incremental multi-step nearest neighbor searchExpert Systems with Applications: An International Journal10.1016/j.eswa.2010.02.14137:8(6018-6027)Online publication date: 1-Aug-2010
https://dl.acm.org/doi/10.1016/j.eswa.2010.02.141

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Effectiveness of optimal incremental multi-step nearest neighbor search

A fast nearest neighbor search algorithm by nonlinear embedding

Improvements of TLAESA nearest neighbour search algorithm and extension to approximation search