一种面向不确定对象的可见k近邻查询算法

真实世界中,常存在很多障碍物,影响空间对象到查询点的可见性及距离,可见k近邻查询查找距查询点最近的k个可见对象,是时空查询领域的一类重要算法.由于度量设备误差以及通信开销的限制等因素,空间对象位置不确定因素广泛存在.文中拟对不确定对象执行可见k近邻查询,提出了概率可见k近邻(PVkNN)查询,即查找前k个成为查询点最近邻居概率最大的节点.为了高效地执行这一查询,文中提出了k-界限剪枝方法,基于可见质心的紧缩过滤以及对不可见对象的剪枝策略,从空间角度过滤掉不符合条件的对象.为避免对候选集合中每个对象的概率都进行精确计算,从概率角度提出了根据概率上下限来对候选集合进行进一步的求精方法,采用近似采样技术来获取可见区域的比例,实现了对PVkNN的高效计算.采用真实和模拟数据集设计实验,充分验证了算法的效率和精度.     

一种使用简化预排序的k-支配Skyline查询算法

近年来,Skyline查询在多目标决策、数据挖掘、数据库可视化等方面得到广泛应用.然而在高维空间环境下,skyline查询因为返回的结果集过大而不能提供有用的信息.因此,学术界提出了七-支配skyline查询的概念.它通过弱化数据点之间的支配关系,使数据点间更容易产生支配关系,从而使结果集的大小保持在一个合适的范围内.现有七-支配skyline查询算法分为建立索引和不建立索引两种类型.其中不建立索引的算法在高维空间,反相关数据和渐近输出等方面表现比较差,而基于索引的算法花费大量时间去建立索引,整体性能都不高.本文提出一种基于简化预排序的七-支配skyline查询算法(SPA),实现用O(n)的时间复杂度对数据进行简化预排序.理论论证和实验数据都显示了SPA算法远比国内外现有的最好算法更加高效.     

P2P环境下面向不确定数据的Top-k查询

分布式环境中的top-k查询已经有了广泛的研究.由于仪器不精确和网络延时等原因,大多数分布式数据都存在不确定性.文中基于水平分布在P2P网络中的不确定数据提出了一个有效的top-k查询处理方法.首先利用Quad-tree构建一个分布式的不确定数据的索引,并基于索引提出了一个空间剪枝算法.然后,根据局部top-k概率与全...     

概率Top-κ查询的层次索引

由于在经济、军事等领域的广泛应用,不确定数据的查询处理技术成为近年来数据库领域的研究热点.概率top-κ查询根据打分函数和概率两个维度来对数据进行排序,因此具有多种查询语义.作为I/O密集型查询,概率top-κ查询需要具备一定通用性的索引技术来提高查询效率.本文从分析概率top-κ查询满足的性质入手,分别基于skyline和支配频率的概念,提出两种层次索引.通过理论分析和实验证明了满足特定性质的概率top-κ查询均可以利用这两种索引来提高I/O效率,其中基于支配频率的索引具有更好的鲁棒性.     

连续不确定XML数据索引技术研究

针对连续不确定XML数据的概率阈值查询,提出CPTI(Continuous Probabilistic Threshold Index)索引技术,包括CPTI结构索引和CPTI值索引。CPTI结构索引扩展了结构索引F-index支持连续不确定XML数据,通过CPTI结构索引查询twig小枝,并确定小枝的路径概率;CPTI值索引是一个二维表,记录cont类节点的概率信息,通过CPTI值索引过滤与查询无关的元素以减少查询中需要处理的元素数目。实验表明,此索引技术可极大地提高查询处理的性能。     

受限网络移动对象的概率最近邻查询

基于自由空间移动对象概率最近邻查询,给出受限网络移动对象概率最近邻(CNPNN)查询概念,提出一种基于网络概率Voronoi图的CNPNN查询算法.利用基于网络距离的概率度量得到不确定数据的网络概率Voronoi单元,建立网络概率Voronoi 图覆盖受限网络.使用对点查询具有优势的R+树,对不确定数据的网络概率Voronoi单元进行索引,减少搜索时间.确定查询对象所在网络Voronoi单元,得到查询对象最可能的最近邻.实验结果表明,该算法时间复杂度为O(n2+mlogmn),在一定条件下具有较好的性能.     

不确定图数据库中高效查询处理

近年来,在多种领域中产生的大量数据都可以自然地建模为图结构,比如蛋白质交互网络、社会网络等.测量手段的不准确性以及数据本身的性质导致不确定性在很多图数据中普遍存在.文中研究不确定图数据库中的高效查询处理方法.首先给出一种数据模型来表示图的不确定性.鉴于对用户提交的查询图通常会产生大量匹配结果,高效得到概率最大的k个匹配常常更具有现实意义.因此文中形式化提出概率top-k子图匹配查询的问题.为了解决提出的查询问题,以附带概率信息的邻居子图为基础,设计了一种有效的索引结构.另外,提出一种高效的基于索引的查询处理方法.该查询处理方法的核心是一个基于搜索树的匹配算法,其中运用了一种概率剪枝技术来提高性能.实验结果表明,所提出方法具有良好的效率和可扩展性.     

无线传感器网络不确定数据PT-Top k查询处理技术

在无线传感器网络现实应用中,感知数据普遍存在不确定性。由于不确定数据引入了概率维度,使得不确定数据查询种类更加丰富,同时也给查询处理带来困难。不确定数据Top-k查询是一个典型的不确定数据查询任务。考虑到无线传感器网络查询处理技术对查询响应时间和网络通信消耗的高要求,研究了面向层次聚簇结构的无线传感器网络不确定数据Top-k查询处理技术。通过分析不确定数据特点,基于x-tuple规则元组模型,采用簇内与簇间的两阶段数据查询处理机制,提出了基于Poisson分布的分布式不确定数据PT-Top k查询处理近似算法TPQP。通过实验,从总体通信消耗、与概率阈值p相关分析、与排序数k相关分析以及数据敏感度分析等方面,说明了TPQP算法在通信消耗、查询响应时间上的优越性。     

一种基于角相似性的k-最近邻搜索算法*

k-最近邻搜索(KNNS) 在高维空间中应用非常广泛,但目前很多KNNS算法是基于欧氏距离对数据进行索引和搜索,不适合采用角相似性的应用。提出一种基于角相似性的k-最近邻搜索算法(BA-KNNS)。该算法先提出基于角相似性的数据索引结构(BA-Index),参照一条中心线和一条参照线,将数据以系列壳—超圆锥体方式进行组织并分别线性存储;然后确定查询对象的空间位置,有效确定一个以从原点到查询对象的直线为中心线的超圆锥体并在其中进行搜索。实验结果表明,BA-KNNS算法较其他k-最近邻搜索算法有更好的性能。     

基于x-tuple的概率阈值top-k查询算法

不确定数据库中的概率阈值top-k查询是计算元组排在前k位的概率和,返回概率和不小于p的元组,但现有的查询语义没有将x-tuple内的元组进行整体处理.针对该情况,定义一种新的查询语义——概率阈值x-top-k查询,并给出查询处理算法.在该查询语义下采用动态规划方法求取x-tuple内每个元组排在前k位的概率和,对其进行聚集后做概率阈值top-k查询,并利用观察法、最大上限值等剪枝方法进行优化.实验结果表明,该算法平均扫描全体数据集中60％的数据即可返回正确结果集,证明其查询处理效率较高.