Document Open Access Logo

Introducing Diversion Graph for Real-Time Spatial Data Analysis with Location Based Social Networks

Authors Sameera Kannangara, Hairuo Xie, Egemen Tanin, Aaron Harwood, Shanika Karunasekera

PDF
Thumbnail PDF

File

LIPIcs.GIScience.2021.I.7.pdf
  • Filesize: 0.58 MB
  • 15 pages

Document Identifiers

Author Details

Sameera Kannangara
  • School of Computing and Information Systems, The University of Melbourne, Australia
Hairuo Xie
  • School of Computing and Information Systems, The University of Melbourne, Australia
Egemen Tanin
  • School of Computing and Information Systems, The University of Melbourne, Australia
Aaron Harwood
  • School of Computing and Information Systems, The University of Melbourne, Australia
Shanika Karunasekera
  • School of Computing and Information Systems, The University of Melbourne, Australia

Funding

This research is funded in part by the Defence Science and Technology Group, Edinburgh, South Australia, under contract MyIP:6104.

Cite As Get BibTex

Sameera Kannangara, Hairuo Xie, Egemen Tanin, Aaron Harwood, and Shanika Karunasekera. Introducing Diversion Graph for Real-Time Spatial Data Analysis with Location Based Social Networks. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part I. Leibniz International Proceedings in Informatics (LIPIcs), Volume 177, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.GIScience.2021.I.7

Abstract

Neighbourhood graphs are useful for inferring the travel network between locations posted in the Location Based Social Networks (LBSNs). Existing neighbourhood graphs, such as the Stepping Stone Graph lack the ability to process a high volume of LBSN data in real time. We propose a neighbourhood graph named Diversion Graph, which uses an efficient edge filtering method from the Delaunay triangulation mechanism for fast processing of LBSN data. This mechanism enables Diversion Graph to achieve a similar accuracy level as Stepping Stone Graph for inferring travel networks, but with a reduction of the execution time of over 90%. Using LBSN data collected from Twitter and Flickr, we show that Diversion Graph is suitable for travel network processing in real time.

Subject Classification

ACM Subject Classification
  • Information systems → Geographic information systems
