{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:27:48Z","timestamp":1750307268570,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":56,"publisher":"ACM","license":[{"start":{"date-parts":[[2010,12,15]],"date-time":"2010-12-15T00:00:00Z","timestamp":1292371200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2010,12,15]]},"DOI":"10.1145\/1900520.1900523","type":"proceedings-article","created":{"date-parts":[[2010,12,20]],"date-time":"2010-12-20T16:13:47Z","timestamp":1292861627000},"page":"1-52","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Sorting in space"],"prefix":"10.1145","author":[{"given":"Hanan","family":"Samet","sequence":"first","affiliation":[{"name":"University of Maryland, College Park, MD"}]}],"member":"320","published-online":{"date-parts":[[2010,12,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"October","author":"Abel D. J.","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): 1--13 , October 1983 . 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): 1--13, October 1983."},{"issue":"4","key":"e_1_3_2_1_2_1","first-page":"147","article-title":"A data structure and query algorithm for a database of areal entities","volume":"16","author":"Abel D. J.","year":"1984","unstructured":"D. J. Abel and J. L. Smith . A data structure and query algorithm for a database of areal entities . Australian Computer Journal , 16 ( 4 ): 147 -- 154 , November 1984 . D. J. Abel and J. L. Smith. A data structure and query algorithm for a database of areal entities. Australian Computer Journal, 16(4): 147--154, November 1984.","journal-title":"Australian Computer Journal"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/846219.847361"},{"key":"e_1_3_2_1_4_1","first-page":"178","volume-title":"Proceedings of the 5th International Symposium on Spatial Data Handling","author":"Aref W. G.","year":"1992","unstructured":"W. G. Aref and H. Samet . Uniquely reporting spatial objects: yet another operation for comparing spatial data structures . In Proceedings of the 5th International Symposium on Spatial Data Handling , pages 178 -- 189 , Charleston, SC , August 1992 . W. G. Aref and H. Samet. Uniquely reporting spatial objects: yet another operation for comparing spatial data structures. In Proceedings of the 5th International Symposium on Spatial Data Handling, pages 178--189, Charleston, SC, August 1992."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/191246.191307"},{"key":"e_1_3_2_1_6_1","volume-title":"The JAVA#8482","author":"Arnold K.","year":"1996","unstructured":"K. Arnold and J. Gosling . The JAVA#8482 ; Programming Language. Addison-Wesley , Reading, MA, 1996 . K. Arnold and J. Gosling. The JAVA#8482; Programming Language. Addison-Wesley, Reading, MA, 1996."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/94788.94794"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3973.3975"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.1530387"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/356789.356797"},{"key":"e_1_3_2_1_12_1","first-page":"147","volume-title":"Proceedings of the IFIP TC2\/\/WG2.6 Fourth Working Conference on Visual Database Systems","author":"Brabec F.","year":"1998","unstructured":"F. Brabec and H. Samet . The VASCO R-tree JAVA#8482; applet. In Visual Database Systems (VDB4) . Proceedings of the IFIP TC2\/\/WG2.6 Fourth Working Conference on Visual Database Systems , pages 147 -- 153 , Chapman and Hall, L'Aquila, Italy , May 1998 . F. Brabec and H. Samet. The VASCO R-tree JAVA#8482; applet. In Visual Database Systems (VDB4). Proceedings of the IFIP TC2\/\/WG2.6 Fourth Working Conference on Visual Database Systems, pages 147--153, Chapman and Hall, L'Aquila, Italy, May 1998."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/647249.719808"},{"key":"e_1_3_2_1_14_1","first-page":"70","volume-title":"Proceedings of the 16th European Workshop on Computational Geometry","author":"Brabec F.","year":"2000","unstructured":"F. Brabec and H. Samet . Visualizing and animating search operations on quadtrees on the worldwide web . In Proceedings of the 16th European Workshop on Computational Geometry , pages 70 -- 76 , Eilat, Israel , March 2000 . F. Brabec and H. Samet. Visualizing and animating search operations on quadtrees on the worldwide web. In Proceedings of the 16th European Workshop on Computational Geometry, pages 70--76, Eilat, Israel, March 2000."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_3_2_1_16_1","volume-title":"Proceedings of the Third International Conference on Computer Graphics Theory and Applications (GRAPP 2008","author":"Floriani L. De","year":"2008","unstructured":"L. De Floriani , M. Facinoli , P. Magillo , and D. Dimitri . A hierarchical spatial index for triangulated surfaces . In Proceedings of the Third International Conference on Computer Graphics Theory and Applications (GRAPP 2008 ), J. Braz, N. Jardim Nunes, and J. Madeiras Pereira, eds., pages 86--91, Funchal, Madeira, Portugal , January 2008 . L. De Floriani, M. Facinoli, P. Magillo, and D. Dimitri. A hierarchical spatial index for triangulated surfaces. In Proceedings of the Third International Conference on Computer Graphics Theory and Applications (GRAPP 2008), J. Braz, N. Jardim Nunes, and J. Madeiras Pereira, eds., pages 86--91, Funchal, Madeira, Portugal, January 2008."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/846219.847395"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502524"},{"key":"e_1_3_2_1_20_1","volume-title":"Design and Implementation of Large Spatial Databases---1st Symposium, SSD'89","volume":"409","author":"Frank A. U.","unstructured":"A. U. Frank and R. Barrera . The Fieldtree: a data structure for geographic information systems . In Design and Implementation of Large Spatial Databases---1st Symposium, SSD'89 , A. Buchmann, O. G\u00fcnther, T. R. Smith, and Y.-F. Wang, eds. , vol. 409 of Springer-Verlag Lecture Notes in Computer Science, pages 29--44, Santa Barbara, CA, July 1989. A. U. Frank and R. Barrera. The Fieldtree: a data structure for geographic information systems. In Design and Implementation of Large Spatial Databases---1st Symposium, SSD'89, A. Buchmann, O. G\u00fcnther, T. R. Smith, and Y.-F. Wang, eds., vol. 409 of Springer-Verlag Lecture Notes in Computer Science, pages 29--44, Santa Barbara, CA, July 1989."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/800250.807481"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/237170.237244"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_3_2_1_24_1","first-page":"136","volume-title":"Proceedings of the 2nd ACM Workshop on Geographic Information Systems, N. Pissinou and K. Makki, eds.","author":"Henrich A.","year":"1994","unstructured":"A. Henrich . A distance-scan algorithm for spatial access structures . In Proceedings of the 2nd ACM Workshop on Geographic Information Systems, N. Pissinou and K. Makki, eds. , pages 136 -- 143 , Gaithersburg, MD , December 1994 . A. Henrich. A distance-scan algorithm for spatial access structures. In Proceedings of the 2nd ACM Workshop on Geographic Information Systems, N. Pissinou and K. Makki, eds., pages 136--143, Gaithersburg, MD, December 1994."},{"key":"e_1_3_2_1_25_1","volume-title":"Advances in Spatial Databases---4th International Symposium, SSD'95","volume":"951","author":"Hjaltason G. R.","unstructured":"G. R. Hjaltason and H. Samet . Ranking in spatial databases . In Advances in Spatial Databases---4th International Symposium, SSD'95 , M. J. Egenhofer and J. R. Herring, eds. , vol. 951 of Springer-Verlag Lecture Notes in Computer Science, pages 83--95, Portland, ME, August 1995. G. R. Hjaltason and H. Samet. Ranking in spatial databases. In Advances in Spatial Databases---4th International Symposium, SSD'95, M. J. Egenhofer and J. R. Herring, eds., vol. 951 of Springer-Verlag Lecture Notes in Computer Science, pages 83--95, Portland, ME, August 1995."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/320248.320255"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/645475.654159"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206049.1206056"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253347"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/800263.809229"},{"key":"e_1_3_2_1_32_1","first-page":"303","volume-title":"Optimizing Methods in Statistics","author":"Klinger A.","year":"1971","unstructured":"A. Klinger . Patterns and search statistics. In Optimizing Methods in Statistics , J. S. Rustagi, ed., pages 303 -- 337 . Academic Press , New York , 1971 . A. Klinger. Patterns and search statistics. In Optimizing Methods in Statistics, J. S. Rustagi, ed., pages 303--337. Academic Press, New York, 1971."},{"key":"e_1_3_2_1_33_1","volume-title":"The Art of Computer Programming: Sorting and Searching","author":"Knuth D. E.","year":"1998","unstructured":"D. E. Knuth . The Art of Computer Programming: Sorting and Searching , vol. 3 . Addison-Wesley , Reading, MA , second edition, 1998 . D. E. Knuth. The Art of Computer Programming: Sorting and Searching, vol. 3. Addison-Wesley, Reading, MA, second edition, 1998."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0146-664X(82)90104-6"},{"key":"e_1_3_2_1_35_1","volume-title":"Technical Report TR-89-063","author":"Omohundro S. M.","year":"1989","unstructured":"S. M. Omohundro . Five balltree construction algorithms. Technical Report TR-89-063 , International Computer Science Institute , Berkeley, CA , December 1989 . S. M. Omohundro. Five balltree construction algorithms. Technical Report TR-89-063, International Computer Science Institute, Berkeley, CA, December 1989."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90027-8"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66954"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0734-189X(87)80151-2"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/4333"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCG.1982.1674149"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/582318.582321"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/360827.360831"},{"key":"e_1_3_2_1_44_1","volume-title":"Image Processing","author":"Samet H.","year":"1990","unstructured":"H. Samet . Applications of Spatial Data Structures : Computer Graphics , Image Processing , and GIS. Addison-Wesley , Reading, MA , 1990 . H. Samet. Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS. Addison-Wesley, Reading, MA, 1990."},{"key":"e_1_3_2_1_45_1","volume-title":"Addison-Wesley","author":"Samet H.","year":"1990","unstructured":"H. Samet . The Design and Analysis of Spatial Data Structures . Addison-Wesley , Reading, MA , 1990 . H. Samet. The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading, MA, 1990."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1042046.1042052"},{"key":"e_1_3_2_1_47_1","volume-title":"Morgan-Kaufmann","author":"Samet H.","year":"2006","unstructured":"H. Samet . Foundations of Multidimensional and Metric Data Structures . Morgan-Kaufmann , San Francisco , 2006 . H. Samet. Foundations of Multidimensional and Metric Data Structures. Morgan-Kaufmann, San Francisco, 2006."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/282957.282966"},{"key":"e_1_3_2_1_50_1","first-page":"360","volume-title":"Proceedings of the 14th International Conference on Very Large Databases (VLDB), F. Bachillon and D. J. DeWitt, eds.","author":"Seeger B.","year":"1988","unstructured":"B. Seeger and H.-P. Kriegel . Techniques for design and implementation of efficient spatial access methods . In Proceedings of the 14th International Conference on Very Large Databases (VLDB), F. Bachillon and D. J. DeWitt, eds. , pages 360 -- 371 , Los Angeles , August 1988 . B. Seeger and H.-P. Kriegel. Techniques for design and implementation of efficient spatial access methods. In Proceedings of the 14th International Conference on Very Large Databases (VLDB), F. Bachillon and D. J. DeWitt, eds., pages 360--371, Los Angeles, August 1988."},{"key":"e_1_3_2_1_51_1","first-page":"71","volume-title":"Proceedings of the 13th International Conference on Very Large Databases (VLDB)","author":"Sellis T.","year":"1987","unstructured":"T. Sellis , N. Roussooulos , and C. Faloutsos . The R+-tree: a dynamic index for multi-dimensional objects . In Proceedings of the 13th International Conference on Very Large Databases (VLDB) , pages 71 -- 79 , Brighton, United Kingdom , September 1987 . T. Sellis, N. Roussooulos, and C. Faloutsos. The R+-tree: a dynamic index for multi-dimensional objects. In Proceedings of the 13th International Conference on Very Large Databases (VLDB), pages 71--79, Brighton, United Kingdom, September 1987."},{"key":"e_1_3_2_1_52_1","first-page":"16","volume-title":"Proceedings of the 22nd International Conference on Very Large Data Bases (VLDB), T. M. Vijayaraman, A. P. Buchmann, C. Mohan, and N. L. Sarda, eds.","author":"Sevcik K.","year":"1996","unstructured":"K. Sevcik and N. Koudas . Filter trees for managing spatial data over a range of size granularities . In Proceedings of the 22nd International Conference on Very Large Data Bases (VLDB), T. M. Vijayaraman, A. P. Buchmann, C. Mohan, and N. L. Sarda, eds. , pages 16 -- 27 , Mumbai (Bombay), India , September 1996 . K. Sevcik and N. Koudas. Filter trees for managing spatial data over a range of size granularities. In Proceedings of the 22nd International Conference on Very Large Data Bases (VLDB), T. M. Vijayaraman, A. P. Buchmann, C. Mohan, and N. L. Sarda, eds., pages 16--27, Mumbai (Bombay), India, September 1996."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/645473.653419"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.790844"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0146-664X(75)80003-7"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90074-R"},{"key":"e_1_3_2_1_57_1","first-page":"444","volume-title":"Game Programming Gems","author":"Ulrich T.","year":"2000","unstructured":"T. Ulrich . Loose octrees . In Game Programming Gems , M. A. DeLoura, ed., pages 444 -- 453 . Charles River Media , Rockland, MA , 2000 . T. Ulrich. Loose octrees. In Game Programming Gems, M. A. DeLoura, ed., pages 444--453. Charles River Media, Rockland, MA, 2000."},{"key":"e_1_3_2_1_58_1","first-page":"27","volume-title":"Proceedings of the 5th International Conference on Foundations of Data Organization and Algorithms (FODO)","author":"Wang W.","year":"1998","unstructured":"W. Wang , J. Yang , and R. Muntz . PK-tree: a spatial index structure for high dimensional point data . In Proceedings of the 5th International Conference on Foundations of Data Organization and Algorithms (FODO) , pages 27 -- 36 , Kobe, Japan , November 1998 . W. Wang, J. Yang, and R. Muntz. PK-tree: a spatial index structure for high dimensional point data. In Proceedings of the 5th International Conference on Foundations of Data Organization and Algorithms (FODO), pages 27--36, Kobe, Japan, November 1998."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.5555\/645481.655573"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01901265"}],"event":{"name":"SA '10: SIGGRAPH ASIA 2010","sponsor":["SIGGRAPH ACM Special Interest Group on Computer Graphics and Interactive Techniques","SIGCHI ACM Special Interest Group on Computer-Human Interaction"],"location":"Seoul Republic of Korea","acronym":"SA '10"},"container-title":["ACM SIGGRAPH ASIA 2010 Courses"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1900520.1900523","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1900520.1900523","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:52:53Z","timestamp":1750243973000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1900520.1900523"}},"subtitle":["multidimensional, spatial, and metric data structures for computer graphics applications"],"short-title":[],"issued":{"date-parts":[[2010,12,15]]},"references-count":56,"alternative-id":["10.1145\/1900520.1900523","10.1145\/1900520"],"URL":"https:\/\/doi.org\/10.1145\/1900520.1900523","relation":{},"subject":[],"published":{"date-parts":[[2010,12,15]]},"assertion":[{"value":"2010-12-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}