{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,3]],"date-time":"2024-08-03T09:18:19Z","timestamp":1722676699918},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGSPATIAL Special"],"published-print":{"date-parts":[[2012,7]]},"abstract":"Range reporting is a one of the most fundamental topics in spatial databases and computational geometry. In this class of problems, the input consists of a set of geometric objects, such as points, line segments, rectangles etc. The goal is to preprocess the input set into a data structure, such that given a query range, one can efficiently report all input objects intersecting the range. The ranges most commonly considered are axis-parallel rectangles, halfspaces, points, simplices and balls.<\/jats:p>","DOI":"10.1145\/2367574.2367575","type":"journal-article","created":{"date-parts":[[2012,9,11]],"date-time":"2012-09-11T22:21:06Z","timestamp":1347402066000},"page":"2-7","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["I\/O-efficient spatial data structures for range queries"],"prefix":"10.1145","volume":"4","author":[{"given":"Lars","family":"Arge","sequence":"first","affiliation":[{"name":"Aarhus University, Denmark"}]},{"given":"Kasper Green","family":"Larsen","sequence":"additional","affiliation":[{"name":"Aarhus University, Denmark"}]}],"member":"320","published-online":{"date-parts":[[2012,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.58"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_3_1","volume-title":"External memory geometric data structures","author":"Arge L.","year":"2005","unstructured":"L. Arge . External memory geometric data structures , 2005 . \"Lecture notes available at http:\/\/www.cs.au.dk\/~large\/ioS06\/ionotes.pdf\". L. Arge. External memory geometric data structures, 2005. \"Lecture notes available at http:\/\/www.cs.au.dk\/~large\/ioS06\/ionotes.pdf\"."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328911.1328920"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.304010"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30140-0_6"},{"key":"e_1_2_1_7_1","volume-title":"Algorithms and theory of computation handbook: general concepts and techniques","author":"Atallah M. J.","year":"2010","unstructured":"M. J. Atallah and M. Blanton , editors . Algorithms and theory of computation handbook: general concepts and techniques . Chapman & Hall\/CRC , 2 edition, 2010 . M. J. Atallah and M. Blanton, editors. Algorithms and theory of computation handbook: general concepts and techniques. Chapman & Hall\/CRC, 2 edition, 2010."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/358841.358850"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"de Berg M.","year":"2008","unstructured":"M. de Berg and O. Cheong and M. van Kreveld and M. Overmars . Computational Geometry: Algorithms and Applications . Springer-Verlag , 3 rd edition, 2008 . Chapter 10. M. de Berg and O. Cheong and M. van Kreveld and M. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, 3rd edition, 2008. Chapter 10.","edition":"3"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/280277.280279"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/505241.505244"},{"key":"e_1_2_1_13_1","first-page":"257","volume-title":"Proc. International Conference on Database Theory","author":"Kanth K. V. R.","year":"1997","unstructured":"K. V. R. Kanth and A. K. Singh . Optimal dynamic range searching in non-replicating index structures . In Proc. International Conference on Database Theory , pages 257 -- 276 , 1997 . K. V. R. Kanth and A. K. Singh. Optimal dynamic range searching in non-replicating index structures. In Proc. International Conference on Database Theory, pages 257--276, 1997."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000014"}],"container-title":["SIGSPATIAL Special"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2367574.2367575","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,30]],"date-time":"2022-12-30T06:54:10Z","timestamp":1672383250000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2367574.2367575"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.1145\/2367574.2367575"],"URL":"https:\/\/doi.org\/10.1145\/2367574.2367575","relation":{},"ISSN":["1946-7729"],"issn-type":[{"value":"1946-7729","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,7]]},"assertion":[{"value":"2012-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}