›› 2010, Vol. 25 ›› Issue (3): 415-430.

• Special Section on Trends Changing Data Management • Previous Articles     Next Articles

Efficient Location Updates for Continuous Queries over Moving Objects

Yu-Ling Hsueh1 (薛幼苓), Roger Zimmermann2, Member, ACM, Senior Member, IEEE, and Wei-Shinn Ku3 (顾维信), Member, ACM, IEEE   

  1. 1Department of Computer Science, University of Southern California, Los Angeles, LA 90089-0781, U.S.A.
    2Department of Computer Science, National University of Singapore, 117417 Singapore
    3Department of Computer Science and Software Engineering, Auburn University, Auburn, AL 36849, U.S.A.
  • Received:2009-11-03 Revised:2009-12-09 Online:2010-05-05 Published:2010-05-05
  • About author:
    Yu-Ling Hsueh received her Ph.D. and M.S. degrees in computer science from University of Southern California (USC) in 2009 and 2003, respectively. Her research interests are temporal/spatial databases, moving object processing, scalable continuous query processing and spatial data indexing. She is currently working for Teradata Corporation.
    Roger Zimmermann is an associate professor with the Department of Computer Science at the National University of Singapore (NUS) where he is also an investigator with the Interactive and Digital Media Institute (IDMI). Prior to joining NUS he held the position of research area director with the Integrated Media Systems Center (IMSC) at the University of Southern California (USC). He received his Ph.D. degree from USC in 1998. His research interests are in the areas of distributed and peer-to-peer systems, collaborative environments, streaming media architectures, georeferenced video search, and mobile location-based services. He has co-authored a book, four patents and more than a hundred conference publications, journal articles and book chapters in the areas of multimedia and information management. He is an associate editor of the ACM Computers in Entertainment magazine and the ACM Transactions on Multimedia Computing, Communications and Applications journal. He is a senior member of the IEEE and a member of ACM. %Contact him at rogerz@comp.nus.edu.sg.
    Wei-Shinn Ku received his Ph.D. degree in computer science from the University of Southern California (USC) in 2007. He also obtained both the M.S. degree in computer science and the M.S. degree in electrical engineering from USC in 2003 and 2006 respectively. He is an assistant professor with the Department of Computer Science and Software Engineering at Auburn University. His research interests include spatial and temporal data management, mobile data management, geographic information systems, and security and privacy. He has published more than 40 research papers in refereed international journals and conference proceedings. He is a member of the ACM and the IEEE.
  • Supported by:

    This work is supported by NSF of USA under Grant Nos. IIS-0534761, CNS-0831502, CNS-0855251, and NUS AcRF under Grant No. WBS R-252-050-280-101/133.

The significant overhead related to frequent location updates from moving objects often results in poor performance. As most of the location updates do not affect the query results, the network bandwidth and the battery life of moving objects are wasted. Existing solutions propose lazy updates, but such techniques generally avoid only a small fraction of all unnecessary location updates because of their basic approach (e.g., safe regions, time or distance thresholds). Furthermore, most prior work focuses on a simplified scenario where queries are either static or rarely change their positions. In this study, two novel efficient location update strategies are proposed in a trajectory movement model and an arbitrary movement model, respectively. The first strategy for a trajectory movement environment is the \emph{Adaptive Safe Region} (ASR) technique that retrieves an adjustable safe region which is continuously reconciled with the surrounding dynamic queries. The communication overhead is reduced in a highly dynamic environment where both queries and data objects change their positions frequently. In addition, we design a framework that supports multiple query types (e.g., range and c-$k$NN queries). In this framework, our query re-evaluation algorithms take advantage of ASRs and issue location probes only to the affected data objects, without flooding the system with many unnecessary location update requests. The second proposed strategy for an arbitrary movement environment is the \emph{Partition-based Lazy Update} (PLU, for short) algorithm that elevates this idea further by adopting Location Information Tables (LITs) which (a) allow each moving object to estimate possible query movements and issue a location update only when it may affect any query results and (b)~enable smart server probing that results in fewer messages. We first define the data structure of an LIT which is essentially packed with a set of surrounding query locations across the terrain and discuss the mobile-side and server-side processes in correspondence to the utilization of LITs. Simulation results confirm that both the ASR and PLU concepts improve scalability and efficiency over existing methods.


[1] Jensen C S, Lin D, Ooi B C. Query and update efficient B+-tree based indexing of moving objects. In Proc. VLDB, Toronto, Canada, Aug. 31-Sept. 3, 2004, pp.768-779.

[2] Mokbel M F, Xiong X, Aref W G. SINA: Scalable incremental processing of continuous queries in spatio-temporal databases. In Proc. SIGMOD Int. Conf. Management of Data, Paris, France, June 13-18, 2004, pp.623-634.

[3] Mouratidis K, Hadjieleftheriou M, Papadias D. Conceptual partitioning: An efficient method for continuous nearest neighbor monitoring. In Proc. SIGMOD Int. Conf. Management of Data, Baltimore, USA, Jun. 14-16, 2005, pp.634-645.

[4] Tao Y, Papadias D, Sun J. The TPR*-tree: An optimized spatio-temporal access method for predictive queries. In Proc. VLDB, Berlin, Germany, Sept. 9-12, 2003, pp.790-801.

