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

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg