Distance join queries on spatial networks

ABSTRACT

The result of a distance join operation on two sets of objects R, S on a spatial network G is a set P of object pairs pq, p É R, q É S such that the distance of an object pair pq is the shortest distance from p to q in G. Several variations to the distance join operation such as UnOrdered, Incremental, topk, Semi-Join impose additional constraints on the distance between the object pairs in P, the ordering of object pairs in P, and on the cardinality of P. A distance join algorithm on spatial networks is proposed that works in conjunction with the SILC framework, which is a new approach to query processing on spatial networks. Experimental results demonstrate up to an order of magnitude speed up when compared with a prominent existing technique.

REFERENCES

• 1: Sergei N. Bespamyatnikh, An optimal algorithm for closest pair maintenance (extended abstract), Proceedings of the eleventh annual symposium on Computational geometry, p.152-161, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220296]
• 2: Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Efficient processing of spatial joins using R-trees, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.237-246, May 25-28, 1993, Washington, D.C., United States
• 3: Michael J. Carey , Donald Kossmann, On saying “Enough already!” in SQL, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.219-230, May 11-15, 1997, Tucson, Arizona, United States
• 4: Hyung-Ju Cho , Chin-Wan Chung, An efficient and scalable approach to CNN queries in a road network, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 5: K. L. Clarkson. Fast algorithm for the all nearest neighbors problem. In FOCS '83: Proceedings of the 24th IEEE Annual Symposium on Foundations of Computer Science, pages 226--232, Tucson, AZ, Nov. 1983.
• 6: Irene Gargantini, An effective way to represent quadtrees, Communications of the ACM, v.25 n.12, p.905-910, Dec 1982 [doi>10.1145/358728.358741]
• 7: A. V. Goldberg and R. F. Werneck. Computing point-to-point shortest paths from external memory. In ALENEX '05: Proceedings of the 7th Workshop on Algorithm Engineering and Experiments, Vancouver, Canada, Jan. 2005.
• 8: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 9: Gisli R. Hjaltason , Hanan Samet, Ranking in Spatial Databases, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.83-95, August 06-09, 1995
• 10: Gísli R. Hjaltason , Hanan Samet, Incremental distance join algorithms for spatial databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.237-248, June 01-04, 1998, Seattle, Washington, United States
• 11: Ning Jing , Yun-Wu Huang , Elke A. Rundensteiner, Hierarchical Encoded Path Views for Path Query Processing: An Optimal Model and Its Performance Evaluation, IEEE Transactions on Knowledge and Data Engineering, v.10 n.3, p.409-432, May 1998 [doi>10.1109/69.687976]
• 12: M. R. Kolahdouzan and C. Shahabi. Voronoi-based k nearest neighbor search for spatial network databases. In VLDB'04: Proceedings of the 30th International Conference on Very Large Data Bases, pages 840--851, Toronto, Canada, Sept. 2004.
• 13: D. Papadias, J. Zhang, N. Mamoulis, and Y. Tao. Query processing in spatial network databases. In VLDB'03: Proceedings of the 29th International Conference on Very Large Databases, pages 802--813, Berlin, Germany, Sept. 2003.
• 14: Hanan Samet, Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics and Geometric Modeling), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 15: Jagan Sankaranarayanan , Houman Alborzi , Hanan Samet, Efficient query processing on spatial networks, Proceedings of the 13th annual ACM international workshop on Geographic information systems, November 04-05, 2005, Bremen, Germany [doi>10.1145/1097064.1097093]
• 16: Cyrus Shahabi , Mohammad R. Kolahdouzan , Mehdi Sharifzadeh, A Road Network Embedding Technique for K-Nearest Neighbor Search in Moving Object Databases, Geoinformatica, v.7 n.3, p.255-273, September 2003 [doi>10.1023/A:1025153016110]
• 17: Shashi Shekhar , Jin Soung Yoo, Processing in-route nearest neighbor queries: a comparison of alternative approaches, Proceedings of the 11th ACM international symposium on Advances in geographic information systems, p.9-16, November 07-08, 2003, New Orleans, Louisiana, USA [doi>10.1145/956676.956678]
• 18: Hyoseop Shin , Bongki Moon , Sukho Lee, Adaptive multi-stage distance join processing, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.343-354, May 15-18, 2000, Dallas, Texas, United States
• 19: P. M. Vaidya, An O(n log n) algorithm for the all-nearest-neighbors problem, Discrete & Computational Geometry, v.4 n.2, p.101-115, Jan. 1989 [doi>10.1007/BF02187718]
• 20: Ouri Wolfson , Prasad Sistla , Bo Xu , Jutai Zhou , Sam Chamberlain, DOMINO: databases fOr MovINg Objects tracking, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.547-549, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Design, Performance

Keywords:
SILC framework, location-based services, path coherence, query processing, spatial databases, spatial networks