论文部分内容阅读
随着无线通信技术的快速发展和移动终端设备的不断普及,位置相关查询(Location Dependent Queries:LDQs)作为基于位置的服务(Location Based Services: LBSs)的支撑技术之一,已经成为学术界和工业界共同关注的热点问题。鉴于不确定数据广泛存在于LBSs中,以及Top-k Dominating查询是一种被广泛运用的LDQ,人们开始研究不确定数据上的Top-k Dominating查询处理方法,并取得了一些研究成果。但是这些研究只限于静态概率数据库,它们不能处理不确定数据流环境下的Top-k Dominating查询,目前国际上还未见针对不确定数据流环境下的Top-k Dominating查询的相关研究。为了高效地提供基于位置的服务,人们通常采用空间数据库外包模式来提供查询服务。在该模式中,由于服务提供者(Services Provider: SP)并不是真正的数据拥有者(Data Owner:DO),它可能受利益的驱使或者其本身缺陷,返回给客户端的结果可能是不正确的或者不可信任的。此外,查询结果在传输过程中,可能被第三方恶意攻击或者篡改,导致客户端接收到的结果是错误的和不可信任的。因此,针对位置相关查询设计高效的认证策略具有重要意义。随着位置定位技术和位置共享服务的发展,在基于位置的服务中产生了大量的空间文本对象,针对空间文本对象的处理技术应运而生,人们也提出了一些研究成果。但到目前为止,这些研究多数局限于欧氏空间,在欧氏空间下的相关技术是不能通过简单的修改便能应用到路网环境中,因此,研究路网中的空间文本对象处理技术具有较高的研究价值。首次讨论了不确定数据流的Top-k Dominating查询的处理问题,定义了如何计算不确定数据的支配分数,鉴于计算该支配分数代价较大,提出了由不确定数据的分数区间来替代支配分数的策略,并设计了逐步压缩分数区间的方法,基于滑动窗口模型提出了SWPTD算法实现对不确定数据流条件下的Top-k Dominating查询(PTOPK)。分析发现,每次滑动窗口移动将使得SWPTD重新计算PTOPK,前一个时刻的计算结果信息没有被充分利用,当滑动窗口较大时,SWPTD算法效率会降低。鉴于并非所有的非PTOPK对象在下一个时刻都能成为查询结果(PTOPK),于是计算每个非PTOPK对象的最小时间间隔,在该时间间隔内,不需考察该对象,基于此思想提出了PEA算法。模拟实验表明PEA算法相对更为高效,具有一定的应用价值。在众多位置相关查询(也称空间查询)中,反向k近邻查询(RkNN)被认为是最基础和应用最广的查询,它广泛运用于基于位置的服务、市场分析和决策支持。基于以上因素,首次研究了RkNN查询的认证问题,提出了SP端处理算法,实现对RkNN查询结果的搜索并基于Influence zone(Zk)构建紧凑的认证对象VO。同时提出两种客户端处理算法(IZ-Auth,AIZ-Auth),其中IZ-Auth是基于VO重新计算RkNN从而实现认证。鉴于位于Zk内的对象就是RkNN结果,AIZ-Auth基于对Influence zone的认证实现对RkNN查询结果的认证。理论分析了算法的复杂度。实验结果表明,所提出的算法能有效地对单色和双色RkNN查询实施认证,AIZ-Auth算法性能要优于相关算法。首次研究了路网中的空间文本反向k近邻查询问题(RSTkNN),为了高效地检索候选对象集Scan,提出了三种剪枝方法和路网扩展终止条件,介绍了RSTkNN查询处理框架。为了验证候选对象,首先提出了基于路网扩展的NE-RSTkNN验证算法;为了克服该算法需多次遍历路网的缺陷,随后提出了基于Voronoi图的VD-RSTkNN验证算法。性能评估表明所提出算法是有效的,且VD-RSTkNN算法在性能上要优于NE-RSTkNN算法。