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

Introduction

The rapid development of wireless communicating and positioning technologies makes it possible to collect large amounts of vehicle trajectory data. Vehicle-mounted GPS receivers (Getting, 1993) can record spatio-temporal trajectory data containing time, location, speed, driving directions, etc. Large data sets can be obtained with successive time and increasing acquisition frequency. They can be applied to traffic studies, such as extracting road network data (Tao, 2000), updating electronic maps (Jiang et al., 2012), analyzing historical traffic information, predicting travel time (Fabritiis et al., 2008), etc. However, the huge amount of data can also generate difficulties in data organization, management, and application. For example, the trajectory data of all taxis in a common city might range from a few GB to tens of GB within one day; with the existing software tools, rendering this quantity of data for visualization is a time-consuming proposition. Since data visualization can provide a qualitative overview and preliminary exploration of large data sets, and assist in identifying regions of interest (Fayyad et al., 2001), it is a fundamental step for more focused data analysis. For some applications of trajectory data, such as detecting changes of underlying road networks, discovering route choice between two locations, revealing traffic patterns, etc., visualization is an important step, thus a novel approach is required to solve the time-consumption issue. A lot of researches on data visualization have been done in recent years: Andrienko and Andrienko (2005) combine data selection and data aggregation for the visualization of large data sets. Shen et al. (2007) propose a dynamic dimensionality reduction algorithm-MMDR to manage large data sets in which data points in the different axis systems are indexed with a single B⁺-tree. Mahran and Mahar (2008) present GriDBSCAN algorithm which constructs a grid that surrounds the data space and divides data according to grid cells. Yan and Weibel (2008) present an algorithm for point generalization to realize cluster visualization.

Spatial data visualization consists of data query and display. The former refers to identifying spatial objects appearing within a given geographical extent. For a trajectory data set, queries can be divided into two types: 1) based on a spatial and a temporal extent, 2) based on an object identifier and a spatial extent (Ma et al., 2009). It often takes a significant portion of computational time for a large spatial data set to return all relevant positioning points. To accelerate the process, various indexing structures have been proposed, such as R-tree, quadtree, KD-tree, and grid index. Among them, the first three indexing structures are mostly designed for vector data. R-tree (Guttman, 1984) and its variants (Sellis et al., 1987; Beckmann et al., 1990; Kamel and Faloutsos, 1994) can build an index without predicting the spatial scope of objects. Quadtree indexing (Finkel and Bentley, 1974) requires a predetermined spatial scope to divide the space into four quadrants, each of which shall be divided into four quadrants recursively if needed. This method offers high convenience but low adjustability. A KD-tree index (Bentley, 1975; Chandran, 2004) is mainly applied to multi-dimensional spatial data by building a binary tree structure in each dimension. Compared with the three indexing structures above, a grid index (Sahr et al., 2003) is often applied to raster data and is easily implemented for large amounts of data. It divides a 2D surface into a series of uniform cells, each of which is assigned a unique identifier and regarded as one indexing unit (Li et al., 2003).

In this paper, trajectory data physically consists of a large number of positioning points which were originally recorded as vector data. If each point is treated as an individual feature and indexed as vector data, then the indexing structure will become impractical for the large number of points in our study (Gu and Wu, 2001). Instead, if the objective is to quickly visually explore the data, we may consider converting these points to raster data and indexing them with a grid approach. The advantage is that the performance of a grid approach is only related to the number of cells rather than the number of points within each cell.

To further improve retrieval efficiency, raster data or images are often projected into an image pyramid structure. An image pyramid is composed of images with the same spatial extent but different resolutions (Adelson et al., 1984; Montanvert et al., 1991). Considering the same geographical area, an image with high resolution contains more detailed information, which requires more time on data rendering. However, the details may not be always necessary if the resolution of display devices (e.g., computer screens) is not as high as that of the image. Image pyramids can resolve this ineffeciency. A high-resolution image is reclassified into multiple copies with different resolutions and recorded into a pyramid. The image resolution and data volume decrease from the bottom to the top so as to meet different requirements for storage and display (Tan and Zhang, 2001; Oscar, 2011).

According to the analysis above, in this paper, we build a grid-based indexing structure for trajectory data in 2D plane by converting vector trajectory data to raster images. Based on the obtained images, an image pyramid is employed to facilitate multi-scale visualization. The proposed approach is verified with Shanghai taxi trajectory data. A software tool for visualization is also developed. The results prove that the proposed approach can solve the time-consuming problem on displaying large data sets and that large volume of trajectory data visualization can be realized at a real-time fashion with our approach. With the constructed image pyramid, the software tool can react to visualization operations instantly. The structure of the paper is organized as follows: Section 2 introduces the principles of the proposed approach; Section 3 defines the data structures; Section 4 details the image pyramid construction; Section 5 describes the visualization process; Section 6 describes the experiments conducted; and conclusions are presented in the last section.

