一种有效的历史移动对象轨迹的k最近邻居查询算法

近10多年来,研究者们已经在k最近邻居(kNN)查询方面做了很多工作,但是对于移动对象轨迹的kNN查询处理却研究得很少.鉴于此,研究了在存储有历史移动对象轨迹信息的TB树结构上的kNN查询问题,并且提出了一种有效的基于最佳优先搜索范例的kNN(k≥1)查询算法,称为BFPkNN.BFPkNN是一种I/O最佳的算法,即它仅仅访问有可能包含最终结果的结点.同时,为了减少存储空间和CPU代价,又提出了若干有效的剪枝策略.大量的实验证明BFPkNN在效率和可扩展性上均大大胜过其他同类算法.     

TwigStar——快速处理XML Twig查询中含通配符*的算法

XMLTwig查询可以表示为一棵带标签结点的查询树,它支持对XML文档进行带有复杂谓词的结构或内容查询.整体(holistic)Twig查询算法已经被公认为XML查询处理的核心算法.很多学者提出了大量基于整体处理的XML Twig查询算法.但是目前已有的算法都只适合于Twig查询中不包含通配符*的情况.而当Twig查询中包含通配符*时,一种简单而直接处理的方法就是,把被查询文档中的所有结点元素都读到内存,把这些元素都看做通配符*所对应的元素,然后按照已有的算法进行查询处理.显然这种方法是不合理的,它会增加大量I/O开销.因此提出了一种有效地支持通配符*的查询处理算法.通过建立索引,它可以很好地处理含通配符*的查询,从而可以避免不必要的I/O开销.最后通过实验证明,算法要明显好于已有的算法.     

高速流环境下近似连续k代表轮廓查询算法

k代表轮廓查询是从传统轮廓查询中衍生出来的一类查询.给定多维数据集合D,轮廓查询从D中找到所有不被其他对象支配的对象,将其返回给用户,便于用户结合自身偏好选择高质量对象.然而,轮廓对象规模通常较大,用户需要从大量数据中进行选择,导致选择速度和质量无法得到保证.与传统轮廓查询相比,k代表轮廓查询从所有轮廓对象中选择“代表性”最强的k个对象返回给用户,有效地解决了传统轮廓查询存在的这一问题.给定滑动窗口W和连续查询q,q监听窗口中的数据.当窗口滑动时,查询q返回窗口中,组合支配面积最大的k个对象.现有算法的核心思想是:实时监测当前窗口中的轮廓对象集合,当轮廓对象集合更新时,算法更新k代表轮廓.然而,实时监测窗口中,轮廓集合的计算代价通常较大.此外,当轮廓集合规模较大时,从中选择k代表轮廓的计算代价是同样巨大的,导致已有算法无法在高速流环境下使用.针对上述问题,提出了ρ-近似k代表轮廓查询.为了支持该查询,提出了查询处理框架PAKRS(predict-basedapproximatekrepresentativeskyline).首先,PAKRS利用高速流的特性对当前窗口进行划分,根据划分结...     

基于网格索引的数据流子空间概率轮廓查询

在数据流子空间上的连续概率轮廓查询(CPSQS)基础上,提出一种基于网格索引结构的概率轮廓查询算法。采用适合于子空间轮廓计算的网格索引结构,将数据空间划分成若干个格,利用格间的支配关系,减少对象之间的比较次数。同时挖掘全空间与子空间上格的概率上下界关系,设计有效的剪枝策略提高CPSQS算法的性能。理论分析和实验结果表 明,该算法能满足实际应用中用户的个性化查询要求,降低查询响应时间。     

基于历史数据的轮廓聚合查询

轮廓查询在涉及多标准决策的空间数据库、数据挖掘、测试观察、用户偏好查询、可视化等领域起着非常重要的作用.近年来人们对于轮廓算法的研究已经趋于完善,尤其对于轮廓的计算.针对一些数据具有历史性这一特点,在具体应用领域中,提出了一种新的查询方法,即基于历史数据的轮廓聚合查询,针对不同的聚合函数,提出了基本算法CETAN. 并在此基础上对算法进行了改进,提出了AACN算法和基于过滤策略的ABT算法.实验结果表明,算法是有效的,极大改善了查询的精确性和多样性.     

一种求解动态数据集中k-支配轮廓的算法

在对高维数据集进行轮廓查询时,K-支配轮廓查询算法能够返回较少的轮廓点,有利于用户的决策,但目前的算法都是针对静态数据集设计,无法对动态数据集进行处理.动态数据可分为非数据流数据和数据流数据,本文针对这两种情况提出了相应的增量求解算法,即当数据集发生变化时,以现有的K-支配轮廓为基础,通过对部分数据点进行计算得到新的K-支配轮廓.证明了算法的正确性和有效性,并通过实验对算法进行了分析和验证.     

外包空间数据库中反向k近邻查询验证

在外包空间数据库模式下,数据持有者委托第三方数据发布者代替它来管理数据并且执行查询.当发布者受到攻击或者由于自身的不安全性,它可能返回不正确的查询结果给用户.基于已有的反向k近邻(ReversekNearest Neighbor,RkNN)查询方法,采用将反向k近邻查询验证转化成k近邻查询验证和范围查询验证的思想,提出一种反向k近邻查询验证的方法,并且设计了相应的算法,用于验证返回给客户端结果的正确性(没有结果点被篡改),有效性(结果点都满足用户的查询要求)和完整性(没有遗漏符合查询要求的结果点).实验验证了算法的有效性和实用性.     

3FO:基于过滤的一种Skyline查询算法

Skyline查询是从一个给定的数据集上返回所有不被其它点支配的点的集合.本文主要针对二维和三维空间上Skyline查询结果的单调性特点提出了一种新的3FO算法,它通过NN过滤、最小值覆盖过滤和单调性过滤三次过滤操作,删除非skyline点数据.可以快速地返回全部的Skyline点.实验结果表明,该算法比传统算法在相同数据集上平均性能提高2-3倍,是一种高效的算法.     

不确定数据库中的阈值轮廓查询处理

传统轮廓查询算法都没有考虑不确定数据的特殊性质,因而不能直接应用到不确定数据应用中.深入地研究了不确定数据库中的轮廓查询处理技术.首先,提出了不确定数据库中阈值轮廓查询的定义;其次,通过对其性质的分析,提出了基于R一树索引的基本的阈值轮廓算法(BPS);接着,通过对其性质的进一步分析,在BPS算法的基础上,增加了有效的过滤策略,提出了改进的阈值轮廓算法(IPS).实验结果表明,IPS算法可以有效地减少阈值轮廓的计算时间,从而满足实际应用的性能需求.     

有效支持XML结构化连接的索引——CATI

结构化连接的效率直接影响着XML查询的性能,目前对XML的结构化连接大多都是基于编码的方法.介绍了一种全新的有效支持XML结构化连接的树索引CATI(compact ancestor tree index)CATI的基本思想是,对于给定的一个祖先后代查询(A-D查询)或Twig查询,遍历XML文档,找出所有的祖先A的实例,用以建立CATI的主干;对于每个A实例,找出它的直接后代D的实例链接在它的后面.因为经典的结构连接算法Stack-Tree算法效率较高且使用较广,因此应用基于CATI的结构连接算法和基于Stack-Tree的结构连接算法就A-D查询和Twig查询做了大量实验.实验结果表明,基于CATI的结构化连接在一般查询情况下性能明显优于基于Stack-Tree的结构化连接.