Home Computational Visual Media Article
PDF (8.3 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Research Article | Open Access

HoLens: A visual analytics design for higher-order movement modeling and visualization

Department of Computer Science and Engineering, The Hong Kong University of Science and Technology, Hong Kong, China
Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China
Thrust of Computational Media and Arts (CMA), The Hong Kong University of Science and Technology (Guangzhou), Guangzhou 511458, China
Department of Computer Science, University of Reading, Berkshire RG6 6AH, UK
Shenzhen Key Laboratory of Safety and Security for Next Generation of Industrial Internet, Southern University of Science and Technology, Shenzhen 518055, China
Show Author Information

Graphical Abstract

View original image Download original image

Abstract

Higher-order patterns reveal sequential multistep state transitions, which are usually superior to origin-destination analyses that depict only first-order geospatial movement patterns. Conventional methods for higher-order movement modeling first construct a directed acyclic graph (DAG) of movements and then extract higher-order patterns from the DAG. However, DAG-based methods rely heavily on identifying movement keypoints, which are challenging for sparse movements and fail to consider the temporal variants critical for movements in urban environments. To overcome these limitations, we propose HoLens, a novel approach for modeling and visualizing higher-order movement patterns in the context of an urban environment. HoLens mainly makes twofold contributions: First, we designed an auto-adaptive movement aggregation algorithm that self-organizes movements hierarchically by considering spatial proximity, contextual information, and temporal variability. Second, we developed an interactive visual analytics interface comprising well-established visualization techniques, including the H-Flow for visualizing the higher-order patterns on the map and the higher-order state sequence chart for representing the higher-order state transitions. Two real-world case studies demonstrate that the method can adaptively aggregate data and exhibit the process of exploring higher-order patterns using HoLens. We also demonstrate the feasibility, usability, and effectiveness of our approach through expert interviews with three domain experts.

Keywords

data visualizationmovement modelingstate sequence visualizationmovement visualizationurban visual analytics

References

[1]
Tao, J.; Xu, J.; Wang, C.; Chawla, N. V. HoNVis: Visualizing and exploring higher-order networks. In: Proceedings of the IEEE Pacific Visualization Symposium, 1–10, 2017.
Crossref
[2]

Xu, J.; Wickramarathne, T. L.; Chawla, N. V. Representing higher-order dependencies in networks. Science Advances Vol. 2, No. 5, e1600028, 2016.

Crossref Google Scholar
[3]
Markov, A. A. Theory of Algorithms. Moscow: Academy of Sciences of the USSR, 1954.
[4]
Chierichetti, F.; Kumar, R.; Raghavan, P.; Sarlos, T. Are web users really Markovian? In: Proceedings of the 21st International Conference on World Wide Web, 609–618, 2012.
Crossref
[5]

Shannon, C. E. A mathematical theory of communication. The Bell System Technical Journal Vol. 27, No. 3, 379–423, 1948.

Crossref Google Scholar
[6]

Grundy, E.; Jones, M. W.; Laramee, R. S.; Wilson, R. P.; Shepard, E. L. C. Visualisation of sensor data from animal movement. Computer Graphics Forum Vol. 28, No. 3, 815–822, 2009.

Crossref Google Scholar
[7]

Nekovee, M.; Moreno, Y.; Bianconi, G.; Marsili, M. Theory of rumour spreading in complex social networks. Physica A: Statistical Mechanics and Its Applications Vol. 374, No. 1, 457–470, 2007.

Crossref Google Scholar
[8]

Kareiva, P. M.; Shigesada, N. Analyzing insect movement as a correlated random walk. Oecologia Vol. 56, No. 2, 234–238, 1983.

Crossref Google Scholar
[9]

Andrienko, N.; Andrienko, G. State transition graphs for semantic analysis of movement behaviours. Information Visualization Vol. 17, No. 1, 41–65, 2018.

Crossref Google Scholar
[10]

Andrienko, N.; Andrienko, G.; Stange, H.; Liebig, T.; Hecker, D. Visual analytics for understanding spatial situations from episodic movement data. KI - Künstliche Intelligenz Vol. 26, No. 3, 241–251, 2012.

Crossref Google Scholar
[11]
Gaffney, S.; Smyth, P. Trajectory clustering with mixtures of regression models. In: Proceedings of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 63–72, 1999.
Crossref
[12]

Gaffney, S. J.; Robertson, A. W.; Smyth, P.; Camargo, S. J.; Ghil, M. Probabilistic clustering of extratropical cyclones using regression mixture models. Climate Dynamics Vol. 29, No. 4, 423–440, 2007.

Crossref Google Scholar
[13]
Lee, J. G.; Han, J.; Whang, K. Y. Trajectory clustering: A partition-and-group framework. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, 593–604, 2007.
Crossref
[14]
Andrienko, G.; Andrienko, N. Spatio-temporal aggregation for visual analysis of movements. In: Proceedings of the IEEE Symposium on Visual Analytics Science and Technology, 51–58, 2008.
Crossref
[15]

Adrienko, N.; Adrienko, G. Spatial generalization and aggregation of massive movement data. IEEE Transactions on Visualization and Computer Graphics Vol. 17, No. 2, 205–219, 2011.

Crossref Google Scholar
[16]

Zhou, Z.; Meng, L.; Tang, C.; Zhao, Y.; Guo, Z.; Hu, M.; Chen, W. Visual abstraction of large scale geospatial origin-destination movement data. IEEE Transactions on Visualization and Computer Graphics Vol. 25, No. 1, 43–53, 2019.

Crossref Google Scholar
[17]

Blaas, J.; Botha, C.; Grundy, E.; Jones, M.; Laramee, R.; Post, F. Smooth graphs for visual exploration of higher-order state transitions. IEEE Transactions on Visualization and Computer Graphics Vol. 15, No. 6, 969–976, 2009.

Crossref Google Scholar
[18]

Rosvall, M.; Esquivel, A. V.; Lancichinetti, A.; West, J. D.; Lambiotte, R. Memory in network flows and its effects on spreading dynamics and community detection. Nature Communications Vol. 5, Article No. 4630, 2014.

Crossref Google Scholar
[19]

Zeng, W.; Fu, C. W.; Müller Arisona, S.; Schubiger, S.; Burkhard, R.; Ma, K. L. Visualizing the relationship between human mobility and points of interest. IEEE Transactions on Intelligent Transportation Systems Vol. 18, No. 8, 2271–2284, 2017.

Crossref Google Scholar
[20]

Dodge, S.; Weibel, R.; Lautenschütz, A. K. Towards a taxonomy of movement patterns. Information Visualization Vol. 7, Nos. 3–4, 240–252, 2008.

Crossref Google Scholar
[21]

Slingsby, A.; van Loon, E. Exploratory visual analysis for animal movement ecology. Computer Graphics Forum Vol. 35, No. 3, 471–480, 2016.

Crossref Google Scholar
[22]

Chen, S.; Yuan, X.; Wang, Z.; Guo, C.; Liang, J.; Wang, Z.; Zhang, X.; Zhang, J. Interactive visual discovering of movement patterns from sparsely sampled geo-tagged social media data. IEEE Transactions on Visualization and Computer Graphics Vol. 22, No. 1, 270–279, 2016.

Crossref Google Scholar
[23]

Chen, W.; Guo, F.; Wang, F. Y. A survey of traffic data visualization. IEEE Transactions on Intelligent Transportation Systems Vol. 16, No. 6, 2970–2984, 2015.

Crossref Google Scholar
[24]

Andrienko, G.; Andrienko, N.; Dykes, J.; Fabrikant, S. I.; Wachowicz, M. Geovisualization of dynamics, movement and change: Key issues and developing approaches in visualization research. Information Visualization Vol. 7, Nos. 3–4, 173–180, 2008.

Crossref Google Scholar
[25]
Kapler, T.; Wright, W. GeoTime information visualization. In: Proceedings of the IEEE Symposium on Information Visualization, 25–32, 2005.
Crossref
[26]

Adrienko, N.; Adrienko, G. Spatial generalization and aggregation of massive movement data. IEEE Transactions on Visualization and Computer Graphics Vol. 17, No. 2, 205–219, 2011.

Crossref Google Scholar
[27]

Guo, D.; Zhu, X. Origin-destination flow data smoothing and mapping. IEEE Transactions on Visualization and Computer Graphics Vol. 20, No. 12, 2043–2052, 2014.

Crossref Google Scholar
[28]

Scheepens, R.; Willems, N.; van de Wetering, H.; Andrienko, G.; Andrienko, N.; van Wijk, J. J. Composite density maps for multivariate trajectories. IEEE Transactions on Visualization and Computer Graphics Vol. 17, No. 12, 2518–2527, 2011.

Crossref Google Scholar
[29]

Feng, Z.; Li, H.; Zeng, W.; Yang, S. H.; Qu, H. Topology density map for urban data visualization and analysis. IEEE Transactions on Visualization and Computer Graphics Vol. 27, No. 2, 828–838, 2021.

Crossref Google Scholar
[30]
Giannotti, F.; Nanni, M.; Pinelli, F.; Pedreschi, D. Trajectory pattern mining. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 330–339, 2007.
Crossref
[31]

Laube, P.; Purves, R. S. An approach to evaluating motion pattern detection techniques in spatio-temporal data. Computers, Environment and Urban Systems Vol. 30, No. 3, 347–374, 2006.

Crossref Google Scholar
[32]

Zeng, W.; Fu, C. W.; Müller Arisona, S.; Schubiger, S.; Burkhard, R.; Ma, K. L. A visual analytics design for studying rhythm patterns from human daily movement data. Visual Informatics Vol. 1, No. 2, 81–91, 2017.

Crossref Google Scholar
[33]

Deng, Z.; Weng, D.; Liu, S.; Tian, Y.; Xu, M.; Wu, Y. A survey of urban visual analytics: Advances and future directions. Computational Visual Media Vol. 9, No. 1, 3–39, 2023.

Crossref Google Scholar
[34]

Huang, X.; Zhao, Y.; Ma, C.; Yang, J.; Ye, X.; Zhang, C. TrajGraph: A graph-based visual analytics approach to studying urban network centralities using taxi trajectory data. IEEE Transactions on Visualization and Computer Graphics Vol. 22, No. 1, 160–169, 2016.

Crossref Google Scholar
[35]

Zeng, W.; Shen, Q.; Jiang, Y.; Telea, A. Route-aware edge bundling for visualizing origin-destination trails in urban traffic. Computer Graphics Forum Vol. 38, No. 3, 581–593, 2019.

Crossref Google Scholar
[36]
Pretorius, A. Visualization of state transition graphs. Ph.D. Dissertation. Eindhoven, the Netherlands: Eindhoven University of Technology, 2008.
[37]

Lu, W. L.; Wang, Y. S.; Lin, W. C. Chess evolution visualization. IEEE Transactions on Visualization and Computer Graphics Vol. 20, No. 5, 702–713, 2014.

Crossref Google Scholar
[38]
Plaisant, C.; Milash, B.; Rose, A.; Widoff, S.; Shneiderman, B. LifeLines: Visualizing personal histories. In: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, 221–227, 1996.
Crossref
[39]

Krstajic, M.; Bertini, E.; Keim, D. CloudLines: Compact display of event episodes in multiple time-series. IEEE Transactions on Visualization and Computer Graphics Vol. 17, No. 12, 2432–2439, 2011.

Crossref Google Scholar
[40]

Schmidt, M. The sankey diagram in energy and material flow management. Journal of Industrial Ecology Vol. 12, No. 1, 82–94, 2008.

Crossref Google Scholar
[41]

Ham, F. V.; van de Wetering, H.; van Wijk, J. J. Interactive visualization of state transition systems. IEEE Transactions on Visualization and Computer Graphics Vol. 8, No. 4, 319–329, 2002.

Crossref Google Scholar
[42]
Wongsuphasawat, K.; Guerra Gómez, J. A.; Plaisant, C.; Wang, T. D.; Taieb-Maimon, M.; Shneiderman, B. LifeFlow: Visualizing an overview of event sequences. In: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, 1747–1756, 2011.
Crossref
[43]

Monroe, M.; Lan, R.; Lee, H.; Plaisant, C.; Shneiderman, B. Temporal event sequence simplification. IEEE Transactions on Visualization and Computer Graphics Vol. 19, No. 12, 2227–2236, 2013.

Crossref Google Scholar
[44]
Shen, Z.; Wei, J.; Sundaresan, N.; Ma, K. L. Visual analysis of massive web session data. In: Proceedings of the IEEE Symposium on Large Data Analysis and Visualization, 65–72, 2012.
Crossref
[45]

Liu, Z.; Kerr, B.; Dontcheva, M.; Grover, J.; Hoffman, M.; Wilson, A. CoreFlow: Extracting and visualizing branching patterns from event sequences. Computer Graphics Forum Vol. 36, No. 3, 527–538, 2017.

Crossref Google Scholar
[46]

Zeng, W.; Fu, C. W.; Arisona, S. M.; Qu, H. Visualizing interchange patterns in massive movement data. Computer Graphics Forum Vol. 32, No. 3pt3, 271–280, 2013.

Crossref Google Scholar
[47]

Slingsby, A.; van Loon, E. Exploratory visual analysis for animal movement ecology. Computer Graphics Forum Vol. 35, No. 3, 471–480, 2016.

Crossref Google Scholar
[48]

Ware, C.; Arsenault, R.; Plumlee, M.; Wiley, D. Visualizing the underwater behavior of humpback whales. IEEE Computer Graphics and Applications Vol. 26, No. 4, 14–18, 2006.

Crossref Google Scholar
[49]
Zhang, J.; Guo, H.; Yuan, X. Efficient unsteady flow visualization with high-order access dependencies. In: Proceedings of the IEEE Pacific Visualization Symposium, 80–87, 2016.
Crossref
[50]

Lu, Y.; Steptoe, M.; Burke, S.; Wang, H.; Tsai, J. Y.; Davulcu, H.; Montgomery, D.; Corman, S. R.; Maciejewski, R. Exploring evolving media discourse through event cueing. IEEE Transactions on Visualization and Computer Graphics Vol. 22, No. 1, 220–229, 2016.

Crossref Google Scholar
[51]
Riehmann, P.; Hanfler, M.; Froehlich, B. Interactive sankey diagrams. In: Proceedings of the IEEE Symposium on Information Visualization, 233–240, 2005.
Crossref
[52]

Wongsuphasawat, K.; Gotz, D. Exploring flow, factors, and outcomes of temporal event sequences with the outflow visualization. IEEE Transactions on Visualization and Computer Graphics Vol. 18, No. 12, 2659–2668, 2012.

Crossref Google Scholar
[53]

Gotz, D.; Stavropoulos, H. DecisionFlow: Visual analytics for high-dimensional temporal event sequence data. IEEE Transactions on Visualization and Computer Graphics Vol. 20, No. 12, 1783–1792, 2014.

Crossref Google Scholar
[54]
Perer, A.; Gotz, D. Data-driven exploration of care plans for patients. In: Proceedings of the CHI Extended Abstracts on Human Factors in Computing Systems, 439–444, 2013.
Crossref
[55]
Zhao, J.; Liu, Z.; Dontcheva, M.; Hertzmann, A.; Wilson, A. MatrixWave: Visual comparison of event sequence data. In: Proceedings of the 33rd Annual ACM Conference on Human Factors in Computing Systems, 259–268, 2015.
Crossref
[56]

Perer, A.; Sun, J. MatrixFlow: Temporal network visual analytics to track symptom evolution during disease progression. Annual Symposium Proceedings Vol. 2012, 716–725, 2012.

Google Scholar
[57]
Yuan, J.; Zheng, Y.; Xie, X. Discovering regions of different functions in a city using human mobility and POIs. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 186–194, 2012.
Crossref
[58]
Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. The R*-tree: An efficient and robust access method for points and rectangles. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, 322–331, 1990.
Crossref
[59]

Schwarz, G. Estimating the dimension of a model. The Annals of Statistics Vol. 6, No. 2, 461–464, 1978.

Crossref Google Scholar
[60]

Akaike, H. A new look at the statistical model identification. IEEE Transactions on Automatic Control Vol. 19, No. 6, 716–723, 1974.

Crossref Google Scholar
[61]

Van der Heyden, M. J.; Diks, C. G. C.; Hoekstra, B. P. T.; DeGoede, J. Testing the order of discrete Markov chains using surrogate data. Physica D: Nonlinear Phenomena Vol. 117, Nos. 1–4, 299–313, 1998.

Crossref Google Scholar
[62]

Kullback, S.; Leibler, R. A. On information and sufficiency. The Annals of Mathematical Statistics Vol. 22, No. 1, 79–86, 1951.

Crossref Google Scholar
[63]

Meulemans, W.; Riche, N. H.; Speckmann, B.; Alper, B.; Dwyer, T. KelpFusion: A hybrid set visualization technique. IEEE Transactions on Visualization and Computer Graphics Vol. 19, No. 11, 1846–1858, 2013.

Crossref Google Scholar
[64]

Baydas, S.; Karakas, B. Defining a curve as a Bezier curve. Journal of Taibah University for Science Vol. 13, No. 1, 522–528, 2019.

Crossref Google Scholar
[65]

Zeng, W.; Fu, C. W.; Müller Arisona, S.; Erath, A.; Qu, H. Visualizing waypoints-constrained origin-destination patterns for massive transportation data. Computer Graphics Forum Vol. 35, No. 8, 95–107, 2016.

Crossref Google Scholar
[66]
Yang, D.; Qu, B.; Yang, J.; Cudre-Mauroux, P. Revisiting user mobility and social relationships in LBSNs: A hypergraph embedding approach. In: Proceedings of the World Wide Web Conference, 2147–2157, 2019.
Crossref
[67]

Yang, D.; Qu, B.; Yang, J.; Cudré-Mauroux, P. LBSN2Vec: Heterogeneous hypergraph embedding for location-based social networks. IEEE Transactions on Knowledge and Data Engineering Vol. 34, No. 4, 1843–1855, 2022.

Google Scholar
[68]

Cao, N.; Gotz, D.; Sun, J.; Qu, H. DICON: Interactive visual analysis of multidimensional clusters. IEEE Transactions on Visualization and Computer Graphics Vol. 17, No. 12, 2581–2590, 2011.

Crossref Google Scholar
[69]

Yang, J.; Hubball, D.; Ward, M. O.; Rundensteiner, E. A.; Ribarsky, W. Value and relation display: Interactive visual exploration of large data sets with hundreds of dimensions. IEEE Transactions on Visualization and Computer Graphics Vol. 13, No. 3, 494–507, 2007.

Crossref Google Scholar
[70]
Post, F. J.; van Walsum, T.; Post, F. H.; Silver, D. Iconic techniques for feature visualization. In: Proceedings of the Visualization, 288–295, 1995.
Crossref
[71]
Sun, D.; Feng, Z.; Chen, Y.; Wang, Y.; Zeng, J.; Yuan, M.; Pong, T. C.; Qu, H. DFSeer: A visual analytics approach to facilitate model selection for demand forecasting. In: Proceedings of the CHI Conference on Human Factors in Computing Systems, 1–13, 2020.
Crossref
Computational Visual Media
Volume 10 Issue 6,
December 2024
Pages 1079-1100
DOI: 10.1007/s41095-023-0392-y
Cite this article:
Feng Z, Zhu F, Wang H, et al. HoLens: A visual analytics design for higher-order movement modeling and visualization. Computational Visual Media, 2024, 10(6): 1079-1100. https://doi.org/10.1007/s41095-023-0392-y
Metrics & Citations  
Article History
Copyright
Rights and Permissions
Return