Efficient Processing of Window Queries in The Pyramid Data Structure.
Walid G. Aref, Hanan Samet:
Efficient Processing of Window Queries in The Pyramid Data Structure.
PODS 1990: 265-272@inproceedings{DBLP:conf/pods/ArefS90,
author = {Walid G. Aref and
Hanan Samet},
title = {Efficient Processing of Window Queries in The Pyramid Data Structure},
booktitle = {Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on
Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee},
publisher = {ACM Press},
year = {1990},
isbn = {0-89791-352-3},
pages = {265-272},
ee = {http://doi.acm.org/10.1145/298514.298579, db/conf/pods/ArefS90.html},
crossref = {DBLP:conf/pods/90},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Abstract
Window operations serve as the basis of a number of
queries that can be posed in a spatial database. Examples
of these window-based queries include the exist
query (i.e., determining whether or not, a spatial feature
exists inside a window) and the report query, (i.e., reporting
the identity of all the features that exist inside a
window). Algorithms are described for answering window
queries in O(n loglog T) time for a window of size
n*n in a feature space (e.g., an image) of size T*T (e.g.,
pixel elements). The significance of this result is that
even though the window contains n² pixel elements, the
worst-case time complexity of the algorithms is almost
linearly proportional (and not, quadratic) to the window
diameter, and does not depend on other factors. The
above complexity bounds are achieved via the introduction
of the incomplete pyramid data structure (a variant
of the pyramid data structure) as the underlying representation
to store spatial features and to answer queries on them.
Copyright © 1990 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 ...
Printed Edition
Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee.
ACM Press 1990, ISBN 0-89791-352-3
Contents
References
- [1]
- ...
- [2]
- ...
- [3]
- ...
- [4]
- ...
- [5]
- ...
- [6]
- ...
- [7]
- Hanan Samet:
The Design and Analysis of Spatial Data Structures.
Addison-Wesley 1990
![bibliographical record in XML](../../xml.gif)
- [8]
- ...
- [9]
- ...
- [10]
- ...
- [11]
- ...
- [12]
- ...
Copyright © Fri Mar 12 17:19:55 2010
by Michael Ley (ley@uni-trier.de)