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

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

基于距离阈值的不确定图可达性查询处理

在不确定数据的处理中,不确定图作为典型的数据模型得到了广泛的关注,研究的内容包括基于不确定图的子图匹配、最近邻查询及连接查询等,本文研究基于距离阈值的不确定图可达性查询,即给定不确定图及图中任意两点s、t和距离阈值d,返回s和t的d可达的概率.提出一种基于随机抽样的可达性查询处理算法.定义了一种不确定图可能图实例的分类树模型.为了提高图实例分类的获取效率,提出基于双向遍历的优化分类树模型.设计了基于图实例类抽样的可达性查询处理算法并通过理论分析和实验验证了算法的性能.     

面向不确定平面图的模式匹配查询

平面图的模式匹配查询可广泛应用于生物网络、社会网络、指纹识别和图像分割等。由于对数据操作时引入的噪声和错误使这些图数据具有不确定性,而确定平面图的查询处理技术不能有效地处理不确定性,因此利用概率语义描述的平面图的模式进行匹配查询。具体地,使用可能世界概率模型定义不确定平面图,基于该模型,研究了不确定模式匹配(UPM)查询。首先给出一个确定算法可避免枚举所有的可能世界,同时给出改进的确定算法可更快速地求解查询。其次设计出采样算法,可快速地估算出匹配概率,并具有较高的精确度。基于真实不确定平面图数据的大量实验验证了该设计。最后将该查询应用于肺部CT图像的分割,结果表明此方法优于经典的图像分割算法。     

不确定性交通网络中的top-k路径查询

该文将交通网络抽象为不确定性图模型,并用概率图的方式研究了不确定交通网络中的top-k路径查询,给出了求解概率图中top-k路径查询的数学模型,提出了一种基于遗传算法的不确定性交通网络top-k路径查询算法,并对算法进行了测试,得到了较好的结果。     

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

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

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

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

基于不确定理论的不确定性数据Top-k查询计算

在不确定性数据集中,基于参数化排名函数的Top-k查询研究近年来备受关注。给出了一种新的解决方法,该方法将不确定性数据集中的元组建模为不确定网络,将有序元组的Top-k查询等价转化为相应样本图中边的不确定测度关系,并对样本图依据所包含边的排序位置进行分类,从而 将不确定性数据中基于参数化排名函数的Top-k查询等价转换为依Top-k值不同的有限查询。本算法避免了计算所有元组在样本图中的排名不确定测度值,提高了不确定图的Top-k查询计算效率。 理论分析和实验结果表明,提出的Top-k查询算法能够从非确定角度解决不确定性数据的Top-k查询计算问题。     

基于可能图的攻击意图检测方法

攻击图模型是网络风险评估的主要技术之一,其通过攻击步骤之间的因果关系来描述攻击者从初始状态到目标状态的攻击过程,分析的整个过程也是以某种形式化方式表述的图数据为基础的,但分析时很少考虑网络链路、网络拥塞、入侵报警等不确定性。结合不确定图的概念将攻击图扩展为可能攻击图(PAG),给出了可能攻击图的构建方法,同时基于可达概率提出了最大可达概率求解算法和最大攻击子图生成及最大可能攻击路径选取算法。实验结果表明,本文所提方法能够在可接受的时间内生成可能攻击图,并能够有效地推测出攻击意图,为作为网络管理员的管理方提供决策依据。     

图结构XML文档上子图查询的高效处理算法

研究了图结构XML数据上子图查询处理,给出了一系列高效的处理算法.基于可达编码,首先提出基于哈希的结构连接算法(HGJoin)来处理图结构XML数据上的可达查询.然后,该算法被扩展来处理特殊的二分图查询.基于这些算法和所给出的代价模型,提出了一般DAG子图查询的处理算法和查询优化策略.这些算法经过简单修改即可有效地处理一般的子图查询.理论分析和实验结果表明,算法具有较高的效率.     

一种保持结点可达性的高效社会网络图匿名算法

为了保护社会网络隐私信息,提出了多种社会网络图匿名化技术.图匿名化目的在于通过图修改操作来防止隐私泄露,同时保证匿名图在社会网络分析和图查询方面的数据可用性.可达性查询是一种基本图查询操作,可达性查询精度是衡量图数据可用性的一项重要指标.然而,当前研究忽略了图匿名对结点可达性的影响,导致较大的可达性信息损失.为了保持匿名图中结点的可达性,提出了可达性保持图匿名化（reachability preserving anonymization,简称RPA）算法,其基本思想是将结点进行分组并采取贪心策略进行匿名,从而减少匿名过程中的可达性信息损失.为了保证RPA算法的实用性,针对其执行效率进行优化,首先提出采用可达区间来高效地评估边添加操作所导致的匿名损失;其次,通过采用候选邻居索引,进一步加速RPA算法对每个结点的匿名过程.基于真实社会网络数据的实验结果表明了RPA算法的高执行效率,同时验证了生成匿名图在可达性查询方面的高精度.     

