{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,7]],"date-time":"2023-02-07T23:32:17Z","timestamp":1675812737672},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[1989,11,1]],"date-time":"1989-11-01T00:00:00Z","timestamp":625881600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The Visual Computer"],"published-print":{"date-parts":[[1989,11]]},"DOI":"10.1007\/bf01999102","type":"journal-article","created":{"date-parts":[[2005,8,5]],"date-time":"2005-08-05T00:44:47Z","timestamp":1123202687000},"page":"349-359","source":"Crossref","is-referenced-by-count":9,"title":["A comparison of the space requirements of multi-dimensional quadtree-based file structures"],"prefix":"10.1007","volume":"5","author":[{"given":"Hanan","family":"Samet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert E.","family":"Webber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"BF01999102_CR1","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1145\/3973.3975","volume":"4","author":"D Ayala","year":"1985","unstructured":"Ayala D, Brunet P, Juan R, Navazo I (1985) Object respresentation by means of nonminimal division quadtrees and octrees. ACM Trans Graph 4(1):41\u201359","journal-title":"ACM Trans Graph"},{"key":"BF01999102_CR2","doi-asserted-by":"crossref","unstructured":"Beckley DA, Evens MW, Raman VK (1985) Multikey retrieval from k-d trees and quad-trees. Proc SIGMOD Conf, Austin, Texas (May 1985), pp 291\u2013301","DOI":"10.1145\/318898.318925"},{"issue":"9","key":"BF01999102_CR3","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"JL Bentley","year":"1975","unstructured":"Bentley JL (1975) Multidimensional binary search trees used for associative scarching. Commun ACM 18(9):509\u2013517","journal-title":"Commun ACM"},{"issue":"4","key":"BF01999102_CR4","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1109\/MCG.1985.276454","volume":"5","author":"I Carlbom","year":"1985","unstructured":"Carlbom I, Chakravarty I, Vanderschel D (1985) A hierarchical data structure for representing the spatial decomposition of 3-D objects. IEEE Comput Graph Appl 5(4):24\u201331","journal-title":"IEEE Comput Graph Appl"},{"issue":"2","key":"BF01999102_CR5","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1145\/356770.356776","volume":"11","author":"D Comer","year":"1979","unstructured":"Comer D (1979) The Ubiquitous B-tree. ACM Comput Surv 11(2):121\u2013137","journal-title":"ACM Comput Surv"},{"issue":"1","key":"BF01999102_CR6","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1109\/MCG.1981.1673936","volume":"1","author":"LJ Doctor","year":"1981","unstructured":"Doctor LJ, Torborg JG (1981) Display techniques for octreeencoded objects. IEEE Comput Graph Appl 1(1):29\u201338","journal-title":"IEEE Comput Graph Appl"},{"key":"BF01999102_CR7","doi-asserted-by":"crossref","unstructured":"Faloutsos C, Sellis T, Roussopoulos N (1987) Analysis of object oriented spatial access methods. Proc SIGMOD Conf, San Francisco (May 1987), pp 426\u2013439","DOI":"10.1145\/38713.38758"},{"issue":"1","key":"BF01999102_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF00288933","volume":"4","author":"RA Finkel","year":"1974","unstructured":"Finkel RA, Bentley JL (1974) Quad trees: a data structure for retrieval on composite keys. Acta Inf 4(1):1\u20139","journal-title":"Acta Inf"},{"key":"BF01999102_CR9","doi-asserted-by":"crossref","unstructured":"Fujimura K, Kunii TL (1985) A hierarchical space indexing method. Proc Comput Graph '85 (Tokyo 1985), T1-4, pp 1\u201314","DOI":"10.1007\/978-4-431-68030-7_2"},{"issue":"12","key":"BF01999102_CR10","doi-asserted-by":"crossref","first-page":"905","DOI":"10.1145\/358728.358741","volume":"25","author":"I Gargantini","year":"1982","unstructured":"Gargantini I (1982a) An effective way to represent quadtrees. Commun ACM 25(12):905\u2013910","journal-title":"Commun ACM"},{"issue":"4","key":"BF01999102_CR11","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/0146-664X(82)90058-2","volume":"20","author":"I Gargantini","year":"1982","unstructured":"Gargantini I (1982b) Linear octtrees for fast processing of three dimensional objects. Comput Graph Image Proc 20(4):365\u2013374","journal-title":"Comput Graph Image Proc"},{"issue":"4","key":"BF01999102_CR12","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/0898-1221(82)90014-1","volume":"8","author":"I Gargantini","year":"1982","unstructured":"Gargantini I (1982c) Detection of connectivity for regions represented by linear quadtrees. Comput Mathe Appl 8(4):319\u2013327","journal-title":"Comput Mathe Appl"},{"key":"BF01999102_CR13","doi-asserted-by":"crossref","unstructured":"Guttman A (1984) R-trees: a dynamic index structure for spatial searching Proc SIGMOD Conf, Boston (June 1984), pp 47\u201357","DOI":"10.1145\/602259.602266"},{"key":"BF01999102_CR14","volume-title":"Efficient computation, and data structures for graphics","author":"GM Hunter","year":"1978","unstructured":"Hunter GM (1978) Efficient computation, and data structures for graphics. PhD Dissertation, Dep Electrical Eng Comput Sci, Princeton Univ, Princeton NJ"},{"issue":"3","key":"BF01999102_CR15","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0146-664X(80)90055-6","volume":"14","author":"CL Jackins","year":"1980","unstructured":"Jackins CL, Tanimoto SL (1980) Oct-trees and their use in representing three-dimensional objects. Comput Graph Image Proc 14(3):249\u2013270","journal-title":"Comput Graph Image Proc"},{"issue":"2","key":"BF01999102_CR16","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1109\/TPAMI.1984.4767508","volume":"6","author":"L Jones","year":"1984","unstructured":"Jones L, Iyengar SS (1984) Space and time efficient virtual quadtrees. IEEE Trans Pattern Anal Mach Intell 6(2):244\u2013247","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"issue":"1","key":"BF01999102_CR17","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1109\/TPAMI.1980.4766967","volume":"2","author":"E Kawaguchi","year":"1980","unstructured":"Kawaguchi E, Endo T (1980) On a method of binary picture representation and its application to data compression. IEEE Trans Pattern Anal Mach Intell 2(1):27\u201335","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"BF01999102_CR18","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/B978-0-12-604550-5.50019-5","volume-title":"Optimizing Methods in Statistics","author":"A Klinger","year":"1971","unstructured":"Klinger A (1971) Patterns and search statistics. In: Rustagi JS (ed) Optimizing Methods in Statistics, Academic Press, New York, pp 303\u2013337"},{"issue":"7","key":"BF01999102_CR19","doi-asserted-by":"crossref","first-page":"885","DOI":"10.1109\/PROC.1980.11754","volume":"68","author":"K Knowlton","year":"1980","unstructured":"Knowlton K (1980) Progressive transmission of grey-scale and binary pictures by simple, efficient, and lossless encoding schemes. Proc IEEE 68(7):885\u2013896","journal-title":"Proc IEEE"},{"key":"BF01999102_CR20","volume-title":"The art of computer programming, vol 1. Fundamental algorithms","author":"DE Knuth","year":"1973","unstructured":"Knuth DE (1973) The art of computer programming, vol 1. Fundamental algorithms (2nd edn). Addison-Wesley, Reading, MA","edition":"2nd edn"},{"issue":"1","key":"BF01999102_CR21","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/0734-189X(85)90018-0","volume":"30","author":"JP Lauzon","year":"1985","unstructured":"Lauzon JP, Mark DM, Kikuchi L, Guevara JA (1985) Twodimensional run-encoding for quadtree representation. Comput Vision Graph Image Proc 30(1):56\u201369","journal-title":"Comput Vision Graph Image Proc"},{"issue":"3","key":"BF01999102_CR22","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0734-189X(84)90215-9","volume":"26","author":"T Matsuyama","year":"1984","unstructured":"Matsuyama T, Hao LV, Nagao M (1984) A file organization for geographic information systems based on spatial proximity. Coraput Vision Graph Image Proc 26(3):303\u2013318","journal-title":"Coraput Vision Graph Image Proc"},{"issue":"2","key":"BF01999102_CR23","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0146-664X(82)90104-6","volume":"19","author":"D Meagher","year":"1982","unstructured":"Meagher D (1982a) Geometric modeling using octree encoding. Comput Graph Image Proc 19(2):129\u2013147","journal-title":"Comput Graph Image Proc"},{"key":"BF01999102_CR24","volume-title":"The octree encoding method for efficient solid modeling. Electrical and Systems Engineering Rep IPL-TR-032","author":"D Meagher","year":"1982","unstructured":"Meagher D (1982b) The octree encoding method for efficient solid modeling. Electrical and Systems Engineering Rep IPL-TR-032, Rensselaer Polytechnic Institute, Troy, NY (August 1982)"},{"key":"BF01999102_CR25","doi-asserted-by":"crossref","unstructured":"Nelson RC, Samet H (1987) A population analysis for hierarchical data structures. Proc SIGMOD Conf, San Francisco (May 1987), pp 270\u2013277","DOI":"10.1145\/38713.38744"},{"key":"BF01999102_CR26","unstructured":"Okawara F, Shimizu K, Nishitani Y (1988) Data compression of the region quadtree and algorithms for set operations. Dept Comput Sci Rep CS-88-6, Gunma Univ, Gunma, Japan (July 1988) (translated from Proc 36th All-Japan Conf on Information Processing, Information Processing Society of Japan, Tokyo, Japan (March 1988) pp 73\u201374)"},{"issue":"1","key":"BF01999102_CR27","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1093\/comjnl\/26.1.83","volume":"26","author":"MA Oliver","year":"1983","unstructured":"Oliver MA, Wiseman NE (1983) Operations on quadtree-encoded images. Comput J 26(1):83\u201391","journal-title":"Comput J"},{"issue":"4","key":"BF01999102_CR28","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0020-0190(82)90027-8","volume":"14","author":"JA Orenstein","year":"1982","unstructured":"Orenstein JA (1982) Multidimensional tries used for associative searching. Inf Proc Lett 14(4):150\u2013157","journal-title":"Inf Proc Lett"},{"key":"BF01999102_CR29","doi-asserted-by":"crossref","unstructured":"Robinson JT (1981) The k-d-B-tree: a search structure for large multidimensional dynamic indexes. Proc SIGMOD Conf, Ann Arbor, Michigan (April 1981), pp 10\u201318","DOI":"10.1145\/582318.582321"},{"key":"BF01999102_CR30","doi-asserted-by":"crossref","unstructured":"Roussopoulos N, Leifker D (1985) Direct spatial search on pictorial databases using Packed R-trees. Proc SIGMOD Conf, Austin, Texas (May 1985), pp 17\u201331","DOI":"10.1145\/318898.318900"},{"issue":"2","key":"BF01999102_CR31","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1145\/356924.356930","volume":"16","author":"H Samet","year":"1984","unstructured":"Samet H (1984) The quadtree and related hierarchical data structures. ACM Comput Surv 16(2):187\u2013260","journal-title":"ACM Comput Surv"},{"issue":"9","key":"BF01999102_CR32","doi-asserted-by":"crossref","first-page":"973","DOI":"10.1145\/4284.4290","volume":"28","author":"H Samet","year":"1985","unstructured":"Samet H (1985) Data structures for quadtree approximation and compression. Commun ACM 28(9):973\u2013993","journal-title":"Commun ACM"},{"key":"BF01999102_CR33","volume-title":"The design and analysis of spatial data structures","author":"H Samet","year":"1990","unstructured":"Samet H (1990a) The design and analysis of spatial data structures. Addison-Wesley, Reading, MA"},{"key":"BF01999102_CR34","volume-title":"Applications of spatial data structures: Computer graphics, image processing, and GIS","author":"H Samet","year":"1990","unstructured":"Samet H (1990b) Applications of spatial data structures: Computer graphics, image processing, and GIS, Addison-Wesley, Reading, MA"},{"issue":"3","key":"BF01999102_CR35","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1145\/325165.325211","volume":"19","author":"H Samet","year":"1985","unstructured":"Samet H, Tamminen M (1985) Bintrees, CSG trees, and time. Comput Graph 19(3):121\u2013130","journal-title":"Comput Graph"},{"issue":"4","key":"BF01999102_CR36","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1109\/34.3918","volume":"10","author":"H Samet","year":"1988","unstructured":"Samet H, Tamminen M (1988) Efficient component labeling of images of arbitrary dimension represented by linear bintrees. ZEEE Trans Pattern Anal Mach Intell 10(4):579\u2013586","journal-title":"ZEEE Trans Pattern Anal Mach Intell"},{"issue":"3","key":"BF01999102_CR37","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1145\/282957.282966","volume":"4","author":"H Samet","year":"1985","unstructured":"Samet H, Webber RE (1985) Storing a collection of polygons using quadtrees. ACM Trans Graph 4(3):182\u2013222","journal-title":"ACM Trans Graph"},{"issue":"6","key":"BF01999102_CR38","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1016\/0031-3203(84)90018-9","volume":"17","author":"H Samet","year":"1984","unstructured":"Samet H, Rosenfeld A, Shaffer CA, Webber RE (1984) A geographic information system using quadtrees. Pattern Recognition 17(6):647\u2013656","journal-title":"Pattern Recognition"},{"issue":"3","key":"BF01999102_CR39","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/0262-8856(87)90049-7","volume":"5","author":"H Samet","year":"1987","unstructured":"Samet H, Shaffer CA, Nelson RC, Huang YG, Fujimura K, Rosenfeld A (1987) Recent developments in linear quadtreebased geographic information systems. Image Vision Comput 5(3):187\u2013197","journal-title":"Image Vision Comput"},{"issue":"3","key":"BF01999102_CR40","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1145\/357994.358026","volume":"27","author":"M Tamminen","year":"1984","unstructured":"Tamminen M (1984) Comment on quad-and octtrees. Commun ACM 27(3):248\u2013249","journal-title":"Commun ACM"},{"issue":"7","key":"BF01999102_CR41","doi-asserted-by":"crossref","first-page":"504","DOI":"10.1145\/358150.358158","volume":"26","author":"M Yau","year":"1983","unstructured":"Yau M, Srihari SN (1983) A hierarchical data structure for multidimensional digital images. Commun ACM 26(7):504\u2013515","journal-title":"Commun ACM"}],"container-title":["The Visual Computer"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01999102.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01999102\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01999102","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T18:04:11Z","timestamp":1586369051000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01999102"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,11]]},"references-count":41,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1989,11]]}},"alternative-id":["BF01999102"],"URL":"https:\/\/doi.org\/10.1007\/bf01999102","relation":{},"ISSN":["0178-2789","1432-8726"],"issn-type":[{"value":"0178-2789","type":"print"},{"value":"1432-8726","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,11]]}}}