Article Preview
TopIntroduction
Moving Object Databases (MOD) (Güting et al., 2000) and more specifically Trajectory Databases (TD) being at the core of spatio-temporal database research, have emerged due to the explosion of mobile devices and positioning technologies. A MOD is the basic component of any mobility-centric application (Kargin, Basoglu, & Daim, 2009). However, although such LBS applications are already in the air for some years, the services currently provided are rather naive, not exploiting the current software capabilities and the recent advances in MOD research field. We argue that one of the reasons for this is due to the common practice in existing approaches, which provides services to mobile users by just taking into account the current location-time and velocity information, arriving at the MOD server as a sequence of updates. Given this model and the fact that LBS applications need to handle huge volumes of data, it rationally arises that performance is a significant problem; therefore, efficient query processing and indexing techniques should be applied. Moreover, this model has limited applicability in real-world applications, since safe estimations about future positions should involve past positions as well.
The key observation that motivates Hermes is that the more the knowledge in hand about the trajectory of a mobile user, the better the exploitation of the advances in spatio-temporal query processing for providing intelligent LBS. Based on this motivation, the aim of this paper is to describe a robust framework capable of aiding either an analyst working with mobility data, or more technically, a developer who models, queries a TD and builds a mobility-centric application on top of the TD.
Moreover, given the ubiquitousness of location-aware devices, databases handling moving objects will, sooner or later, face enormous volumes of data. It consequently arises that performance in the presence of vast data sizes, is a significant problem for moving object databases and the only way to deal with such enormous sizes is the exploitation of specialized access methods used for spatio-temporal indexing purposes. The domain of spatio-temporal indexing, as well as other related domains, such as multimedia (Chatterjee, & Chen, 2010) and spatial indexing, is dominated by the presence of the R-tree, along with its variations and extensions. Among others, 3D R-trees (Theodoridis, Vazirgiannis, & Sellis, 1996), TB-trees and STR-trees (Pfoser, Jensen, & Theodoridis 2000), and PA-trees (Ni, & Ravishankar, 2007) are considered as extensions of the R-tree in the spatio-temporal domain. As in the case of appropriate moving object data types and methods for extending the type system of ORDBMS, except the well-known R-trees, which are suitable only for static spatial data, none of the above proposals have been incorporated into existing ORDBMS. Among them, the Trajectory Bundle tree (TB-tree) (Pfoser et al., 2000), is adopted in this work and appropriately designed and implemented inside Hermes taking advantage of the indexing extensibility interface of ORDBMS. Being a member of the R-tree family, TB-tree is able to support traditional queries such as range and distance-based queries. At the same time, it supports objects moving on the unconstrained space, and is the only one that fulfills the need for trajectory preservation so as to efficiently support trajectory-based operations.
Furthermore, apart from simple query operators (e.g. range queries) natively supported by R-trees, there is a variety of spatio-temporal operators which require more sophisticated query processing techniques in order to be efficiently processed. Among them, an important class of queries is the so-called k nearest neighbor (k-NN) search, where one is interested in finding the k closest trajectories to a predefined query object Q (stationary or moving). Thus, one of the challenges being present in the domain of trajectory databases is to develop mechanisms to perform k-NN search on MODs exploiting spatio-temporal indexes storing historical information. Among the solutions proposed in the literature we adopt the one proposed by (Frentzos, Gratsias, Pelekis, & Theodoridis 2007) which efficiently supports Nearest Neighbor (NN) queries over historical trajectory data.