有向图上的广义可达性查询处理方法

随着社会网络、生物信息学、本体等应用的迅速发展,如何在图上进行高效的信息检索成为一个亟待解决的问题。两点间可达性查询是一种常见的查询方式,目前针对此类查询已经提出了许多算法。但是在一些应用中,这种查询语义并不能满足用户需求。基于此,提出了两种广义可达性查询语义。研究了如何在大图上进行高效的广义可达性查询的问题,依据Path-tree编码的特性提出了一种新的二级索引机制——RB+索引。基于RB+索引,针对不同类型查询提出了两种高效的查询处理方法。该方法充分利用Path-tree编码的特性,有效地处理广义可达性查询。通过实验对提出的索引和查询算法进行了验证。     

不确定数据库中概率top-k和排序查询算法

传感器网络等技术的广泛应用产生了大量不确定数据。近年来,对于不确定数据的处理和查询成为数据库和数据挖掘领域研究的热点。其中,传统关系数据库中的top-k查询和排序查询怎样拓展到不确定数据是其中的焦点之一。研究近年来提出的不确定数据库上top-k查询和排序查询算法,归纳和比较目前各种不同查询算法所适应的语义世界和应用场景,并详细分析各种算法的执行效率和算法复杂度。另外,对于不确定数据top-k查询和排序查询所面临的挑战和可能的研究方向进行了总结。     

Continuous ranking on uncertain streams

Data uncertainty widely exists in many web applications, financial applications and sensor networks. Ranking queries that return a number of tuples with maximal ranking scores are important in the field of database management. Most existing work focuses on proposing static solutions for various ranking semantics over uncertain data. Our focus is to handle continuous ranking queries on uncertain data streams: testing each new tuple to output highly-ranked tuples. The main challenge comes from not only the fact that the possible world space will grow exponentially when new tuples arrive, but also the requirement for low space- and time-complexity to adapt to the streaming environments. This paper aims at handling continuous ranking queries on uncertain data streams. We first study how to handle this issue exactly, then we propose a novel method (exponential sampling) to estimate the expected rank of a tuple with high quality. Analysis in theory and detailed experimental reports evaluate the proposed methods.     

不确定性Top-K 查询处理

高效Top-K查询处理在涉及大量数据交互的应用中是一项重要技术,随着应用中不确定性数据的大量涌现,不确定性数据的管理逐渐引起人们的重视.不确定性数据上Top-K查询从语义和处理上都呈现出与传统Top-K查询不同的特点.在主流不确定性数据模型和可能世界语义模型下,学者们已经提出了多种不确定性Top-K查询的语义和处理方法.介绍了当前不确定性Top-K查询的研究工作,并对其进行分类,讨论包括语义、排序标准、算法以及应用等方面的技术.最后提出不确定性Top-K查询面临的挑战和下一步的发展方向.     

Adding regular expressions to graph reachability and pattern queries

It is increasingly common to find graphs in which edges are of different types, indicating a variety of relationships. For such graphs we propose a class of reachability queries and a class of graph patterns, in which an edge is specified with a regular expression of a certain form, expressing the connectivity of a data graph via edges of various types. In addition, we define graph pattern matching based on a revised notion of graph simulation. On graphs in emerging applications such as social networks, we show that these queries are capable of finding more sensible information than their traditional counterparts. Better still, their increased expressive power does not come with extra complexity. Indeed, (1) we investigate their containment and minimization problems, and show that these fundamental problems are in quadratic time for reachability queries and are in cubic time for pattern queries. (2) We develop an algorithm for answering reachability queries, in quadratic time as for their traditional counterpart. (3) We provide two cubic-time algorithms for evaluating graph pattern queries, as opposed to the NP-completeness of graph pattern matching via subgraph isomorphism. (4) The effectiveness and efficiency of these algorithms are experimentally verified using real-life data and synthetic data.     

A survey of queries over uncertain data

Uncertain data have already widely existed in many practical applications recently, such as sensor networks, RFID networks, location-based services, and mobile object management. Query processing over uncertain data as an important aspect of uncertain data management has received increasing attention in the field of database. Uncertain query processing poses inherent challenges and demands non-traditional techniques, due to the data uncertainty. This paper surveys this interesting and still evolving research area in current database community, so that readers can easily obtain an overview of the state-of-the-art techniques. We first provide an overview of data uncertainty, including uncertainty types, probability representation models, and sources of probabilities. We next outline the current major types of uncertain queries and summarize the main features of uncertain queries. Particularly, we present and analyze several typical uncertain queries in detail, such as skyline queries, top- $k$ queries, nearest-neighbor queries, aggregate queries, join queries, range queries, and threshold queries over uncertain data. Finally, we present many interesting research topics on uncertain queries that have not yet been explored.     

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

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