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

Separability of Polyhedra for Optimal Filtering of Spatial and Constraint Data.

Alexander Brodsky, Catherine Lassez, Jean-Louis Lassez, Michael J. Maher: Separability of Polyhedra for Optimal Filtering of Spatial and Constraint Data. PODS 1995: 54-65
@inproceedings{DBLP:conf/pods/BrodskyLLM95,
  author    = {Alexander Brodsky and
               Catherine Lassez and
               Jean-Louis Lassez and
               Michael J. Maher},
  title     = {Separability of Polyhedra for Optimal Filtering of Spatial and
               Constraint Data},
  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     = {54-65},
  ee        = {http://doi.acm.org/10.1145/212433.212449, db/conf/pods/BrodskyLLM95.html},
  crossref  = {DBLP:conf/pods/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The filtering method considered in this paper is based on approximation of a spatial object in d-dimensional space by the minimal convex polyhedron that encloses the object and whose facets are normal to preselected axes. These axes are not necessarily the standard coordinate axes and, furthermore, their number is not determined by the dimension of the space. We optimize filtering by selecting optimal such axes based on analysis of stored objects or a sample thereof. The number of axes selected represents a trade-off between access time and storage overhead, as more axes usually lead to better filtering but require more overhead to store the associated access structures. We address the problem of minimizing the number of axes required to achieve a predefined quality of filtering and the reverse problem of optimizing the quality of filtering when the number of axes is fixed. In both cases we also show how to find an optimal collection of axes. In order to solve these problems, we introduce and study the key notion of separability classification, which is a general tool potentially useful in many applications of a computational geometry flavor. The approach is best suited to applications in which the spatial data is relatively static, some directions are more dominant than others, and the dimension of the space is not high; maps are a prime example.

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, 1068 KB]

References

[B75]
Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) BibTeX
[BVCS93]
...
[BJM93]
Alexander Brodsky, Joxan Jaffar, Michael J. Maher: Toward Practical Constraint Databases. VLDB 1993: 567-580 BibTeX
[BLL93]
Alexander Brodsky, Catherine Lassez: Separability of Polyhedra and a New Approach to Spatial Storage (Extended Abstract). PPCP 1993: 7-11 BibTeX
[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
[Ed83]
...
[Fr84]
...
[Gun87]
...
[Gut84]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX
[HLL93]
...
[J90]
H. V. Jagadish: Spatial Search with Polyhedra. ICDE 1990: 311-319 BibTeX
[KRVV93]
Paris C. Kanellakis, Sridhar Ramaswamy, Darren Erik Vengroff, Jeffrey Scott Vitter: Indexing for Data Models with Constraints and Classes. PODS 1993: 233-243 BibTeX
[Las90]
Jean-Louis Lassez: Querying Constraints. PODS 1990: 288-298 BibTeX
[McC]
Edward M. McCreight: Priority Search Trees. SIAM J. Comput. 14(2): 257-276(1985) BibTeX
[Ni90]
Jürg Nievergelt: 7 ± 2 Criteria for Assessing and Comparing Spatial data Structures. SSD 1989: 3-27 BibTeX
[NS87]
Randal C. Nelson, Hanan Samet: A Population Analysis for Hierarchical Data Structures. SIGMOD Conference 1987: 270-277 BibTeX
[Or89]
Jack A. Orenstein: Redundancy in Spatial Databases. SIGMOD Conference 1989: 295-305 BibTeX
[R81]
John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 BibTeX
[RL84]
...
[RL85]
Nick Roussopoulos, Daniel Leifker: Direct Spatial Search on Pictorial Databases Using Packed R-Trees. SIGMOD Conference 1985: 17-31 BibTeX
[SaW85]
...
[SiW82]
...
[SRF87]
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX
[Ta82]
...
[TN87]
...

Referenced by

  1. Elisa Bertino, Barbara Catania, Boris Chidlovskii: Indexing Constraint Databases by Using a Dual Representation. ICDE 1999: 618-627
  2. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
  3. Jan Chomicki, Dina Q. Goldin, Gabriel M. Kuper: Variable Independence and Aggregation Closure. PODS 1996: 40-48
  4. Paris C. Kanellakis: Constraint Programming and Database Languages: A Tutorial. PODS 1995: 46-53
  5. Jan Chomicki, Gabriel M. Kuper: Measuring Infinite Relations. PODS 1995: 78-85
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