SMe: explicit & implicit constrained-space probabilistic threshold range queries for moving objects

详细信息    查看全文

• 作者：Zhi-Jie Wang ; Bin Yao ; Reynold Cheng ; Xiaofeng Gao ; Lei Zou ; Haibing Guan…
• 关键词：Probabilistic threshold range query ; Uncertain objects ; Obstacles ; Query processing ; Indexing
• 刊名：GeoInformatica
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：20
• 期：1
• 页码：19-58
• 全文大小：4,533 KB
• 参考文献：1.Albinsson P-A, Zhai S (2003) High precision touch screen interaction. In: International Conference on Human Factors in Computing Systems (CHI), pages 105–112
  2.Ali ME, Tanin E, Zhang R, Ramamohanarao K (2012) Probabilistic voronoi diagrams for probabilistic moving nearest neighbor queries. Data and Knowledge Engineering (DKE) 75:1–33CrossRef
  3.Chaudhuri S, Das G, Hristidis V, Weikum G (2004) Probabilistic ranking of database query results. In: International Conference on Very Large Data Bases (VLDB), pp 888–899
  4.Cheema MA, Brankovic L, Lin X, Zhang W, Wang W. (2010) Multi-guarded safe zone: An effective technique to monitor moving circular range queries.. In: IEEE International Conference on Data Engineering (ICDE), pp 189–200
  5.Chen J, Cheng R (2007) Efficient evaluation of imprecise location dependent queries. In: IEEE International Conference on Data Engineering (ICDE), pp 586–595
  6.Cheng R, Chen L, Chen J, Xie X (2009) Evaluating probability threshold k-nearest-neighbor queries over uncertain data. In: International Conference on Extending Database Technology (EDBT), pp 672–683
  7.Cheng R, Kalashnikov DV, Prabhakar S (2004) Querying imprecise data in moving object environments. IEEE Transactions on Knowledge and Data Engineering (TKDE) 16(9):1112–1127CrossRef
  8.Cheng R, Xia Y, Prabhakar S, Shah R, Vitter JS (2004) Efficient indexing methods for probabilistic threshold queries over uncertain data. In: International Conference on Very Large Data Bases (VLDB), pp 876–887
  9.Chung BSE, Lee W-C, Chen ALP (2009) Processing probabilistic spatio-temporal range queries over moving objects with uncertainty. In: International Conference on Extending Database Technology (EDBT), pp 60–71
  10.Cui B, Lin D, Impact K.-L. Tan. (2006) A twin-index framework for efficient moving object query processing. Data and Knowledge Engineering (DKE) 59(1):63–85CrossRef
  11.Duwaer AL (1993) Data processing system with a touch screen and a digitizing tablet, both integrated in an input device. US Patent, 5231381
  12.Gao Y, Zheng B (2009) Continuous obstructed nearest neighbor queries in spatial databases. In: ACM International Conference on Management of Data (SIGMOD), pp 577–589
  13.Gedik B, Wu K-L, Yu PS, Liu L (2006) Processing moving queries over moving objects using motion-adaptive indexes. IEEE Transactions on Knowledge and Data Engineering (TKDE) 18(5):651–668CrossRef
  14.Hofmann MO, McGovern A, Whitebread KR (1998) Mobile agents on the digital battlefield. In: Agents, pp 219–225
  15.Hu H, Xu J, Lee DL (2005) A generic framework for monitoring continuous spatial queries over moving objects. In: ACM International Conference on Management of Data (SIGMOD), pp 479–490
  16.Hua M, Pei J, Zhang W, Lin X (2008) Ranking queries on uncertain data: a probabilistic threshold approach. In: ACM International Conference on Management of Data (SIGMOD), pp 673–686
  17.Kuijpers B, databases W. Othman. Trajectory (2010) Data models, uncertainty and complete query languages. Journal of Computer and System Sciences (JCSS) 76 (7):538–560CrossRef
  18.McCarthy M, He Z, Wang XS (2014) Evaluation of range queries with predicates on moving objects. IEEE Transactions on Knowledge and Data Engineering (TKDE) 26(5):1144–1157CrossRef
  19.Mokbel MF, Aref WG (2008) Sole: scalable on-line execution of continuous queries on spatio-temporal data streams. The VLDB Journal (VLDB J.) 17(5):971–995CrossRef
  20.Mokbel MF, Xiong X, Sina W., Aref G. (2004) Scalable incremental processing of continuous queries in spatio-temporal databases. In: ACM International Conference on Management of Data (SIGMOD), pp 623–634
  21.Mokhtar H, Su J, Ibarra OH (2002) On moving object queries. In: International Symposium on Principles of Database Systems (PODS), pp 188–198
  22.Murphy RR (2014) Disaster Robotics. The MIT Press, Cambridge
  23.Olteanu D, Wen H. (2012) Ranking query answers in probabilistic databases: Complexity and efficient algorithms. In: IEEE International Conference on Data Engineering (ICDE), pp 282–293
  24.Pfoser D, Jensen CS (1999) Capturing the uncertainty of moving-object representations. In: International Symposium on Advances in Spatial Databases (SSD), pp 111–132
  25.Prabhakar S, Xia Y, Kalashnikov DV, Aref WG, Hambrusch SE (2002) Query indexing and velocity constrained indexing: Scalable techniques for continuous queries on moving objects. IEEE Transactions on Computers (TC) 51(10):1124–1140CrossRef
  26.Qi Y, Jain R, Singh S, Prabhakar S (2010) Threshold query optimization for uncertain data. In: ACM International Conference on Management of Data (SIGMOD), pp 315–326
  27.Sidlauskas D, Saltenis S, Jensen CS (2012) Parallel main-memory indexing for moving-object query and update workloads. In: ACM International Conference on Management of Data (SIGMOD) , pp 37–48
  28.Sistla AP, Wolfson O, Chamberlain S, Dao S (1997) Modeling and querying moving objects. In: IEEE International Conference on Data Engineering (ICDE), pp 422–432
  29.Sistla AP, Wolfson O, Chamberlain S, Dao S (1997) Querying the uncertain position of moving objects. In: Temporal Databases, pp 310–337
  30.Sultana N, Hashem T, Kulik L (2014) Group nearest neighbor queries in the presence of obstacles. In: ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL/GIS), pp 481–484
  31.Sun W, Chen C, Zheng B, Chen C, Zhu L, Liu W, Huang Y (2013) Merged aggregate nearest neighbor query processing in road networks. In: ACM Conference on Information and Knowledge Management (CIKM), pp 2243–2248
  32.Tao Y, Cheng R, Xiao X, Ngai WK, Kao B, Prabhakar S (2005) Indexing multi-dimensional uncertain data with arbitrary probability density functions. In: International Conference on Very Large Data Bases (VLDB), pp 922–933
  33.Tao Y, Papadias D, Sun J (2003) The tpr*-tree: An optimized spatio-temporal access method for predictive queries. In: International Conference on Very Large Data Bases (VLDB), pp 790–801
  34.Tao Y., Xiao X., Cheng R. (2007) Range search on multidimensional uncertain data. ACM Transactions on Database Systems (TODS) 32(3)
  35.Trajcevski G (2003) Probabilistic range queries in moving objects databases with uncertainty. In: International ACM Workshop on Data Engineering for Wireless and Mobile Access (MobiDE), pp 39–45
  36.Trajcevski G, Choudhary AN, Wolfson O, Ye L, Li G (2010) Uncertain range queries for necklaces. In: International Conference on Mobile Data Management (MDM), pp 199–208
  37.Trajcevski G, Wolfson O, Hinrichs K, Chamberlain S (2004) Managing uncertainty in moving objects databases. ACM Transactions on Database Systems (TODS) 29(3):463–507CrossRef
  38.Wang H, Zimmermann R (2011) Processing of continuous location-based range queries on moving objects in road networks. IEEE Transactions on Knowledge and Data Engineering (TKDE) 23(7):1065–1078CrossRef
  39.Wang Z-J, Wang D-H, Yao B, Guo M (2015) Probabilistic range query over uncertain moving objects in constrained two-dimensional space. IEEE Transactions on Knowledge and Data Engineering (TKDE) 27(3):866–879CrossRef
  40.Wolfson O, Sistla AP, Chamberlain S, Yesha Y (1999) Updating and querying databases that track mobile units. Distributed and Parallel Databases (DPD) 7(3):257–387CrossRef
  41.Wolfson O, Xu B, Chamberlain S, Jiang L (1998) Moving objects databases: Issues and solutions. In: International Conference on Scientific and Statistical Database Management (SSDBM), pp 111–122
  42.Wu K-L, Chen S-K, Yu PS (2006) Incremental processing of continual range queries over moving objects. IEEE Transactions on Knowledge and Data Engineering (TKDE) 18(11):1560–1575CrossRef
  43.Xie X, Lu H, Pedersen TB (2013) Efficient distance-aware query evaluation on indoor moving objects. In: IEEE International Conference on Data Engineering (ICDE), pp 434–445
  44.Yuan Y, Chen L, Wang G (2010) Efficiently answering probability threshold-based shortest path queries over uncertain graphs. In: International Conference on Database Systems for Advanced Applications (DASFAA), pp 155–170
  45.Zhang M, Chen S, Jensen CS, Ooi BC, Zhang Z (2009) Effectively indexing uncertain moving objects for predictive queries. Proceedings of the VLDB Endowment (PVLDB) 2(1):1198–1209CrossRef
  46.Zhang R, Jagadish HV, Dai BT, Ramamohanarao K (2010) Optimized algorithms for predictive range and knn queries on moving objects. Information Systems (IS) 35(8):911–932CrossRef
  47.Zhang Y, Lin X, Tao Y, Zhang W, Wang H (2012) Efficient computation of range aggregates against uncertain location-based queries. IEEE Transactions on Knowledge and Data Engineering (TKDE) 24(7):1244–1258CrossRef
  48.Zheng K, Trajcevski G, Zhou X, Scheuermann P (2011) Probabilistic range queries for uncertain trajectories on road networks. In: International Conference on Extending Database Technology (EDBT), pp 283–294
  