Keywords
  • moving objects
  • shortest path
  • graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. D. V. Andrade and L. H. de Figueiredo. Good approximations for the relative neighbourhood graph. In Proceedings of the 13th Canadian Conference on Computational Geometry, University of Waterloo, Ontario, Canada, August 13-15, 2001, pages 25-28, 2001. URL: http://www.cccg.ca/proceedings/2001/lhf-96805.ps.gz.
  2. P. Bose, L. Devroye, W. S. Evans, and D. G. Kirkpatrick. On the spanning ratio of gabriel graphs and beta-skeletons. SIAM J. Discrete Math., 20(2):412-427, 2006. URL: https://doi.org/10.1137/S0895480197318088.
  3. J. Cardinal, S. Collette, and S. Langerman. Empty region graphs. Computational geometry, 42(3):183-195, 2009. URL: https://doi.org/10.1016/j.comgeo.2008.09.003.
  4. J. Chae, D. Thom, Y. Jang, S. Kim, T. Ertl, and D. S. Ebert. Public behavior response analysis in disaster events utilizing visual analytics of microblog data. Computers & Graphics, 38:51-60, 2014. URL: https://doi.org/10.1016/j.cag.2013.10.008.
  5. J. Cortés, S. Martínez, and F. Bullo. Robust rendezvous for mobile autonomous agents via proximity graphs in arbitrary dimensions. IEEE Transactions on Automatic Control, 51(8):1289-1298, 2006. URL: https://doi.org/10.1109/TAC.2006.878713.
  6. M. de Berg, W. Meulemans, and B. Speckmann. Delineating imprecise regions via shortest-path graphs. In I. F. Cruz, D. Agrawal, C. S. Jensen, E. Ofek, and E. Tanin, editors, 19th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, ACM-GIS 2011, November 1-4, 2011, Chicago, IL, USA, Proceedings, pages 271-280. ACM, 2011. URL: https://doi.org/10.1145/2093973.2094010.
  7. K. R. Gabriel and R. R. Sokal. A new statistical approach to geographic variation analysis. Systematic Biology, 18(3):259-278, 1969. Google Scholar
  8. S. Kannangara, E. Tanin, A. Harwood, and S. Karunasekera. Stepping stone graph for public movement analysis. In F. Banaei-Kashani, E. G. Hoel, R. H. Güting, R. Tamassia, and L. Xiong, editors, Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL 2018, Seattle, WA, USA, November 06-09, 2018, pages 149-158. ACM, 2018. URL: https://doi.org/10.1145/3274895.3274913.
  9. S. Kannangara, E. Tanin, A. Harwood, and S. Karunasekera. Stepping stone graph: A graph for finding movement corridors using sparse trajectories. ACM Trans. Spatial Algorithms and Systems, 5(4):23:1-23:24, 2019. URL: https://doi.org/10.1145/3324883.
  10. K. H. Lim, S. Jayasekara, S. Karunasekera, A. Harwood, L. Falzon, J. Dunn, and G. Burgess. RAPID: real-time analytics platform for interactive data mining. In U. Brefeld, E. Curry, E. Daly, B. MacNamee, A. Marascu, F. Pinelli, M. Berlingerio, and N. Hurley, editors, Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2018, Dublin, Ireland, September 10-14, 2018, Proceedings, Part III, volume 11053 of Lecture Notes in Computer Science, pages 649-653. Springer, 2018. URL: https://doi.org/10.1007/978-3-030-10997-4_44.
  11. A. M. MacEachren, A. R. Jaiswal, A. C. Robinson, S. Pezanowski, A. Savelyev, P. Mitra, X. Zhang, and J. I. Blanford. Senseplace2: Geotwitter analytics support for situational awareness. In 2011 IEEE Conference on Visual Analytics Science and Technology, VAST 2011, Providence, Rhode Island, USA, October 23-28, 2011, pages 181-190. IEEE Computer Society, 2011. URL: https://doi.org/10.1109/VAST.2011.6102456.
  12. D. W. Matula and R. R. Sokal. Properties of gabriel graphs relevant to geographic variation research and the clustering of points in the plane. Geographical analysis, 12(3):205-222, 1980. Google Scholar
  13. K. Ramamohanarao, H.Xie, L. Kulik, S. Karunasekera, E. Tanin, R. Zhang, and E. B. Khunayn. Smarts: Scalable microscopic adaptive road traffic simulator. ACM TIST, 8(2):26:1-26:22, 2017. URL: https://doi.org/10.1145/2898363.
  14. D. Sinclair. S-hull: a fast radial sweep-hull routine for delaunay triangulation. CoRR, abs/1604.01428, 2016. URL: http://arxiv.org/abs/1604.01428.
  15. B. Thomee, D. A. Shamma, G. Friedland, B. Elizalde, K. Ni, D. Poland, D. Borth, and L. Li. YFCC100M: the new data in multimedia research. Commun. ACM, 59(2):64-73, 2016. URL: https://doi.org/10.1145/2812802.
  16. G. T. Toussaint. Comment: Algorithms for computing relative neighbourhood graph. Electronics Letters, 16(22):860-860, October 1980. Google Scholar
  17. G. T. Toussaint. The relative neighbourhood graph of a finite planar set. Pattern recognition, 12(4):261-268, 1980. Google Scholar
  18. R. B. Urquhart. Algorithms for computation of relative neighbourhood graph. Electronics Letters, 16(14):556-557, July 1980. Google Scholar
  19. X. Wei and X. Angela Yao. A conceptual framework for representation of location-based social media activities (short paper). In S. Winter, A. Griffin, and M. Sester, editors, 10th International Conference on Geographic Information Science, GIScience 2018, August 28-31, 2018, Melbourne, Australia, volume 114 of LIPIcs, pages 62:1-62:7. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.GISCIENCE.2018.62.
  20. J. Xie, T. Yang, and G. Li. Extracting geospatial information from social media data for hazard mitigation, typhoon hato as case study (short paper). In S. Winter, A. Griffin, and M. Sester, editors, 10th International Conference on Geographic Information Science, GIScience 2018, August 28-31, 2018, Melbourne, Australia, volume 114 of LIPIcs, pages 65:1-65:6. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.GISCIENCE.2018.65.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact