Indexing of Network Constrained Moving Objects Dieter Pfoser Computer Technology Institute Akteou 11 & Poulopoulou Str. Athens, Hellas +30-103416220 [email protected] Christian S. Jensen Department of Computer Science Aalborg University 9220 Aalborg Øst, Denmark +45- 96 35 89 00 [email protected] ABSTRACT With the proliferation of mobile computing, the ability to index efficiently the movements of mobile objects becomes important. Objects are typically seen as moving in two-dimensional (x,y) space, which means that their movements across time may be embedded in the three-dimensional (x,y,t) space. Further, the movements are typically represented as trajectories, sequences of connected line segments. In certain cases, movement is restricted, and specifically in this paper, we aim at exploiting that movements occur in transportation networks to reduce the dimensionality of the data. Briefly, the idea is to reduce movements to occur in one spatial dimension. As a consequence, the movement data becomes two-dimensional (x,t). The advantages of considering such lower-dimensional trajectories are the reduced overall size of the data and the lower-dimensional indexing challenge. Since off-the-shelf database management systems typically do not offer higher-dimensional indexing, this reduction in dimensionality allows us to use such DBMSes to store and index trajectories. Moreover, we argue that, given the right circumstances, indexing these dimensionality-reduced trajectories can be more efficient than using a three-dimensional index. This hypothesis is verified by an experimental study that incorporates trajectories stemming from real and synthetic road networks. Categories and Subject Descriptors H.2.8 [Database Management]: Physical Design – Access methods General Terms Algorithms, Theory Keywords Spatiotemporal databases, indexing moving objects, indexing network data, moving object databases. 1 INTRODUCTION We are currently experiencing rapid technological developments that promise widespread use of on-line mobile personal information appliances [16]. Industry analysts uniformly predict that mobile Internet terminals will significantly outnumber the desktop computers on the Internet. This proliferation of devices offers companies the opportunity to provide a diverse range of e-services. It is essential to many services, termed location-enabled services, that they be sensitive to the users' changing locations. Location awareness is made possible by a combination of political developments, e.g., the de-scrambling of the GPS signals and the US E911 mandate, and the continued advances in positioning technologies. Prominent examples of location-based services concern vehicle navigation, tracking, and monitoring, where the positions of air, sea, or land-based equipment such as airplanes, fishing boats and freighters, and cars and trucks are of interest. This paper is concerned with the indexing of the movements of mobile objects for post-processing (e.g., data mining) purposes. The size and shape of an object is often fixed and of little importance – only its position matters. Thus, the problem becomes one of recording the position of a moving object across time. The movement of an object may then be represented by a trajectory, or polyline, in the three dimensional (x,y,t) space composed from two spatial dimensions and one time dimension [14]. Depending on the particular objects and applications under consideration, the movements of the objects may be subject to constraints. Specifically, we may distinguish among three movement scenarios, namely unconstrained movement (vessels at sea), constrained movement (pedestrians), and movement in transportation networks (trains and, typically, cars) [12]. The latter scenario, which we will assume, occurs when the applications at hand are interested in the positions of the objects with respect to the transportation network. For example, we may expect that many applications will be interested only in the positions of cars with respect to the road network, rather than in their absolute coordinates. The movement effectively occurs in a different space than for the first two scenarios. When faced with a new type of data such as the movements of network-constrained objects, how to efficiently process queries against these data is an important challenge. It is instructive to consider three complementary approaches. First, we may attempt to use existing access methods, but this may either not be possible or may in itself not be efficient. Second, we may invent new access methods. These allow for more efficient indexing, but their integration into a database management system may be complex. Third, we may attempt to “model” or transform the data such that existing methods can be reused. In the context of trajectories, the first approach implies the use of, e.g., a three-dimensional R-tree to index the data. Adopting the second approach, we would develop a new trajectory index, e.g., [10] [14]. With the third approach, we might apply a transformation to the data such as the duality Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, orrepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee. GIS’03, November 7-8, 2003, New Orleans, Louisiana, USA. Copyright 2003 ACM 1-58113-730-3/03/0011…$5.00. 25transformation [6]. The second approach might be desirable in the long term, but may not be attractive in a short or medium term. For example, it took a dozen years before the R-tree found its way into some commercial database products [11]. Thus, depending on the type of data, it can prove beneficial to attempt to reuse existing access methods by applying transformations to the data. This allows for easy integration of the new type of data into commercial database systems. In this work, we lower the dimensionality of the trajectories by exploiting that the objects are constrained to a transportation network. This allows for a simplified approach to the indexing of trajectories. Our approach thus combines the first and third approaches from above. Often, dimensionality reduction is used to discover redundant dimensions in general-purpose data to avoid indexing