A cost model for similarity queries in metric spaces
Published 1 May 1998
Paolo Ciaccia, Marco Patella, Pavel Zezula
Citations194
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work insists that the distance distribution of objects can be profitably used to solve the problem of estimating CPU and I/O costs for processing range and k-nearest neighbors queries over metric spaces, and develops a concrete cost model for the M-tree access method.
Abstract
Article A cost model for similarity queries in metric spaces Share on Authors: Paolo Ciaccia DEIS - CSITE-CNR, Bologna, Italy DEIS - CSITE-CNR, Bologna, ItalyView Profile , Marco Patella DEIS - CSITE-CNR, Bologna, Italy DEIS - CSITE-CNR, Bologna, ItalyView Profile , Pavel Zezula IEI-CNR, Pisa, Italy IEI-CNR, Pisa, ItalyView Profile Authors Info & Claims PODS '98: Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsMay 1998 Pages 59–68https://doi.org/10.1145/275487.275495Online:01 May 1998Publication History 104citation586DownloadsMetricsTotal Citations104Total Downloads586Last 12 Months16Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access
Keywords
Computer Science
American Journal of Physics<i>The Fractal Geometry of Nature</i>
21,750 Citations1983Benoît B. Mandelbrot, John Wheeler
R-trees
6,543 Citations1984Antonin Guttman
A dynamic index structure called an R-tree is described which meets this need, and algorithms for searching and updating it are given and it is concluded that it is useful for current database systems in spatial applications.
IEEE Transactions on Pattern Analysis and Machine IntelligenceComparing images using the Hausdorff distance
4,474 Citations1993D.P. Huttenlocher, G.A. Klanderman +1 more
Efficient algorithms for computing the Hausdorff distance between all possible relative positions of a binary image and a model are presented and it is shown that the method extends naturally to the problem of comparing a portion of a model against an image.
The R*-tree: an efficient and robust access method for points and rectangles
4,176 Citations1990Norbert Beckmann, Hans‐Peter Kriegel +2 more
The R*-tree is designed which incorporates a combined optimization of area, margin and overlap of each enclosing rectangle in the directory which clearly outperforms the existing R-tree variants.
M-tree: An Efficient Access Method for Similarity Search in Metric Spaces
1,534 Citations1997Paolo Ciaccia, Marco Patella +1 more
The results demonstrate that the Mtree indeed extends the domain of applicability beyond the traditional vector spaces, performs reasonably well in high-dimensional data spaces, and scales well in case of growing files.
Near Neighbor Search in Large Metric Spaces
553 Citations1995Sergey Brin
A data structure to solve the problem of finding approximate matches in a large database called a GNAT { Geometric Near-neighbor Access Tree} is introduced based on the philosophy that the data structure should act as a hierarchical geometrical model of the data as opposed to a simple decomposition of theData that does not use its intrinsic geometry.
On packing R-trees
491 Citations1993Ibrahim Kamel, Christos Faloutsos
An analytical formula is introduced to compute the average response time of a range query as a function of the geometric characteristics of the R-tree, to achieve better ordering of the rectangles and eventually better packing.
Minds at UW (University of Wisconsin)Generalized Search Trees for Database Systems
467 Citations1995Joseph M. Hellerstein, Jeffrey F. Naughton +1 more
The Generalized Search Tree is introduced, an index structure supporting an extensible set of queries and data types and providing all the basic search tree logic required by a database system, thereby unifying disparate structures such as B+-tree and R-trees in a single piece of code and opening the application of search trees to general extensibility.
A cost model for nearest neighbor search in high-dimensional data space
374 Citations1997Stefan Berchtold, Christian Böhm +2 more
A new cost model for nearest neighbor search in high-dimensional data space is developed which takes boundary effects into account and therefore also works in high dimensions and is applicable to different data distributions and index structures.
Distance-based indexing for high-dimensional metric spaces
332 Citations1997Tolga Bozkaya, Meral Özsoyoğlu
This paper introduces a distance based index structure called multi-vantage point (mvp) tree for similarity queries on high-dimensional metric spaces and shows that mvp-tree outperforms the vp-tree 20% to 80% for varying query ranges and different distance distributions.
A model for the prediction of R-tree performance
263 Citations1996Yannis Theodoridis, Timos Sellis
An analytical model that predicts the performance of R-trees (and its variants) when a range query needs to be answered and constitutes a useful tool for spatial query optimizers that need to evaluate the cost of a complex spatial query and its execution procedure.
Beyond uniformity and independence
242 Citations1994Christos Faloutsos, Ibrahim Kamel
It is believed that the fractal dimension will help replace the uniformity and independence assumptions, allowing more accurate analysis for any spatial access method, as well as better estimates for query optimization on multi-attribute queries.
Digital Repository at the University of Maryland (University of Maryland College Park)Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension
177 Citations2018Alberto Belussi, Christos Faloutsos
It is shown that, among the infinite family of fractal dimensions, the so called “Correlation Dimension” Dz is the one that the authors need to predict the selectivity of spatial join, and the main contribution is that the average number of neighbors for a given point of the point-set follows a power law, with LI& as the exponent.
Content-Based Image Indexing
157 Citations1994Tzi‐cker Chiueh
This paper forms the content-based image indexing problem as a multi-dimensional nearest-neighbor search problem, and develops/implement an optimistic vantage-point tree algorithm that can dynamically adapt the indexed search process to the characteristics of given queries.
Lecture notes in computer sciencePerformance of nearest neighbor queries in R-trees
148 Citations1997Apostolos N. Papadopoulos, Yannis Manolopoulos
This paper combines techniques that were inherently used for the analysis of range and spatial join queries, in order to derive measures regarding the performance of NN queries, to estimate the number of disk accesses introduced due to the processing of an NN query.
A structural approach to fingerprint classification
118 Citations1996Dario Maio, Davide Maltoni
A new structural approach to the fingerprint classification problem is presented, where from the segmentation of the directional image a relational graph compactly summarising the macro-structure of the fingerprint is derived.
Matching and indexing sequences of different lengths
86 Citations1997Tolga Bozkaya, Nasser Yazdani +1 more
This paper proposes an indexing scheme which is totally based on lengths and relative distances between sequences, and uses vp-trees as the underlying distance-based index structures in its method.
Lecture notes in computer scienceProcessing complex similarity queries with distance-based access methods
52 Citations1998Paolo Ciaccia, Marco Patella +1 more
This paper considers the relevant case where complex similarity queries are defined through a generic language £ and whose predicates refer to a single feature F and suggests that the index should process complex queries as a whole, thus evaluating multiple similarity predicates at a time.
Efficient querying on genomic databases by using metric space indexing techniques
11 Citations2002Weimin Chen, Karl Aberer
This paper investigates two different indexing techniques, namely the variations of GNAT trees and M-trees to support fast query evaluation for local alignment, by transforming the alignment problem to a variant metric space neighborhood search problem.