Principle

Figure 1 gives an overview of the proposed approach. As mentioned in Sect. 1, first the vector-based point data are converted to raster data. Given an image resolution, the coordinates of a point are represented as a row number and a column number in an image. All positioning points are mapped to a blank image according to a mapping function which is determined by the image resolution and spatial extent of the data set. However, for high image resolution, the image may not be created successfully due to hardware constraints. Therefore, instead of creating a large image, we split it into pieces and create map tiles. By this means, vector-based trajectory data are converted to a series of contiguous map tiles, which share the same size while do not intersect with each other. These map tiles can construct the original large image when tessellated.

Second, a grid-based indexing structure is constructed. The grid is composed of contiguous square cells. The numbers of cells along two axes are in conformity with the above image resolution. If an image size is W×L, a W×L grid is built. This implies that cells are in one-to-one correspondence with image pixels. Therefore, positioning points projected to a certain image pixel are recorded in the corresponding cell. The built indexing structure contains a list of point identifiers associated with grid cell identifiers.

Third, an image pyramid is constructed based on the above map tiles. The map tiles are stored into the bottom layer of the pyramid. For upper layers, the original large image is also replaced with map tiles. Map tiles in upper layers are created in order of layer number through a pixel-combination method, which can efficiently and effectively combine four neighboring pixels in an existing image into one pixel in a new image. For a constructed image pyramid, from its bottom to the top, resolution of the original large image decreases by 50% both in width and height layer by layer, and reaches the minimum at the top.

In this way, each pyramid layer is organized to a series of map tiles. These map tiles, each of which represents a geographical area, are directly applied to visualization operations. Display levels are in accordance with pyramid layers. The bottom of the pyramid is associated with a highest displaying level while the top corresponds to the lowest one. At a given display extent and zooming level, an intersection operation between map tiles of a certain layer and the given extent is conducted. The results contain a set of map tiles which appear at the intersection and their display positions. A tiled display of these image tiles is performed. Every time when the displaying level or extent changes (due to map visualization operations), the intersection operation is repeated, which updates the resulting map tiles and positions.

Data structures

Trajectory data

Let set T = {t₁,t₂,…t_n} denote taxi trajectory data consisting of n positioning points, T^period denote the acquisition time period. Every positioning point t_i has the following attributes:

t_i^xdenotes x coordinate of acquisition location.

t_i^ydenotes y coordinate of acquisition location.

t_i^{time}denotes acquisition time.

{{\displaystyle t}}_i^{carId}denotes which car the positioning point belongs to, distinguished by car plate.

{{\displaystyle t}}_i^{speed}denotes instant driving speed at acquisition time.

{{\displaystyle t}}_i^{state}denotes whether the taxi is loaded.

Image pyramid

Let Pyramid(level, bound[X_w,X_e,Y_n,Y_s]) be an image pyramid, where level denotes the pyramid height (counting from 0). A pyramid with k layers indicates that it has k types of image resolutions. Use bound[X_w,X_e,Y_n,Y_s] to denote the spatial extent which the pyramid covers, with X_w,X_e,Y_n,Y_s being the west, east, north and south margins, respectively. We use L₀, L₁, L₂, … to represent pyramid layers from the bottom to the top, where image resolution varies sequentially, as shown in Fig. 2. L₀ represents the bottom layer with the largest image resolution.

Map tiles

Let P_i =<LP_i,SP_i>denote the image group of L_i, in which LP_i denotes its original large image and SP_i is a matrix whose elements represent different locations of map tiles within LP_i. Each map tile has a size of height_i × width_i. Therefore, SP_i [row, column] is associated with a map tile of size height_i × width_i which lies at row, column within the large image. To ensure that a unique file name can identify each location of map tiles, a naming rule for map tiles is defined as follows: a file name equals its layer number (1 digit) plus row number (3 digits) and the column number (3 digits) within a large image. For example, “6062013.bmp” denotes a map tile located at row 62, column 13 within L₆’s large image.

Constructing an image pyramid

