IntroductionRelated WorkIndexing and Query Processing of MotionModel and AssumptionsNative Space Indexing Technique (NSI)Parametric Space Indexing Technique (PSI)Empirical EvaluationConclusionQuerying Mobile Objects in Spatio-TemporalDatabasesKriengkrai Porkaew1, Iosif Lazaridis2, and Sharad Mehrotra21King Mongkut’s University of Technology at Thonburi, Thailand2University of California, Irvine, USAAbstract. In dynamic spatio-temporal environments where objects maycontinuously move in space, maintaining consistent information aboutthe location of objects and processing motion-specific queries is a chal-lenging problem. In this paper, we focus on indexing and query process-ing techniques for mobile objects. Specifically, we develop a classificationof different types of selection queries that arise in mobile environmentsand explore efficient algorithms to evaluate them. Query processing algo-rithms are developed for both native space and parametric space indexingtechniques. A performance study compares the two indexing strategiesfor different types of queries.1 IntroductionIncreasingly, emerging application domains require database management sys-tems to represent mobile objects and support querying on the motion propertiesof objects [16,5,12]. For example, a traffic monitoring application may requirestorage of information about mobile vehicles (e.g., buses, taxicabs, ambulances,automobiles). Similarly, tanks, airplanes, and military formations in a war sim-ulation application need to be represented. A weather simulation would needrepresentation and querying over trajectories of various weather patterns, e.g.,storm fronts. Motion properties of objects are dynamic – i.e., the location ofmobile objects changes continuously as time passes, without an explicit updateto the database1. This is in contrast to static objects traditionally supported indatabases whose value changes only with an explicit update.Motion information of objects can be represented in the database using mo-tion parameters and location functions which compute the position of the objectin space at any time. Different such parameters and functions may be associatedwith different objects, based on the type of their motion. As an example, con-sider an object that translates linearly with constant velocity in 2-dimensionalspace. The motion parameters in this case correspond to the object’s startinglocation (xs,ys) at some initial time tsand its velocity (vx,vy) along the spatialdimensions. Using these parameters the location of the object at any future timet>tscan be determined.1Other object properties besides location can also be dynamic, e.g., fuel level of amoving vehicleC.S. Jensen et al. (Eds.): SSTD 2001, LNCS 2121, pp. 59–78, 2001.c Springer-Verlag Berlin Heidelberg 200160 K. Porkaew, I. Lazaridis, and S. MehrotraTypes of Queries: Similar to queries in traditional spatio-temporal data-bases over static objects, queries over mobile objects involve projection, selec-tion, join, and aggregation operations. In this paper, we focus on selection queriessince they are the building block for more complex SQL queries. Selection queriesmay be classified as either range or nearest neighbor queries. In the first case, ob-jects that fall within a given spatio-temporal range are retrieved. In the secondone, we are interested in objects that are relatively “closer” to the query point.The notion of proximity differs between time and the spatial dimensions.In the temporal sense, proximity means co-occurence within a certain time pe-riod. Spatially, it refers to geographical/geometrical closeness. Thus, it is highlydesirable to separate the selection predicate into spatial and temporal compo-nents, each of which can be specified in a different manner, either as a k-NearestNeighbor or Range predicate.In Fig. 1 the types of queries that are meaningful are marked with (√). Wewill now give examples of queries handled in our system.Temporal kNN Temporal RangeSpatial kNN ×√Spatial Range√ √Fig. 1. Spatio-Temporal Selection Query Classification• A Spatio-temporal Range Query is specified by both a spatial and atemporal range. An example is “retrieve all vehicles that were within a mile ofthe location (spatial range) of an accident between 4-5pm (temporal range)”.• A Temporal kNN Query is specified with a spatial range and a nearestneighbor predicate on the temporal value. An example is “retrieve the first tenvehicles that were within 100 yards (spatial range) from the scene of an accidentordered based on the difference between the time the accident occured and thetime the vehicle crossed the spatial region (temporal kNN predicate)”. Note thatin a temporal kNN query, we are sometimes interested only in the most recentpast or in upcoming future events but not in both. In such cases, the tempo-ral kNN query will expand the search only in one direction of the temporaldimension.• A Spatial kNN Query is specified with a temporal range and a kNNpredicate on the spatial dimensions. For example, “retrieve the five ambulancesthat were nearest to the location of the accident between 4-5pm”.• A Spatio-Temporal kNN Query, marked with (×) in Fig. 1, wouldspecify a kNN predicate in both the spatial and temporal dimensions. Such aquery type is not possible since it would imply that a total order existed betweenthe temporal and the spatial dimensions.Querying Mobile Objects in Spatio-Temporal Databases 61Contributions: We explore two approaches – native space indexing (NSI)and parametric space indexing (PSI) and we have developed algorithms for eval-uating all previously described query types, using both of these approaches. Inthe NSI approach, motion is indexed in the original space in which it occurs,while in the PSI approach a parametric space defined by the motion parametersof the objects is used. Work on indexing mobile objects has recently been stud-ied in [16,5,12]; we will discuss the state of the art in the following section. Thispaper makes the following contribution to the existing literature. First, whilemost existing approaches have explored techniques to support spatio-temporalrange queries over mobile objects, we also develop techniques for temporal andspatial kNN queries as described above, by appropriately adapting techniquesproposed for kNN in [11,4]. Furthermore, the emphasis of existing techniques[5,12] has been on the PSI strategy. In contrast, we explore both NSI and PSIstrategies and
View Full Document
Unlocking...