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