Processing Moving Queries over MovingObjects Using Motion-Adaptive IndexesBuggra Gedik, Student Member, IEEE Computer Society, Kun-Lung Wu, Senior Member, IEEE,Philip S. Yu, Fellow, IEEE, and Ling Liu, Senior Member, IEEEAbstract—This paper describes a motion-adaptive indexing scheme for efficient evaluation of moving continual queries (MCQs) overmoving objects. It uses the concept of motion-sensitive bounding boxes (MSBs) to model moving objects and moving queries. Thesebounding boxes automatically adapt their sizes to the dynamic motion behaviors of individual objects. Instead of indexing frequentlychanging object positions, we index less frequently changing object and query MSBs, where updates to the bounding boxes areneeded only when objects and queries move across the boundaries of their boxes. This helps decrease the number of updates to theindexes. More importantly, we use predictive query results to optimistically precalculate query results, decreasing the number ofsearches on the indexes. Motion-sensitive bounding boxes are used to incrementally update the predictive query results. Furthermore,we introduce the concepts of guaranteed safe radius and optimistic safe radius to extend our motion-adaptive indexing scheme toevaluating moving continual k -nearest neighbor ðkNNÞ queries. Our experiments show that the proposed motion-adaptive indexingscheme is efficient for the evaluation of both moving continual range queries and moving continual kNN queries.Index Terms—Moving object databases, spatio-temporal indexing, continual queries.æ1INTRODUCTIONWITH the continued advances in mobile computing andpositioning technologies, such as GPS [16], locationmanagement has become an active area of research. Severalresearch efforts have been made to address the problem ofindexing moving objects or moving object trajectories tosupport efficient evaluation of continual spatial queries.Our focus in this paper is on moving continual queries overmoving objects (MCQs for short). There are two major typesof MCQs: moving continual range queries and moving continualk-nearest neighbor queries.Efficient evaluation of MCQs is an important issue inboth mobile systems and moving object tracking systems.Research on evaluating range queries over moving objectpositions has so far focused on static continual rangequeries [19], [11], [3]. A static continual range queryspecifies a spatial range together with a time interval andtracks the set of objects that locate within this spatial regionover the given time period. The result of the query changesas the objects being queried move over time. Althoughsimilar, a moving continual range query exhibits somefundamental differences when compared to a static con-tinual range query. A moving continual range query has anassociated moving object, called the focal object of the query[7]; the spatial region of the query moves continuously asthe query’s focal object moves. Moving continual queriesintroduce a new challenge in indexing, due mainly to thehighly dynamic nature of both queries and objects.MCQs have different applications, such as environmentalawareness, object tracking and monitoring, location-basedservices, virtual environments, and computer games, toname a few. Here is an example of a moving continualquery, MCQ1: “Give me the positions of those customerswho are looking for taxis and are within five miles (of mylocation at each instant of time or at an interval of everyminute) during the next 20 minutes,” posted by a taxi driveron the road. The focal object of MCQ1is the taxi on theroad. Another example is MCQ2: “Give me the number offriendly units within a five-mile radius around me duringthe next two hours,” posted by a soldier equipped withmobile devices marching in the field, or a moving tank in amilitary setting. The focal object of MCQ2is the soldiermarching in the field or the moving tank.Different specializations of MCQs can result in inter-esting classes of MCQs. One is called moving continualqueries over static objects, where the target objects arestationary objects in the query region. An example of sucha query is MCQ3: “Give me the locations and names ofthe gas stations offering gasoline for less than $1.20 pergallon within 10 miles, during the next half an hour,”posted by a driver of a moving car, where the focal objectof the query is the car on the move and the target objectsare the gas stations within 10 miles with respect to thelocation of the car. Another interesting specialization isthe so called static continual queries over moving objects,where the queries are posed with static focal objects orwithout focal objects. An example query is MCQ4: “Giveme the list of AAA vehicles that are currently on servicecall in downtown Atlanta (or five miles from my officelocation), during the next hour.” Note that these specia-lizations of MCQs are computationally easier to evaluate.Our focus in this paper is the evaluation of MCQs in theirmost general form, such as MCQ1and MCQ2.Due to frequent updates to the index structures, tradi-tional indexing approaches built on moving object positionsgenerally do not work well for MCQs [19], [11]. In order totackle this problem, several researchers have introducedalternative approaches based on the idea of indexing theIEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 18, NO. 5, MAY 2006 651. B. Gedik and L. Liu are with the College of Computing, Georgia Institute ofTechnology, 801 Atlantic Drive, Atlanta, GA 30332-0280.E-mail: {bgedik, lingliu}@cc.gatech.edu.. K.-L. Wu and P.S. Yu are with the IBM T.J. Watson Research Center, 19Skyline Drive, Hawthorne, NY 10532. E-mail: {klwu, psyu}@us.ibm.com.Manuscript received 6 Jan. 2005; revised 7 Sept. 2005; accepted 25 Oct. 2005;published online 17 Mar. 2006.For information on obtaining reprints of this article, please send e-mail to:[email protected], and reference IEEECS Log Number TKDE-0011-0105.1041-4347/06/$20.00 ß 2006 IEEE Published by the IEEE Computer Societyparameters of the motion functions of the moving objects[12], [20], [24], [1]. They effectively alleviate the problem offrequent updates to the indexes, as the indexes need to beupdated only when the parameters change. These ap-proaches are mostly based on R-tree-like structures andproduce time-parameterized minimum bounding rectanglesthat enlarge continuously [20], [24], [19]. As a consequenceof enlarged bounding rectangles, the search performancecan deteriorate over