Indexing large-scale GPS tracks

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.

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.