As stated in Sect. 2, map tiles instead of the original large image are stored into each pyramid layer. Pixel-combination can also be interpreted as combining four neighboring map tiles in a layer to form a new one of the same size and storing it into its upper layer. In this way, the image pyramid has the following features: (i) the number of map tiles for each layer decreases from pyramid bottom to top, (ii) The number of map tiles in the top layer is 1, (iii) The number of map tiles in any particular layer is four times of that in the layer above, iv) All the map tiles are of the same size. These features dictate that the original large image in the bottom layer should be divided as having the same number of map tiles in width and height and the number should be in the form of 2^M. For an integrated image pyramid, its height level equals M. The size of map tiles are denoted as width × height, then the original large image in the bottom layer should have a resolution of width × 2^M in width, height × 2^M in height.

Given a pyramid Pyramid(level, bound[X_w, X_e, Y_n, Y_s]), with the above image resolution (width × 2^M) × (height × 2^M), the way positioning points should be mapped to a blank image is determined. The number of map units in each pixel, denoted by scale₀, is defined as the larger one of (X_e-X_w)/(width × 2^M) and (Y_n-Y_s)/(height - 2^M) to avoid any positioning points falling outside the image. Assume that a positioning point t_k^y in a trajectory data set T is mapped to an image pixel, which appears at row row and column column. The two values are calculated by the following mapping function:

(1)\begin{array}{l}row=(Y_n-t_k^y)/scal{e}_{\mathrm{0}}\end{array}

(2)\begin{array}{l}column=(t_k^x-X_w)/scal{e}_{\mathrm{0}}\end{array}

(Results are rounded down to the nearest integer.).

After mapping, each image pixel is assigned a value, “1” or “0.” If the image pixel contains any positioning point, it is assigned a value of “1”, otherwise, it is assigned a value of “0”. Based on the results, map tiles in the bottom layer of the pyramid are created, as shown in Fig.3. The algorithm is as follows:

1) Repeat for row = 0 to 2^M-1

2) Repeat for column = 0 to 2^M-1

3) Create a blank map tile of size width×height

4) Repeat for r = height×row to (height×(row + 1)-1)

5) Repeat for c = width×column to (width×(column + 1)-1)

6) If pixel at (r, c) has a value of 1

7) Assign the pixel at (r- height×row, c- width×column) a value of 1

8) Else assign the pixel a value of 0

9) End Repeat

10) End Repeat

11) Record the map tile’s position as SP₀[row, column]

12) Name the map tile according to the defined rule

13) column = column + 1

14) End Repeat

15) row = row + 2

16) End Repeat

Based on the conversion from vector trajectory data to raster data, a gird-based indexing structure is built. The grid is composed of width × 2^M *height × 2^M square cells, with width × 2^M cells along X axis and height × 2^M cells along Y axis. Each cell is assigned a unique identifier: 1, 2, 3…. The spatial extent of each cell is in accordance with that of corresponding image pixel. If a cell’s position in the grid is denoted by [row, column], the west, east, north and south margin of its extent is X_w + column × scale₀, X_w + (column + 1) × scale₀, Y_n-row × scale₀, Y_n-(row + 1) × scale₀ respectively. All positioning points are allocated to different cells based on the above mapping process. A cell is denoted as cell(identifier, extent, pointsList), where pointsList is a set of relevant point identifiers. To obtain rapid access to a positioning point, first we need to reach its associated cell by comparing spatial extents of the point and cells, then search from a list of points within the cell.

Based on map tiles of the bottom layer, other map tiles are created layer by layer. SP_i[m, n] denotes an map tile’s position within LP_i, as defined in Sect. 3. Starting from SP₀[0, 0], combine every four neighboring images and record the newly formed image’s position as an element of SP₁. When combining pixels, we define the new pixel value as 1 if at least one of the original four pixels has a value of 1, otherwise we define the pixel value as 0, as shown in Fig. 4. By combining all four neighboring map tiles of the bottom layer, map tiles of its immediate upper layer are created. Figure 5 gives an example for image combination.

Other map tiles are created in the same way. The entire process of constructing an image pyramid is described as follows:

1) While current layer id k<M

2) Repeat for row = 0 to 2^M-k-2

3) Repeat for column = 0 to 2^M-k-2

4) combine the four map tiles at SP_k [row, column], SP_k [row, column+ 1], SP_k[row+ 1, column], SP_k [row+ 1, column+ 1]

5) record the newly formed image’s position as S_Pk+1[row/2, column/2]

6) column = column + 2

7) End repeat

8) row = row + 2

9) End repeat

10) k = k + 1

11) End while.

Applying the above algorithm, we can construct a pyramid of M layers. Resolutions of each layer’s original large image, the number of map tiles and image combination times are reduced by 75% compared with that of the immediate lower layer. Each map tile represents a geographical area and all map tiles in a layer together compose the entire research area bound. The spatial area that a map tile represents can be obtained according to its position in SP_i and corresponding map scale scale_i which equals 2ⁱ × scale₀.

