›› 2010, Vol. 25 ›› Issue (5): 982-998.doi: 10.1007/s11390-010-1078-3

• Distributed Computing and Systems • Previous Articles     Next Articles

Uncertain Distance-Based Range Queries over Uncertain Moving Objects

Yi-Fei Chen1,2 (陈逸菲), Member, CCF, Xiao-Lin Qin1,* (秦小麟), Senior Member, CCF and Liang Liu1 (刘 亮), Student Member, CCF   

  1. 1. College of Information Science and Technology, Nanjing University of Aeronautics and Astronautics Nanjing 210016, China;
    2. College of Information and Control, Nanjing University of Information Science and Technology, Nanjing 210044, China
  • Received:2009-12-02 Revised:2010-08-01 Online:2010-09-01 Published:2010-09-01
  • About author:
    Yi-Fei Chen received her B.S. degree in information engineering and M.S. degree in system analysis and integration from Nanjing University of Information Science and Technology in 2002 and 2005 respectively. She is currently a Ph.D. candidate in computer application at Nanjing University of Aeronautics and Astronautics. Her current research interests include spatio-temporal databases, moving objects databases. She is a member of CCF.
    Xiao-Lin Qin received his M.S. degree in computer application technology from Nanjing University of Aeronautics and Astronautics (NUAA). He is now a professor and Ph.D. supervisor of the College of Information Science and Technology, NUAA. His main research interests include spatio-temporal databases, secure database, data management and disaster tolerance in distributed environment and information security. He is a senior member of CCF.
    Liang Liu received his B.S. degree in software engineering from Northwestern Polytechnical University in 2005. He is currently a Ph.D. candidate in computer application at Nanjing University of Aeronautics and Astronautics. His current research interests include data management in sensor network. He is a student member of CCF.
  • Supported by:

    This work is supported by the National High Technology Research and Development 863 Program of China under Grant No. 2007AA01Z404, and the Program of Jiangsu Province under Grant No.BE2008135.

Distance-based range search is crucial in many real applications. In particular, given a database and a query issuer, a distance-based range search retrieves all the objects in the database whose distances from the query issuer are less than or equal to a given threshold. Often, due to the accuracy of positioning devices, updating protocols or characteristics of applications (for example, location privacy protection), data obtained from real world are imprecise or uncertain. Therefore, existing approaches over exact databases cannot be directly applied to the uncertain scenario. In this paper, we redefine the distance-based range query in the context of uncertain databases, namely the probabilistic uncertain distance-based range (PUDR) queries, which obtain objects with confidence guarantees. We categorize the topological relationships between uncertain objects and uncertain search ranges into six cases and present the probability evaluation in each case. It is verified by experiments that our approach outperform Monte-Carlo method utilized in most existing work in precision and time cost for uniform uncertainty distribution. This approach approximates the probabilities of objects following other practical uncertainty distribution, such as Gaussian distribution with acceptable errors. Since the retrieval of a PUDR query requires accessing all the objects in the databases, which is quite costly, we propose spatial pruning and probabilistic pruning techniques to reduce the search space. Two metrics, false positive rate and false negative rate are introduced to measure the qualities of query results. An extensive empirical study has been conducted to demonstrate the efficiency and effectiveness of our proposed algorithms under various experimental settings.

[1] Yang X, Xiao G, Wang B, Chen M. The management of uncertain moving objects. Communications of the CFF, 2009, 4(5): 21-31.

[2] Pfoser D, Jensen C S. Capturing the uncertainty of moving object representations. In Proc. SSD,1999, Hong Kong, China, Jul. 20-23, 1999, pp.111-131.

[3] Cvilis A, Jensen C S, Pakainis S. Techniques for efficient road network-based tracking of moving objects. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(5): 698-713.

[4] Almeida V T D, Güting R H. Indexing the trajectories of moving objects in networks. GeoInformatica, 2005, 9(1): 1-47.

[5] Wolfson O, Sistla A P, Chamberlain S, Yesha Y. Updating and querying databases that track mobile units. Distributed and Parallel Databases, 1999, 7(3): 257-387.

[6] Trajcevski G, Wolfson O, Chamberlain S, Zhang F. The geometry of uncertainty in moving objects databases. In Proc. the 8th Int. Conf. Extending Database Technology, Prague, Czech, Mar. 25-27, 2002, pp.233-250.

[7] Trajcevski G. Probabilistic range queries in moving objects databases with uncertainty. In Proc. MobiDE,2003, San Diego, USA, Sept. 19, 2003, pp.39-45.

[8] Cheng R, Kalashnikov D V, Prabhakar S. Querying imprecise data in moving object environments. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(9): 1112-1127.

