Approximate Similarity Retrieval with M-Trees.
Pavel Zezula, Pasquale Savino, Giuseppe Amato, Fausto Rabitti:
Approximate Similarity Retrieval with M-Trees.
VLDB J. 7(4): 275-293(1998)@article{DBLP:journals/vldb/ZezulaSAR98,
author = {Pavel Zezula and
Pasquale Savino and
Giuseppe Amato and
Fausto Rabitti},
title = {Approximate Similarity Retrieval with M-Trees},
journal = {VLDB J.},
volume = {7},
number = {4},
year = {1998},
pages = {275-293},
ee = {db/journals/vldb/ZezulaSAR98.html},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Abstract
Motivated by the urgent need to improve the efficiency of similarity queries, approximate similarity retrieval is investigated in the environment of a metric tree index called the M-tree.
Three different approximation techniques are proposed, which show how to forsake query precision for improved performance.
Measures are defined that can quantify the improvements in performance efficiency and the quality of approximations.
The proposed approximation techniques are then tested on various synthetic and real-life files.
The evidence obtained from the experiments confirms our hypothesis that a high-quality approximated similarity search can be performed at a much lower cost than that needed to obtain the exact results.
The proposed approximation techniques are scalable and appear to be independent of the metric used.
Extensions of these techniques to the environments of other similarity search indexes are also discussed.
Key Words
Access structures - Distance only data - Similarity search - Approximation algorithms - Performance evaluation
Copyright © 1998 by Springer, Berlin, Heidelberg.
Permission to make digital or hard copies of the abstract is granted provided that copies are not made or distributed for profit or
direct commercial advantage, and that copies show this notice along with the full citation.
Citation Page
CDROM Version: Load the CDROM "Volume 5 Issue 2, JACM, VLDB-J, POS, ..." and ...
DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...
References
- [1]
- Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, Angela Y. Wu:
An Optimal Algorithm for Approximate Nearest Neighbor Searching Fixed Dimensions.
J. ACM 45(6): 891-923(1998)
- [2]
- Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger:
The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles.
SIGMOD Conference 1990: 322-331
- [3]
- Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel:
The X-tree : An Index Structure for High-Dimensional Data.
VLDB 1996: 28-39
- [4]
- Tolga Bozkaya, Z. Meral Özsoyoglu:
Distance-Based Indexing for High-Dimensional Metric Spaces.
SIGMOD Conference 1997: 357-368
- [5]
- Sergey Brin:
Near Neighbor Search in Large Metric Spaces.
VLDB 1995: 574-584
- [6]
- ...
- [7]
- ...
- [8]
- Paolo Ciaccia, Marco Patella, Pavel Zezula:
M-tree: An Efficient Access Method for Similarity Search in Metric Spaces.
VLDB 1997: 426-435
- [9]
- Paolo Ciaccia, Marco Patella, Pavel Zezula:
Processing Complex Similarity Queries with Distance-Based Access Methods.
EDBT 1998: 9-23
- [10]
- Paolo Ciaccia, Marco Patella, Pavel Zezula:
A Cost Model for Similarity Queries in Metric Spaces.
PODS 1998: 59-68
- [11]
- Tzi-cker Chiueh:
Content-Based Image Indexing.
VLDB 1994: 582-593
- [12]
- Antonin Guttman:
R-Trees: A Dynamic Index Structure for Spatial Searching.
SIGMOD Conference 1984: 47-57
- [13]
- Patrick A. V. Hall, Geoff R. Dowling:
Approximate String Matching.
ACM Comput. Surv. 12(4): 381-402(1980)
- [14]
- ...
- [15]
- Jirí Matousek:
Geometric Range Searching.
ACM Comput. Surv. 26(4): 421-461(1994)
- [16]
- Thomas Seidl, Hans-Peter Kriegel:
Efficient User-Adaptable Similarity Search in Large Multimedia Databases.
VLDB 1997: 506-515
- [17]
- Markus A. Stricker, Markus Orengo:
Similarity of Color Images.
Storage and Retrieval for Image and Video Databases (SPIE) 1995: 381-392
- [18]
- David A. White, Ramesh Jain:
Similarity Indexing with the SS-tree.
ICDE 1996: 516-523
- [19]
- Pavel Zezula, Pasquale Savino, Fausto Rabitti, Giuseppe Amato, Paolo Ciaccia:
Processing M-trees with Parallel Resources.
RIDE 1998: 147-154
Last update Fri May 25 09:49:58 2012
CET by the DBLP Team — 
Data released under the ODC-BY 1.0 license — See also our legal information page