Visualization operations

Let MapExtent(X_min, X_max, Y_min, Y_max) denote the geographical area that need to be displayed, with the four parameters indicating the west, east, south and north margin respectively. Let MapCenter(X, Y) denote the central point of the area, and i refer to the display level corresponding to L_i. Assume that the map tiles intersecting with MapExtent are those which are located from row p to q, column m to n. p, q, m, n are determined by the following formulas:

(3)\begin{array}{l}p=(Y_n-Y_{\max })/(scal{e}_i\times height)\end{array}

(4)\begin{array}{l}q=(Y_n-Y_{\min })/(scal{e}_i\times height)\end{array}

(5)\begin{array}{l}m=(X_{\min }-X_w)/(scal{e}_i\times width)\end{array}

(6)\begin{array}{l}n=(X_{\max }-X_w)/(scal{e}_i\times width)\end{array}

(Results are rounded down to the nearest integer.).

Let Extent(X₁, X₂, Y₁, Y₂) denote the spatial area represented by the map tile located at SP_i[row, column], with the four parameters indicating the west, east, north and south margin, respectively. The parameters can be calculated based on the following formulas:

(7)\begin{array}{l}{X}_{\mathrm{1}}=column\times width\times scal{e}_i+X_w\end{array}

(8)\begin{array}{l}{X}_{\mathrm{2}}=(column+\mathrm{1})\times width\times scal{e}_i+X_w\end{array}

(9)\begin{array}{l}{Y}_{\mathrm{1}}=Y_n-row\times height\times scal{e}_i\end{array}

(10)\begin{array}{l}{Y}_{\mathrm{2}}=Y_n-(row+\mathrm{1})\times height\times scal{e}_i\end{array}

Intersection implies that, for a certain map tile, X₁ or X₂ must be between X_min and X_max while Y₁ or Y₂ must range from Y_min to Y_max. There are nine circumstances for intersection between MapExtent and Extent, as shown in Fig. 6.

Under the first circumstance, part of the map tile intersects with MapExtent at screen’s top left corner, leaving the rest outside MapExtent. In this case, X₁≤X_min≤X₂≤X_max, Y_min≤Y₂≤Y_max≤Y₁. The map tile must be located at SP_i[p, m], such as A in Fig. 6. The intersection is enclosed by points 1, 2, 5, and 6 whose coordinates are accordingly (X_min, Y_max), (X₂, Y_max), (X_min, Y₂) and (X₂, Y₂). A’s displaying position, the opposite of point 1’s pixel position in A, can be represented by ((X_{\mathrm{1}}-X_{\min })/scal{e}_i,(Y_{\mathrm{1}}-Y_{\max })/scal{e}_i).

Under the second circumstance, part of the map tile intersects with the upper part of MapExtent, with the rest outside of MapExtent. In this case, X_min≤X₁≤X₂≤X_max, Y_min≤Y₂≤Y_max≤Y₁, the map tile must be located at row p, denoted by SP_i[p, column], such as B in Fig. 5. Points 2, 3, 7 and 6 form the intersection. B’s displaying position can be obtained by shifting A’s position n*width to the right: ((X_{\mathrm{1}}-X_{\min })/scal{e}_i+(column-m)\times width,(Y_{\mathrm{1}}-Y_{\max })/scal{e}_i). The intersection of the third case occurs when B’s displaying position is shifted to the very right, such as C in Fig. 6. C lies at SP_i[p, n], intersecting with MapExtent at its top right corner.

Other circumstances of intersecting are as shown as D, E, F, G, H, I in Fig. 6. Their displaying locations can also be regarded as shifting A’s position n × width horizontally or n × height vertically. Therefore, the displaying position of the map tile at SP_i[row, column] can be denoted as:

((X_{\mathrm{1}}-X_{\min })/scal{e}_i+(column-m)\times width,(Y_{\mathrm{1}}-Y_{\max })/scal{e}_i+(row-p)\times height),

when row equals p or q, column equals m or n, the map tile intersects with the corners of MapExtent, such as A, C, G, I.

In fact, map navigation, zooming in, and zooming out imply changes of MapExtent. For map navigation, the changes result from transfer of MapCenter. Updates of map tiles happen inside the same layer. However, MapCenter remains unchanged when zooming in or zooming out is conducted. MapExtent is reduced or expanded by a certain factor. Every time when zooming in or zooming out is activated, intersection calculation is then transferred to a lower or upper layer which results in replacement of current map tiles to those from another layer.

