Indexing large-scale GPS tracks

• US 8,078,394 B2
• Filed: 02/26/2008
• Issued: 12/13/2011
• Est. Priority Date: 02/26/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Longhao, Zheng, Yu, Xie, Xing, Ma, Wei-Ying
• Primary Examiner(s): To, Tuan C.
• Application Number:
  US12/037,263
• Publication Number:
  US 20090216787A1
• Time in Patent Office: 1,386 Days
• Field of Search: 701/201, 340/995.13, 707100-102, 706/52
• US Class Current: 701/201
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/2477 Temporal data queries
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

Described is a technology by which uploaded GPS data is indexed according to spatio-temporal relationships to facilitate efficient insertion and retrieval. The indexes may be converted to significantly smaller-sized data structures when new updates to that structure are not likely. GPS data is processed into a track of spatially-partitioned segments such that each segment has a cell. Each cell has an associated temporal index (a compressed start-end tree), into which data for that cell'"'"'s segments are inserted. The temporal index may include an end time index that relates each segment'"'"'s end time to a matching start time index. Given query input comprising a spatial predicate and a temporal predicate, tracks may be searched for by determining which spatial candidate cells may contain matching results. For each candidate cell, the search accesses the cell'"'"'s associated temporal index to find any track or tracks that correspond to the temporal predicate.

Claims

1. In a computing environment, a method comprising:

using a computing device for;

processing GPS data into a track of segments as partitioned by a spatial grid such that each segment has a corresponding grid cell; and

for each segment, inserting data representative of that segment into a temporal index associated with the grid cell corresponding to that segment, including creating an entry for that segment based on an end time of that segment and an entry based on a start time of that segment;

searching for at least one track of GPS data using the temporal index.

2. The method of claim 1 further comprising,

searching for at least one resulting track based upon an input spatial predicate and temporal predicate, including by determining which spatial grid cell or cells are candidate cells for the resulting track, and for each candidate cell, accessing its associated temporal index to find any track or tracks that correspond to the temporal predicate.

3. The method of claim 1 wherein creating the entry for that segment based on the end time comprises using the end time to determine a key to an end time index, with a value associated with the key comprising a pointer to a start time index containing a start time entry for that segment.

4. The method of claim 1 wherein creating the entry for that segment based on the start time comprises using the start time as a key to a start time index, with a value associated with the key comprising an end time of that segment and an identifier of the track.

5. The method of claim 4 wherein the end time index indexes a group of segments each within a time range, and further comprising, creating a new start time index when a number of segments in the group exceed a partition threshold.

6. The method of claim 1 further comprising, compressing the temporal index from one data structure into a data structure that uses less storage space.

7. The method of claim 1 further comprising, determining whether the temporal index has a low likelihood of being updated, and if so, compressing the temporal index from one data structure into a data structure that uses less storage space.

8. The method of claim 7 wherein determining whether the temporal index has a low likelihood of being updated comprises evaluating a time of last update of the temporal index.

9. The method of claim 1 wherein creating the entry for the segment based on the end time comprises using the end time to determine a key to an end time index, with a value associated with the key comprising a pointer to a start time index containing a start time entry for that segment, and wherein creating the entry for that segment based on the start time comprises using the start time as a key to the start time index, with a value associated with the key comprising the end time of that segment and an identifier of the track.

10. In a computing environment, a system comprising:

a general purpose computing device;

a computer program comprising program modules executable by the general purpose computing device, comprising;

an insertion logic module that builds compressed start-end trees from sets of GPS data;

a search logic module that searches among compressed start-end trees to find one or more tracks corresponding to a subset of GPS data that match a spatio-temporal input request; and

compression logic that converts at least one of the compressed start-end trees from one data structure type to another based on a likelihood of each compressed start-end tree being updated according to subsequently-received GPS data.

11. The system of claim 10 wherein each compressed start-end tree comprises a B+ tree, a B-tree, R-tree, or a binary tree, and wherein the compression logic converts a B+ tree, a B-tree, R-tree, or binary tree into an array structure or table structure.

12. The system of claim 10 wherein each compressed start-end tree comprises a B+ tree, and wherein the compression logic converts each B+ tree to a dynamic array when the likelihood of that compressed start-end tree being updated is low.

13. The system of claim 10 wherein the insertion mechanism determines segments of a track according to spatially partitioned cells, and for each segment, inserts start and end time data representative of that segment into a particular compressed start-end tree associated with the cell corresponding to that segment.

14. The system of claim 10 wherein each compressed start-end tree comprises an end time index that contains the end time data for a plurality of segments.

15. The system of claim 14 wherein each compressed start-end tree comprises a plurality of start time indexes, with each segment grouped into an associated one of the indexes based on its end time, and wherein the end time index contains a reference to the one start time index that is associated with each segment.

16. One or more computer-readable storage devices having stored thereon a data structure, comprising:

an end time index that contains entries corresponding to a plurality of end times for segments that have common spatial relationships;

a plurality of start time indexes, each start time index containing entries for start times of segments that have end times within a time range corresponding to that index; and

wherein the data structure may be identified relative to other data structures based on spatial data, and searched via temporal data to determine from the start times and end times one or more tracks that are associated with one or more segments that correspond to the temporal data.

17. The one or more computer-readable storage devices of claim 16 wherein the end time of each segment determines a key in the end time index that is used to determine which start time index is associated with that segment.

18. The one or more computer-readable storage devices of claim 16 wherein the start time of each segment is used as a key to the start time index to determine which track is associated with that segment.

19. The one or more computer-readable storage devices of claim 16 wherein the start time of each segment is used as a key to the start time index to determine the end time of that segment.

20. The one or more computer-readable storage devices of claim 16 wherein the data structure may be converted from a tree structure to an array or table structure.