[9] Chung B, Lee W C, Chen A L P. Processing probabilistic spatio-temporal range queries over moving objects with uncertainty. In Proc. the 12th Int. Conf. Extending Database Technology, Saint Petersburg, Russia, Mar. 24-26, 2009, pp.60-71.

[10] Chen J C, Cheng R. Efficient evaluation of imprecise location-dependent queries. In Proc. the 23rd Int. Conf. Data Engineering, Istanbul, Turkey, Apr. 15-20, 2007, pp.586-589.

[11] Ishikawa Y, Iijima Y, Yu X J. Spatial range querying for Gaussian-based imprecise query objects. In Proc. the 2009 IEEE Int. Conf. Data Engineering, Shanghai, China, Mar. 29-Apr. 2, 2009, pp.676-687.

[12] Tao Y, Xiao X, Cheng R. Range search on multidimensional uncertain data. ACM TODS, 2007, 32(3): 1-54.

[13] Ku W S, Zimmermann R, Peng W C et al. Privacy protected query processing on spatial networks. In Proc. the 23rd Int. Conf. Data Engineering, Istanbul, Turkey, Apr. 15-20, 2007, pp.215-220.

[14] Bordogna G, Pagani G, Pasi G, Psaila G. Evaluating uncertain location-based spatial queries. In Proc. the 2008 ACM Symp. Applied Computing, Fortaleza, Brazil, Mar. 16-20, 2008, pp.1095-1100.

[15] Berg M D, Kreveld M V et al. Algorithms and Application of Computational Geometry, 2nd Edition, Beijing: Tsinghua University Press, 2005.

[16] Tao Y, Cheng R, Xiao X, Ngai W K, Kao B, Prabhakar S. Indexing multi-dimensional uncertain data with arbitrary probability density functions. In Proc. the 31st Int. Conf. Very Large Data Bases, Trondheim, Norway, 2005, pp.922-933.

[17] Saltenis S, Jensen C S, Leutenegger S T, Lopez M A. Indexing the positions of continuously moving objects. ACM SIGMOD Record, 2000, 29(2): 331-342.

[18] Lian X, Chen L. Probabilistic group nearest neighbor queries in uncertain databases. TKDE, 2008, 20(6): 809-824.

[19] Brinkhoff T. A framework for generating network-based moving objects.GeoInformatica, 2002, 6(2): 153-180.

[20] Ding Z, Güting R H. Uncertainty management for network constrained moving objects. In Proc. the 15th Int. Conf. Database and Expert Systems Applications, Zaragoza, Spain, 2004, pp.411-421.

[21] Chen J, Meng X. Indexing future trajectories of moving objects in a constrained network. Journal of Computer Science and Technology, 2007, 22(2): 245-251.

No related articles found!
Full text



[1] Sun Zhongxiu; Shang Lujun;. DMODULA:A Distributed Programming Language[J]. , 1986, 1(2): 25 -31 .
[2] Zhang Bo; Zhang Ling;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[3] Meng Liming; Xu Xiaofei; Chang Huiyou; Chen Guangxi; Hu Mingzeng; Li Sheng;. A Tree-Structured Database Machine for Large Relational Database Systems[J]. , 1987, 2(4): 265 -275 .
[4] Lin Qi; Xia Peisu;. The Design and Implementation of a Very Fast Experimental Pipelining Computer[J]. , 1988, 3(1): 1 -6 .
[5] Sun Chengzheng; Tzu Yungui;. A New Method for Describing the AND-OR-Parallel Execution of Logic Programs[J]. , 1988, 3(2): 102 -112 .
[6] Zhang Bo; Zhang Tian; Zhang Jianwei; Zhang Ling;. Motion Planning for Robots with Topological Dimension Reduction Method[J]. , 1990, 5(1): 1 -16 .
[7] Zhou Di; Xu Xiangwen;. A Distributed Error Recovery Technique and Its Implementation and Application on UNIX[J]. , 1990, 5(2): 127 -138 .
[8] Wang Dingxing; Zheng Weimin; Du Xiaoli; Guo Yike;. On the Execution Mechanisms of Parallel Graph Reduction[J]. , 1990, 5(4): 333 -346 .
[9] Zhou Quan; Wei Daozheng;. A Complete Critical Path Algorithm for Test Generation of Combinational Circuits[J]. , 1991, 6(1): 74 -82 .
[10] Zhao Jinghai; Liu Shenquan;. An Environment for Rapid Prototyping of Interactive Systems[J]. , 1991, 6(2): 135 -144 .

ISSN 1000-9000(Print)

CN 11-2296/TP

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