ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Window Query-Optimal Clustering of Spatial Objects.

Bernd-Uwe Pagel, Hans-Werner Six, Mario Winter: Window Query-Optimal Clustering of Spatial Objects. PODS 1995: 86-94
@inproceedings{DBLP:conf/pods/PagelSW95,
  author    = {Bernd-Uwe Pagel and
               Hans-Werner Six and
               Mario Winter},
  title     = {Window Query-Optimal Clustering of Spatial Objects},
  booktitle = {Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 22-25, 1995, San Jose,
               California},
  publisher = {ACM Press},
  year      = {1995},
  isbn      = {0-89791-730-8},
  pages     = {86-94},
  ee        = {http://doi.acm.org/10.1145/212433.212458, db/conf/pods/PagelSW95.html},
  crossref  = {DBLP:conf/pods/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

During the last decade various spatial data structures have been designed and compared against each other with respect to their performance. Still missing is a lower bound result, e.g. an optimal spatial data clustering, which would allow for the absolute comparison of the performance of the well-known data structures with the optimum. In this paper, we address the static situation where the data is known in beforehand. An optimal data clustering for this setting will also provide a lower bound for the dynamic situation where the input data is not known in advance and the data structure is built up by iterated insertions. Using as performance measure the expected number of data bucket accesses needed to perform a window query, the static clustering problem turns into a classical optimization problem. For the special case of bucket capacity cb>=2 the optimization problem is solvable in polynomial time, whereas for cb>=3 it is NP-hard. In experiments using simulated annealing heuristics for the optimization the best dynamic structures as well as the static packed R-tree perform about 20% worse than the optimum on average. However, we again want to emphazise that we understand our contribution as lower bound result rather than another speed-up variant of classical spatial data structures.

Copyright © 1995 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 Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 22-25, 1995, San Jose, California. ACM Press 1995, ISBN 0-89791-730-8
Contents BibTeX

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 842 KB]

References

[BKSS90]
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
[BPS94]
Lukas Bachmann, Bernd-Uwe Pagel, Hans-Werner Six: Optimizing Spatial Data Structures For Static Data. IGIS 1994: 247-258 BibTeX
[GJ75]
M. R. Garey, David S. Johnson: Complexity Results for Multiprocessor Scheduling under Resource Constraints. SIAM J. Comput. 4(4): 397-411(1975) BibTeX
[GLS81]
...
[Gut84]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX
[HLL94]
Kien A. Hua, Sheau-Dong Lang, Wen K. Lee: A Decomposition-Based Simulated Annealing Technique for Data Clustering. PODS 1994: 117-128 BibTeX
[HSW89]
Andreas Henrich, Hans-Werner Six, Peter Widmayer: The LSD tree: Spatial Access to Multidimensional Point and Nonpoint Objects. VLDB 1989: 45-53 BibTeX
[IK90]
Yannis E. Ioannidis, Younkyung Cha Kang: Randomized Algorithms for Optimizing Large Join Queries. SIGMOD Conference 1990: 312-321 BibTeX
[IW87]
Yannis E. Ioannidis, Eugene Wong: Query Optimization by Simulated Annealing. SIGMOD Conference 1987: 9-22 BibTeX
[KF93]
Ibrahim Kamel, Christos Faloutsos: On Packing R-trees. CIKM 1993: 490-499 BibTeX
[Law76]
...
[LB86]
...
[MBM89]
F. J. McErlean, David A. Bell, Sally I. McClean: The use of simulated annealing for clustering data in databases. Inf. Syst. 15(2): 233-245(1990) BibTeX
[Mey91]
...
[PST93]
Bernd-Uwe Pagel, Hans-Werner Six, Heinrich Toben: The Transformation Technique for Spatial Objects Revisited. SSD 1993: 73-88 BibTeX
[PSTW93]
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 BibTeX
[SFGM93]
Michael Stonebraker, James Frew, Kenn Gardels, Jeff Meredith: The Sequoia 2000 Benchmark. SIGMOD Conference 1993: 2-11 BibTeX
[Swa89]
Arun N. Swami: Optimization of Large Join Queries: Combining Heuristic and Combinatorial Techniques. SIGMOD Conference 1989: 367-376 BibTeX
[vLA87]
...

Referenced by

  1. Joseph M. Hellerstein, Lisa Hellerstein, George Kollios: On the Generation of 2-Dimensional Index Workloads. ICDT 1999: 113-130
  2. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
  3. Yannis Theodoridis, Timos K. Sellis: A Model for the Prediction of R-tree Performance. PODS 1996: 161-171
  4. Bernd-Uwe Pagel, Hans-Werner Six: Are Window Queries Representative for Arbitrary Range Queries? PODS 1996: 150-160
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:12 2009