 |
|
|
Optimal Multi-Step k-Nearest Neighbor Search |
Full Paper (PDF)
Slides (PDF)
|
For an increasing number of modern database applications, efficient support of similarity search becomes an important task. Along with the complexity of the objects such as images, molecules and mechanical parts, also the complexity of the similarity models increases more and more. Whereas algorithms that are directly based on indexes work well for simple medium- dimensional similarity distance functions, they do not meet the efficiency requirements of complex high-dimensional and adaptable distance functions. The use of a multi-step query processing strategy is recommended in these cases, and our investigations substantiate that the number of candidates which are produced in the filter step and exactly evaluated in the refinement step is a fundamental efficiency parameter. After revealing the strong performance shortcomings of the state-of-the-art algorithm for k-nearest neighbor search [Kor+ 96], we present a novel multi-step algorithm which is guaranteed to produce the minimum number of candidates. Experimental evaluations demonstrate the significant performance gain over the previous solution, and we observed average improvement factors of up to 120 for the number of candidates and up to 48 for the total runtime. |
References, where available, link to the DBLP on the World Wide Web.
[AFS 93]Rakesh Agrawal, Christos Faloutsos, Arun N. Swami:
Efficient Similarity Search In Sequence Databases.
FODO 1993: 69-84[AKS 98]...
[ALSS 95]Rakesh Agrawal, King-Ip Lin, Harpreet S. Sawhney, Kyuseok Shim:
Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases.
VLDB 1995: 490-501[AMN 95]...
[BBKK 97]Stefan Berchtold, Christian Böhm, Daniel A. Keim, Hans-Peter Kriegel:
A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space.
PODS 1997: 78-86[Ber+ 97]Stefan Berchtold, Christian Böhm, Bernhard Braunmüller, Daniel A. Keim, Hans-Peter Kriegel:
Fast Similarity Search in Multimedia Databases.
SIGMOD Conference 1997: 1-12[Ber+ 98]Stefan Berchtold, Bernhard Ertl, Daniel A. Keim, Hans-Peter Kriegel, Thomas Seidl:
Fast Nearest Neighbor Search in High-Dimensional Space.
ICDE 1998: 209-218[BHKS 93]Thomas Brinkhoff, Holger Horn, Hans-Peter Kriegel, Ralf Schneider:
A Storage and Access Architecture for Efficient Query Processing in Spatial Database Systems.
SSD 1993: 357-376[BKK 96]Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel:
The X-tree : An Index Structure for High-Dimensional Data.
VLDB 1996: 28-39[BK 97]Stefan Berchtold, Hans-Peter Kriegel:
S3: Similarity Search in CAD Database Systems.
SIGMOD Conference 1997: 564-567[BMH 92]...
[CPZ 97]Paolo Ciaccia, Marco Patella, Pavel Zezula:
M-tree: An Efficient Access Method for Similarity Search in Metric Spaces.
VLDB 1997: 426-435[Fal+ 94]Christos Faloutsos, Ron Barber, Myron Flickner, Jim Hafner, Wayne Niblack, Dragutin Petkovic, William Equitz:
Efficient and Effective Querying by Image Content.
JIIS 3(3/4): 231-262(1994)[FBF 77]Jerome H. Friedman, Jon Louis Bentley, Raphael A. Finkel:
An Algorithm for Finding Best Matches in Logarithmic Expected Time.
TOMS 3(3): 209-226(1977)[FL 95]Christos Faloutsos, King-Ip Lin:
FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets.
SIGMOD Conference 1995: 163-174[FRM 94]Christos Faloutsos, M. Ranganathan, Yannis Manolopoulos:
Fast Subsequence Matching in Time-Series Databases.
SIGMOD Conference 1994: 419-429[GG 97]...
[GM 93]James E. Gary, Rajiv Mehrotra:
Similar shape retrieval using a structural feature index.
IS 18(7): 525-537(1993)[Haf+ 95]...
[Hen 94]...
[HS 95]Gisli R. Hjaltason, Hanan Samet:
Ranking in Spatial Databases.
SSD 1995: 83-95[Jag 91]H. V. Jagadish:
A Retrieval Technique for Similar Shapes.
SIGMOD Conference 1991: 208-217[Kor+ 96]Flip Korn, Nikolaos Sidiropoulos, Christos Faloutsos, Eliot Siegel, Zenon Protopapas:
Fast Nearest Neighbor Search in Medical Image Databases.
VLDB 1996: 215-226[KS 98]...
[KSS 97]Hans-Peter Kriegel, Thomas Schmidt, Thomas Seidl:
3D Similarity Search by Shape Approximation.
SSD 1997: 11-28[OM 88]Jack A. Orenstein, Frank Manola:
PROBE Spatial Data Modeling and Query Processing in an Image Database Application.
TSE 14(5): 611-629(1988)[PM 97]Apostolos Papadopoulos, Yannis Manolopoulos:
Performance of Nearest Neighbor Queries in R-Trees.
ICDT 1997: 394-408[PS 93]...
[RKV 95]Nick Roussopoulos, Stephen Kelley, Frédéic Vincent:
Nearest Neighbor Queries.
SIGMOD Conference 1995: 71-79[RP 92]...
[Sei 97]...
[SK 97]Thomas Seidl, Hans-Peter Kriegel:
Efficient User-Adaptable Similarity Search in Large Multimedia Databases.
VLDB 1997: 506-515[Spr 91]Robert F. Sproull:
Refinements to Nearest-Neighbor Searching in k-Dimensional Trees.
Algorithmica 6(4): 579-589(1991)[WJ 96]David A. White, Ramesh Jain:
Similarity Indexing with the SS-tree.
ICDE 1996: 516-523
Referenced By:
- Mihael Ankerst, Bernhard Braunmüller, Hans-Peter Kriegel, Thomas Seidl:
Improving Adaptable Similarity Query Processing by Using Approximations.
VLDB 1998: 206-217
|
@inproceedings{DBLP:conf/sigmod/SeidlK98,
author = {Thomas Seidl and
Hans-Peter Kriegel},
editor = {Laura M. Haas and
Ashutosh Tiwary},
title = {Optimal Multi-Step k-Nearest Neighbor Search},
booktitle = {SIGMOD 1998, Proceedings ACM SIGMOD International Conference
on Management of Data, June 2-4, 1998, Seattle, Washington, USA},
publisher = {ACM Press},
year = {1998},
isbn = {0-89791-955-5},
pages = {154-165},
crossref = {DBLP:conf/sigmod/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
|
DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).
|
|
