{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T04:28:29Z","timestamp":1778300909911,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540672272","type":"print"},{"value":"9783540464396","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-46439-5_29","type":"book-chapter","created":{"date-parts":[[2007,8,1]],"date-time":"2007-08-01T02:09:46Z","timestamp":1185934186000},"page":"413-429","source":"Crossref","is-referenced-by-count":14,"title":["A Unified Approach for Indexed and Non-indexed Spatial Joins"],"prefix":"10.1007","author":[{"given":"Lars","family":"Arge","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Octavian","family":"Procopiuc","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sridhar","family":"Ramaswamy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Torsten","family":"Suel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Vahrenhold","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey Scott","family":"Vitter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2000,3,24]]},"reference":[{"key":"29_CR1","doi-asserted-by":"crossref","unstructured":"S. Acharya, V. Poosala, and S. Ramaswamy. Selectivity estimation in spatial databases. In Proc. SIGMOD Intl. Conf. on Management of Data, pages 13\u201324, 1999.","DOI":"10.1145\/304181.304184"},{"key":"29_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1007\/3-540-60220-8_74","volume-title":"Proc. Workshop on Algorithms and Data Structures","author":"L. Arge","year":"1995","unstructured":"L. Arge. The buffer tree: A new technique for optimal I\/O-algorithms. In Proc. Workshop on Algorithms and Data Structures, LNCS 955, pages 334\u2013345, 1995. A complete version appears as BRICS technical report RS-96-28, University of Aarhus."},{"key":"29_CR3","unstructured":"L. Arge, R. Barve, O. Procopiuc, L. Toma, D. E. Vengroff, and R. Wickeremesinghe. TPIE User Manual and Reference (edition 0.9.01a). Duke University, 1999. The manual and software distribution are available on the web at http:\/\/www.cs.duke.edu\/TPIE\/ ."},{"key":"29_CR4","unstructured":"L. Arge, O. Procopiuc, S. Ramaswamy, T. Suel, and J. S. Vitter. Scalable sweeping-based spatial join. In Proc. Intl. Conf. on Very Large Databases, pages 570\u2013581, 1998."},{"key":"29_CR5","unstructured":"L. Arge, O. Procopiuc, S. Ramaswamy, T. Suel, and J. S. Vitter. Theory and practice of I\/O-efficient algorithms for multidimensional batched searching problems. In ACM-SIAM Symp. on Discrete Algorithms, pages 685\u2013694, 1998."},{"key":"29_CR6","doi-asserted-by":"crossref","unstructured":"L. Becker, K. Hinrichs, and U. Finke. A new algorithm for computing joins with grid files. In Proc. IEEE Intl. Conf. on Data Engineering, pages 190\u2013197, 1993.","DOI":"10.1109\/ICDE.1993.344063"},{"issue":"2","key":"29_CR7","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1145\/93605.98741","volume":"19","author":"Norbert Beckmann","year":"1990","unstructured":"N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R*-tree: An efficient and robust access method for points and rectangles. In Proc. SIGMOD Intl. Conf. on Management of Data, pages 322\u2013331, 1990.","journal-title":"ACM SIGMOD Record"},{"issue":"2","key":"29_CR8","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1145\/170036.170075","volume":"22","author":"Thomas Brinkhoff","year":"1993","unstructured":"T. Brinkhoff, H.-P. Kriegel, and B. Seeger. Efficient processing of spatial joins using R-trees. In Proc. SIGMOD Intl. Conf. on Management of Data, pages 237\u2013246, 1993.","journal-title":"ACM SIGMOD Record"},{"key":"29_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/BFb0054359","volume-title":"Proc. Scandinavian Workshop on Algorithms Theory","author":"G. S. Brodal","year":"1998","unstructured":"G. S. Brodal and J. Katajainen. Worst-case efficient external-memory priority queues. In Proc. Scandinavian Workshop on Algorithms Theory, LNCS 1432, pages 107\u2013118, 1998."},{"key":"29_CR10","unstructured":"D. J. DeWitt, N. Kabra, J. M. Patel, and J.-B. Yu. Client-server Paradise. In Proc. Intl. Conf. on Very Large Databases, pages 558\u2013569, 1994."},{"key":"29_CR11","doi-asserted-by":"crossref","unstructured":"M. Goodrich, J.-J. Tsay, D. E. Vengroff, and J. S. Vitter. External-memory computational geometry. In Proc. IEEE Symp. on Foundations of Computer Science, pages 714\u2013723, 1993.","DOI":"10.1109\/SFCS.1993.366816"},{"key":"29_CR12","doi-asserted-by":"crossref","unstructured":"O. G\u00fcnther. Efficient computation of spatial joins. In Proc. IEEE Intl. Conf. on Data Engineering, pages 50\u201359, 1993.","DOI":"10.1109\/ICDE.1993.344078"},{"key":"29_CR13","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0020-0255(87)90018-1","volume":"42","author":"R. H. G\u00fcting","year":"1987","unstructured":"R. H. G\u00fcting and W. Schilling. A practical divide-and conquer algorithm for the rectangle intersection problem. Information Sciences, 42: 95\u2013112, 1987.","journal-title":"Information Sciences"},{"key":"29_CR14","doi-asserted-by":"crossref","unstructured":"A. Guttman. R-trees: A dynamic index structure for spatial searching. In Proc. SIGMOD Intl. Conf. on Management of Data, pages 47\u201357, 1984.","DOI":"10.1145\/971697.602266"},{"issue":"2","key":"29_CR15","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1145\/141484.130316","volume":"21","author":"Erik G. Hoel","year":"1992","unstructured":"E. G. Hoel and H. Samet. A qualitative comparison study of data structures for large linear segment databases. In Proc. SIGMOD Intl. Conf. on Management of Data, pages 205\u2013214, 1992.","journal-title":"ACM SIGMOD Record"},{"key":"29_CR16","unstructured":"Y.-W. Huang, N. Jing, and E. Rundensteiner. Spatial joins using R-trees: Breadth-first traversal with global optimizations. In Proc. Intl. Conf. on Very Large Databases, pages 396\u2013405, 1997."},{"key":"29_CR17","doi-asserted-by":"crossref","unstructured":"I. Kamel and C. Faloutsos. On packing R-trees. In Proc. Intl. Conf. on Information and Knowledge Management, pages 47\u201357, 1993.","DOI":"10.1145\/170088.170403"},{"key":"29_CR18","doi-asserted-by":"crossref","unstructured":"K. Kim and S. K. Cha. Sibling clustering of tree-based spatial indexes for efficient spatial query processing. In Proc. ACM Intl. Conf. Information and Knowledge Management, pages 398\u2013405, 1998.","DOI":"10.1145\/288627.288686"},{"key":"29_CR19","doi-asserted-by":"crossref","unstructured":"M. Kitsuregawa, L. Harada, and M. Takagi. Join strategies on KD-tree indexed relations. In Proc. IEEE Intl. Conf. on Data Engineering, pages 85\u201393, 1989.","DOI":"10.1109\/ICDE.1989.47203"},{"issue":"2","key":"29_CR20","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1145\/253262.253340","volume":"26","author":"Nick Koudas","year":"1997","unstructured":"N. Koudas and K. C. Sevcik. Size separation spatial join. In Proc. SIGMOD Intl. Conf. on Management of Data, pages 324\u2013335, 1996.","journal-title":"ACM SIGMOD Record"},{"issue":"2","key":"29_CR21","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1145\/191843.191881","volume":"23","author":"Ming-Ling Lo","year":"1994","unstructured":"M.-L. Lo and C. V. Ravishankar. Spatial joins using seeded trees. In Proc. SIG-MOD Intl. Conf. on Management of Data, pages 209\u2013220, 1994.","journal-title":"ACM SIGMOD Record"},{"key":"29_CR22","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1007\/3-540-60159-7_20","volume-title":"Proc. Intl. Symp. on Spatial Databases","author":"M.-L. Lo","year":"1995","unstructured":"M.-L. Lo and C. V. Ravishankar. Generating seeded trees from data sets. In Proc. Intl. Symp. on Spatial Databases, LNCS 951, pages 328\u2013347, 1995."},{"issue":"2","key":"29_CR23","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1145\/235968.233337","volume":"25","author":"Ming-Ling Lo","year":"1996","unstructured":"M.-L. Lo and C. V. Ravishankar. Spatial hash-joins. In Proc. SIGMOD Intl. Conf. on Management of Data, pages 247\u2013258, 1996.","journal-title":"ACM SIGMOD Record"},{"key":"29_CR24","doi-asserted-by":"crossref","unstructured":"N. Mamoulis and D. Papadias. Integration of spatial join algorithms for joining multiple inputs. In Proc. SIGMOD Intl. Conf. on Management of Data, pages 1\u201312, 1999.","DOI":"10.1145\/304181.304183"},{"key":"29_CR25","doi-asserted-by":"crossref","unstructured":"N. Mamoulis, D. Papadias, and Y. Theodoridis. Processing and optimization of multiway spatial joins using R-trees. In Proc. Symp. on Principles of Database Systems, pages 44\u201355, 1999.","DOI":"10.1145\/303976.303981"},{"key":"29_CR26","unstructured":"D. R. Musser and A. Saini. STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library. Addison-Wesley, 1996."},{"issue":"1","key":"29_CR27","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1145\/348.318586","volume":"9","author":"J. Nievergelt","year":"1984","unstructured":"J. Nievergelt, H. Hinterberger, and K. C. Sevcik. The grid file: An adaptable, symmetric multikey file structure. ACM Trans. on Database Systems, 9(1):38\u201371, March 1984.","journal-title":"ACM Trans. on Database Systems"},{"key":"29_CR28","doi-asserted-by":"crossref","unstructured":"J. A. Orenstein. A comparison of spatial query processing techniques for native and parameter spaces. In Proc. SIGMOD Intl. Conf. on Management of Data, pages 343\u2013352, 1990.","DOI":"10.1145\/93605.98743"},{"issue":"5","key":"29_CR29","doi-asserted-by":"publisher","first-page":"611","DOI":"10.1109\/32.6139","volume":"14","author":"J. A. Orenstein","year":"1988","unstructured":"J. A. Orenstein and F. A. Manola. PROBE spatial data modeling and query processing in an image database application. IEEE Trans. on Software Engineering, 14(5):611\u2013629, May 1988.","journal-title":"IEEE Trans. on Software Engineering"},{"issue":"2","key":"29_CR30","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1145\/235968.233338","volume":"25","author":"Jignesh M. Patel","year":"1996","unstructured":"J. M. Patel and D. J. DeWitt. Partition based spatial-merge join. In Proc. SIG-MOD Intl. Conf. on Management of Data, pages 259\u2013270, 1996.","journal-title":"ACM SIGMOD Record"},{"key":"29_CR31","volume-title":"Computational Geometry: An Introduction","author":"F. P. Preparata","year":"1988","unstructured":"F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer, Berlin, 2nd edition, 1988.","edition":"2nd edition"},{"key":"29_CR32","doi-asserted-by":"crossref","unstructured":"D. Rotem. Spatial join indices. In Proc. IEEE Intl. Conf. on Data Engineering, pages 500\u2013509, 1991.","DOI":"10.1109\/ICDE.1991.131499"},{"key":"29_CR33","doi-asserted-by":"crossref","unstructured":"H. Samet. The Design and Analysis of Spatial Data Structures. Addison-Wesley, 1990.","DOI":"10.1007\/3-540-52208-5_28"},{"key":"29_CR34","unstructured":"T. Sellis, N. Roussopoulos, and C. Faloutsos. The R+-tree: A dynamic index for multi-dimensional objects. In Proc. Intl. Conf. on Very Large Databases, pages 507\u2013518, 1987."},{"key":"29_CR35","unstructured":"TIGER\/Line\u2122Files, 1997 Technical Documentation. Washington, DC, September 1998. http:\/\/www.census.gov\/geo\/tiger\/TIGER97D.pdf ."},{"key":"29_CR36","unstructured":"U. Vahalia. UNIX Internals: The New Frontiers. Prentice Hall, 1996."},{"issue":"2","key":"29_CR37","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1145\/22952.22955","volume":"12","author":"P. Valduriez","year":"1987","unstructured":"P. Valduriez. Join indices. ACM Trans. on Database Systems, 12(2):218\u2013246, June 1987.","journal-title":"ACM Trans. on Database Systems"}],"container-title":["Lecture Notes in Computer Science","Advances in Database Technology \u2014 EDBT 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46439-5_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T01:37:03Z","timestamp":1737337023000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46439-5_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540672272","9783540464396"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/3-540-46439-5_29","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2000]]}}}