A pyramid-based approach to visual exploration of a large volume of vehicle trajectory data

Abstract

Advances in positioning and wireless communicating technologies make it possible to collect large volumes of trajectory data of moving vehicles in a fast and convenient fashion. These data can be applied to traffic studies. Behind this application, a methodological issue that still requires particular attention is the way these data should be spatially visualized. Trajectory data physically consists of a large number of positioning points. With the dramatic increase of data volume, it becomes a challenge to display and explore these data. Existing commercial software often employs vector-based indexing structures to facilitate the display of a large volume of points, but their performance downgrades quickly when the number of points is very large, for example, tens of millions. In this paper, a pyramid-based approach is proposed. A pyramid method initially is invented to facilitate the display of raster images through the tradeoff between storage space and display time. A pyramid is a set of images at different levels with different resolutions. In this paper, we convert vector-based point data into raster data, and build a grid-based indexing structure in a 2D plane. Then, an image pyramid is built. Moreover, at the same level of a pyramid, image is segmented into mosaics with respect to the requirements of data storage and management. Algorithms or procedures on grid-based indexing structure, image pyramid, image segmentation, and visualization operations are given in this paper. A case study with taxi trajectory data in Shanghai is conducted. Results demonstrate that the proposed method outperforms the existing commercial software.

Keywords

large volumes of trajectory data / visualization / grid-based indexing structure / image pyramid

References

[1] Adelson E H, Anderson C H, Bergen J R, Burt P J, Ogden J M (1984). Pyramid methods in image processing. Radio Corporation of America Engineer, 29(6): 33-41

[2] Andrienko G, Andrienko N (2005). Blending aggregation and selection: adapting parallel coordinates for the visualization of large datasets. The Cartographic Journal, 42(1): 49-60

[3] Beckmann N, Kriegel H P, Schneider R, Seeger B (1990). The R*-tree: an efficient and robust access method for points and rectangles. In: Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, 322

[4] Bentley J L (1975). Multidimensional binary search trees used for associative searching. Commun ACM, 18(9): 509-517

[5] Chandran S (2004). Introduction to kd-trees. Technical Report, University of Maryland Department of Computer Science, College Park, Maryland, USA.

[6] Fabritiis C D, Ragona R, Valenti G (2008). Traffic estimation and prediction based on real time floating car data. In: 11th International IEEE Conference, 197-203

[7] Fayyad U, Wierse A, Grinstein G (2001). Information visualization in data mining and knowledge discovery. San Francisco: Morgan Kaufmann Publishers, 21

[8] Finkel R A, Bentley J L (1974). Quad trees: a data structure for retrieval on composite keys. Acta Informatica, 4(1): 1-9

[9] Getting I (1993). The global positioning system. IEEE Spectrum, 30(12): 36-38, 43-47

[10] Gu J, Wu C B (2001). Research on common space indexing methods. Microcomputth Applications, 17(6): 76-79 (in Chinese)

[11] Guttman A (1984). R-trees: a dynamic index structure for spatial searching. In: Proceedings of the 1984 ACMSIGMOD Conference, Boston, MA, 47-57

[12] Jiang Y J, Li X, Li X J, Sun J (2012). Geometrical characteristics extraction and accuracy analysis of road network based on vehicle trajectory data. Journal of Geo-information Science, 14(2): 165-170

[13] Kamel I, Faloutsos C (1994). Hilbert R-tree: an improved R-tree using fractals. In: Proceedings of VLDB Conference, 500-509

[14] Li D R, Zhu X Y, Ging J Y (2003). From digital map to spatial information multi-grid. Geomatics and Information Science of Wuhan University, 28(6): 646-650(in Chinese)

[15] Ma Q, Yang B, Qian W N, Zhou A Y (2009). Query processing of massive trajectory data based on mapreduce. In: Proceedings of CloudDbACM: 9-16

[16] Mahran S, Mahar K (2008). Using grid for accelerating density-based clustering. In: Proceedings of the 8th IEEE International Conference on Computer and Information Technology, 35-40

[17] Montanvert A, Meer P, Rosenfeld A (1991). Hierarchical image analysis using irregular tessellations. IEEE Trans Pattern Anal Mach Intell, 13(4): 307-316

[18] Oscar S C (2011). Image stitching. Universitat Politècnica de Catalunya, 15-17

[19] Sahr K, White D, Kimerling A J (2003). Geodesic discrete global grid systems. Cartography and Geographic Information Science, 30(2): 121-134

[20] Sellis T, Roussopoulos N, Faloutsos C (1987). The R+-Tree: a dynamic index for multi-dimensional objects. In: VLDB’1987, 507-518

[21] Shen H T, Zhou X, Zhou A (2007). An adaptive and dynamic dimensionality reduction method for high-dimensional indexing. The VLDB Journal, 16(2): 219-234

[22] Tan C L, Zhang Z (2001). Text block segmentation using pyramid structure. SPIE Document Recognition and Retrieval, 8: 297-306

[23] Tao C V (2000). Mobile mapping technology for road network data acquisition. Journal of Geospatial Engineering, 2(2): 1-13

[24] Yan H, Weibel R (2008). An algorithm for point cluster generalization based on the Voronoi diagram. Computers and GeoSciences, 34(8): 939-954

Acknowledgements

This research was sponsored by Open Grant from Shanghai Key Laboratory for Urban Ecology and Sustainability (SHUES), Scientific Research Starting Foundation for Returned Overseas Chinese Scholars (Ministry of Education, China), Director Grant of Key Laboratory of Geographical Information Science (No. KLGIS2011C01), and Shanghai Natural Science Foundation (No. 11ZR1410100).

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg