Optimizing All-Nearest-Neighbor Queries with Trigonometric Pruning

Published at 22nd International Conference on Scientific and Statistical Database Management (SSDBM)

Conference Date: June 30^th to July 2^nd of 2010
Conference Location: Heidelberg, Germany
Conference Title: 22^nd International Conference on Scientific and Statistical Database Management (SSDBM), Heidelberg, Germany, 2010
Conference Chairs: Andreas Reuter, Michael Gertz Conference Co-Chairs: Tony Hey, Bertram Ludäscher

Abstract

Many applications require to determine the k-nearest neighbors for multiple query points simultaneously. This task is known as all-(k)-nearest- neighbor (AkNN) query. In this paper, we suggest a new method for efficient AkNN query processing which is based on spherical approximations for indexing and query set representation. In this setting, we propose trigonometric pruning which enables a significant decrease of the remaining search space for a query. Employing this new pruning method, we considerably speed up AkNN queries.

Copyright Notes

Tobias Emrich, Franz Graf, Hans-Peter Kriegel, Matthias Schubert, Marisa Thoma
"Optimizing All-Nearest-Neighbor Queries with Trigonometric Pruning", 22nd International Conference on Scientific and Statistical Database Management (SSDBM), Heidelberg, Germany, 2010.

M. Gertz and B. Ludäscher (Eds.): SSDBM 2010, LNCS 6187, pp. 501-518, 2010.
© Springer-Verlag Berlin Heidelberg 2010

DOI: 10.1007/978-3-642-13818-8_35

Documents

This is the author’s version of the work. It is posted here by permission of Springer for your personal use. Not for redistribution.

Paper

BibTex

@INPROCEEDINGS{EmrGraKriSchetal10b,
  AUTHOR    = {Emrich, Tobias and Graf, Franz and Kriegel, Hans-Peter
              and Schubert, Matthias and Thoma, Marisa},
  TITLE     = {Optimizing All-Nearest-Neighbor Queries with Trigonometric Pruning},
  BOOKTITLE = {Proceedings of the 22nd International Conference on
              Scientific and Statistical Database Management (SSDBM),
              Heidelberg, Germany},
  VOLUME    = {6187},
  PAGES     = {501--518},
  YEAR      = {2010},
  DOI       = {10.1007/978-3-642-13818-8_35}
}