{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T19:29:00Z","timestamp":1790882940008,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540005797","type":"print"},{"value":"9783540364771","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-36477-3_10","type":"book-chapter","created":{"date-parts":[[2007,5,5]],"date-time":"2007-05-05T08:31:09Z","timestamp":1178353869000},"page":"128-151","source":"Crossref","is-referenced-by-count":123,"title":["Route Planning and Map Inference with Global Positioning Traces"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Edelkamp","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan","family":"Schr\u00f6dl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2003,2,28]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"R. K. Ahuja, K. Mehlhorn, J. B. Orbin, and R. E. Tarjan. Faster algorithms for the shortest path problem. Journal of the ACM, pages 213\u2013223, 1990.","DOI":"10.1145\/77600.77615"},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"I. J. Balaban. An optimal algorithm for finding segment intersection. In ACM Symposium on Computational Geometry, pages 339\u2013364, 1995.","DOI":"10.1145\/220279.220302"},{"key":"10_CR3","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1109\/TC.1979.1675432","volume":"28","author":"J. L. Bentley","year":"1979","unstructured":"J. L. Bentley and T. A. Ottmann. Algorithms for reporting and counting geometric intersections. Transactions on Computing, 28:643\u2013647, 1979.","journal-title":"Transactions on Computing"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"U. Brandes, F. Schulz, D. Wagner, and T. Willhalm. Travel planning with self-made maps. In Workshop on Algorithm Engineering and Experiments (ALENEX), 2001.","DOI":"10.1007\/3-540-44808-X_10"},{"key":"10_CR5","first-page":"200","volume":"32","author":"B. Chazelle","year":"1986","unstructured":"B. Chazelle. Reporting and counting segment intersections. Computing System Science, 32:200\u2013212, 1986.","journal-title":"Computing System Science"},{"key":"10_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/147508.147511","volume":"39","author":"B. Chazelle","year":"1992","unstructured":"B. Chazelle and H. Edelsbrunner. An optimal algorithm for intersecting lines in the plane. Journal of the ACM, 39:1\u201354, 1992.","journal-title":"Journal of the ACM"},{"key":"10_CR7","unstructured":"T.H. Cormen, C.E. Leiserson,and R.L. Rivest.Introduction to Algorithms. The MIT Press, 1990."},{"issue":"11","key":"10_CR8","doi-asserted-by":"publisher","first-page":"632","DOI":"10.1145\/363269.363610","volume":"12","author":"R. B. Dial","year":"1969","unstructured":"R. B. Dial. Shortest-path forest with topological ordering. Communication of the ACM, 12(11):632\u2013633, 1969.","journal-title":"Communication of the ACM"},{"key":"10_CR9","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E. W. Dijkstra","year":"1959","unstructured":"E. W. Dijkstra. A note on two problems in connection with graphs. Numerische Mathematik, 1:269\u2013271, 1959.","journal-title":"Numerische Mathematik"},{"issue":"5","key":"10_CR10","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/S0924-2716(01)00027-2","volume":"55","author":"P. Doucette","year":"2001","unstructured":"P. Doucette, P. Agouris, A. Stefanidis, and M. Musavi. Self-organized clustering for road extraction in classified imagery. Journal of Photogrammetry and Remote Sensing, 55(5\u20136):347\u2013358, March 2001.","journal-title":"Journal of Photogrammetry and Remote Sensing"},{"key":"10_CR11","unstructured":"S. Edelkamp and S. Schroedl. Localizing A*. In National Conference on Artificial Intelligence (AAAI), pages 885\u2013890, 2000."},{"issue":"3","key":"10_CR12","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M. L. Fredman","year":"1987","unstructured":"M. L. Fredman and R. E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithm. Journal of the ACM, 34(3):596\u2013615, 1987.","journal-title":"Journal of the ACM"},{"key":"10_CR13","unstructured":"S. Handley, P. Langley, and F. Rauscher. Learning ot predict the duration of an automobile trip. In Knowledge Discovery and Data Mining (KDD), pages 219\u2013223, 1998."},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"A. C. Harvey. Forecasting, Structural Time Series Models and the Kalman Filter. Cambridge University Press, 1990.","DOI":"10.1017\/CBO9781107049994"},{"key":"10_CR15","unstructured":"C. A. Hipke. Verteilte Visualisierung von Geometrischen Algorithmen. PhD thesis, University of Freiburg, 2000."},{"issue":"6","key":"10_CR16","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1145\/360825.360861","volume":"18","author":"D. S. Hirschberg","year":"1975","unstructured":"D. S. Hirschberg. A linear space algorithm for computing common subsequences. Communications of the ACM, 18(6):341\u2013343, 1975.","journal-title":"Communications of the ACM"},{"issue":"1","key":"10_CR17","first-page":"3","volume":"55","author":"P. Klein","year":"1997","unstructured":"P. Klein, S. Rao, M. Rauch, and S. Subramanian. Faster shortest-path algorithms for planar graphs. Special Issue of Journal of Computer and System Sciences on selected papers of STOC 1994, 55(1):3\u201323, 1997.","journal-title":"Special Issue of Journal of Computer and System Sciences on selected papers of STOC 1994"},{"key":"10_CR18","unstructured":"R. E. Korf and W. Zhang. Divide-and-conquer frontier search applied to optimal sequence allignment. In National Conference on Artificial Intelligence (AAAI), pages 910\u2013916, 2000."},{"key":"10_CR19","unstructured":"J. B. MacQueen. Some methods for classification and analysis of multivariate observations. In Symposium on Math, Statistics, and Probability, volume 1, pages 281\u2013297, 1967."},{"key":"10_CR20","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn and U. Meyer. External-memory breadth-first search with sublinear I\/O. In European Symposium on Algorithms (ESA), 2002.","DOI":"10.1007\/3-540-45749-6_63"},{"issue":"1","key":"10_CR21","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/BF02294245","volume":"50","author":"G. W. Milligan","year":"1985","unstructured":"G. W. Milligan and M. C. Cooper. An examination of procedures for determining the number of clusters in a data set. Psychometrika, 50(1):159\u2013179, 1985.","journal-title":"Psychometrika"},{"key":"10_CR22","unstructured":"C. Navigation Technologies, Sunnyvale. Software developer\u2019s toolkit, 5.7.4 solaris edition, 1996."},{"key":"10_CR23","doi-asserted-by":"crossref","unstructured":"B. W. Parkinson, J. J. Spilker, P. Axelrad, and P. Enge. Global Positioning System: Theory and Applications. American Institute of Aeronautics and Astronautics, 1996.","DOI":"10.2514\/4.866395"},{"key":"10_CR24","doi-asserted-by":"crossref","unstructured":"L. Piegl and W. Tiller. The nurbs book. Springer, 1997.","DOI":"10.1007\/978-3-642-59223-2"},{"key":"10_CR25","doi-asserted-by":"crossref","unstructured":"C. A. Pribe and S. O. Rogers. Learning to associate driver behavior with traffic controls. In Proceedings of the 78th Annual Meeting of the Transportation Review Board, Washington, DC, January 1999.","DOI":"10.3141\/1679-13"},{"key":"10_CR26","doi-asserted-by":"crossref","unstructured":"S. Rogers, P. Langley, and C. Wilson. Mining GPS data to augment road models. In Knowledge Discovery and Data Mining (KDD), pages 104\u2013113, 1999.","DOI":"10.1145\/312129.312208"},{"key":"10_CR27","series-title":"Technical Report","volume-title":"Map refinement from GPS traces","author":"S. Schroedl","year":"2000","unstructured":"S. Schroedl, S. Rogers, and C. Wilson. Map refinement from GPS traces. Technical Report RTC 6\/2000, DaimlerChrysler Research and Technology North America, Palo Alto, CA, 2000."},{"key":"10_CR28","doi-asserted-by":"crossref","unstructured":"F. Schulz, D. Wagner, and K.6Weihe. Dijkstra\u2019s algorithm on-line: An empirical case study from public railroad transport. Journal of Experimental Algorithmics, 5(12), 2000.","DOI":"10.1145\/351827.384254"},{"key":"10_CR29","doi-asserted-by":"crossref","unstructured":"F. Schulz, D. Wagner, and C. Zaroliagis. Using multi-level graphs for timetable information. In Workshop on Algorithm Engineering and Experiments (ALENEX), 2002.","DOI":"10.1007\/3-540-45643-0_4"},{"key":"10_CR30","series-title":"Lect Notes Comput Sci","volume-title":"Memory Hierarchies","author":"L. Thoma","year":"2003","unstructured":"L. Thoma and N. Zeh. I\/O-efficient algorithms for sparse graphs. In Memory Hierarchies, Lecture Notes in Computer Science. Springer, 2002. To appear."},{"key":"10_CR31","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1145\/316542.316548","volume":"46","author":"M. Thorup","year":"1999","unstructured":"M. Thorup. Undirected single-source shortest paths with positive integer weights in linear time. Journal of the ACM, 46:362\u2013394, 1999.","journal-title":"Journal of the ACM"},{"key":"10_CR32","unstructured":"J. Wang, S. Rogers, C. Wilson, and S. Schroedl. Evaluation of a blended DGPS\/DR system for precision map refinement. In Proceeedings of the ION Technical Meeting 2001, Institute of Navigation, Long Beach, CA, 2001."}],"container-title":["Lecture Notes in Computer Science","Computer Science in Perspective"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36477-3_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T14:39:17Z","timestamp":1556375957000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36477-3_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540005797","9783540364771"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/3-540-36477-3_10","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2003]]}}}