一种基于图结构分解的图近似查询方法研究

图近似查询能够得到与查询图近似的结果集,相比较精确查询具有更广泛的应用范围。为提高近似查询的查准率和查全率,提出一种基于图结构分解的查询算法。该算法通过对查询图和目标图进行图结构分解,对其建立图分解索引,利用查询图的最小生成树集得到满足阈值的生成树集,通过图标准编码在索引中快速定位,查找出所有可能的近似结果。实验结果表明,该算法能有效得到近似结果,提高查询速度。     

RIAIL:大规模图上的可达性查询索引方法

图被广泛用来建模在社交网络、语义网、计算生物学和软件分析中的应用.可达性查询是图数据上的一种基础查询.当前,针对图上的可达性查询已经提出了一些索引算法,但是它们不能灵活地扩展到大的图数据.因此,提出了一种索引方法RIAIL(reachability index augmented by interval labeling).RIAIL将结点的标记信息表示成四元组.前两个元素是区间标记,编码生成树的可达性信息,后两个元素编码非树边的可达性信息.RIAIL查询时只需索引且索引创建代价小.最后,通过大量真实和人工生成数据集上的实验说明,RIAIL能够高效地处理可达性查询,并且可以简单地扩展到大的图数据.     

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

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

基于索引的并行图可达性查询算法

随着图数据库(Graph Database)的不断发展,各种应用程序中都存在着大规模图数据,使得图的可达性查询算法受到了广泛的关注.然而由于其空间消耗与查询效率难以平衡,图可达性查询算法面临着严峻的挑战.基于串行运算的传统图查询算法,很难发挥现有多核心处理器的计算性能.针对上述问题,提出了一种基于双链表的索引,称为2-lists.该索引表由两部分组成,其中一部分存储图数据的信息,另一部分辅助索引,实现顶点的随机访问.基于该索引,提出了一种并行化深度优先搜索算法(Parallel Depth-First Search, PDFS).该算法利用多线程技术,并为每个线程分配独立的存储空间.通过对线程工作量的监督,为线程的指定缓冲区分配指定数量的任务,进而完成负载平衡.在斯坦福SNAP(Stanford Network Analysis Platform, SNAP)实验室的公开数据集上的实验结果表明,2-lists索引占用的空间更小,基于2-lists的并行化深度优先搜索算法的表现更好.     

基于参考节点嵌入的图可达性查询

针对k步可达性查询算法无法解决带距离约束的图可达性查询问题,提出基于参考节点嵌入的图可达性查询算法。首先,从所有节点中选出极少数有代表性的全局参考节点,预先计算所有节点与全局参考节点之间的最短路径距离;然后,采用最短路径树和范围最小值查询技术求得局部参考节点;接着,利用三角不等式关系得到查询点对距离范围;最后,根据查询条件中的距离值与查询点对距离范围上、下限值的大小关系,可快速得出可达性结论。针对社会关系网络和公路网络数据,将所提算法与Dijkstra算法、K-Reach算法进行实验对比测试。相较于K-Reach算法,其索引建立时间小4个数量级,其索引规模小2个数量级;相较于Dijkstra算法,在公路网络和社会关系网络中,直接得出可达性结论的比例分别为92%和78.6%,其查询时间大大缩短,分别降低了95.5%和92%。实验结果表明：所提算法能够通过使用较小的索引开销,实现在线查询计算复杂度的降低,可很好地解决既适用于有权图又适用于无权图带距离约束的可达性查询问题。     

图数据隐私保护可达性查询算法研究

数据库领域越来越多的数据通过图的结构进行存储,随着图数据规模的快速增长和云计算的兴起,数据拥有者希望将数据外包给具有强大计算能力的服务商为其客户提供查询服务。为解决数据库中的可达性查询问题,提出一种隐私保护的可达性索引和查询方法。对原始的2-hop索引构建方法进行优化,设计maxISCover启发式方法,给出根据人工节点添加算法建立pp-2-hop索引的unifyIS和unifyLS算法,并在此基础上,给出基于密文域的优化可达性查询方法。实验结果表明,基于maxISCover优化方法和unifyIS算法建立的索引大小相比于基于原始2-hop索引的方法减小1个~2个数量级。     

Smith图导出关系模式的分解算法与递归处理

本文提出了一种由优化的Ｓｍｉｔｈ图导出规范化关系模式的分解算法,包括确定根结点、,生成森林、导出规范化、关系模式等。这些都是用递归处理实现的,本文给出了这些递归处理的描述,最后介绍了一个例子。     

一个适于并行处理的N链递归查询算法

目前 ,存在两个制约演绎数据库发展的关键问题 ,其一是效率低下 ;其二是现有的查询算法适用范围窄 .针对这两个问题 ,本文介绍了一种应用于 N链递归而且适合并行处理的算法     

面向大规模图数据的分布式可达性索引与查询策略

针对构建大规模图数据可达性索引时的构建时间长、存储代价高和响应时间长等问题,提出一种分布式可达性索引与查询策略(DRIQ)。在不破坏原图中节点可达性的前提下,将大规模图划分成若干小规模子图,并对每个子图分布式并行地创建可达性索引,从而提高可达性索引创建效率。给出保持图划分后各子图内节点间以及子图间节点可达性的方法,从而保证基于DRIQ进行可达性查询的正确性。实验结果表明,与传统可达性查询方法相比,该策略具有高效性和可扩展性。     

有向无环图上k步可达查询优化算法

