不确定移动对象的模糊时空范围查询  

Fuzzy Spatio-Temporal Range Querying over Uncertain Moving Objects

作　　者：陈逸菲[1,2] 秦小麟 李博涵 

机构地区：[1]南京航空航天学计算机科学与技术学院,南京210016 [2]南京信息工程大学信息与控制学院,南京210044

出　　处：《计算机研究与发展》2012年第10期2161-2170,共10页Journal of Computer Research and Development

基　　金：高等学校博士学科点专项科研基金项目(20103218110017);江苏省科技支撑计划资助项目(BE2008135);中国博士后科学基金项目(20100481133)

摘　　要：指出不确定性和模糊性在时空语义上的区别;提出不确定移动对象的模糊时空范围查询问题,即查询条件中时间、空间范围的外延是模糊的,无清晰的边界,而目标对象的位置不确定;用模糊集表示模糊查询条件,概率密度函数表示移动对象在各自不确定区域内的可能位置分布;给出了不确定对象关于模糊查询条件匹配度的计算方法;设计了基于α截集的无效对象排除和有效对象确认规则及查询算法.算法规则适用于任意概率密度分布.现有的确定或不确定范围查询可以看成是模糊时空范围查询的特例.通过实验验证了算法的效率,在各种参数设置下。Uncertainty and fuzziness are semantically different in spatio-temporal data management and related applications. We propose a novel type of query, namely fuzzy spatio-temporal range （FSTR） query over uncertain moving objects, which simultaneously integrates the location uncertainty and the users＇ preferences expressed qualitatively with fuzzy conditions or items. Both the temporal and spatial searching conditions in FSTR queries are vague, namely they have no crisp boundaries. FSTR queries are executed on the uncertain datasets. To address these two kinds of indeterminate phenomena, we utilize fuzzy sets and probability density functions （pdfs） to represent fuzzy querying conditions and the possible distributions of objects＇ locations respectively. We present the qualifying guarantee evaluation of objects about vague query conditions, and propose pruning techniques based on the a-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. The approach here makes no assumption on objects＇ pdfs and is applicable to arbitrary kind of pdfs. FSTR queries can be taken as the general form of existing certain or uncertain range queries. An empirical study has been conducted to demonstrate the efficiency and effectiveness of algorithms under various experimental settings. The experiment results show that about 30~90~ objects in the query results are obtained by the proposed rules directly without costly matching degree evaluation.

关 键 词：位置服务 移动对象 不确定性 模糊性 时空范围查询 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]