Uncertain Distance-Based Range Queries over Uncertain Moving Objects

被引:2
作者
陈逸菲 [1 ,2 ,3 ]
秦小麟 [1 ,3 ]
刘亮 [1 ,3 ]
机构
[1] College of Information Science and Technology,Nanjing University of Aeronautics and Astronautics
[2] College of Information and Control,Nanjing University of Information Science and Technology
[3] CCF
关键词
moving objects; uncertainty; distance-based range query;
D O I
暂无
中图分类号
TP391.3 [检索机];
学科分类号
081203 ; 0835 ;
摘要
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.
引用
收藏
页码:982 / 998
页数:17
相关论文
共 6 条
[1]   Range search on multidimensional uncertain data [J].
Tao, Yufei ;
Xiao, Xiaokui ;
Cheng, Reynold .
ACM TRANSACTIONS ON DATABASE SYSTEMS, 2007, 32 (03)
[2]   Indexing future trajectories of moving objects in a constrained network [J].
Chen, Ji-Dong ;
Meng, Xiao-Feng .
JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY, 2007, 22 (02) :245-251
[3]   Indexing the Trajectories of Moving Objects in Networks* [J].
Victor Teixeira de Almeida ;
Ralf Hartmut Güting .
GeoInformatica, 2005, 9 :33-60
[4]   A framework for generating network-based moving objects [J].
Brinkhoff, T .
GEOINFORMATICA, 2002, 6 (02) :153-180
[5]   Indexing the positions of continuously moving objects [J].
Saltenis, S ;
Jensen, CS ;
Leutenegger, ST ;
Lopez, MA .
SIGMOD RECORD, 2000, 29 (02) :331-342
[6]   Updating and querying databases that track mobile units [J].
Wolfson, O ;
Sistla, AP ;
Chamberlain, S ;
Yesha, Y .
DISTRIBUTED AND PARALLEL DATABASES, 1999, 7 (03) :257-287