Efficient integration of road maps

ABSTRACT

Integration of two road maps is finding a matching between pairs of objects that represent, in the maps, the same real-world road. Several algorithms were proposed in the past for road-map integration; however, these algorithms are not efficient and some of them even require human feedback. Thus, they are not suitable for many important applications (e.g., Web services) where efficiency, in terms of both time and space, is crucial. This paper presents two efficient algorithms for integrating maps in which roads are represented as polylines. The main novelty of these algorithms is in using only the locations of the endpoints of the polylines rather than trying to match whole lines. Experiments on real-world data are given, showing that our approach of integration based on matching merely endpoints is efficient and accurate (that is, it provides high recall and precision).

REFERENCES

• 1: Catriel Beeri , Yerach Doytsher , Yaron Kanza , Eliyahu Safra , Yehoshua Sagiv, Finding corresponding objects when integrating several geo-spatial datasets, Proceedings of the 13th annual ACM international workshop on Geographic information systems, November 04-05, 2005, Bremen, Germany [doi>10.1145/1097064.1097078]
• 2: C. Beeri, Y. Kanza, E. Safra, and Y. Sagiv. Object fusion in geographic information systems. In VLDB, pages 816--827, 2004.
• 3: Maria A. Cobb , Miyi J. Chung , Harold Foley, III , Frederick E. Petry , Kevin B. Shaw , H. Vincent Miller, A Rule-based Approach for the Conflation of Attributed Vector Data, Geoinformatica, v.2 n.1, p.7-35, March 1998 [doi>10.1023/A:1009788905049]
• 4: Y. Doytsher and S. Filin. The detection of of corresponding objects in a linear-based map conflation. Surveying and Land Information Systems, 60(2):117--128, 2000.
• 5: Y. Gabay and Y. Doytsher. An approach to matching lines in partly similar engineering maps. Geomatica, 54(3):297--310, 2000.
• 6: B. Rosen and A. Saalfeld. Match criteria for automatic alignment. In Proceedings of 7th International Symposium on Computer-Assisted Cartography (Auto-Carto 7), pages 1--20, 1985.
• 7: A. Saalfeld. Conflation-automated map compilation. International Journal of Geographical Information Systems, 2(3):217--228, 1988.
• 8: Monika Sester , Karl-Heinrich Anders , Volker Walter, Linking Objects of Different Spatial Data Sets by Integration and Aggregation, Geoinformatica, v.2 n.4, p.335-358, December 1998 [doi>10.1023/A:1009705404707]
• 9: V. Walter and D. Fritsch. Matching spatial data sets: a statistical approach. International Journal of Geographical Information Science, 13(5):445--473, 1999.
• 10: J. Mark Ware , Christopher B. Jones, Matching and aligning features in overlayed coverages, Proceedings of the 6th ACM international symposium on Advances in geographic information systems, p.28-33, November 02-07, 1998, Washington, D.C., United States [doi>10.1145/288692.288699]

INDEX TERMS

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

General Terms:
Algorithms, Experimentation

Keywords:
corresponding objects, integration, location-based join, matching polylines, road map, spatial network