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

The Quadtree and Related Hierarchical Data Structures.

Hanan Samet: The Quadtree and Related Hierarchical Data Structures. ACM Comput. Surv. 16(2): 187-260(1984)
@article{DBLP:journals/csur/Samet84,
  author    = {Hanan Samet},
  title     = {The Quadtree and Related Hierarchical Data Structures},
  journal   = {ACM Comput. Surv.},
  volume    = {16},
  number    = {2},
  year      = {1984},
  pages     = {187-260},
  ee        = {db/journals/csur/Samet84.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

A tutorial survey is presented of the quadtree and related hierarchical data structures. They are based on the principle of recursive decomposition. The emphasis is on the representation of data used in applications in image processing, computer graphics, geographic information systems, and robotics. There is a greater emphasis on region data (i.e., two-dimensional shapes) and to a lesser extent on point, curvilinear, and three-dimensional data. A number of operations in which such data structures find use are examined in greater detail.

Copyright © 1984 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.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

References

[Abel 1984]
...
[Abel and Smith 1983]
...
[Aho et al. 1974]
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX
[Ahuja 1983]
...
[Ahuja and Nash 1984]
...
[Anderson 1983]
D. P. Anderson: Techniques for Reducing Pen Plotting Time. ACM Trans. Graph. 2(3): 197-212(1983) BibTeX
[Ballard 1981]
Dana H. Ballard: Strip Trees: A Hierarchical Representation for Curves. Commun. ACM 24(5): 310-321(1981) BibTeX
[Bell et al. 1983]
...
[Bentley 1975a]
...
[Bentley 1975b]
Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) BibTeX
[Bentley and Friedman 1979]
Jon Louis Bentley, Jerome H. Friedman: Data Structures for Range Searching. ACM Comput. Surv. 11(4): 397-409(1979) BibTeX
[Bentley and Stanat 1975]
Jon Louis Bentley, Donald F. Stanat: Analysis of Range Searches in Quad Trees. Inf. Process. Lett. 3(6): 170-173(1975) BibTeX
[Besslich 1982]
...
[Blum 1967]
...
[Brooks and Lozano Perez 1983]
Rodney A. Brooks, Tomás Lozano-Pérez: A Subdivision Algorithm Configuration Space for Findpath With Rotation. IJCAI 1983: 799-806 BibTeX
[Burkhardt 1983]
Walter A. Burkhard: Interpolation-Based Index Maintenance. BIT 23(3): 274-294(1983) BibTeX
[Burt 1980]
...
[Burt et al. 1981]
...
[Burton 1977]
Warren Burton: Representation of Many-Sided Polygons and Polygonal Lines for Rapid Processing. Commun. ACM 20(3): 166-171(1977) BibTeX
[Burton and Kollias 1983]
...
[Carlson 1982]
...
[Chien and Aggrawal 1984]
...
[Cohen et al. 1980]
...
[Comer 1979]
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX
[Connolly 1984]
...
[Cook 1978]
...
[Creutzburg 1981]
...
[Davis and Roussopoulos 1980]
Larry S. Davis, Nick Roussopoulos: Approximate pattern matching in a pattern database system. Inf. Syst. 5(2): 107-119(1980) BibTeX
[DeCoulon and Johnsen 1976]
...
[DeFloriani et al. 1982]
...
[DeMillo et al. 1978]
Richard A. DeMillo, Stanley C. Eisenstat, Richard J. Lipton: Preserving Average Proximity in Arrays. Commun. ACM 21(3): 218-231(1978) BibTeX
[Doctor and Torborg 1981]
...
[Duda and Hart 1973]
...
[Dyer 1980]
...
[Dyer 1981]
...
[Dyer 1982]
...
[Dyer et al. 1980]
Charles R. Dyer, Azriel Rosenfeld, Hanan Samet: Region Representation: Boundary Codes from Quadtrees. Commun. ACM 23(3): 171-179(1980) BibTeX
[Eastman 1970]
...
[Edelsbrunner 1984]
...
[Edelsbrunner and van Leeuwen 1983]
...
[Edelsbrunner e tal. 1985]
Herbert Edelsbrunner, Leonidas J. Guibas, Jorge Stolfi: Optimal Point Location in a Monotone Subdivision. SIAM J. Comput. 15(2): 317-340(1986) BibTeX
[Fagin et al. 1979]
Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, H. Raymond Strong: Extendible Hashing - A Fast Access Method for Dynamic Files. ACM Trans. Database Syst. 4(3): 315-344(1979) BibTeX
[Faugeras and Ponce 1983]
Olivier D. Faugeras, Jean Ponce: Prism Trees: A Hierarchical Representation for 3-D Objects. IJCAI 1983: 982-988 BibTeX
[Faugeras et al. 1984]
...
[Faverjon 1984]
...
[Finkel and Bentley 1974]
Raphael A. Finkel, Jon Louis Bentley: Quad Trees: A Data Structure for Retrieval on Composite Keys. Acta Inf. 4: 1-9(1974) BibTeX
[Fredkin 1960]
...
[Freeman 1974]
Herbert Freeman: Computer Processing of Line-Drawing Images. ACM Comput. Surv. 6(1): 57-97(1974) BibTeX
[Friedman et al. 1977]
Jerome H. Friedman, Jon Louis Bentley, Raphael A. Finkel: An Algorithm for Finding Best Matches in Logarithmic Expected Time. ACM Trans. Math. Softw. 3(3): 209-226(1977) BibTeX
[Gargantini 1982a]
Irene Gargantini: An Effective Way to Represent Quadtrees. Commun. ACM 25(12): 905-910(1982) BibTeX
[Gargantini 1982b]
...
[Gargantini 1983]
...
[Gaston and Lozano Perez 1984]
...
[Gibson and Lucas 1982]
...
[Gillepsie and Davis 1981]
...
[Gomez and Guzman 1979]
...
[Grosky and Jain 1983]
...
[Harary 1969]
...
[Hertel and Mehlhorn 1983]
Stefan Hertel, Kurt Mehlhorn: Fast Triangulation of Simple Polygons. FCT 1983: 207-218 BibTeX
[Hinrichs and Nievergelt 1983]
Klaus Hinrichs, Jürg Nievergelt: The Grid File: A Data Structure to Support Proximity Queries on Spatial Objects. WG 1983: 100-113 BibTeX
[Hoare 1972]
...
[Horowitz and Pavlidis 1976]
Steven L. Horowitz, Theodosios Pavlidis: Picture Segmentation by a Tree Traversal Algorithm. J. ACM 23(2): 368-388(1976) BibTeX
[Huffman 1952]
...
[Hunter 1978]
...
[Hunter and Steiglitz 1979a]
...
[Hunter and Steiglitz 1979b]
...
[Ibrahim 1984]
...
[Ismail and Steele 1980]
...
[Jackins and Tanimoto 1980]
...
[Jackins and Tanimoto 1983]
...
[Jones and Iyengar 1984]
...
[Kawaguchi and Endo 1980]
...
[Kawaguchi et al. 1980]
...
[Kawaguchi et al. 1983]
...
[Kedem 1981]
...
[Kelly 1971]
...
[Kirkpatrick 1983]
David G. Kirkpatrick: Optimal Search in Planar Subdivisions. SIAM J. Comput. 12(1): 28-35(1983) BibTeX
[Klinger 1971]
...
[Klinger and Dyer 1976]
...
[Klinger and Rhodes 1979]
...
[Knott 1971]
Gary D. Knott: Expandable Open Addressing Hash Table Storage and Retrieval. SIGFIDET Workshop 1971: 187-206 BibTeX
[Knowlton 1980]
...
[Knuth 1973]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[Knuth 1975]
Donald E. Knuth: The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison-Wesley 1973
BibTeX
[Lauzon et al. 1984]
...
[Lee and Shacter 1980]
...
[Lee and Wong 1977]
D. T. Lee, C. K. Wong: Worst-Case Analysis for Region and Partial Region Searches in Multidimensional Binary Search Trees and Balanced Quad Trees. Acta Inf. 9: 23-29(1977) BibTeX
[Letelier 1983]
...
[Li et al. 1982]
...
[Linn 1973]
...
[Lipton and Tarjan 1977]
Richard J. Lipton, Robert Endre Tarjan: Application of a Planar Separator Theorem. FOCS 1977: 162-170 BibTeX
[Litwin 1980]
Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 BibTeX
[Lozano-Perez 1981]
...
[Lumia 1983]
...
[Lumia et al. 1983]
...
[Martin 1982]
...
[Matsuyama et al. 1984]
...
[McCluskey 1965]
...
[McKeown and Denlinger 1984]
...
[Meagher 1982]
...
[Merrett 1978]
...
[Merrett and Otoo 1981]
T. H. Merrett, Ekow J. Otoo: Dynamic Multipaging: A Storage Structure for Large Shared Data Banks. JCDKB 1982: 237-255 BibTeX
[Merrill 1973]
R. D. Merrill: Representation of Contours ad Regions for Efficient Computer Search. Commun. ACM 16(2): 69-82(1973) BibTeX
[Milford and Willis 1984]
...
[Minsky and Pepert 1969]
...
[Morton 1966]
...
[Mudur and Koparkar 1984]
...
[Nagy and Wagle 1979]
George Nagy, Sharad Wagle: Geographic Data Processing. ACM Comput. Surv. 11(2): 139-181(1979) BibTeX
[Nievergelt and Preparata 1982]
Jürg Nievergelt, Franco P. Preparata: Plane-Sweep Algorithms for Intersecting Geometric Figures. Commun. ACM 25(10): 739-747(1982) BibTeX
[Nievergelt et al. 1984]
Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) BibTeX
[Nilsson 1969]
Nils J. Nilsson: A Mobile Automaton: An Application of Artificial Intelligence Techniques. IJCAI 1969: 509-520 BibTeX
[Oliver and Wiseman 1983a]
M. A. Oliver, Neil E. Wiseman: Operations on Quadtree Encoded Images. Comput. J. 26(1): 83-91(1983) BibTeX
[Oliver and Wiseman 1983b]
M. A. Oliver, Neil E. Wiseman: Operations on Quadtree Leaves and Related Image Areas. Comput. J. 26(4): 375-380(1983) BibTeX
[Omalayole and Klinger 1980]
Joseph Olu Omolayole, Allen Klinger: A Hierarchical Data Structure Scheme for Storing Pictures. Pictorial Information Systems 1980: 1-38 BibTeX
[Orenstein 1982]
Jack A. Orenstein: Multidimensional Tries Used for Associative Searching. Inf. Process. Lett. 14(4): 150-157(1982) BibTeX
[Orenstein 1983]
Jack A. Orenstein: A Dynamic Hash File for Random and Sequential Accessing. VLDB 1983: 132-141 BibTeX
[Orenstein and Merrett 1984]
Jack A. Orenstein, T. H. Merrett: A Class of Data Structures for Associative Searching. PODS 1984: 181-190 BibTeX
[ORourke 1981]
...
[ORourkeand Sloan 1984]
...
[Ouksel and Scheuermann 1983]
Aris M. Ouksel, Peter Scheuermann: Storage Mappings for Multidimensional Linear Dynamic Hashing. PODS 1983: 90-105 BibTeX
[Overmars 1983]
Mark H. Overmars: The Design of Dynamic Data Structures. Lecture Notes in Computer Science Vol. 156 Springer 1983, ISBN 3-540-12330-X
BibTeX
[Overmars and van Leeuwen 1982]
Mark H. Overmars, Jan van Leeuwen: Dynamic Multi-Dimensional Data Structures Based on Quad- and K - D Trees. Acta Inf. 17: 267-285(1982) BibTeX
[Peters 1984]
...
[Peucker 1976]
...
[Peuquet 1983]
...
[Peuquet 1983]
...
[Pfaltz and Rosenfeld 1967]
...
[Pietikainen et al. 1982]
...
[Raman and Iyengar 1983]
V. K. Raman, S. Sitharama Iyengar: Properties and Applications of Forests of Quadtrees. BIT 23(4): 472-(1983) BibTeX
[Ranade 1981]
...
[Ranade and Shneier 1981]
...
[Ranade et al. 1980]
...
[Ranade et al. 1982]
...
[Reddy and Rubin 1978]
...
[Requicha 1980]
Aristides A. G. Requicha: Representations for Rigid Solids: Theory, Methods, and Systems. ACM Comput. Surv. 12(4): 437-464(1980) BibTeX
[Rheinboldt and Mesztenzi 1980]
...
[Riseman and Arbib 1977]
...
[Robinson 1981]
John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 BibTeX
[Rosenfeld 1983]
...
[Rosenfeld 1984]
...
[Rosenfeld and Kak 1982]
...
[Rosenfeld and Pfaltz 1966]
Azriel Rosenfeld, John L. Pfaltz: Sequential Operations in Digital Picture Processing. J. ACM 13(4): 471-494(1966) BibTeX
[Rosenfeld et al. 1982]
...
[Rosenfeld et al. 1983]
...
[Roth 1982]
...
[Rutovitz 1968]
...
[Samet 1980a]
Hanan Samet: Region Representation: Quadtrees from Boundary Codes. Commun. ACM 23(3): 163-170(1980) BibTeX
[Samet 1980b]
...
[Samet 1980c]
Hanan Samet: Deletion in Two-Dimensional Quad Trees. Commun. ACM 23(12): 703-710(1980) BibTeX
[Samet 1981a]
...
[Samet 1981b]
Hanan Samet: Connected Component Labeling Using Quadtrees. J. ACM 28(3): 487-501(1981) BibTeX
[Samet 1981c]
...
[Samet 1982a]
...
[Samet 1982b]
...
[Samet 1983]
Hanan Samet: A Quadtree Medial Axis Transform. Commun. ACM 26(9): 680-693(1983) BibTeX
[Samet 1984]
...
[Samet 1985a]
...
[Samet 1985b]
...
[Samet 1985c]
Hanan Samet: Data Structures for Quadtree Approximation and Compression. Commun. ACM 28(9): 973-993(1985) BibTeX
[Samet and Krishnamurthy 1983]
...
[Samet and Rosenfeld 1980]
...
[Samet and Shaffer 1984]
...
[Samet and Tamminen 1984]
...
[Samet and Tamminen 1985]
...
[Samet Webber 1982]
...
[Samet Webber 1983]
...
[Samet Webber 1984]
...
[Shamos 1978]
...
[Shamos and Hoey 1975]
Michael Ian Shamos, Dan Hoey: Closest-Point Problems. FOCS 1975: 151-162 BibTeX
[Shneier 1981a]
...
[Shneier 1981b]
...
[Shneier 1981c]
...
[Sloan 1981]
...
[Sloan and Tanimoto 1979]
Kenneth R. Sloan Jr., Steven L. Tanimoto: Progressive Refinement of Raster Images. IEEE Trans. Computers 28(11): 871-874(1979) BibTeX
[Srihari 1981]
Sargur N. Srihari: Representation of Three-Dimensional Digital Images. ACM Comput. Surv. 13(4): 399-424(1981) BibTeX
[Sutherland et al. 1974]
Ivan E. Sutherland, Robert F. Sproull, Robert A. Schumacker: A Characterization of Ten Hidden-Surface Algorithms. ACM Comput. Surv. 6(1): 1-55(1974) BibTeX
[Tamminien 1981]
...
[Tamminen 1982]
...
[Tamminen 1983]
...
[Tamminen 1984a]
Markku Tamminen: Comment on Quad- and Octtrees. Commun. ACM 27(3): 248-249(1984) BibTeX
[Tamminen 1984b]
...
[Tamminen and Samet 1984]
...
[Tanimoto 1976]
...
[Tanimoto 1979]
...
[Tanimoto and Klinger 1980]
...
[Tanimoto and Pavlidis 1975]
...
[Tarjan 1975]
Robert Endre Tarjan: Efficiency of a Good But Not Linear Set Union Algorithm. J. ACM 22(2): 215-225(1975) BibTeX
[Toussaint 1980]
...
[Tropf and Herzog 1981]
...
[Tucker 1984a]
...
[Tucker 1984b]
...
[Uhr 1972]
...
[Unnikrishnan and Venkatesh 1984]
...
[Van Leeuwen and Wood 1981]
Jan van Leeuwen, Derick Wood: The Measure Problem for Rectangular Ranges in d-Space. J. Algorithms 2(3): 282-300(1981) BibTeX
[Van Lierop 1984]
...
[Warnock 1969]
...
[Webber 1984]
...
[Webber 1978]
...
[Willard 1982]
Dan E. Willard: Polygon Retrieval. SIAM J. Comput. 11(1): 149-165(1982) BibTeX
[Woodwark 1982]
John R. Woodwark: The Explicit Quad Tree as a Structure for Computer Graphics. Comput. J. 25(2): 235-238(1982) BibTeX
[Wu et al. 1982]
...
[Yamaguchi et al. 1984]
...
[Yau 1984]
...
[Yau and Srihari 1983]
Mann-May Yau, Sargur N. Srihari: A Hierarchical Data Structure for Multidimensional Digital Images. Commun. ACM 26(7): 504-515(1983) BibTeX
[Yerry and Shepard 1983]
...

