›› 2012, Vol. ›› Issue (2): 376-396.doi: 10.1007/s11390-012-1229-9

• Machine Learning and Data Mining • Previous Articles     Next Articles

Fuzzy Distance-Based Range Queries over Uncertain Moving Objects

Yi-Fei Chen1,2 (陈逸菲), Member, CCF, Xiao-Lin Qin1,* (秦小麟), Senior Member, CCF, Liang Liu1 (刘亮), Student Member, CCF, and Bo-Han Li1 (李博涵), 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:2011-01-16 Revised:2011-08-31 Online:2012-03-05 Published:2012-03-05
  • Supported by:

    This work was supported by the National High Technology Research and Development 863 Program of China under Grant No. 2007AA01Z404, the National Research Foundation for the Doctoral Program of Higher Education of China under Grant No. 20103218110017, the Science & Technology Pillar Program of Jiangsu Province of China under Grant No. BE2008135, and the Postdoctoral Science Foundation of China under Grant No. 20100481133.

Data obtained from real world are imprecise or uncertain due to the accuracy of positioning devices, updating protocols or characteristics of applications. On the other hand, users sometimes prefer to qualitatively express their requests with vague conditions and different parts of search region are in-equally important in some applications. We address the problem of efficiently processing the fuzzy range queries for uncertain moving objects whose whereabouts in time are not known exactly, for which the basic syntax is find objects always/sometimes near to the query issuer with the qualifying guarantees no less than a given threshold during a given temporal interval. We model the location uncertainty of moving objects on the utilization of probability density functions and describe the indeterminate boundary of query range with fuzzy set. We present the qualifying guarantee evaluation of objects, and propose pruning techniques based on the ff-cut of fuzzy set to shrink the search space efficiently. We also design rules to reject non-qualifying objects and validate qualifying objects in order to avoid unnecessary costly numeric integrations in the refinement step. An extensive empirical study has been conducted to demonstrate the efficiency and effectiveness of algorithms under various experimental settings.

[1] Yang X, Xiao G, Wang B et al. The management of un-certain 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. the 6th Int. Symp. Advancesin Spatial Database (SSD 1999), Hong Kong, China, Jul. 20-23, 1999, pp.111-131.

[3] Pfoser D, Tryfnoa N, Jensen C S. Indeterminacy and spatiao-temporal data: Basic definitions and case study. GeoInfor-matica, 2005, 9(3): 211-236.

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

[5] Chen Y F, Qin X L, Liu L. Uncertain distance-based rangequery over uncertain moving objects. Journal of ComputerScience and Technology, 2010, 25(5): 982-998.

[6] Leick A. GPS Satellite Surveying (3rd Edition). Hoboken,New Jersey: J. Wiley & Sons Press, 2004.

[7] Wolfson O, Sistla A P, Chamberlain S, Yesha Y. Updatingand querying databases that track mobile units. Distributedand Parallel Databases, 1999, 7(3): 257-287.

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

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

[10] Tao Y, Xiao X, Cheng R. Range search on multidimensionaluncertain data. ACM Transactions on Database Systems,2007, 32(3).

[11] Trajcevki G, Wolfson O, Hinrichs K, Chamberlain S. Manag-ing uncertainty in moving objects databases. ACM Transac-tions on Database Systems, 2004, 29(3): 463-507.

[12] Trajcevski G. Probabilistic range queries in moving objectsdatabases with uncertainty. In Proc. MobiDE 2003, SanDiego, USA, Sep. 19, 2003, pp.39-45.

[13] Huang Y K, Lee C. Efficient evaluation of continuous spatio-temporal queries on moving objects with uncertain velocity.Geoinformatica, 2010, 14(2): 163-200.

[14] Huang E, Xiao L R. An efficient representation modelof distance distribution between two uncertain objects.http://www.comp.polyu.edu.hk/~csehung/paper/wmwa14-lncs.pdf.

[15] Schneider M. Uncertainty management for spatial data indatabases: Fuzzy spatial data types. In Proc. the 6th Int.Symp. Advances in Spatial Database (SSD 1999), Hong Kong,China, July 20-23, 1999, pp.330-351.

[16] Pauly A, Schneider M. VASA: An algebra for vague spatialdata in databases. Journal of Information Systems. 2010,35(1): 111-138.

[17] Pauly A, Schneider M. Topological predicates between vaguespatial objects. In Proc. the 9th Int. Symp. Advances in Spa-tial and Temporal Databases (SSTD 2005), Angra dos Reis,Brazil, Aug. 22-24, 2005, pp.418-432.

[18] Bordogna G, Pagani M, Pasi G, Psaila G. Evaluating uncer-tain location-based spatial queries. In Proc. the 2008 ACMSymp. Applied Computing, Fortaleza, Brazil, Mar. 16-20,2008, pp.1095-1100.

[19] Zheng K, Fung P C, Zhou X F. K-nearest neighbor search forfuzzy objects. In Proc. SIGMOD2010, Indianapolis, USA,June 6-11, 2010, pp.699-710.

[20] Tao Y F, Cheng R, Xiao X K, Ngai W K, Kao B, PrabhakarS. Indexing multi-dimensional uncertain data with arbitraryprobability density functions. In Proc. the 31st Int. Conf.Very Large Data Bases, Trondheim, Norway, Aug. 30-Sept. 2,2005, pp.922-933.

[21] Civilis A, Jensen C S, Pakainis S. Techniques for efficient roadnetwork-based tracking of moving objects. IEEE Transac-tions on Knowledge and Data Engineering, 2005, 17(5): 698-712.

[22] Zadeh L A. Fuzzy sets. Information and Control, 1965, 8(3):338-353.

[23] Li H G. The Base and Application Algorithms of FuzzyMathematics. Beijing: Science Press, 2005, pp.83-88 (in Chi-nese).

[24] Saltenis S, Jensen C S, Leutenegger S T, Lopez M A. Indexingthe positions of continuously moving objects. ACM SIGMODRecord, 2000, 29(2): 331-342.

[25] de Berg M, van Kreveld M et al. Computational Geometry:Algorithms and Applications. 2nd edition, Beijing: TsinghuaUniversity Press, 2005.

[26] Chen S, Jensen C S, Lin D. A benchmark for evaluating mov-ing object indexes. In Proc. PVLDB2008, Auckland, NewZealand, August 23-28, 2008, pp.1574-2585.

[27] Lian X, Chen L. Efficient processing of probabilistic reversenearest neighbor queries over uncertain data. The VLDBJournal, 2009, 18(3): 787-808.
No related articles found!
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

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