An Experimental Performance Comparison for Indexing Mobile Objects on the Plane

Introduction

This paper focuses on the problem of indexing mobile objects in two dimensions and efficiently answering range queries over the objects’ future locations. This problem is motivated by a set of real-life applications such as intelligent transportation systems, cellular communications, and meteorology monitoring. The basic approach uses discrete movements, where the problem of dealing with a set of moving objects can be considered as equivalent to a sequence of database snapshots of the object positions/extents taken at time instants , with each time instant denoting the moment where a change took place. From this point of view, the indexing problems in such environments can be dealt with by suitably extending indexing techniques from the area of spatio-temporal databases (Gaede & Gunther, 1998; Salzberg & Tsotras, 1999). In (Manolopoulos, Theodoridis, & Tsotras, 2000) it is exposed how these indexing techniques can be generalized to handle efficiently queries in a discrete spatio-temporal environment.

The common thrust behind these indexing structures lies in the idea of abstracting each object’s position as a continuous function of time, f(t), and updating the database whenever the function parameters change. Accordingly an object is modelled as a pair consisting of its extent at a reference time (design parameter) and of its motion vector. One categorization of the aforementioned structures is according to the family of the underlying access method used. In particular, there are approaches based either on R-trees or on Quadtrees as explained in (Raptopoulou, Vassilakopoulos, & Manolopoulos, 2004, 2006). On the other hand, these structures can be also partitioned into those that: (a) are based on geometric duality and represent the stored objects in the dual space (Agarwal, Arge, & Erickson, 2000; Kollios, Gunopulos, & Tsotras, 1999; Patel, Chen, & Chakka, 2004), and (b) leave the original representation intact by indexing data in their native dimensional space (Beckmann, Begel, Schneider, & Seeger, 1990; Papadopoulos, Kollios, Gunopulos, & Tsotras, 2002; Saltenis, Jensen, Leutenegger, & Lopez, 2000; Saltenis et al., 2001; Tao, Papadias, & Sun, 2003). The geometric duality transformation is a tool extensively used in the Computational Geometry literature, which maps hyper-planes in to points and vice-versa. In this paper we present and experimentally evaluate techniques using the duality transform as in (Kollios et al., 1999; Papadopoulos et al., 2002) to efficiently index future locations of moving points on the plane.

In the next section, we present a brief overview of the most basic practical methods. We then give a formal description of the problem. Next, we introduce the duality transform methods and then briefly present our main contribution, followed by the ISBs access method that compares favourably with the solutions of (Kollios et al., 1999; Papadopoulos et al., 2002), the TPR* index (Tao et al., 2003), the STRIPES index (Patel et al., 2004) and the LBTs index (Sioutas et al., 2007) as well. In simple words, the new solution is the most efficient in terms of update I/O performance. Moreover, with respect to the query I/O performance, solution of ISBs is 4 or 5 faster than LBTs method and outperforms STRIPES (state of the art as of now) in many settings. Finally, we present a thorough experimental evaluation, followed by a conclusion.