{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T16:44:23Z","timestamp":1772815463977,"version":"3.50.1"},"reference-count":57,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[1994,12,1]],"date-time":"1994-12-01T00:00:00Z","timestamp":786240000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1994,12]]},"DOI":"10.1007\/bf01188717","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T10:55:44Z","timestamp":1108724144000},"page":"498-532","source":"Crossref","is-referenced-by-count":17,"title":["External segment trees"],"prefix":"10.1007","volume":"12","author":[{"given":"G.","family":"Blankenagel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R. H.","family":"G\ufffdting","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"Ahn, I., Towards an Implementation of Database Management Systems with Temporal Support.Proceedings of the International Conference on Data Engineering, Los Angeles, CA, 1986, pp. 374?381.","DOI":"10.1109\/ICDE.1986.7266242"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"832","DOI":"10.1145\/182.358434","volume":"26","author":"J. F. Allen","year":"1983","unstructured":"Allen, J. F., Maintaining Knowledge about Temporal Intervals.Comm. ACM 26 (1983), 832?843.","journal-title":"Comm. ACM"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"J. L. Bentley","year":"1975","unstructured":"Bentley, J. L., Multidimensional Binary Search Trees Used for Associative Searching.Comm. ACM 18 (1975), 509?517.","journal-title":"Comm. ACM"},{"key":"CR4","unstructured":"Bentley, J. L., Solutions to Klee's Rectangle Problems. Department of Computer Science, Carnegie Mellon University, Unpublished manuscript, 1977."},{"key":"CR5","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1109\/TSE.1979.234200","volume":"5","author":"J. L. Bentley","year":"1979","unstructured":"Bentley, J. L., Multidimensional Bineary Search Trees in Database Application.IEEE Trans. Software Engrg. 5 (1979), 333?340.","journal-title":"IEEE Trans. Software Engrg."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/0020-0190(79)90117-0","volume":"8","author":"J. L. Bentley","year":"1979","unstructured":"Bentley, J. L., Decomposable Searching Problems.Inform. Process. Lett. 8 (1979), 244?351.","journal-title":"Inform. Process. Lett."},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"Blankenagel, G., Intervall-Indexstukturen und externe Algorithmen f\u00fcr Nicht-Standard-Datenbanksysteme. Dissertation, FernUniversit\u00e4t Hagen, April 1991. Also available as:Intervall-Indexstrukturen in Datenbanksystemen, Informatik-Fachberichte, vol. 312, Springer-Verlag, Berlin, 1992.","DOI":"10.1007\/978-3-642-77590-1"},{"key":"CR8","unstructured":"Blankenagel, G., and R. H. G\u00fcting, XP-Trees: External Priority Search Trees. Informatik-Report 92, FernUniversit\u00e4t Hagen, 1990."},{"key":"CR9","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1007\/BF01934457","volume":"23","author":"W. Burkhard","year":"1983","unstructured":"Burkhard, W., Interpolation-Based Index Maintenance.BIT 23 (1983), 274?294.","journal-title":"BIT"},{"key":"CR10","unstructured":"Edelsbrunner, H., Dynamic Rectangle Intersection Searching. Report F47, Institut f\u00fcr Informationsverarbeitung, Technische Universit\u00e4t Graz, 1980."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0020-0190(81)90053-3","volume":"13","author":"H. Edelsbrunner","year":"1981","unstructured":"Edelsbrunner, H., and H. A. Maurer, On the Intersection of Orthogonal Objects.Inform. Process. Lett. 13 (1981), 177?181.","journal-title":"Inform. Process. Lett."},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"Faloutsos, C, T. Sellis, and N. Roussopoulos, Analysis of Object Oriented Spatial Access Methods.Proceedings of the ACM SIGMOD Conference, 1987, pp. 426?439.","DOI":"10.1145\/38713.38758"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF00288933","volume":"4","author":"R. A. Finkel","year":"1974","unstructured":"Finkel, R. A., and J. L. Bentley, Quad Trees: A Data Structure for Retrieval on Composite Keys.Acta Inform. 4 (1974), 1?9.","journal-title":"Acta Inform."},{"key":"CR14","unstructured":"Frank, A., Applications of DBMS to Land Information Systems.Proceedings of the 7th VLDB Conference, Cannes, 1981, pp. 448?453."},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"Frank, A. U., and R. Barrera, The Fieldtree: A Data Structure for Geographic Information Systems.Proceedings of the Symposium on the Design and Implementation of Large Spatial Databases, Santa Barbara, CA, 1989, pp. 29?44.","DOI":"10.1007\/3-540-52208-5_20"},{"key":"CR16","doi-asserted-by":"crossref","unstructured":"Freeston, M. W., A Well-Behaved File Structure for the Storage of Spatial Objects.Proceedings of the Symposium on the Design and Implementation of Large Spatial Databases, Santa Barbara, CA, 1989, pp. 287?300.","DOI":"10.1007\/3-540-52208-5_33"},{"key":"CR17","first-page":"322","volume-title":"Lecture Notes in Computer Science, vol. 367","author":"M. W. Freeston","year":"1989","unstructured":"Freeston, M. W., Advances in the Design of the BANG-File. In: W. Litwin, H.-J. Schek (eds.),Proceedings of the 3rd International Conference on Foundations of Data Organization and Algorithms, 1989, Lecture Notes in Computer Science, vol. 367. Springer-Verlag, Berlin, pp. 322?338."},{"key":"CR18","first-page":"246","volume-title":"Informatik-Fachberichte, vol. 204","author":"O. G\u00fcnther","year":"1989","unstructured":"G\u00fcnther, O., and J. Bilmes, The Implementation of the Cell Tree: Design Alternatives and Performance Evaluation.Proceedings of BTW '89 (Datenbanksysteme in B\u00fcro, Technik und Wissenschaft), Z\u00fcrich, March 1989, Informatik-Fachberichte, vol. 204, Springer-Verlag, Berlin, 1989, pp. 246?265."},{"key":"CR19","volume-title":"Lecture Notes in Computer Science, vol. 367","author":"O. G\u00fcnther","year":"1989","unstructured":"G\u00fcnther, O., and E. Wong, The Arc Tree: An Approximation Scheme to Represent Arbitrary Curved Shapes. In: W. Litwin, H.-J. Schek (eds.),Proceedings of the 3rd International Conference on Foundations of Data Organization and Algorithms, 1989, Lecture Notes in Computer Science, vol. 367, Springer-Verlag, Berlin."},{"key":"CR20","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/S0019-9958(84)80011-X","volume":"63","author":"R. H. G\u00fcting","year":"1984","unstructured":"G\u00fcting, R. H., Dynamic c-Oriented Polygonal Intersection Searching.Inform, and Control 63 (1984), 143?163.","journal-title":"Inform, and Control"},{"key":"CR21","doi-asserted-by":"crossref","unstructured":"G\u00fcting, R. H., Geo-Relational Algebra: A Model and Query Language for Geometric Database Systems. In: J. W. Schmidt, S. Ceri, and M. Missikoff (eds.),Proceedings of the International Conference on Extending Database Technology, Venice, March 1988, pp. 506?527.","DOI":"10.1007\/3-540-19074-0_70"},{"key":"CR22","unstructured":"G\u00fcting, R. H., Gral: An Extensible Relational Database System for Geometric Applications.Proceedings of the 15th International Conference on Very Large Data Bases, 1989, pp. 33?44."},{"key":"CR23","first-page":"375","volume-title":"Informatik-Fachberichte, vol. 33","author":"R. H. G\u00fcting","year":"1980","unstructured":"G\u00fcting, R. H., and H.-P. Kriegel,Multidimensional B-Tree: An Efficient Dynamic File Structure for Exact Match Queries. Informatik-Fachberichte, vol. 33, Springer-Verlag, Berlin, pp. 375?388. 1980."},{"key":"CR24","first-page":"135","volume-title":"Lecture Notes in Computer Science, vol. 104","author":"R. H. G\u00fcting","year":"1981","unstructured":"G\u00fcting, R. H., and H.-P. Kriegel,Dynamic k-Dimensional Multiway Search Under Time-Varying Access Frequencies. Lecture Notes in Computer Science, vol. 104, Springer-Verlag, Berlin, 1981, pp. 135?145."},{"key":"CR25","doi-asserted-by":"crossref","unstructured":"Guttman, A., R-Trees: A Dynamic Index Structure for Spatial Searching.Proceedings of the ACM SIGMOD Conference, Boston, 1984, pp. 47?57.","DOI":"10.1145\/602259.602266"},{"key":"CR26","first-page":"409","volume-title":"Proceedings of the 1975 National Computer Conference","author":"G. D. Held","year":"1975","unstructured":"Held, G. D., M. R. Stonebraker, and E. Wong, INGRES?A Relational Data Base System.Proceedings of the 1975 National Computer Conference, AFIPS Press, Reston, VA, 1975, pp. 409?416."},{"key":"CR27","unstructured":"Henrich, A., H.-W. Six, and P. Widmayer, The LSD Tree: Spatial Access to Multi-dimensional Point and Non Point Objects.Proceedings of the 15th International Conference on Very Large Data Bases, Amsterdam, 1989, pp. 45?53."},{"key":"CR28","volume-title":"Dissertation No. 7743","author":"K. H. Hinrichs","year":"1985","unstructured":"Hinrichs, K. H., The Grid File System: Implementation and Case Studies of Applications. Dissertation No. 7743, ETH, Zurich, 1985."},{"key":"CR29","first-page":"100","volume-title":"Proceedings of the WG","author":"K. H. Hinrichs","year":"1983","unstructured":"Hinrichs, K. H., and J. Nievergelt, The Grid File: A Data Structure Designed To Support Proximity Queries on Spatial Objects. In: M. Nagl and J. Perl (eds.),Proceedings of the WG, Trauner, Linz, 1983, pp. 100?113."},{"key":"CR30","doi-asserted-by":"crossref","unstructured":"Hutflesz, A., H.-W. Six, and P. Widmayer, Globally Order Preserving Multidimensional Linear Hashing.Proceedings of the 4th International Conference on Data Engineering, Los Angeles, CA, 1988, pp. 572?579.","DOI":"10.1109\/ICDE.1988.105505"},{"key":"CR31","doi-asserted-by":"crossref","unstructured":"Hutflesz, A., H.-W. Six, and P. Widmayer, The Twin Grid File: A Nearly Space Optimal Index Structure. In: J. W. Schmidt, S. Ceri, and M. Missikoff (eds.),Proceedings of the International Conference on Extending Database Technology, Venice, March 1988, pp. 352?363.","DOI":"10.1007\/3-540-19074-0_62"},{"key":"CR32","doi-asserted-by":"crossref","unstructured":"Hutflesz, A, H.-W. Six, and P. Widmayer, The Twin Grid File: Space Optimizing Access Schemes.Proceedings of the ACM SIGMOD Conference, 1988, pp. 183?190.","DOI":"10.1145\/50202.50222"},{"key":"CR33","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/BF03037383","volume":"4","author":"R. Kowalski","year":"1986","unstructured":"Kowalski, R., and M. Sergot, A Logic-Based Calculus of Events.New Generation Comput.4 (1986), 67?95.","journal-title":"New Generation Comput"},{"key":"CR34","first-page":"110","volume-title":"Proceedings of the 8th Conference on Graphtheoretic Concepts in Computer Science","author":"H.-P. Kriegel","year":"1982","unstructured":"Kriegel, H.-P., Variants of Multidimensional B-Trees as Dynamic Index Structure for Associative Retrieval in Database Systems.Proceedings of the 8th Conference on Graphtheoretic Concepts in Computer Science, Hanser, M\u00fcnchen, 1982, pp. 110?128."},{"key":"CR35","unstructured":"Kriegel, H.-P., and B. Seeger, Techniques for Design and Implementation of Efficient Spatial Access Methods.Proceedings of the 14th International Conference on Very Large Data Bases, Los Angeles, CA, 1988, pp. 360?371."},{"key":"CR36","doi-asserted-by":"crossref","unstructured":"Kriegel, H.-P., and B. Seeger, PLOP-Hashing: A Grid File Without Directory.Proceedings of the 4th International Conference on Data Engineering, Los Angeles, CA, 1988, pp. 369?376.","DOI":"10.1109\/ICDE.1988.105439"},{"key":"CR37","doi-asserted-by":"crossref","unstructured":"Kriegel, H.-P., Schiwietz, R. Schneider, and B. Seeger, Performance Comparison of Point and Spatial Access Methods.Proceedings of the Symposium on the Design and Implementation of Large Spatial Databases, Santa Barbara, CA, 1989, pp. 89?114.","DOI":"10.1007\/3-540-52208-5_23"},{"key":"CR38","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., L. V. Hao, and M. Nagao, A File Organization for Geographic Information Systems Based on Spatial Proximity.Comput. Vision Graphics Image Process. 26 (1984), 303?318.","journal-title":"Comput. Vision Graphics Image Process."},{"key":"CR39","volume-title":"Report CSL-81-5","author":"E. M. McCreight","year":"1982","unstructured":"McCreight, E. M., Priority Search Trees. Report CSL-81-5, XEROX Research Center, Palo Atto, CA, 1982."},{"key":"CR40","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1137\/0214021","volume":"14","author":"E. M. McCreight","year":"1985","unstructured":"McCreight, E. M., Priority Search Trees.SIAM J. Comput. 14 (1985), 257?276.","journal-title":"SIAM J. Comput."},{"key":"CR41","first-page":"40","volume":"15","author":"E. McKenzie","year":"1986","unstructured":"McKenzie, E., Bibliography: Temporal Databases.SIGMOD Record 15 (1986), 40?52.","journal-title":"SIGMOD Record"},{"key":"CR42","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1145\/348.318586","volume":"9","author":"J. Nievergelt","year":"1984","unstructured":"Nievergelt, J., H. Hinterberger, and K. C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure.ACM Trans Database Systems 9 (1984), 38?71.","journal-title":"ACM Trans Database Systems"},{"key":"CR43","first-page":"247","volume-title":"Informatik-Fachberichte, vol. 136","author":"B. C. Ooi","year":"1987","unstructured":"Ooi, B. C.,Spatial kd-Tree: A Data Structure for Geographic Database. Informatik-Fachberichte, vol. 136, Springer-Verlag, Berlin 1987, pp. 247?258."},{"key":"CR44","doi-asserted-by":"crossref","unstructured":"Otoo, E. J., Balanced Multidimensional Extendible Hash Tree.Proceedings of the 5th ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, Cambridge, MA, 1986, pp. 100?113.","DOI":"10.1145\/6012.6015"},{"key":"CR45","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1007\/BF01932838","volume":"21","author":"M. Ouksel","year":"1981","unstructured":"Ouksel, M., and P. Scheuermann, Multidimensional B-Trees: Analysis of Dynamic Behavior,BIT 21 (1981), 401?418.","journal-title":"BIT"},{"key":"CR46","doi-asserted-by":"crossref","unstructured":"Overmars, M. H., and M. H. M. Smid, Maintaining Range Trees in Secondary Memory.Proceedings of the 5th STACS, Bordeaux, 1988, pp. 38?51.","DOI":"10.1007\/BFb0035830"},{"key":"CR47","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1109\/TCAD.1985.1270098","volume":"4","author":"J. B. Rosenberg","year":"1985","unstructured":"Rosenberg, J. B., Geographical Data Structures Compared: A Study of Data Structures Supporting Region Queries.IEEE Trans. Comput. Aided Design 4 (1985), 53?67.","journal-title":"IEEE Trans. Comput. Aided Design"},{"key":"CR48","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1145\/50020.50021","volume":"20","author":"H. Samet","year":"1988","unstructured":"Samet, H., Hierarchical Representations of Collections of Small Rectangles.ACM Comput. Surv. 20 (1988), 271?309.","journal-title":"ACM Comput. Surv."},{"key":"CR49","unstructured":"Sellis, T., Roussopoulos, N., and C. Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects.Proceedings of the 13th International Conference on Very Large Data Bases, Brighton, 1987, pp. 507?518."},{"key":"CR50","series-title":"Informatik-Fachberichte, vol. 126","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1007\/978-3-642-71388-0_42","volume-title":"Proc. GI-Jahrestagung","author":"H.-W. Six","year":"1986","unstructured":"Six, H.-W., and P. Widmayer, Hintergrundspeicherstrukturen f\u00fcr ausgedehnte Objekte.Proc. GI-Jahrestagung, Informatik-Fachberichte, vol. 126, Springer-Verlag, Berlin, 1986, pp. 538?552."},{"key":"CR51","doi-asserted-by":"crossref","unstructured":"Six, H.-W., and P. Widmayer, Spatial Searching in Geometric Databases.Proceedings of the 4th International Conference on Data Engineering, Los Angeles, CA, 1988, pp. 496?503.","DOI":"10.1109\/ICDE.1988.105496"},{"key":"CR52","unstructured":"Smid, M., Dynamic Data Structures on Multiple Storage Media. Dissertation, Universiteit van Amsterdam, 1989."},{"key":"CR53","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1145\/22952.22956","volume":"12","author":"R. Snodgrass","year":"1987","unstructured":"Snodgrass, R., The Temporal Query Language TQuel.ACM Trans. Database Systems 12 (1987), 247?298.","journal-title":"ACM Trans. Database Systems"},{"key":"CR54","doi-asserted-by":"crossref","unstructured":"Snodgrass, R., and I. Ahn, A Taxomy of Time in Databases.Proceedings of ACM-SIGMOD, Austin, 1985, pp. 236?246.","DOI":"10.1145\/971699.318921"},{"key":"CR55","unstructured":"Tamminen, M., Some Aspects of Defining Spatially Referenced Data.Proceedings of FIG XVI Congress, Montreux, 1981."},{"key":"CR56","doi-asserted-by":"crossref","unstructured":"Tamminen, M., Efficient Spatial Access to a Database.Proceedings of the A CM SIGMOD Conference, Orlando, 1982, pp. 200?206.","DOI":"10.1145\/582353.582389"},{"key":"CR57","doi-asserted-by":"crossref","unstructured":"Tamminen, M., and R. Sulonen, The EXCELL Method for Efficient Geometric Access to Data.Proceedings of the 19th ACM IEEE Design Automation Conference, Las Vegas, CA, 1982, pp. 345?351.","DOI":"10.1109\/DAC.1982.1585522"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01188717.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01188717\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01188717","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,5]],"date-time":"2020-04-05T20:51:08Z","timestamp":1586119868000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01188717"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,12]]},"references-count":57,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1994,12]]}},"alternative-id":["BF01188717"],"URL":"https:\/\/doi.org\/10.1007\/bf01188717","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,12]]}}}