• 作者单位：Zhi-Jie Wang (1)
  Bin Yao (1)
  Reynold Cheng (2)
  Xiaofeng Gao (1)
  Lei Zou (3)
  Haibing Guan (1)
  Minyi Guo (1)
  
  1. Shanghai Key Laboratory of Scalable Computing and Systems, Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai, China
  2. Department of Computer Science, University of Hong Kong, Hongkong, China
  3. Institute of Computer Science and Technology, Peking University, Beijing, China
  
• 刊物类别：Earth and Environmental Science
• 刊物主题：Geography
  Geographical Information Systems and Cartography
  Data Structures, Cryptology and Information Theory
  Computer Science, general
  Information Storage and Retrieval
  Multimedia Information Systems
  
• 出版者：Springer Netherlands
• ISSN：1573-7624

文摘

This paper studies the constrained-space probabilistic threshold range query (CSPTRQ) for moving objects, where objects move in a constrained-space (i.e., objects are forbidden to be located in some specific areas), and objects’ locations are uncertain. We differentiate two forms of CSPTRQs: explicit and implicit ones. Specifically, for each moving object o, we model its location uncertainty as a closed region, u, together with a probability density function. We also model a query range, R, as an arbitrary polygon. An explicit query can be reduced to a search (over all the u) that returns a set of tuples in form of (o, p) such that p ≥ p _t , where p is the probability of o being located in R, and 0≤p _t ≤ 1 is a given probabilistic threshold. In contrast, an implicit query returns only a set of objects (without attaching the specific probability information), whose probabilities being located in R are higher than p _t . The CSPTRQ is a variant of the traditional probabilistic threshold range query (PTRQ). As objects moving in a constrained-space are common, clearly, it can also find many applications. At the first sight, our problem can be easily tackled by extending existing methods used to answer the PTRQ. Unfortunately, those classical techniques are not well suitable for our problem, due to a set of new challenges. Another method used to answer the constrained-space probabilistic range query (CSPRQ) can be easily extended to tackle our problem, but a simple adaptation of this method is inefficient, due to its weak pruning/validating capability. To solve our problem, we develop targeted solutions that are easy-to-understand and also easy-to-implement. Our central idea is to swap the order of geometric operations and to compute the appearance probability in a multi-step manner. We demonstrate the efficiency and effectiveness of the proposed methods through extensive experiments. Meanwhile, from the experimental results, we further perceive the difference between explicit and implicit queries; this finding is interesting and also meaningful especially for the topics of other types of probabilistic threshold queries. Keywords Probabilistic threshold range query Uncertain objects Obstacles Query processing Indexing