{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T01:30:35Z","timestamp":1791423035150,"version":"4.3.3"},"publisher-location":"New York, NY, USA","reference-count":57,"publisher":"ACM","license":[{"start":{"date-parts":[[2011,6,13]],"date-time":"2011-06-13T00:00:00Z","timestamp":1307923200000},"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":[[2011,6,13]]},"DOI":"10.1145\/1998196.1998198","type":"proceedings-article","created":{"date-parts":[[2011,6,14]],"date-time":"2011-06-14T10:45:32Z","timestamp":1308048332000},"page":"1-10","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":94,"title":["Orthogonal range searching on the RAM, revisited"],"prefix":"10.1145","author":[{"given":"Timothy M.","family":"Chan","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kasper Green","family":"Larsen","sequence":"additional","affiliation":[{"name":"Aarhus University, Aarhus, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mihai","family":"P\u0103tra\u015fcu","sequence":"additional","affiliation":[{"name":"AT&T Labs, New York, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,6,13]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_4"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.58"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810959.1811001"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1748030"},{"key":"e_1_3_2_1_5_1","volume-title":"J. E. Goodman and J. O'Rourke","author":"Agarwal P. K.","year":"2004","unstructured":"P. K. Agarwal . Range searching . In J. E. Goodman and J. O'Rourke , editors, CRC Handbook of Discrete and Computational Geometry. CRC Press , Inc., 2004 . P. K. Agarwal. Range searching. In J. E. Goodman and J. O'Rourke, editors, CRC Handbook of Discrete and Computational Geometry. CRC Press, Inc., 2004."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/223\/03131"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(84)80015-7"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796605"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.304010"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/358841.358850"},{"key":"e_1_3_2_1_11_1","first-page":"179","volume-title":"Proc. 1st ACM\/SIAM Symposium on Discrete Algorithms","author":"Bentley J. L.","year":"1990","unstructured":"J. L. Bentley , K. L. Clarkson , and D. B. Levine . Fast linear expected-time algorithms for computing maxima and convex hulls . In Proc. 1st ACM\/SIAM Symposium on Discrete Algorithms , pages 179 -- 187 , 1990 . J. L. Bentley, K. L. Clarkson, and D. B. Levine. Fast linear expected-time algorithms for computing maxima and convex hulls. In Proc. 1st ACM\/SIAM Symposium on Discrete Algorithms, pages 179--187, 1990."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1980.1675628"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133121"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/07068669X"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873616"},{"key":"e_1_3_2_1_16_1","volume-title":"II: offline search. ACM Transactions on Algorithms, submitted","author":"Chan T. M.","year":"2010","unstructured":"T. M. Chan and M. Patra\u015fcu . Transdichotomous results in computational geometry , II: offline search. ACM Transactions on Algorithms, submitted , 2010 . Preliminary version in STOC '07. T. M. Chan and M. Patra\u015fcu. Transdichotomous results in computational geometry, II: offline search. ACM Transactions on Algorithms, submitted, 2010. Preliminary version in STOC'07."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215051"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217026"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/77600.77614"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/79147.79149"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225291"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840440"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840441"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187879"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365723"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187740"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12200-2_16"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90040-4"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/322276.322281"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90040-4"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808675"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01189991"},{"key":"e_1_3_2_1_33_1","first-page":"517","volume-title":"Proc. 26th Symposium on Theoretical Aspects of Computer Science","author":"Grossi R.","year":"2009","unstructured":"R. Grossi , A. Orlandi , R. Raman , and S. S. Rao . More haste, less waste: Lowering the redundancy in fully indexable dictionaries . In Proc. 26th Symposium on Theoretical Aspects of Computer Science , pages 517 -- 528 , 2009 . R. Grossi, A. Orlandi, R. Raman, and S. S. Rao. More haste, less waste: Lowering the redundancy in fully indexable dictionaries. In Proc. 26th Symposium on Theoretical Aspects of Computer Science, pages 517--528, 2009."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195997000260"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652131"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/505241.505244"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30551-4_49"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02882-3_22"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/323233.323246"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321910"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00145-3"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90021-9"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.1"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00075-1"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214021"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247069.1247130"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2008.09.001"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90041-7"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.83"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.69"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132551"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"Preparata F. P.","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos . Computational Geometry: An Introduction . Springer-Verlag , New York, NY , 1985 . F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, New York, NY, 1985."},{"key":"e_1_3_2_1_53_1","first-page":"378","volume-title":"Proc. 6th ACM\/SIAM Symposium on Discrete Algorithms","author":"Subramanian S.","year":"1995","unstructured":"S. Subramanian and S. Ramaswamy . The P-range tree: a new data structure for range searching in secondary memory . In Proc. 6th ACM\/SIAM Symposium on Discrete Algorithms , pages 378 -- 387 , 1995 . S. Subramanian and S. Ramaswamy. The P-range tree: a new data structure for range searching in secondary memory. In Proc. 6th ACM\/SIAM Symposium on Discrete Algorithms, pages 378--387, 1995."},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/0146-664X(80)90034-9"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(77)90031-X"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237864"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90064-3"}],"event":{"name":"SoCG '11: Symposium on Computational Geometry","location":"Paris France","acronym":"SoCG '11","sponsor":["SIGGRAPH ACM Special Interest Group on Computer Graphics and Interactive Techniques","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the twenty-seventh annual symposium on Computational geometry"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1998196.1998198","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1998196.1998198","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:06:27Z","timestamp":1750230387000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1998196.1998198"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,13]]},"references-count":57,"alternative-id":["10.1145\/1998196.1998198","10.1145\/1998196"],"URL":"https:\/\/doi.org\/10.1145\/1998196.1998198","relation":{},"subject":[],"published":{"date-parts":[[2011,6,13]]},"assertion":[{"value":"2011-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}