Adaptive multi-stage distance join processing

Abstract

A spatial distance join is a relatively new type of operation introduced for spatial and multimedia database applications. Additional requirements for ranking and stopping cardinality are often combined with the spatial distance join in on-line query processing or internet search environments. These requirements pose new challenges as well as opportunities for more efficient processing of spatial distance join queries. In this paper, we first present an efficient k-distance join algorithm that uses spatial indexes such as R-trees. Bi-directional node expansion and plane-sweeping techniques are used for fast pruning of distant pairs, and the plane-sweeping is further optimized by novel strategies for selecting a sweeping axis and direction. Furthermore, we propose adaptive multi-stage algorithms for k-distance join and incremental distance join operations. Our performance study shows that the proposed adaptive multi-stage algorithms outperform previous work by up to an order of magnitude for both k-distance join and incremental distance join queries, under various operational conditions.

References

1. 1 L. Arge, O. Procopiuc, S. Ramaswamy, T. Suel, and J. S. Vitter. Scalable sweeping-based spatial join. In Proceedings of the 24th VLDB Conference, pages 259-270, New York, USA, June 1998.
2. 2 S. Arya, D. M. Mount, and O. Narayan. Accounting for boundary effects in nearest neighbor searching. In Proc. 11th Annual Symp. on Computational Geometry, pages 336-344, Vancouver, Canada, 1995.
3. 3 Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger. The R -tree: An efficient and robust access method for points and rectangles. In Proceedings of the 1990 ACM-SIGMOD Conference, pages 322-331, Atlantic City, NJ, May 1990.
4. 4 S. Berchtold, B. Ertl, D. Keim, H.-P. Kriegel, and T. Seidl. Fast nearest neighbor search in high-dimensional spaces. In Proceedings of the 14th Intl. Conf. on Data Engineering, Orlando, Florida, September 1998.
5. 5 S. Berchtold, D. A. Keim, and H.-P. Kriegel. The X-tree: An index structure for high-dimensional data. In Proceedings of the 22nd VLDB Conference, Bombay, India, September 1996.
6. 6 Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger. Multi-step processing of spatial joins. In Proceedings of the 1994 ACM-SIGMOD Conference, pages 197-208, Minneapolis, Minnesota, May 1994.
7. 7 Thomas Brinkhoff, Hans-Peter Kriegel, and Bernhard Seeger. Efficient processing of spatial joins using R-Trees. In Proceedings of the 1993 ACM-SIGMOD Conference, pages 237-246, Washington, DC, May 1993.
8. 8 Michael J. Carey and Donald Kossmann. On saying "enough already" in SQL. In Proceedings of the 1997 ACM- SIGMOD Conference, pages 219-230, Tucson, AZ, May 1997.
9. 9 Michael J. Carey and Donald Kossmann. Reducing the braking distance of an SQL query engine. In Proceedings of the 24th VLDB Conference, pages 158-169, New York, NY, August 1998.
10. 10 Donko Donjerkovic and Raghu Ramakrishnan. Probabilistic optimization of top N queries. In Proceedings of the 25th VLDB Conference, Edinburgh, Scotland, September 1999.
11. 11 Antonin Guttman. R-Trees: A dynamic index structure for spatial searching. In Proceedings of the 1984 ACM-SIGMOD Conference, pages 47-57, Boston, MA, June 1984.
12. 12 G. R. Hjaltason and H. Samet. Ranking in spatial databases. In Proc. of 4th Intl. Symposium on Large Spatial Databases(SSD'95), pages 83-95, September 1995.
13. 13 Gisli R. Hjaltason and Hanan Samet. Incremental distance join algorithms for spatial databases. In Proceedings of the 1998 ACM-SIGMOD Conference, pages 237-248, Seattle, WA, June 1998.
14. 14 F. Korn, N. Sidiropoulos, C. Faloutsos, E. Siegel, and Z. Protopapas. Fast nearest neighbor search in medical image databases. In Proceedings of the 22nd VLDB Conference, pages 215-226, June 1996.
15. 15 Ming-Ling Lo and Chinya V.Ravishankar. Spatial joins using seeded trees. In Proceedings of the 1994 ACM-SIGMOD Conference, pages 209-220, Minneapolis, Minnesota, May 1994.
16. 16 Ming-Ling Lo and Chinya V. Ravishankar. Spatial hashjoin. In Proceedings of the 1996 ACM-SIGMOD Conference, pages 247-258, Montreal, Canada, June 1996.
17. 17 Bureau of the Census. Tiger/Line Precensus Files: 1997 technical documentation. Washington, DC, 1997.
18. 18 Jack A.Orenstein. A comparison of spatial query processing techniques for native and parameter spaces. In Proceedings of the 1990 ACM-SIGMOD Conference, pages 343-352, Atlantic City, New Jersey, May 1990.
19. 19 Jignesh M. Patel and David J. DeWitt. Partition based spatial-merge join. In Proceedings of the 1996 ACM- SIGMOD Conference, pages 259-270, Montreal, Canada, June 1996.
20. 20 Franco P. Preparata and Michael Ian Shamos. Computational Geometry: An Introdution. Springer-Verlag, New York, NY, 1985.
21. 21 Nick Roussopoulos, Stephen Kelley, and Frederic Vincent. Nearest neighbor queries. In Proceedings of the 1995 ACM- SIGMOD Conference, pages 71-79, San Jose, CA, May 1995.
22. 22 Thomas Seidl and Hans-Peter Kriegel. Optimal multi-step k-nearest neighbor search. In Proceedings of the 1998 ACM- SIGMOD Conference, pages 154-165, Seattle, Washington, June 1998.

Index Terms

• Information systems

  • Data management systems

    • Query languages

  • Information systems applications

• Theory of computation

  • Theory and algorithms for application domains

    • Database theory

      • Database query languages (principles)