Efficient processing of window queries in the pyramid data structure

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 &Ogr;(n log logT) time for a window of size n x n in a feature space (e.g., an image) of size T x T (e.g., pixel elements). The significance of this result is that even though the window contains n2 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.

REFERENCES

• 1: W. G. Aref and H. Samet. Efficient techniques for the check-out operation in spatial databases. Submitted for publication, 1990.
• 2: W. G. Aref and H. Samet. Window queries in spatial databases. In preparation, 1990.
• 3: C. Ft. Dyer. The space efficiency of quadtrees. Computer Graphics and Image Processing, 19(4):335- 348, August 1982.
• 4: Peter Henderson, Functional Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1980
• 5: A Klinger. Patterns and search statistics. In J. S. Rustagi, editor, Optimizing Methods in Statistics, pages 303-337. Academic Press, New York, 1971.
• 6: Hanan Samet, Applications of spatial data structures: Computer graphics, image processing, and GIS, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 7: H. Sam t. D ig, A, lU,i o~ Sp,ti Z D t, Structures. Addison-Wesley, Reading, MA, 1990.
• 8: Clifford A. Shaffer, A formula for computing the number of quadtree node fragments created by a shift, Pattern Recognition, v.7 n.1, p.45-49, January 1988
• 9: C. A. Shaffer and H. Samet. An in-core hierarchical data structure organization for a geographic database. Technical Report Computer Science TR 1886, University of Maryland, College Park, MD, July 1987.
• 10: S. Tanimoto and T. Pavlidis. A hierarchical data structure for picture processing. Computer Graphics and Image Processing, 4(2):104-119, June 1975.
• 11: Lewis Wiley Tucker, Computer vision using quadtree refinement (artificial intelligence, segmentation, knowledge), 1984
• 12: j. W. J. Williams. Algorithm 232: Heapsort. Communications of the A CM, 7(6):347-348, June 1964.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  E. Data

General Terms:
Algorithms, Design, Management, Measurement, Performance, Theory