基于阈值的概率图可达查询

图的可达性查询被广泛应用于生物网络、社会网络、本体网络、RDF网络等.由于对数据操作时引入的噪声和错误使这些图数据具有不确定性,而确定图的可达查询不能有效地处理不确定性,因此该文研究用概率语义描述的图可达性查询.具体的,该文使用可能世界概率模型定义不确定图(称为概率图),基于该模型,研究了基于阈值的概率可达查询(T-PR).首先为避免枚举所有可能世界,给出一个基本算法可精确求解T-PR查询.其次为进一步加速基本算法,给出3种改进方法,它们是不确定事件界、同构图的缩减、基于不相交路径和割集的界.通过合理的组合给出3种方法的合并算法.最后基于真实概率图数据的大量实验验证了该文的设计.     

基于区间编码的图结构XML数据上DAG匹配算法

图结构的XML数据被越来越多地应用在实践中,相关的问题也随之而生 .传统的XML树模型处理算法和图结构模型处理技术并不能够有效地处理图结构XML数据上的DAG查询 .提出了一种基于可达性区间编码的GraphJoin算法,利用区间桶这种数据结构,直接对图结构XML数据上的DAG查询进行全局匹配 .理论分析和实验结果表明,这种算法在查询时间和执行效率上好于现有的技术.     

室内概率阈值反向最近邻查询

室内空间变得越发的庞大和复杂,随之产生了越来越多的室内空间查询需求.目前已有文献提出了针对室内空间环境的范围查询和最近邻查询,而作为常见的空间查询类型的反向最近邻查询,尚未有相关的研究.为此,提出了室内概率阈值反向最近邻查询和基于定位设备的设备可达图模型.在图模型基础上,提出了室内概率阈值反向最近邻查询处理算法,该算法由基于图模型的批量剪枝、基于室内距离的剪枝、基于概率的剪枝和概率计算4部分构成,通过剪枝策略修剪掉不可能出现在结果集中的对象,从而缩小了查询空间,提高了效率.     

一种新的基于递归分解的图可达性查询算法

针对现实中许多超大规模图可达性查询的问题,提出了一种新的基于递归分解的算法,即将原图递归分解成一系列生成树和剩余图两类子图,并通过分别查询这两类子图来减少查询开销.相比于区间标记、链分解、2-hop标签和路径树等传统算法,该算法不仅空间开销更小,且时间复杂度更低.仿真实验表明,该算法对处理大规模有向图可达性问题上存储规模更小且查询效率更高.     

时间区间上的不确定移动对象距离范围查询

针对目标对象与查询发出者皆为不确定移动对象的情况,提出了一种时间区间上的距离范围查询（DRqTI）.此类查询搜索出数据集中在给定时间区间内,到查询发出者距离不超过阈值的目标对象,查询结果中包含对象满足查询条件的有效时间段和匹配度.提出了基于轨迹、基于时间区间和基于距离的三种剪枝策略,并给出了精炼和匹配度计算方法,在此基础上设计了查询处理算法.实验分析表明,三种剪枝策略中基于距离的方法性能最佳,提出的算法能有效处理DRqTI问题.     

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

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

面向不确定图的概率可达查询

图的可达性查询被广泛应用于生物网络、社会网络、本体网络、RDF数据库和XML数据库等.由于对数据操作时引入的噪声和错误使这些图数据具有不确定性,已经有大量的针对不确定RDF和XML数据库的研究.文中使用可能世界语义模型构建不确定图,基于该模型,研究了概率可达查询(PR).处理PR查询是#P完全问题,对此文中首先给出一个基本随机算法,可快速地估算出可达概率,并且该值有很高的精确度.进一步,文中为随机算法引入条件分布(称为"条件随机算法"),采用图的不相交路径集和割集作为条件概率分布,因此改进的随机算法可准确地并且是在多项式时间内处理查询.最后基于真实不确定图数据的大量实验结果验证了文中的设计.     

空间数据库中最小距离聚集查询及其算法

提出了一种新的距离查询形式-最小距离聚集查询,这种查询计算几个对象集中对象到一个中心对象集中对象的距离和,并返回最小的K个距离和.在空间数据库中,对基于R树索引的数据集给出了基于最近邻居的方法和阈值算法来回答查询.通过大量实验对两种算法进行了比较,结果显示阈值算法具有较好的性能.     

面向不确定图的k最近邻查询

生物网络、社会网络、交际网络等复杂的网络被广泛的研究,由于数据抽出时引入的噪声和错误使这些数据具有不确定性,因此可以对这些应用使用不确定图模型建模,k最近邻查询问题是查询一个图上的距离某个特定点最近的k个邻居节点的问题,它是不确定图上的一个基础问题.设计了一个解决不确定图上最近邻问题的框架,首先定义了一种新颖的不确定图上的k最近邻查询,然后提出了针对该查询的一般处理算法,同时对该算法进行了优化,使算法效率得到极大提高.理论分析和实验结果表明提出的算法能够高效地处理不确定图上的k最近邻查询.     

不确定图上的高效top-k近邻查询处理算法

图的不确定性普遍存在,研究不确定图的高效查询处理具有重要意义.文中提出了不确定图上一种新型查询——近邻查询.给定一个查询标签集R和距离约束σ,在不确定图G上进行近邻查询是要找到标签集包含R并且任意两个顶点间距离不超过σ的匹配顶点集.为解决该问题,文中首先提出了“可靠期望距离”,然后基于可靠期望距离建立了高效的近邻关系图...