[5] Xiong X, Mokbel M F, Aref W G. SEA-CNN: Scalable processing of continuous k-nearest neighbor queries in spatiotemporal databases. In Proc. ICDE, Tokyo, Japan, Apr. 5-8, 2005, pp.643-654.

[6] Hu H, Xu J, Lee D L. A generic framework for monitoring continuous spatial queries over moving objects. In Proc. SIGMOD Int. Conf. Management of Data, Baltimore, USA, Jun. 14-16, 2005, pp.479-490.

[7] Mouratidis K, Papadias D, Bakiras S, Tao Y. A thresholdbased algorithm for continuous monitoring of k nearest neighbors. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(11): 1451-1464.

[8] Prabhakar S, Xia Y, Kalashnikov D V, Aref W G, Hambrusch S E. Query indexing and velocity constrained indexing: Scalable techniques for continuous queries on moving objects. IEEE Transactions on Computers, 2002, 51(10): 1124-1140.

[9] Prabhakar S, Xia Y, Kalashnikov D V, Aref W G, Hambrusch S E. Query indexing and velocity constrained indexing: Scalable techniques for continuous queries on moving objects. IEEE Transactions on Computers, 2002, 51(10): 1124-1140.

[10] Cai Y, Hua K, Cao G. Processing range-monitoring queries on heterogeneous mobile objects. In Proc. MDM, Berkeley, USA, Jan. 19-22, 2004, p.27.

[11] Yuu X, Pu K Q,Koudas N. Monitoring k-nearest neighbor queries over moving objects. In Proc. ICDE, Tokyo, Japan, Apr. 5-8, 2005, pp.631-642.

[12] Saltenis S, Jensen C S, Leutenegger S T, Lopez M A. Indexing the positions of continuously moving objects. In Proc. ACM SIGMOD Int. Conf. Management of Data, Dallas, USA, May 15-18, 2000, pp.331-342.

[13] Tao Y, Faloutsos C, Papadias D, Liu B. Prediction and indexing of moving objects with unknown motion patterns. In Proc. SIGMOD Int. Conf. Management of Data, Paris, France, June 13-18, 2004, pp.611-622.

[14] Mokbel M F and Aref W G. GPAC: Generic and progressive processing of mobile queries over mobile data. In Proc. MDM, Ayia Napa, Cyprus, May 9-13, 2005, pp.155-163.

[15] Cheng R, Lam K Y, Prabhakar S, Liang B. An efficient location update mechanism for continuous queries over moving objects. Information Systems, 2007, 32(4): 593-620.

[16] Cheng R, Lam K Y, Prabhakar S, Liang B. An efficient location update mechanism for continuous queries over moving objects. Information Systems, 2007, 32(4): 593-620.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Min Yinghua; Yashwant K. Malaiya; Jin Boping;. Aliasing Errors in Parallel Signature Analyzers[J]. , 1990, 5(1): 24 -40 .
[2] Ruo-Chen Liu, Li-Cheng Jiao, and Hai-Feng Du. Clonal Strategy Algorithm Based on the Immune Memory[J]. , 2005, 20(5): 728 -734 .
[3] En-Jian Bai and Xiao-Juan Liu. Some Notes on Prime-Square Sequences[J]. , 2007, 22(3): 481 -486 .
[4] Xiao-Yong Fang, Zhi-Gang Luo, and Zheng-Hua Wang. Predicting RNA Secondary Structure Using Profile Stochastic Context-Free Grammars and Phylogenic Analysis[J]. , 2008, 23(4 ): 582 -589 .
[5] KangWoo Lee. Guiding Attention by Cooperative Cues[J]. , 2008, 23(5 ): 874 -884 .
[6] Tao Jiang, Fellow, ACM. Some Algorithmic Challenges in Genome-Wide Ortholog Assignment[J]. , 2010, 25(1): 42 -52 .
[7] Ming-Wei Zhang (张明卫), Member, CCF, Bin Zhang (张斌), Senior Member, CCF, Ying Liu (刘莹), Jun Na (那俊) and Zhi-Liang Zhu (朱志良), Senior Member, CCF. Web Service Composition Based on QoS Rules[J]. , 2010, 25(6): 1143 -1156 .
[8] Wei-Feng Pan (潘伟丰), Member, CCF, Bing Li (李兵), Senior Member, CCF, Yu-Tao Ma (马于涛), Member, CCF, ACM, Ye-Yi Qin (覃叶宜) and Xiao-Yan Zhou (周晓燕). Measuring Structural Quality of Object-Oriented Softwares via Bug Propagation Analysis on Weighted Software Networks[J]. , 2010, 25(6): 1202 -1213 .
[9] Mahshid Rahnamay-Naeini, and Masoud Sabaei. A Combinational Perspective in Stimulating Cooperation in Mobile Ad Hoc Networks[J]. , 2011, 26(2): 256 -268 .
[10] Wei Jiang (姜伟), Tian Wu (吴甜), Song-Lin Hu (虎嵩林), Senior Member, CCF, and Zhi-Yong Liu (刘志勇), Senior Member, CCF. QoS-Aware Automatic Service Composition: A Graph View[J]. , 2011, 26(5): 837 -853 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved