Indexing Large Trajectory Data Sets With SETIV

 

Prasad Chakka, Adam Everspaugh, Jignesh M. Patel

 

With the rapid increase in the use of

inexpensive location-aware sensors in a variety of new applications, large

amounts of time-sequenced location data will soon be accumulated.

Efficient indexing techniques for managing these large volumes of

trajectory data sets are urgently needed. The key requirements for a good

trajectory indexing technique is that it must support both searches and

inserts efficiently.

This paper proposes a new indexing mechanism called SETI, a Scalable and

Efficient Trajectory Index, that meets these requirements. SETI uses a

simple two-level index structure to decouple the indexing of the spatial

and the temporal dimensions. This decoupling makes both searches and

inserts very efficient. Based on an actual implementation in SHORE, we

demonstrate that SETI clearly outperforms two previously proposed

trajectory indexing mechanisms, namely the 3D R-tree and the TB-tree.

Unlike previously proposed trajectory indexing structures, SETI is a

logical indexing structure that uses existing spatial indexing structures,

such as R-trees, without any modifications. Consequently, database systems

that currently support R-trees can easily implement SETI, making it a both

a practical and an efficient choice for indexing trajectory data sets in

many existing database systems.