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

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Online Edition: ACM Digital Library

References

[1]
...
[2]
...
[3]
...
[4]
...
[5]
...
[6]
...
[7]
Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
...
[9]
...
[10]
...
[11]
...
[12]
...

Home | Conferences | Journals | Series | FAQ — Search: Faceted | Complete | Author
Copyright © Fri Mar 12 17:19:55 2010 by Michael Ley (ley@uni-trier.de)