Case study

Data preprocessing

This paper employs taxi trajectory data from Shanghai on a certain day as experimental data. The data are stored in CSV format, and require 2.5 GB of disk space, for a total of 48,181,838 records. Each record includes time, taxi identity, longitude, latitude, availability, and driving speed. The experiment environment consists of a computer with Intel Core 2 CPU (2.26 GHz), 3 GB memory space, 500 GB hard disk. C# is used to implement the above procedures and algorithms. Trajectory data are managed by Microsoft SQL Server 2005. 47,786,795 valid records, involving 18,656 taxis remain after spatial outliers are detected and removed. Before conducting experiments, we convert geographical coordinates (i.e., latitude and longitude) to projection coordinates. Table 1 shows part of trajectory data after preprocessing. Column X and column Y list the coordinates of positioning points.

Constructing image pyramid

To explore the influence of size of map tiles and pyramid layer numbers on the efficiency of pyramid construction, four experiments have been designed. The relevant parameters are given in Table 2. The four experiments construct four integrated pyramids, i.e., level = M. The boundary of Shanghai determines bound. Experiment 1 and experiment 3 construct a pyramid of six layers, from L₀ to L₅, and experiment 2 and experiment 4 construct a pyramid of five layers, from L₀ to L₄. Pyramids of experiment 1 and 2 share the same largest image resolution 16384 × 16384, and pyramids of experiment 3 and 4 share the same largest image resolution 8192 × 8192. Coordinates of positioning points and positions of image pixels where points fall are recorded in a SQL table. When creating a map tile, a query on the table is conducted. The query results include records whose corresponding image pixels are contained in the map tile where the image pixels that appear in the query results are assigned a value of 1, or 0 otherwise. In this way, a series of map tiles are created. Then the indexing structure and pyramid are built.

Based on the aforementioned principles, a software tool for visualization operations is designed. The program, whose input is the constructed image pyramid, can realize image translation by mouse dragging, and image magnification and reduction by scrolling the mouse wheel. Figure 7 shows the program interface. Part of the trajectory data are zoomed in and are illustrated in white.

Discussion

The time cost of the four experiments are demonstrated in Table 3. In each case, building the indexing structure requires the majority of computational time, while creating map tiles is of relatively lower cost. Given a specific largest image resolution, resolution of map tiles is inversely proportional to M. Table 3 also shows that a large M costs more time as compared with a large size of map tiles. This implies that it takes more time to create more and smaller images than fewer and larger ones. That’s because a new database query is conducted every time a map tile is created. The query condition is different for creating a larger image from a smaller one. However, time cost is directly related to query frequency instead of query condition. Creating more images implies greater query time. In addition, of the four experiments, the time for building each indexing structure is similar. This is because for a given data set, the computing time is in accordance with the number of records. Table 4 shows the disk space occupied by map tiles.

We also display the same data set with ESRI’s ArcMap on the same computer: positioning points start to appear gradually after about 14 min and require another 40 min to load all positioning points on the screen. For each zooming or panning operation, tens of minutes, at least, are required to render the image.. Compared with ArcMap, map operation based on the proposed approach is executed in a real-time fashion. All relevant points are displayed on the screen immediately and concurrently. The input image pyramid needs to be constructed only once and then it can be applied to different visualization applications or transplanted to other devices.

Conclusions

This paper proposes an approach that can quickly display large amounts of trajectory data at multiple scales. It first converts vector-based point data to map tiles, builds a grid-based indexing structure for the point data, and then constructs an image pyramid based on the map tiles. This approach is designed with respect to the historical features of trajectory data, namely, the efficiency of visualization and query is of greater importance than that of updating. Visualization can be realized on the basis of the constructed image pyramid. The more layers the image pyramid has, the more resolutions the image holds, thus the more displaying requirements it can meet. Given a spatial extent, only some relevant map tiles instead of all tiles are tessellated for display. When the spatial extent is of large size, map tiles in the upper layers with less detailed information will be displayed. When the displaying area is small, map tiles in the lower layers with more detailed information will be displayed. To validate the proposed approach, a case study is provided, and the experimental result shows that our approach outperforms the existing commercial software. With respect to the excellent efficiency of the proposed approach, in the future, it will be applied to visualization process of specific points. For example, “locations of all taxis at a certain time instant,” “locations of all taxis that are loaded in a certain time instant,” “routes of a taxi in a certain period of time,” etc. When a query on a trajectory database is executed, a new image pyramid can be constructed for the selected points and applied to the visualization process. The visualization results can assist with more focused data analysis, such as detecting taxi hotspots and rush hours.

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