INDEXING LARGE-SCALE GPS TRACKS
First Claim
1. In a computing environment, a method comprising:
- 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.
2 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 Claims
-
1. In a computing environment, a method comprising:
-
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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. In a computing environment, a system comprising:
-
insertion logic that builds compressed start-end trees from sets of GPS data; search logic 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. - View Dependent Claims (11, 12, 13, 14, 15)
-
-
16. One or more computer-readable media 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. - View Dependent Claims (17, 18, 19)
-
-
20. The one or more computer-readable media of claim wherein the data structure may be converted from a tree structure to an array or table structure.
Specification