{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T04:51:43Z","timestamp":1776833503605,"version":"3.51.2"},"publisher-location":"Berlin, Heidelberg","reference-count":56,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540522089","type":"print"},{"value":"9783540469247","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1990]]},"DOI":"10.1007\/3-540-52208-5_28","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:23:38Z","timestamp":1330205018000},"page":"191-212","source":"Crossref","is-referenced-by-count":225,"title":["Hierarchical spatial data structures"],"prefix":"10.1007","author":[{"given":"Hanan","family":"Samet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"issue":"1","key":"10_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0734-189X(83)90017-8","volume":"24","author":"D.J. Abel","year":"1983","unstructured":"-D.J. Abel and J.L. Smith, A data structure and algorithm based on a linear key for a rectangle retrieval problem, Computer Vision, Graphics, and Image Processing 24, 1(October 1983), 1\u201313.","journal-title":"Computer Vision, Graphics, and Image Processing"},{"issue":"1","key":"10_CR2","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/3973.3975","volume":"4","author":"D. Ayala","year":"1985","unstructured":"-D. Ayala, P. Brunet, R. Juan, and I. Navazo, Object representation by means of nonminimal division quadtrees and octrees, ACM Transactions on Graphics 4, 1(January 1985), 41\u201359.","journal-title":"ACM Transactions on Graphics"},{"issue":"5","key":"10_CR3","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1145\/358645.358661","volume":"24","author":"D.H. Ballard","year":"1981","unstructured":"-D.H. Ballard, Strip trees: A hierarchical representation for curves, Communications of the ACM 24, 5(May 1981), 310\u2013321 (see also corrigendum, Communications of the ACM 25, 3(March 1982), 213).","journal-title":"Communications of the ACM"},{"issue":"4","key":"10_CR4","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1109\/MCG.1985.276454","volume":"5","author":"I. Carlbom","year":"1985","unstructured":"-I. Carlbom, I. Chakravarty, and D. Vanderschel, A hierarchical data structure for representing the spatial decomposition of 3-D objects, IEEE Computer Graphics and Applications 5, 4(April 1985), 24\u201331.","journal-title":"IEEE Computer Graphics and Applications"},{"issue":"2","key":"10_CR5","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1145\/356770.356776","volume":"11","author":"D. Comer","year":"1979","unstructured":"-D. Comer, The Ubiquitous B-tree, ACM Computing Surveys 11, 2(June 1979), 121\u2013137.","journal-title":"ACM Computing Surveys"},{"key":"10_CR6","unstructured":"-H. Edelsbrunner, Dynamic rectangle intersection searching, Institute for Information Processing Report 47, Technical University of Graz, Graz, Austria, February 1980."},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"-C. Faloutsos, T. Sellis, and N. Roussopoulos, Analysis of object oriented spatial access methods, Proceedings of the SIGMOD Conference, San Francisco, May 1987, 426\u2013439.","DOI":"10.1145\/38713.38758"},{"issue":"1","key":"10_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF00288933","volume":"4","author":"R.A. Finkel","year":"1974","unstructured":"-R.A. Finkel and J.L. Bentley, Quad trees: a data structure for retrieval on composite keys, Acta Informatica 4, 1(1974), 1\u20139.","journal-title":"Acta Informatica"},{"issue":"1","key":"10_CR9","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1145\/356625.356627","volume":"6","author":"H. Freeman","year":"1974","unstructured":"-H. Freeman, Computer processing of line-drawing images, ACM Computing Surveys 6, 1(March 1974), 57\u201397.","journal-title":"ACM Computing Surveys"},{"key":"10_CR10","unstructured":"-K. Fujimura and T.L. Kunii, A hierarchical space indexing method, Proceedings of Computer Graphics'85, Tokyo, 1985, T1\u20134, 1\u201314."},{"issue":"12","key":"10_CR11","doi-asserted-by":"publisher","first-page":"905","DOI":"10.1145\/358728.358741","volume":"25","author":"I. Gargantini","year":"1982","unstructured":"-I. Gargantini, An effective way to represent quadtrees, Communications of the ACM 25, 12(December 1982), 905\u2013910.","journal-title":"Communications of the ACM"},{"key":"10_CR12","series-title":"Lecture Notes in Computer Science","volume-title":"Efficient structures for geometric data management","author":"O. G\u00fcnther","year":"1987","unstructured":"-O. G\u00fcnther, Efficient structures for geometric data management, Ph.D. dissertation, UCB\/ERL M87\/77, Electronics Research Laboratory, College of Engineering, University of California at Berkeley, Berkeley, CA, 1987 (Lecture Notes in Computer Science 337, Springer-Verlag, Berlin, 1988)."},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"-A. Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the SIGMOD Conference, Boston, June 1984, 47\u201357.","DOI":"10.1145\/602259.602266"},{"key":"10_CR14","volume-title":"The grid file system: implementation and case studies of applications","author":"K. Hinrichs","year":"1985","unstructured":"-K. Hinrichs, The grid file system: implementation and case studies of applications, Ph.D. dissertation, Institut fur Informatik, ETH, Zurich, Switzerland, 1985."},{"key":"10_CR15","first-page":"100","volume-title":"Proceedings of the WG'83 (International Workshop on Graphtheoretic Concepts in Computer Science)","author":"K. Hinrichs","year":"1983","unstructured":"-K. Hinrichs and J. Nievergelt, The grid file: a data structure designed to support proximity queries on spatial objects, Proceedings of the WG'83 (International Workshop on Graphtheoretic Concepts in Computer Science), M. Nagl and J. Perl, Eds., Trauner Verlag, Linz, Austria, 1983, 100\u2013113."},{"issue":"2","key":"10_CR16","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1145\/321941.321956","volume":"23","author":"S.L. Horowitz","year":"1976","unstructured":"-S.L. Horowitz and T. Pavlidis, Picture segmentation by a tree traversal algorithm, Journal of the ACM 23, 2(April 1976), 368\u2013388.","journal-title":"Journal of the ACM"},{"key":"10_CR17","volume-title":"Efficient computation and data structures for graphics","author":"G.M. Hunter","year":"1978","unstructured":"-G.M. Hunter, Efficient computation and data structures for graphics, Ph.D. dissertation, Department of Electrical Engineering and Computer Science, Princeton University, Princeton, NJ, 1978."},{"key":"10_CR18","volume-title":"Geometrees for interactive visualization of geology: an evaluation","author":"G.M. Hunter","year":"1981","unstructured":"-G.M. Hunter, Geometrees for interactive visualization of geology: an evaluation, System Science Department, Schlumberger-Doll Research, Ridgefield, CT, 1981."},{"issue":"2","key":"10_CR19","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1109\/TPAMI.1979.4766900","volume":"1","author":"G.M. Hunter","year":"1979","unstructured":"-G.M. Hunter and K. Steiglitz, Operations on images using quad trees, IEEE Transactions on Pattern Analysis and Machine Intelligence 1, 2(April 1979), 145\u2013153.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"3","key":"10_CR20","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0146-664X(80)90055-6","volume":"14","author":"C.L. Jackins","year":"1980","unstructured":"-C.L. Jackins and S.L. Tanimoto, Oct-trees and their use in representing three-dimensional objects, Computer Graphics and Image Processing 14, 3(November 1980), 249\u2013270.","journal-title":"Computer Graphics and Image Processing"},{"issue":"1","key":"10_CR21","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1109\/TPAMI.1980.4766967","volume":"2","author":"E. Kawaguchi","year":"1980","unstructured":"-E. Kawaguchi and T. Endo, On a method of binary picture representation and its application to data compression, IEEE Transactions on Pattern Analysis and Machine Intelligence 2, 1(January 1980), 27\u201335.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"10_CR22","doi-asserted-by":"crossref","unstructured":"-G. Kedem, The Quad-CIF tree: a data structure for hierarchical on-line algorithms, Proceedings of the Nineteenth Design Automation Conference, Las Vegas, June 1982, 352\u2013357.","DOI":"10.1145\/800263.809229"},{"key":"10_CR23","first-page":"303","volume-title":"Optimizing Methods in Statistics","author":"A. Klinger","year":"1971","unstructured":"-A. Klinger, Patterns and Search Statistics, in Optimizing Methods in Statistics, J.S. Rustagi, Ed., Academic Press, New York, 1971, 303\u2013337."},{"issue":"1","key":"10_CR24","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/S0146-664X(76)80006-8","volume":"5","author":"A. Klinger","year":"1976","unstructured":"-A. Klinger and C.R. Dyer, Experiments in picture representation using regular decomposition, Computer Graphics and Image Processing 5, 1(March 1976), 68\u2013105.","journal-title":"Computer Graphics and Image Processing"},{"issue":"1","key":"10_CR25","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1109\/TPAMI.1979.4766875","volume":"1","author":"A. Klinger","year":"1979","unstructured":"-A. Klinger and M.L. Rhodes, Organization and access of image data by areas, IEEE Transactions on Pattern Analysis and Machine Intelligence 1, 1(January 1979), 50\u201360.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"1","key":"10_CR26","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/0146-664X(82)90074-0","volume":"20","author":"M. Li","year":"1982","unstructured":"-M. Li, W.I. Grosky, and R. Jain, Normalized quadtrees with respect to translations, Computer Graphics and Image Processing 20, 1(September 1982), 72\u201381.","journal-title":"Computer Graphics and Image Processing"},{"issue":"3","key":"10_CR27","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0734-189X(84)90215-9","volume":"26","author":"T. Matsuyama","year":"1984","unstructured":"-T. Matsuyama, L.V. Hao, and M. Nagao, A file organization for geographic information systems based on spatial proximity, Computer Vision, Graphics, and Image Processing 26, 3(June 1984), 303\u2013318.","journal-title":"Computer Vision, Graphics, and Image Processing"},{"key":"10_CR28","unstructured":"-E.M. McCreight, Efficient algorithms for enumerating intersecting intervals and rectangles, Xerox Palo Alto Research Center Report CSL-80-09, Palo Alto, California, June 1980."},{"key":"10_CR29","unstructured":"-D. Meagher, Octree encoding: a new technique for the representation, The manipulation, and display of arbitrary 3-d objects by computer, Technical Report IPL-TR-80-111, Image Processing Laboratory, Rensselaer Polytechnic Institute, Troy, New York, October 1980."},{"issue":"2","key":"10_CR30","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0146-664X(82)90104-6","volume":"19","author":"D. Meagher","year":"1982","unstructured":"-D. Meagher, Geometric modeling using octree encoding, Computer Graphics and Image Processing 19, 2(June 1982), 129\u2013147.","journal-title":"Computer Graphics and Image Processing"},{"key":"10_CR31","volume-title":"A computer oriented geodetic data base and a new technique in file sequencing","author":"G.M. Morton","year":"1966","unstructured":"-G.M. Morton, A computer oriented geodetic data base and a new technique in file sequencing, IBM Ltd., Ottawa, Canada, 1966."},{"key":"10_CR32","unstructured":"-I. Navazo, Contribuci\u00f3 a les tecniques de modelat geometric d'objectes poli\u00e8drics usant la codificaci\u00f3 amb arbres octals, Ph.D. dissertation, Escola Tecnica Superior d'Enginyers Industrials, Department de Methodes Informatics, Universitat Politechnica de Barcelona, Barcelona, Spain, January 1986."},{"issue":"4","key":"10_CR33","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1145\/15886.15908","volume":"20","author":"R.C. Nelson","year":"1986","unstructured":"-R.C. Nelson and H. Samet, A consistent hierarchical representation for vector data, Computer Graphics 20, 4(August 1986), pp. 197\u2013206 (also Proceedings of the SIGGRAPH'86 Conference, Dallas, August 1986).","journal-title":"Computer Graphics"},{"issue":"1","key":"10_CR34","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1145\/348.318586","volume":"9","author":"J. Nievergelt","year":"1984","unstructured":"-J. Nievergelt, H. Hinterberger, and K.C. Sevcik, The grid file: an adaptable, symmetric multikey file structure, ACM Transactions on Database Systems 9, 1(March 1984), 38\u201371.","journal-title":"ACM Transactions on Database Systems"},{"issue":"4","key":"10_CR35","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0020-0190(82)90027-8","volume":"14","author":"J.A. Orenstein","year":"1982","unstructured":"-J.A. Orenstein, Multidimensional tries used for associative searching, Information Processing Letters 14, 4(June 1982), 150\u2013157.","journal-title":"Information Processing Letters"},{"key":"10_CR36","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F.P. Preparata","year":"1985","unstructured":"-F.P. Preparata and M.I. Shamos, Computational Geometry: An Introduction, Springer-Verlag, New York, 1985."},{"key":"10_CR37","first-page":"126","volume-title":"Proceedings of CAD 82 Conference","author":"K.M. Quinlan","year":"1982","unstructured":"-K.M. Quinlan and J.R. Woodwark, A spatially-segmented solids database \u2014 justification and design, Proceedings of CAD 82 Conference, Butterworth, Guildford, United Kingdom, 1982, 126\u2013132."},{"key":"10_CR38","volume-title":"Representation of three-dimensional objects, CMU-CS-78-113","author":"D.R. Reddy","year":"1978","unstructured":"-D.R. Reddy and S. Rubin, Representation of three-dimensional objects, CMU-CS-78-113, Computer Science Department, Carnegie-Mellon University, Pittsburgh, April 1978."},{"issue":"2","key":"10_CR39","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1145\/356924.356930","volume":"16","author":"H. Samet","year":"1984","unstructured":"-H. Samet, The quadtree and related hierarchical data structures, ACM Computing Surveys 16, 2(June 1984), 187\u2013260.","journal-title":"ACM Computing Surveys"},{"issue":"4","key":"10_CR40","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1145\/50020.50021","volume":"20","author":"H. Samet","year":"1988","unstructured":"-H. Samet, Hierarchical representations of collections of small rectangles, ACM Computing Surveys 20, 4(December 1988), 271\u2013309.","journal-title":"ACM Computing Surveys"},{"key":"10_CR41","volume-title":"The Design and Analysis of Spatial Data Structures","author":"H. Samet","year":"1989","unstructured":"-H. Samet, The Design and Analysis of Spatial Data Structures, Addison-Wesley, Reading, MA, 1989."},{"key":"10_CR42","volume-title":"Applications of Spatial Data Structures: Computer Graphics, Image Processing and GIS","author":"H. Samet","year":"1989","unstructured":"-H. Samet, Applications of Spatial Data Structures: Computer Graphics, Image Processing and GIS, Addison-Wesley, Reading, MA, 1989."},{"issue":"6","key":"10_CR43","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1016\/0031-3203(84)90018-9","volume":"17","author":"H. Samet","year":"1984","unstructured":"-H. Samet, A. Rosenfeld, C.A. Shaffer, and R.E. Webber, A geographic information system using quadtrees, Pattern Recognition 17, 6 (November\/December 1984), 647\u2013656.","journal-title":"Pattern Recognition"},{"issue":"6","key":"10_CR44","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1016\/0020-0190(87)90113-X","volume":"24","author":"H. Samet","year":"1987","unstructured":"-H. Samet, C.A. Shaffer, and R.E. Webber, Digitizing the plane with cells of non-uniform size, Information Processing Letters 24, 6(April 1987), 369\u2013375.","journal-title":"Information Processing Letters"},{"issue":"3","key":"10_CR45","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1145\/282957.282966","volume":"4","author":"H. Samet","year":"1985","unstructured":"-H. Samet and R.E. Webber, Storing a collection of polygons using quadtrees, ACM Transactions on Graphics 4, 3(July 1985), 182\u2013222 (also Proceedings of Computer Vision and Pattern Recognition 83, Washington, DC, June 1983, 127\u2013132).","journal-title":"ACM Transactions on Graphics"},{"key":"10_CR46","unstructured":"-H. Samet and R.E. Webber, A comparison of the space requirements of multi-dimensional quadtree-based file structures, to appear in The Visual Computer (also University of Maryland Computer Science TR-1711)."},{"issue":"3","key":"10_CR47","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1109\/38.513","volume":"8","author":"H. Samet","year":"1988","unstructured":"-H. Samet and R.E. Webber, Hierarchical data structures and algorithms for computer graphics. Part I. Fundamentals, IEEE Computer Graphics and Applications 8, 3(May 1988), 48\u201368.","journal-title":"IEEE Computer Graphics and Applications"},{"issue":"4","key":"10_CR48","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1109\/38.7750","volume":"8","author":"H. Samet","year":"1988","unstructured":"-H. Samet and R.E. Webber, Hierarchical data structures and algorithms for computer graphics. Part II. Applications, IEEE Computer Graphics and Applications 8, 4(July 1988), 59\u201375.","journal-title":"IEEE Computer Graphics and Applications"},{"key":"10_CR49","unstructured":"-T. Sellis, N. Roussopoulos, and C. Faloutsos, The R+-tree: a dynamic index for multi-dimensional objects, Computer Science TR-1795, University of Maryland, College Park, MD, February 1987."},{"issue":"3","key":"10_CR50","doi-asserted-by":"crossref","first-page":"402","DOI":"10.1016\/0734-189X(87)90045-4","volume":"37","author":"C.A. Shaffer","year":"1987","unstructured":"-C.A. Shaffer and H. Samet, Optimal quadtree construction algorithms, Computer Vision, Graphics, and Image Processing 37, 3(March 1987), 402\u2013419.","journal-title":"Computer Vision, Graphics, and Image Processing"},{"issue":"3","key":"10_CR51","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1016\/0146-664X(81)90042-3","volume":"16","author":"M. Shneier","year":"1981","unstructured":"-M. Shneier, Calculations of geometric properties using quadtrees, Computer Graphics and Image Processing 16, 3(July 1981), 296\u2013302.","journal-title":"Computer Graphics and Image Processing"},{"issue":"3","key":"10_CR52","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/0146-664X(81)90002-2","volume":"17","author":"M. Shneier","year":"1981","unstructured":"-M. Shneier, Two hierarchical linear feature representations: edge pyramids and edge quadtrees, Computer Graphics and Image Processing 17, 3(November 1981), 211\u2013224.","journal-title":"Computer Graphics and Image Processing"},{"key":"10_CR53","doi-asserted-by":"crossref","unstructured":"-M. Tamminen, The EXCELL method for efficient geometric access to data, Acta Polytechnica Scandinavica, Mathematics and Computer Science Series No. 34, Helsinki, 1981.","DOI":"10.1109\/DAC.1982.1585522"},{"issue":"2","key":"10_CR54","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/S0146-664X(75)80003-7","volume":"4","author":"S. Tanimoto","year":"1975","unstructured":"\u2014 S. Tanimoto and T. Pavlidis, A hierarchical data structure for picture processing, Computer Graphics and Image Processing 4, 2(June 1975), 104\u2013119.","journal-title":"Computer Graphics and Image Processing"},{"key":"10_CR55","volume-title":"Divided leaf octal trees, Research Note","author":"D.J. Vanderschel","year":"1984","unstructured":"\u2014 D.J. Vanderschel, Divided leaf octal trees, Research Note, Schlumberger-Doll Research, Ridgefield, CT, March 1984."},{"key":"10_CR56","volume-title":"A hidden surface algorithm for computer generated half tone pictures, Computer Science Department TR 4\u201315","author":"J.L. Warnock","year":"1969","unstructured":"\u2014 J.L. Warnock, A hidden surface algorithm for computer generated half tone pictures, Computer Science Department TR 4\u201315, University of Utah, Salt Lake City, June 1969."}],"container-title":["Lecture Notes in Computer Science","Design and Implementation of Large Spatial Databases"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-52208-5_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:23:32Z","timestamp":1605648212000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-52208-5_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990]]},"ISBN":["9783540522089","9783540469247"],"references-count":56,"URL":"https:\/\/doi.org\/10.1007\/3-540-52208-5_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990]]}}}