{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T06:31:29Z","timestamp":1790749889990,"version":"4.1.0"},"reference-count":43,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2003,1]]},"abstract":"<jats:p>In this paper we present the external interval tree, an optimal external memory data structure for answering stabbing queries on a set of dynamically maintained intervals. The external interval tree can be used in an optimal solution to the dynamic interval management problem, which is a central problem for object-oriented and temporal databases and for constraint logic programming. Part of the structure uses a weight-balancing technique for efficient worst-case manipulation of balanced trees, which is of independent interest. The external interval tree, as well as our new balancing technique, have recently been used to develop several efficient external data structures.<\/jats:p>","DOI":"10.1137\/s009753970240481x","type":"journal-article","created":{"date-parts":[[2003,10,11]],"date-time":"2003-10-11T19:55:33Z","timestamp":1065902133000},"page":"1488-1508","source":"Crossref","is-referenced-by-count":105,"title":["Optimal External Memory Interval Management"],"prefix":"10.1137","volume":"32","author":[{"given":"Lars","family":"Arge","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeffrey Scott","family":"Vitter","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,2,17]]},"reference":[{"key":"R1","unstructured":"Pankaj Agarwal, Lars Arge, Gerth Brodal, Jeffrey Vitter, I\/O\u2010efficient dynamic point location in monotone planar subdivisions (extended abstract), ACM, New York, 1999, 11\u2013201735598"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00035-1"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Pankaj Agarwal, Jeff Erickson, Geometric range searching and its relatives, Contemp. Math., Vol. 223, Amer. Math. Soc., Providence, RI, 1999, 1\u20135699m:68203","DOI":"10.1090\/conm\/223\/03131"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"L. Arge,\n                      External memory data structures (invited paper)\n                      , in Proceedingsof the 9th Annual European Symposium on Algorithms, Aarhus, Denmark, 2001, Lecture Notes in Comput. Sci. 2161, Springer\u2010Verlag, Berlin. 2001, pp. 1\u201329.","DOI":"10.1007\/3-540-44676-1_1"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Lars Arge, External memory data structures, Massive Comput., Vol. 4, Kluwer Acad. Publ., Dordrecht, 2002, 313\u20133571965531","DOI":"10.1007\/978-1-4615-0005-6_9"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1021-x"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"L. Arge, V. Samoladas, and J. S. Vitter,\n                      On two\u2010dimensional indexability and optimal range search indexing\n                      , in Proceedings of the 18th ACM Symposium on Principles of Database Systems, Philadelphia, PA, 1999, pp. 346\u2013357.","DOI":"10.1145\/303976.304010"},{"key":"R9","unstructured":"L. Arge and J. Vahrenhold,\n                      I\/O\u2010efficient dynamic planar point location\n                      , Internat. J. Comput. Geom. Appl., to appear."},{"key":"R10","unstructured":"L. Arge, D. E. Vengroff, and J. S. Vitter,\n                      External\u2010memory algorithms for processing line segments in geographic information systems\n                      , Algorithmica, to appear."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Lars Arge, Jeffrey Vitter, Optimal dynamic interval management in external memory (extended abstract), IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, 560\u20135691450654","DOI":"10.1109\/SFCS.1996.548515"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288683"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Michael Bender, Erik Demaine, Martin Farach\u2010Colton, Cache\u2010oblivious B\u2010trees, IEEE Comput. Soc. Press, Los Alamitos, CA, 2000, 399\u20134091931837","DOI":"10.1109\/SFCS.2000.892128"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"G. Blankenagel,\n                      Intervall\u2010Indexstructuren in Datenbanksystemen\n                      , Informatik\u2010Farberichte 312, Springer\u2010Verlag, Berlin, 1992.","DOI":"10.1007\/978-3-642-77590-1"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/BF01188717"},{"key":"R16","unstructured":"G. Blankenagel and R. H. G\u00fcting,\n                      XP\u2010Trees\u2014External Priority Search Trees\n                      , Technical report, FernUniversit\u00e4t Hagen, Informatik\u2010Bericht 92, Hagen, Germany, 1990."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90018-3"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"Y.\u2010J. Chiang and C. T. Silva,\n                      I\/O optimal isosurface extraction\n                      , in Proceedings of IEEE Visualization, Phoenix, AZ, 1997, pp. 293\u2013300.","DOI":"10.1109\/VISUAL.1997.663895"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"Yi\u2010Jen Chiang, Cl\u00e1udio Silva, External memory techniques for isosurface extraction in scientific visualization, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Vol. 50, Amer. Math. Soc., Providence, RI, 1999, 247\u20132771730714","DOI":"10.1090\/dimacs\/050\/14"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"Y.\u2010J. Chiang, C. T. Silva, and W. J. Schroeder,\n                      Interactive out\u2010of\u2010core isosurface extraction\n                      , in Proceedings of IEEE Visualization, Research Triangle Park, NC, 1998, pp. 167\u2013174.","DOI":"10.1109\/VISUAL.1998.745299"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"R22","first-page":"0","volume":"13","author":"Edelsbrunner Herbert","year":"1983","journal-title":"Internat. J. Comput. Math."},{"key":"R23","first-page":"0","volume":"13","author":"Edelsbrunner Herbert","year":"1983","journal-title":"Internat. J. Comput. Math."},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1145\/280277.280279"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"Roberto Grossi, Giuseppe Italiano, Efficient cross\u2010trees for external memory, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Vol. 50, Amer. Math. Soc., Providence, RI, 1999, 87\u20131062000h:68051","DOI":"10.1090\/dimacs\/050\/04"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1999.2811"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288968"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"Ch. Icking, R. Klein, Th. Ottmann, Priority search trees in secondary memory (extended abstract), Lecture Notes in Comput. Sci., Vol. 314, Springer, Berlin, 1988, 84\u2013931018394","DOI":"10.1007\/3-540-19422-3_7"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"P. C. Kanellakis, G. Kuper, and P. Revesz,\n                      Constraint query languages\n                      , in Proceedings of the 9th ACM Symposium on Principles of Database Systems, Nashville, TN, 1990, pp. 299\u2013313.","DOI":"10.1145\/298514.298582"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0043"},{"key":"R31","volume-title":"The art of computer programming. Volume 3","author":"Knuth Donald","year":"1973"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1137\/0214021"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-69900-9"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1137\/0202005"},{"key":"R35","doi-asserted-by":"crossref","unstructured":"J. Nievergelt and P. Widmayer,\n                      Spatial data structures: Concepts and design choices\n                      , in Algorithmic Foundations of GIS, Lecture Notes in Comput. Sci. 1340, M. van Kreveld, J. Nievergelt, T. Roos, and P. Widmayer, eds., Springer\u2010Verlag, Berlin, 1997, pp. 153\u2013197.","DOI":"10.1007\/3-540-63818-0_6"},{"key":"R36","volume-title":"The design of dynamic data structures","author":"Overmars Mark","year":"1983"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"Sridhar Ramaswamy, Efficient indexing for constraint and temporal databases, Lecture Notes in Comput. Sci., Vol. 1186, Springer, Berlin, 1997, 419\u20134311627197","DOI":"10.1007\/3-540-62222-5_61"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"S. Ramaswamy and P. Kanellakis,\n                      OODB Indexing by Class Division\n                      , A. P. I. C. Series, Academic Press, New York, 1995.","DOI":"10.1145\/568271.223809"},{"key":"R39","doi-asserted-by":"crossref","unstructured":"S. Ramaswamy and S. Subramanian,\n                      Path caching: A technique for optimal external searching\n                      , in Proceedings of the 13th ACM Symposium on Principles of Database Systems, Minneapolis, MN, 1994, pp. 25\u201335.","DOI":"10.1145\/182591.182595"},{"key":"R40","unstructured":"Sairam Subramanian, Sridhar Ramaswamy, The p\u2010range tree: a new data structure for range searching in secondary memory, ACM, New York, 1995, 378\u201338796f:68027"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1145\/384192.384193"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3839"},{"key":"R43","doi-asserted-by":"crossref","unstructured":"Dan Willard, Reduced memory space for multidimensional search trees, Lecture Notes in Comput. Sci., Vol. 182, Springer, Berlin, 1985, 363\u2013374786898","DOI":"10.1007\/BFb0024024"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S009753970240481X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:20:58Z","timestamp":1787336458000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S009753970240481X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,1]]},"references-count":43,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2003,1]]}},"alternative-id":["10.1137\/S009753970240481X"],"URL":"https:\/\/doi.org\/10.1137\/s009753970240481x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,1]]}}}