Efficient Indexing in Moving Object Trajectories

In the last decade, there has been an explosive growth in the number of location-aware systems. Accordingly, large amounts of spatio-temporal data are accumulated. Efficient indexing and querying techniques to manage these large volumes of trajectory data sets are necessary. In this paper we propose ETB-tree (Extended TB-tree), an efficient and scalable indexing to respond the moving object trajectories related queries. Reducing the search space is the main purpose of ETB-tree to decrease the response-time of queries. In the proposed method, each trajectory is separately indexed using a distinct TB-tree. The roots of these trees participate in constructing a particular sorted link list. Every node in this linked list contains constraining information related to its associative tree in order to restrict the overall search space. According to presented results in this paper, the new indexing approach achieves much better performance than TB-tree. Finally, we will show that this indexing method is suitable to the several important categories of queries such as range queries, time slice queries, window queries, k-nearest neighbor queries, closest pair queries, or trajectory queries

Keywords:

indexing , trajectory , spatio-temporal database , TB-tree , Query