k步可达查询用于在给定的有向无环图（DAG）中回答两点之间是否存在长度不超过k的路径。针对现有方法的索引规模大、查询处理效率低的问题,提出一种基于部分点的双向最短路径索引来提升索引的可达信息覆盖率,并提出一组优化规则来减小索引规模;然后提出基于简化图的正反互逆拓扑索引来加速回答不可达查询;最后提出远距离优先的双向遍历策略来提高查询处理的效率。基于21个真实数据集（如引用网络、社交网络等）的实验结果表明,相比已有的高效方法PLL及BFSI-B,所提出的算法具有更小的索引规模和更快的查询响应速度。     

基于布尔函数的网络可达性验证方法

针对SDN中由于不同应用的转发路径交叠等导致的数据平面配置问题,提出一种基于布尔函数的网络可达性验证方法。首先,将网络拓扑抽象为端口拓扑并计算端口邻接矩阵;之后,生成网络的路径空间和各端口的转发函数并计算每条路径的路径函数;最后通过判断路径函数的可满足性来确定路径的可达性。通过仿真实验,对网络拓扑和流规则规模等因素对算法验证效率的影响进行研究,并将所提方法与APV和DASDA进行性能比较。实验结果表明,所提方法能够有效检测SDN中的流规则配置问题。随着网络中环路的增加和流规则规模的增长,验证网络所需的时间开销逐渐增加。其中,网络拓扑对路径生成时间影响较大,而转发函数的生成时间则主要受流规则规模的影响。方法的验证时间相较于APV和DASDA分别平均缩短约53.76%和27.74%。     

基于路网可达性的交通控制子区划分方法研究

为了提高子区划分的效率,保证子区划分结果的合理性,提出了一种基于路网可达性的子区划分方法。以路口为顶点,路段为边,修正的路段阻抗为边权得到路网加权网络,通过权系数开关化转为非加权网络;采用[K]步可达矩阵来分析网络的可达性,以可达性最好的顶点为核心顶点,求解核心顶点的[K]步可达顶点群得到子区划分结果;以子区路网路段占有率方差为评价指标,对子区划分结果进行优化。以北京市亦庄林肯公园地区路网为例的仿真结果表明：基于路网可达性的子区划分,可以找到路网中关联最为紧密的顶点群,且以子区内部路段的占有率方差作为评价指标可以保证子区内部路段状态的相似性,为子区划分的优化提供指导。     

MashUp web data sources and services based on semantic queries

This paper describes a process for mashing heterogeneous data sources based on the Multi-data source Fusion Approach (MFA) (Nachouki and Quafafou, 2008 [52]). The aim of MFA is to facilitate the fusion of heterogeneous data sources in dynamic contexts such as the Web. Data sources are either static or active: static data sources can be structured or semi-structured (e.g. XML documents or databases), whereas active sources are services (e.g. Web services). Our main objective is to combine (Web) data sources with a minimal effort required from the user. This objective is crucial because the mashing process implies easy and fast integration of data sources. We suppose that the user is not expert in this field but he/she understands the meaning of data being integrated. In this paper, we consider two important aspects of the Web mashing process. The first one concerns the information extraction from the Web. The results of this process are the static data sources that are used later together with services in order to create a new result/application. The second one concerns the problem of semantic reconciliation of data sources. This step consists to generate the Conflicts data source in order to improve the problem of rewriting semantic queries into sub-queries (not addressed in this paper) over data sources. We give the design of our system MDSManager. We show this process through a real-life application.     

含生成森林有向图的零特征值及在编队控制中的应用

本文研究了含有m-生成森林有向图拉普拉斯矩阵的零特征值重数,其中m≥1是一个整数。对于这个问题,这个图一般不含有生成树。即使初始时具有生成树,受到隐秘的攻击或经过障碍物造成的智能体之间的通信阻挡（如在分布式控制、分布式（在线）优化、多智能体算子等问题中）等因素后,这个图也可能不再含有生成树。另外,作为一个研究方向,它本身亦是个有趣的科学问题。为了解决这个问题,本文证明了拉普拉斯矩阵的零特征值重数等于这个图中的生成森林个数,这个结论可以看作是在带有生成树的有向图情形（即m=1时）的一个推广。再者,结合分布式优化方法,所得结论被应用于单积分器多智能体系统下的编队控制,表明了达到的编队队形处在通信图拉普拉斯矩阵的核空间中。最后给出了一个例子用以展示在编队控制中的应用。     

基于P2P网络的云资源多维查询算法

在云资源共享服务模式中,为实现云资源的多维度查询,提出一种基于P2P网络的云资源多维查询算法.在结构化对等网络的基础上设计一种分层的云资源网络拓扑结构.首先对云资源的属性和属性值分别进行编码,结合云资源多维发布策略实现了云资源多维查询;然后给出了该算法的查询效率分析和稳定性分析.实验结果表明,该算法能快速高效地实现云资源多维度查询,并且不会随着查询维度数和网络节点数的增加而产生较大的查询时延.     

Selectivity estimation of range queries based on data density approximation via cosine series

Selectivity estimation is an integral part of query optimization. In this paper, we propose to approximate data density functions of relations by cosine series and use the approximations to estimate selectivities of range queries. We lay down the foundation for applying cosine series to range query size estimation and compare it with some notable approaches, such as the wavelets, DCT, kernel-spline, sketch, and Legendre polynomials. Experimental results have shown that our approach is simple to construct, easy to update, and fast to estimate. It also yields accurate estimates, especially in multi-dimensional cases.