标签约束图上的k步可达性查询

标签约束图上的k步可达性查询问题,回答了在一个标签约束图上两点之间是否存在一条长度不大于k的路径并且这条路径上的标签都在用户给定的标签集中的问题。标签约束图上的k步可达性查询问题在现实中有着广泛的应用,然而现有算法无法直接回答这个问题。因此,首先提出LK2H算法。LK2H算法主要包括构建索引和查询两个步骤。第一步是给图上的所有顶点构建一组包含k和标签信息的2-Hop索引,第二步是基于构建好的索引进行查询。在查询时,为了尽可能地为用户返回更多的信息,LK2H算法优化了一类不可达查询的返回结果：当用户无法明确所有的标签类型,不能给出完整的标签约束,进而导致查询结果为不可达时,将完整的标签集返回给用户。其次,提出优化算法LK2H+。LK2H+算法通过构建部分顶点的2-Hop索引进一步缩减索引大小和索引的构建时间,并基于构建好的索引进行查询。查询时,需要对顶点按照是否构建了索引进行分类讨论。最后,基于15个真实数据集进行测试。实验结果表明,LK2H算法和LK2H+算法都可以高效地解决标签约束图上的k步可达性查询问题。     

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

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

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

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

标签约束可达查询的高效处理方法

基于标签约束的可达性查询s→\\-Lt用于回答给定图中顶点s到顶点t是否存在路径标签属于L的有向路径.针对现有方法索引构建时间长、索引规模大、查询效率低的问题,首先基于k个点构建双向路径标签索引,并提出相应的优化措施减小索引规模,以此来加速可达查询的处理速度.由于其索引没有完全覆盖可达查询,虽然索引规模小,但仍然无法避免查询过程中的图遍历操作.为此,进一步提出覆盖所有可达信息的双向路径标签索引,基于该索引,查询处理时可以完全避免图上的遍历操作.最后,基于多个真实数据集进行测试,实验结果从索引大小、索引构建时间和查询响应时间方面验证了所提方法相对现有方法具有索引规模小、索引时间短且查询响应快的优势.     

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

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

带权大图上的K步可达性查询算法

可达性查询作为图中最常用的基本操作，在生物信息学、智慧交通等领域应用广泛，但在一些现实问题中，仅仅进行可达性查询并不能满足人们对距离信息的需求，K步可达性查询应运而生。目前已有的K步可达性查询的处理对象为有向无环图，无法充分反映顶点间的距离信息，并且无环图并不符合交通网络等实际应用情况。针对以上问题，提出一种针对带权有向图的K步可达性查询算法。通过求解近似最小顶点覆盖集，分别构建了顶点覆盖集内索引和顶点覆盖集外的双向最短路径索引，有效避免了查询时的I/O操作，提高了查询效率。在10个数据集上进行对比实验，并通过比较索引构建时间、索引规模、查询时间等指标证明了该算法的高效性。     

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

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

L(k)-index:一种支持标签路径的高效k双拟结构索引

针对基于k双拟的结构索引创建和更新低效问题、查询结果重复验证问题以及标签路径不可获得性问题,提出了一种新的结构索引L(k)-index.L(k)-index通过引入标签路径,在创建时无须k次遍历原数据,并采取批量更新策略,大大提高索引创建和更新的效率,而在空间上仅有很小增加.对于长度大于k+1的路径查询,L(k)-index无须访问原数据进行验证,并支持批量节点的标签路径获得.通过大量实验表明,同A(k)-index相比,L(k)-index创建时间平均提高66.7%,查询处理时间效率平均提高68.9%,批量更新效率平均每节点提高58.8%,而空间仅增加22.5%.     

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

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

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

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