Referenced by

  1. Enrico Nardelli, Guido Proietti: S*-Tree: An Improved S+-Tree for Coloured Images. ADBIS 1999: 156-167
  2. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
  3. Yannis Theodoridis, Timos K. Sellis, Apostolos Papadopoulos, Yannis Manolopoulos: Specifications for Efficient Indexing in Spatiotemporal Databases. SSDBM 1998: 123-132
  4. Min Wang, Jeffrey Scott Vitter, Balakrishna R. Iyer: Selectivity Estimation in the Presence of Alphanumeric Correlations. ICDE 1997: 169-180
  5. Clive G. Page: Astronomical Tables, 2-D Indexing, and Fuzzy-joins. SSDBM 1996: 44-52
  6. John F. Karpovich, James C. French, Andrew S. Grimshaw: High Performance Access to Radio Astronomy Data: A Case Study. SSDBM 1994: 240-249
  7. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
  8. Frank Olken, Doron Rotem: Sampling from Spatial Databases. ICDE 1993: 199-208
  9. Gennaro Costagliola, Genoveffa Tortora, Timothy Arndt: A Unifying Approach to Iconic Indexing for 2-D and 3-D Scences. IEEE Trans. Knowl. Data Eng. 4(3): 205-222(1992)
  10. Fangju Wang: Relational-Linear Quadtree Approach for Two-Dimensional Spatial Representation and Manipulation. IEEE Trans. Knowl. Data Eng. 3(1): 118-122(1991)
  11. Oliver Günther, Jeff Bilmes: Tree-Based Access Methods for Spatial Databases: Implementation and Performance Evaluation. IEEE Trans. Knowl. Data Eng. 3(3): 342-356(1991)
  12. Aris M. Ouksel, Otto Mayer: The Nested Interpolation Based Grid File. MFDBS 1991: 173-187
  13. Christos Faloutsos, Yi Rong: DOT: A Spatial Access Method Using Fractals. ICDE 1991: 152-159
  14. H. V. Jagadish: Spatial Search with Polyhedra. ICDE 1990: 311-319
  15. Jaideep Srivastava, Jack S. Eddy Tan, Vincent Y. Lum: TBSAM: An Access Method for Efficient Processing of Statistical Queries. IEEE Trans. Knowl. Data Eng. 1(4): 414-423(1989)
  16. Jack A. Orenstein: Redundancy in Spatial Databases. SIGMOD Conference 1989: 295-305
  17. Doron Rotem: Clustered Multiattribute Hash Files. PODS 1989: 225-234
  18. Oliver Günther: The Design of the Cell Tree: An Object-Oriented Index Structure for Geometric Databases. ICDE 1989: 598-605
  19. David W. Embley, George Nagy: On the Integration of Lexical and Spatial Data in a Unified High-Level Model. DASFAA 1989: 329-336
  20. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  21. Bernhard Seeger, Hans-Peter Kriegel: Techniques for Design and Implementation of Efficient Spatial Access Methods. VLDB 1988: 360-371
  22. Robert Laurini, Françoise Milleret: Spatial Data Base Queries: Relational Algebra versus Computational Geometry. SSDBM 1988: 291-313
  23. Witold Litwin, Djamel Eddine Zegour, Gérard Lévy: Multilevel Trie Hashing. EDBT 1988: 309-335
  24. Randal C. Nelson, Hanan Samet: A Population Analysis for Hierarchical Data Structures. SIGMOD Conference 1987: 270-277
  25. Christos Faloutsos, Timos K. Sellis, Nick Roussopoulos: Analysis of Object Oriented Spatial Access Methods. SIGMOD Conference 1987: 426-439
  26. Jack A. Orenstein: Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986: 326-336
  27. Ekow J. Otoo: Balanced Multidimensional Extendible Hash Tree. PODS 1986: 100-113
  28. D. A. Beckley, Martha W. Evens, V. K. Raman: Multikey Retrieval from K-d Trees and Quad-Trees. SIGMOD Conference 1985: 291-301
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:54:43 2009