Towards an Analysis of Range Query Performance in Spatial Data Structures.
Bernd-Uwe Pagel, Hans-Werner Six, Heinrich Toben, Peter Widmayer:
Towards an Analysis of Range Query Performance in Spatial Data Structures.
PODS 1993: 214-221@inproceedings{DBLP:conf/pods/PagelSTW93,
author = {Bernd-Uwe Pagel and
Hans-Werner Six and
Heinrich Toben and
Peter Widmayer},
title = {Towards an Analysis of Range Query Performance in Spatial Data
Structures},
booktitle = {Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems, May 25-28, 1993, Washington,
DC},
publisher = {ACM Press},
year = {1993},
isbn = {0-89791-593-3},
pages = {214-221},
ee = {http://doi.acm.org/10.1145/153850.153878, db/conf/pods/PagelSTW93.html},
crossref = {DBLP:conf/pods/93},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
In this paper, we motivate four different user defined window query classes and derive a probabilistic model for each of them.
For each model, we characterize the efficiency of spatial data structures in terms of the expected number of data bucket accesses needed to perform a window query.
Our analytical approach exhibits the performance phenomena independent of data structure and implementation details and whether the objects are points or non-point objects.
Copyright © 1993 by the ACM,
Inc., used by permission. Permission to make
digital or hard copies is granted provided that
copies are not made or distributed for profit or
direct commercial advantage, and that copies show
this notice on the first page or initial screen of
a display along with the full citation.
Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98.
and ...
Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings.
and ...
BibTeX
Printed Edition
Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 25-28, 1993, Washington, DC.
ACM Press 1993, ISBN 0-89791-593-3
Contents BibTeX
[Abstract and Index Terms]
[Full Text in PDF Format, 737 KB]
References
- [1]
- 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 BibTeX
- [2]
- Michael Freeston:
The BANG File: A New Kind of Grid File.
SIGMOD Conference 1987: 260-269 BibTeX
- [3]
- ...
- [4]
- Antonin Guttman:
R-Trees: A Dynamic Index Structure for Spatial Searching.
SIGMOD Conference 1984: 47-57 BibTeX
- [5]
- Andreas Henrich, Hans-Werner Six, Peter Widmayer:
The LSD tree: Spatial Access to Multidimensional Point and Nonpoint Objects.
VLDB 1989: 45-53 BibTeX
- [6]
- Andreas Hutflesz, Hans-Werner Six, Peter Widmayer:
The R-File: An Efficient Access Structure for Proximity Queries.
ICDE 1990: 372-379 BibTeX
- [7]
- Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik:
The Grid File: An Adaptable, Symmetric Multikey File Structure.
ACM Trans. Database Syst. 9(1): 38-71(1984) BibTeX
- [8]
- Bernhard Seeger, Hans-Peter Kriegel:
The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems.
VLDB 1990: 590-601 BibTeX
Referenced by
- Simonas Saltenis, Christian S. Jensen, Scott T. Leutenegger, Mario A. Lopez:
Indexing the Positions of Continuously Moving Objects.
SIGMOD Conference 2000: 331-342
- Flip Korn, S. Muthukrishnan:
Influence Sets Based on Reverse Nearest Neighbor Queries.
SIGMOD Conference 2000: 201-212
- Christian Böhm, Hans-Peter Kriegel:
Dynamically Optimizing High-Dimensional Index Structures.
EDBT 2000: 36-50
- Ju-Hong Lee, Deok-Hwan Kim, Chin-Wan Chung:
Multi-dimensional Selectivity Estimation Using Compressed Histogram Information.
SIGMOD Conference 1999: 205-214
- Dimitris Papadias, Nikos Mamoulis, Yannis Theodoridis:
Processing and Optimization of Multiway Spatial Joins Using R-Trees.
PODS 1999: 44-55
- Joseph M. Hellerstein, Lisa Hellerstein, George Kollios:
On the Generation of 2-Dimensional Index Workloads.
ICDT 1999: 113-130
- Guido Proietti, Christos Faloutsos:
I/O Complexity for Range Queries on Region Data Stored Using an R-tree.
ICDE 1999: 628-635
- Volker Gaede, Oliver Günther:
Multidimensional Access Methods.
ACM Comput. Surv. 30(2): 170-231(1998)
- Apostolos Papadopoulos, Yannis Manolopoulos:
Similarity Query Processing Using Disk Arrays.
SIGMOD Conference 1998: 225-236
- Yannis Theodoridis, Emmanuel Stefanakis, Timos K. Sellis:
Cost Models for Join Queries in Spatial Databases.
ICDE 1998: 476-483
- Scott T. Leutenegger, Mario A. Lopez:
The Effect of Buffering on the Performance of R-Trees.
ICDE 1998: 164-171
- Apostolos Papadopoulos, Yannis Manolopoulos:
Multiple Range Query Optimization in Spatial Databases.
ADBIS 1998: 71-82
- Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner:
A Cost Model for Estimating the Performance of Spatial Joins Using R-trees.
SSDBM 1997: 30-38
- Joseph M. Hellerstein, Elias Koutsoupias, Christos H. Papadimitriou:
On the Analysis of Indexing Schemes.
PODS 1997: 249-256
- Apostolos Papadopoulos, Yannis Manolopoulos:
Performance of Nearest Neighbor Queries in R-Trees.
ICDT 1997: 394-408
- Yannis Theodoridis, Timos K. Sellis:
A Model for the Prediction of R-tree Performance.
PODS 1996: 161-171
- Bernd-Uwe Pagel, Hans-Werner Six:
Are Window Queries Representative for Arbitrary Range Queries?
PODS 1996: 150-160
- Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer:
Generalized Search Trees for Database Systems.
VLDB 1995: 562-573
- Alberto Belussi, Christos Faloutsos:
Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension.
VLDB 1995: 299-310
- Bernd-Uwe Pagel, Hans-Werner Six, Mario Winter:
Window Query-Optimal Clustering of Spatial Objects.
PODS 1995: 86-94
- Christos Faloutsos, Ibrahim Kamel:
Beyond Uniformity and Independence: Analysis of R-trees Using the Concept of Fractal Dimension.
PODS 1994: 4-13
- Paolo Giulio Franciosa, Maurizio Talamo:
ESPRIT Project EP6881 AMUSING.
IEEE Data Eng. Bull. 16(3): 46-50(1993)
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:08 2009