{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T04:40:56Z","timestamp":1773895256995,"version":"3.50.1"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,9,14]],"date-time":"2014-09-14T00:00:00Z","timestamp":1410652800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Geoinformatica"],"published-print":{"date-parts":[[2015,4]]},"DOI":"10.1007\/s10707-014-0216-4","type":"journal-article","created":{"date-parts":[[2014,9,13]],"date-time":"2014-09-13T05:56:39Z","timestamp":1410587799000},"page":"331-364","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["A Dilution-matching-encoding compaction of trajectories over road networks"],"prefix":"10.1007","volume":"19","author":[{"given":"Ranit","family":"Gotsman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yaron","family":"Kanza","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,9,14]]},"reference":[{"issue":"1","key":"216_CR1","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"R Bellman","year":"1958","unstructured":"Bellman R (1958) On a routing problem. Q Appl Math 16(1):87\u201390","journal-title":"Q Appl Math"},{"key":"216_CR2","doi-asserted-by":"crossref","unstructured":"Borradaile G, Sankowski P, Wulff-Nilsen C (2010) Min st-cut oracle for planar graphs with near-linear preprocessing time. In: Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS \u201910. IEEE Computer Society, Washington,DC, pp 601\u2013610","DOI":"10.1109\/FOCS.2010.63"},{"key":"216_CR3","doi-asserted-by":"crossref","first-page":"937","DOI":"10.1137\/S0097539700369387","volume":"33","author":"P Bose","year":"2004","unstructured":"Bose P, Morin P (2004) Online routing in triangulations. SIAM J Comput 33:937\u2013951","journal-title":"SIAM J Comput"},{"issue":"1-2","key":"216_CR4","doi-asserted-by":"crossref","first-page":"1009","DOI":"10.14778\/1920841.1920968","volume":"3","author":"X Cao","year":"2010","unstructured":"Cao X, Cong G, Jensen CS (2010) Mining significant semantic locations from GPS data. Proc VLDB Endowment 3(1\u20132):1009\u20131020","journal-title":"Proc VLDB Endowment"},{"key":"216_CR5","doi-asserted-by":"crossref","unstructured":"Chen Y, Jiang K, Zheng Y, Li C, Yu N (2009) Trajectory simplification method for location-based social networking services. In: Proc. of the ACM international workshop on location-based social networks. Seattle, Washington, pp 33\u201340","DOI":"10.1145\/1629890.1629898"},{"issue":"5","key":"216_CR6","doi-asserted-by":"crossref","first-page":"698","DOI":"10.1109\/TKDE.2005.80","volume":"17","author":"A Civilis","year":"2005","unstructured":"Civilis A, Jensen CS, Pakalnis S (2005) Techniques for efficient road-network-based tracking of moving objects. IEEE Trans Knowl Data Eng 17(5):698\u2013712","journal-title":"IEEE Trans Knowl Data Eng"},{"issue":"1","key":"216_CR7","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra EW (1959) A note on two problems in connexion with graphs. Numer Math 1(1):269\u2013271","journal-title":"Numer Math"},{"issue":"2","key":"216_CR8","doi-asserted-by":"crossref","first-page":"112","DOI":"10.3138\/FM57-6770-U75U-7727","volume":"10","author":"DH Douglas","year":"1973","unstructured":"Douglas DH, Peucker TK (1973) Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica: Inter. J Geogr Inf Geovisualization 10 (2):112\u2013122","journal-title":"J Geogr Inf Geovisualization"},{"key":"216_CR9","doi-asserted-by":"crossref","unstructured":"Doytsher Y, Galon B, Kanza Y (2010) Querying geo-social data by bridging spatial networks and social networks. In: Proc. of the 2nd ACM SIGSPATIAL international workshop on location-based social networks, San Jose, pp 39\u201346","DOI":"10.1145\/1867699.1867707"},{"key":"216_CR10","doi-asserted-by":"crossref","unstructured":"Doytsher Y, Galon B, Kanza Y (2011) Storing routes in socio-spatial networks and supporting social-based route recommendation. In: Proc. of the 3rd ACM SIGSPATIAL international workshop on location-based social networks, pp 49\u201356","DOI":"10.1145\/2063212.2063219"},{"key":"216_CR11","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1145\/2185677.2185739","volume-title":"An effective coreset compression algorithm for large scale sensor networks. In: Proceedings of the 11th international conference on information processing in sensor networks","author":"D Feldman","year":"2012","unstructured":"Feldman D, Sugaya A, Rus D (2012) An effective coreset compression algorithm for large scale sensor networks. In: Proceedings of the 11th international conference on information processing in sensor networks. ACM, Beijing, pp 257\u2013268"},{"key":"216_CR12","unstructured":"Fredman ML, Tarjan RE (1984) Fibonacci heaps and their uses in improved network optimization algorithms. In: Proceedings of the 25th annual symposium on foundations of computer science. IEEE, pp 338\u2013346"},{"issue":"5","key":"216_CR13","doi-asserted-by":"crossref","first-page":"695","DOI":"10.1007\/s00778-011-0244-8","volume":"20","author":"F Giannotti","year":"2011","unstructured":"Giannotti F, Nanni M, Pedreschi D, Pinelli F, Renso C, Rinzivillo S, Trasarti R (2011) Unveiling the complexity of human mobility by querying and mining massive trajectory data. VLDB J 20(5):695\u2013719","journal-title":"VLDB J"},{"key":"216_CR14","first-page":"241","volume-title":"Compact representation of GPS trajectories over vectorial road networks. In: Proc. of the 13th international conference on advances in spatial and temporal databases, SSTD\u201913","author":"R Gotsman","year":"2013","unstructured":"Gotsman R, Kanza Y (2013) Compact representation of GPS trajectories over vectorial road networks. In: Proc. of the 13th international conference on advances in spatial and temporal databases, SSTD\u201913. Springer-Verlag, Munich, pp 241\u2013258"},{"key":"216_CR15","unstructured":"Greenfeld JS (2002) Matching GPS observations to locations on a digital map. In: Proceedings of the 81st annual meeting of the transportation research board"},{"issue":"3","key":"216_CR16","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1137\/S0895480190177042","volume":"7","author":"D Hartvigsen","year":"1994","unstructured":"Hartvigsen D, Mardon R (1994) The all-pairs min cut problem and the minimum cycle basis problem on planar graphs. SIAM J Discret Math 7(3):403\u2013418","journal-title":"SIAM J Discret Math"},{"key":"216_CR17","doi-asserted-by":"crossref","unstructured":"Hershberger J, Snoeyink J (1994) An o(n logn) implementation of the Douglas-Peucker algorithm for line simplification. In: Proceedings of the tenth annual symposium on computational geometry. ACM, Stony Brook, New York, pp 383\u2013384","DOI":"10.1145\/177424.178097"},{"key":"216_CR18","unstructured":"Hummel B (2006) Map matching for vehicle guidance. In: Dynamic and mobile GIS: Investigating space and time. CRC Press, pp 437\u2013438"},{"issue":"1","key":"216_CR19","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/S0734-189X(86)80027-5","volume":"36","author":"H Imai","year":"1986","unstructured":"Imai H, Iri M (1986) Computational-geometric methods for polygonal approximations of a curve. Comp Vis, Graph, Image Proc 36(1):31\u201341","journal-title":"Comp Vis, Graph, Image Proc"},{"key":"216_CR20","doi-asserted-by":"crossref","unstructured":"Levin R, Kravi E, Kanza Y (2012) Concurrent and robust topological map matching. In: Proceedings of the 20th international conference on advances in geographic information systems, SIGSPATIAL \u201912. ACM, Redondo Beach, pp 617\u2013620","DOI":"10.1145\/2424321.2424431"},{"key":"216_CR21","doi-asserted-by":"crossref","unstructured":"Li Q, Zheng Y, Xie X, Chen Y, Liu W, Ma WY (2008) Mining user similarity based on location history. In: Proceedings of the 16th ACM SIGSPATIAL international conference on advances in geographic information systems, GIS \u201908. ACM, Irvine, pp 34:1\u201334:10","DOI":"10.1145\/1463434.1463477"},{"key":"216_CR22","doi-asserted-by":"crossref","unstructured":"Meratnia N, de By RA (2004) Spatiotemportal compression techniques for moving point objects. In: Proceedings of the 9th international conference on extending database technology (EDBT). Heraklion Crete, Greece, pp 765\u2013782","DOI":"10.1007\/978-3-540-24741-8_44"},{"key":"216_CR23","doi-asserted-by":"crossref","unstructured":"Muckell J, Hwang JH, Lawson CT, Ravi SS (2010) Algorithms for compressing GPS trajectory data: An empirical evaluation. In: Proceedings of the 18th SIGSPATIAL international conference on advances in geographic information systems, GIS \u201910. ACM, San Jose, pp 402\u2013405","DOI":"10.1145\/1869790.1869847"},{"key":"216_CR24","unstructured":"Muckell J, Hwang JH, Patil V, Lawson CT, Ping F, Ravi SS (2011) SQUISH: An online approach for GPS trajectory compression. In: Proceedings of the 2nd international conference on computing for geospatial research & applications, COM.Geo \u201911. ACM, Washington, DC, pp 13:1\u2013 13:8"},{"key":"216_CR25","doi-asserted-by":"crossref","unstructured":"Muckell J Jr, PWO, Hwang JH, Lawson CT, Ravi SS (2013) Compression of trajectory data: a comprehensive evaluation and new approach. Geoinformatica","DOI":"10.1007\/s10707-013-0184-0"},{"issue":"1","key":"216_CR26","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K Mulmuley","year":"1987","unstructured":"Mulmuley K, Vazirani UV, Vazirani VV (1987) Matching is as easy as matrix inversion. Combinatorica 7(1):105\u2013113","journal-title":"Combinatorica"},{"key":"216_CR27","doi-asserted-by":"crossref","unstructured":"Newson P, Krumm J (2009) Hidden Markov map matching through noise and sparseness. In: Proceedings of the 17th ACM SIGSPATIAL international conference on advances in geographic information systems, pp 336\u2013343","DOI":"10.1145\/1653771.1653818"},{"key":"216_CR28","doi-asserted-by":"crossref","unstructured":"Ore O (1962) Theory of Graphs. AMS Colloquium Publications 38.American Mathematical Soc","DOI":"10.1090\/coll\/038"},{"key":"216_CR29","first-page":"784","volume-title":"Amnesic online synopses for moving objects. In: Proceedings of the 15th ACM international conference on information and knowledge management, CIKM \u201906","author":"M Potamias","year":"2006","unstructured":"Potamias M, Patroumpas K, Sellis T (2006) Amnesic online synopses for moving objects. In: Proceedings of the 15th ACM international conference on information and knowledge management, CIKM \u201906. ACM, Arlington, pp 784\u2013785"},{"key":"216_CR30","doi-asserted-by":"crossref","unstructured":"Potamias M, Patroumpas K, Sellis T (2006) Sampling trajectory streams with spatiotemporal criteria. In: Proceedings of the 18th international conference on scientific and statistical database management, SSDBM \u201906. IEEE Computer Society, Washington, DC, pp 275\u2013284","DOI":"10.1109\/SSDBM.2006.45"},{"key":"216_CR31","doi-asserted-by":"crossref","unstructured":"Potamias M, Patroumpas K, Sellis T (2007) Online amnesic summarization of streaming locations. In: Proc. of the 10th international conference on advances in spatial and temporal databases, SSTD\u201907. Springer-Verlag, Boston, pp 148\u2013166","DOI":"10.1007\/978-3-540-73540-3_9"},{"key":"216_CR32","doi-asserted-by":"crossref","unstructured":"Quddus MA, Ochieng W, Zhao L, Noland RB (2003) A general map matching algorithm for transport telematics applications. GPS Resolut 7(3)","DOI":"10.1007\/s10291-003-0069-z"},{"key":"216_CR33","doi-asserted-by":"crossref","unstructured":"Quddus MA, Ochieng WY, Noland RB (2007) Current map-matching algorithms for transport applications: State-of-the art and future research directions. In: Transportation research part c: Emerging technologies","DOI":"10.1016\/j.trc.2007.05.002"},{"key":"216_CR34","doi-asserted-by":"crossref","unstructured":"Trajcevski G, Cao H, Scheuermanny P, Wolfsonz O, Vaccaro D (2006) On-line data reduction and the quality of history in moving objects databases. In: Proceedings of the 5th ACM international workshop on data engineering for wireless and mobile access, MobiDE \u201906. ACM, Chicago, pp 19\u201326","DOI":"10.1145\/1140104.1140110"},{"issue":"2","key":"216_CR35","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1109\/TIT.1967.1054010","volume":"13","author":"AJ Viterbi","year":"1967","unstructured":"Viterbi AJ (1967) Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. Trans Inf Theory 13 (2):260\u2013269","journal-title":"Trans Inf Theory"},{"key":"216_CR36","doi-asserted-by":"crossref","unstructured":"White CE, Bernstein D, Kornhauser AL (2000) Some map matching algorithms for personal navigation assistants. In: Transportation research part c: emerging technologies, vol 8, pp 91\u2013108","DOI":"10.1016\/S0968-090X(00)00026-7"},{"key":"216_CR37","first-page":"192","volume-title":"An adaptive algorithm for online time series segmentation with error bound guarantee. In: Proceedings of the 15th international conference on extending database technology, EDBT \u201912","author":"Z Xu","year":"2012","unstructured":"Xu Z, Zhang R, Kotagiri R, Parampalli U (2012) An adaptive algorithm for online time series segmentation with error bound guarantee. In: Proceedings of the 15th international conference on extending database technology, EDBT \u201912. ACM, Berlin, pp 192\u2013203"},{"key":"216_CR38","first-page":"254","volume-title":"Destination prediction by sub-trajectory synthesis and privacy protection against such prediction. In: Proc. of the 2013 IEEE international conference on data engineering (ICDE 2013)","author":"AY Xue","year":"2013","unstructured":"Xue AY, Zhang R, Zheng Y, Xie X, Huang J, Xu Z (2013) Destination prediction by sub-trajectory synthesis and privacy protection against such prediction. In: Proc. of the 2013 IEEE international conference on data engineering (ICDE 2013). IEEE Computer Society, Washington, DC, pp 254\u2013265"},{"key":"216_CR39","unstructured":"Yin H, Wolfson O (2004) A weight-based map matching method in moving objects databases. In: Proceedings of the 16th international conference on scientific and statistical database management, SSDBM \u201904. IEEE Computer Society, Washington, DC, pp 437\u2013438"},{"key":"216_CR40","doi-asserted-by":"crossref","unstructured":"Zheng K, Trajcevski G, Zhou X, Scheuermann P (2011) Probabilistic range queries for uncertain trajectories on road networks. In: Proceedings of the 14th international conference on extending database technology, EDBT\/ICDT \u201911. ACM, Uppsala, Sweden, pp 283\u2013294","DOI":"10.1145\/1951365.1951400"},{"key":"216_CR41","doi-asserted-by":"crossref","unstructured":"Zheng K, Zheng Y, Xie X, Zhou X (2012) Reducing uncertainty of low-sampling-rate trajectories. In: Proceedings of the 2012 IEEE 28th international conference on data engineering. IEEE Computer Society, Washington, DC, pp 1144\u20131155","DOI":"10.1109\/ICDE.2012.42"},{"key":"216_CR42","doi-asserted-by":"crossref","unstructured":"Zheng Y, Li Q, Chen Y, Xie X, Ma WY (2008) Understanding mobility based on GPS data. In: Proceedings of the 10th international conference on ubiquitous computing, UbiComp \u201908. ACM, Seoul, pp 312\u2013321","DOI":"10.1145\/1409635.1409677"},{"issue":"1","key":"216_CR43","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1921591.1921596","volume":"5","author":"Y Zheng","year":"2011","unstructured":"Zheng Y, Zhang L, Ma Z, Xie X, Ma WY (2011) Recommending friends and locations based on individual location history. ACM Trans Web 5(1):1\u20135. 44","journal-title":"ACM Trans Web"},{"key":"216_CR44","doi-asserted-by":"crossref","unstructured":"Zheng Y, Zhang L, Xie X, Ma WY (2009) Mining interesting locations and travel sequences from GPS trajectories. In: Proceedings of the 18th international conference on world wide web, WWW \u201909. ACM, Madrid, pp 791\u2013800","DOI":"10.1145\/1526709.1526816"},{"key":"216_CR45","doi-asserted-by":"crossref","unstructured":"Zheng Y, Zhou X (eds.) (2011) Computing with Spatial Trajectories, Springer","DOI":"10.1007\/978-1-4614-1629-6"}],"container-title":["GeoInformatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10707-014-0216-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10707-014-0216-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10707-014-0216-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,2]],"date-time":"2024-06-02T13:16:30Z","timestamp":1717334190000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10707-014-0216-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,14]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,4]]}},"alternative-id":["216"],"URL":"https:\/\/doi.org\/10.1007\/s10707-014-0216-4","relation":{},"ISSN":["1384-6175","1573-7624"],"issn-type":[{"value":"1384-6175","type":"print"},{"value":"1573-7624","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,9,14]]}}}