{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T05:18:27Z","timestamp":1672636707814},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,12,4]],"date-time":"2019-12-04T00:00:00Z","timestamp":1575417600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Defence Science and Technology Group, Edinburgh, South Australia","award":["MyIP:6104"]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2019,12,31]]},"abstract":"There are many real world applications that require identifying public movements such as identifying movement corridors in cities and most popular paths. If one is not given user trajectories but rather sporadic location data, such as location-based social network data, finding movement related information becomes difficult. Rather than processing all points in a dataset given a query, a clever approach is to construct a graph, based on user locations, and query this graph to answer questions such as shortest paths, most popular paths, and movement corridors. Shortest path graph is one of the popular graphs. However, the shortest path graph can be inefficient and ineffective for analysing movement data, as it calculates the graph edges considering the shortest paths over all the points in a dataset. Therefore, edge sets resulting from shortest path graphs are usually very restrictive and not suitable for movement analysis because of its global view of the dataset. We propose the stepping stone graph, which calculates the graph considering point pairs rather than all points; the stepping stone graph focuses on possible local movements, making it both efficient and effective for location-based social network related data. We demonstrate its capabilities by applying it in the Location-Based Social Network domain and comparing with the shortest path graph. We also compare its properties to a range of other graphs and demonstrate how stepping stone graph relates to Gabriel graph, relative neighbourhood graph, and Delaunay triangulation.<\/jats:p>","DOI":"10.1145\/3324883","type":"journal-article","created":{"date-parts":[[2019,12,5]],"date-time":"2019-12-05T14:07:24Z","timestamp":1575554844000},"page":"1-24","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Stepping Stone Graph"],"prefix":"10.1145","volume":"5","author":[{"given":"Sameera","family":"Kannangara","sequence":"first","affiliation":[{"name":"The University of Melbourne, Victoria, Australia"}]},{"given":"Egemen","family":"Tanin","sequence":"additional","affiliation":[{"name":"The University of Melbourne, Victoria, Australia"}]},{"given":"Aaron","family":"Harwood","sequence":"additional","affiliation":[{"name":"The University of Melbourne, Victoria, Australia"}]},{"given":"Shanika","family":"Karunasekera","sequence":"additional","affiliation":[{"name":"The University of Melbourne, Victoria, Australia"}]}],"member":"320","published-online":{"date-parts":[[2019,12,4]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"10th International Conference on Geographic Information Science (GIScience\u201918 (LIPIcs), Stephan Winter, Amy Griffin, and Monika Sester (Eds.)","volume":"114","author":"Amores David","year":"2018","unstructured":"David Amores , Maria Vasardani , and Egemen Tanin . 2018 . Early detection of herding behaviour during emergency evacuations . In 10th International Conference on Geographic Information Science (GIScience\u201918 (LIPIcs), Stephan Winter, Amy Griffin, and Monika Sester (Eds.) , Vol. 114 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 1:1--1:15. David Amores, Maria Vasardani, and Egemen Tanin. 2018. Early detection of herding behaviour during emergency evacuations. In 10th International Conference on Geographic Information Science (GIScience\u201918 (LIPIcs), Stephan Winter, Amy Griffin, and Monika Sester (Eds.), Vol. 114. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 1:1--1:15."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480197318088"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2008.09.003"},{"key":"e_1_2_1_4_1","volume-title":"Ebert","author":"Chae Junghoon","year":"2014","unstructured":"Junghoon Chae , Dennis Thom , Yun Jang , SungYe Kim , Thomas Ertl , and David S . Ebert . 2014 . Public behavior response analysis in disaster events utilizing visual analytics of microblog data. Computers 8 Graphics 38 (2014), 51--60. Junghoon Chae, Dennis Thom, Yun Jang, SungYe Kim, Thomas Ertl, and David S. Ebert. 2014. Public behavior response analysis in disaster events utilizing visual analytics of microblog data. Computers 8 Graphics 38 (2014), 51--60."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2006.878713"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2093973.2094010"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Matt Duckham Marc J. van Kreveld Ross Purves Bettina Speckmann Yaguang Tao Kevin Verbeek and Jo Wood. 2016. Modeling checkpoint-based movement with the Earth Mover\u2019s Distance. See Miller et al. [16] 225--239. Matt Duckham Marc J. van Kreveld Ross Purves Bettina Speckmann Yaguang Tao Kevin Verbeek and Jo Wood. 2016. Modeling checkpoint-based movement with the Earth Mover\u2019s Distance. See Miller et al. [16] 225--239.","DOI":"10.1007\/978-3-319-45738-3_15"},{"key":"e_1_2_1_8_1","first-page":"259","article-title":"A new statistical approach to geographic variation analysis","volume":"18","author":"Ruben Gabriel K.","year":"1969","unstructured":"K. Ruben Gabriel and Robert R. Sokal . 1969 . A new statistical approach to geographic variation analysis . Systematic Biology 18 , 3 (1969), 259 -- 278 . K. Ruben Gabriel and Robert R. Sokal. 1969. A new statistical approach to geographic variation analysis. Systematic Biology 18, 3 (1969), 259--278.","journal-title":"Systematic Biology"},{"key":"e_1_2_1_9_1","volume-title":"Man Lung Yiu, and Christian S. Jensen","author":"Jeung Hoyoung","year":"2011","unstructured":"Hoyoung Jeung , Man Lung Yiu, and Christian S. Jensen . 2011 . Trajectory pattern mining. In Computing with Spatial Trajectories, Yu Zheng and Xiaofang Zhou (Eds.). Springer , 143--177. Hoyoung Jeung, Man Lung Yiu, and Christian S. Jensen. 2011. Trajectory pattern mining. In Computing with Spatial Trajectories, Yu Zheng and Xiaofang Zhou (Eds.). Springer, 143--177."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3274895.3274913"},{"key":"e_1_2_1_11_1","volume-title":"Radke","author":"Kirkpatrick David G.","year":"1985","unstructured":"David G. Kirkpatrick and John D . Radke . 1985 . A framework for computational morphology. In Machine Intelligence and Pattern Recognition. Vol. 2 . Elsevier , 217--248. David G. Kirkpatrick and John D. Radke. 1985. A framework for computational morphology. In Machine Intelligence and Pattern Recognition. Vol. 2. Elsevier, 217--248."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247546"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/2832415.2832496"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 2011 IEEE Conference on Visual Analytics Science and Technology (VAST \u201911)","author":"MacEachren Alan M.","unstructured":"Alan M. MacEachren , Anuj R. Jaiswal , Anthony C. Robinson , Scott Pezanowski , Alexander Savelyev , Prasenjit Mitra , Xiao Zhang , and Justine I. Blanford . 2011. SensePlace2: GeoTwitter analytics support for situational awareness . In Proceedings of the 2011 IEEE Conference on Visual Analytics Science and Technology (VAST \u201911) . IEEE Computer Society, 181--190. Alan M. MacEachren, Anuj R. Jaiswal, Anthony C. Robinson, Scott Pezanowski, Alexander Savelyev, Prasenjit Mitra, Xiao Zhang, and Justine I. Blanford. 2011. SensePlace2: GeoTwitter analytics support for situational awareness. In Proceedings of the 2011 IEEE Conference on Visual Analytics Science and Technology (VAST \u201911). IEEE Computer Society, 181--190."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2013.76"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-45738-3","volume-title":"Proceedings of the 9th International Conference on Geographic Information Science (GIScience\u201916)","volume":"9927","author":"Miller Jennifer A.","year":"2016","unstructured":"Jennifer A. Miller , David O\u2019Sullivan , and Nancy Wiegand ( Eds .). 2016 . Proceedings of the 9th International Conference on Geographic Information Science (GIScience\u201916) . Lecture Notes in Computer Science , Vol. 9927 . Springer. Jennifer A. Miller, David O\u2019Sullivan, and Nancy Wiegand (Eds.). 2016. Proceedings of the 9th International Conference on Geographic Information Science (GIScience\u201916). Lecture Notes in Computer Science, Vol. 9927. Springer."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2006.02.008"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2898363"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3140029"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Dipto Sarkar Ren\u00e9e Sieber and Raja Sengupta. 2016. GIScience considerations in spatial social networks. See Miller et al. [16] 85--98. Dipto Sarkar Ren\u00e9e Sieber and Raja Sengupta. 2016. GIScience considerations in spatial social networks. See Miller et al. [16] 85--98.","DOI":"10.1007\/978-3-319-45738-3_6"},{"key":"e_1_2_1_21_1","volume-title":"S-hull: A fast radial sweep-hull routine for Delaunay triangulation. CoRR abs\/1604.01428.","author":"Sinclair David","year":"2016","unstructured":"David Sinclair . 2016 . S-hull: A fast radial sweep-hull routine for Delaunay triangulation. CoRR abs\/1604.01428. David Sinclair. 2016. S-hull: A fast radial sweep-hull routine for Delaunay triangulation. CoRR abs\/1604.01428."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2812802"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(80)90066-7"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3324883","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T10:10:39Z","timestamp":1672567839000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3324883"}},"subtitle":["A Graph for Finding Movement Corridors using Sparse Trajectories"],"short-title":[],"issued":{"date-parts":[[2019,12,4]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12,31]]}},"alternative-id":["10.1145\/3324883"],"URL":"http:\/\/dx.doi.org\/10.1145\/3324883","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"value":"2374-0353","type":"print"},{"value":"2374-0361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,4]]},"assertion":[{"value":"2018-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-12-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}
