SIHC:一种高效的时态图上k-core查询算法

许多实体之间的关系可以建模为时态图,其中每条边都与表示其发生的时间相关联,k-core是捕获密集子图的基本模型,在近些年得到了广泛研究.给定时间区间I=[s,e]和k值,时态图G上的k-core子图查询从区间I对应的快照图GI中返回相应的k-core子图.针对时态图中的k-core子图查询问题,现有方法是基于PHC索引(Pruned Historical Core-Index)的算法.对任意可能的k值,PHC索引维护了所有可能出现在某个时间区间的k-core子图中的顶点集Sk,且为集合中每个顶点存储了一组时间区间,用于判定该点是否属于给定时间区间的k-core子图.基于PHC索引查询k-core子图时,需要访问Sk集合中的所有顶点,并判断每个顶点的可满足性.由于Sk集合对应于最大区间快照图的k-core子图里的所有顶点,且实际中用户查询区间对应的快照图往往比最大区间快照图小得多,基于PHC索引的查询算法存在许多无效判断,需要对大量不在结果集中的顶点进行检测,且无效检测次数随着查询区间的缩短而增多,从而导致算法效率较低.针对该问题,本文提出一种新的索引,即最短区间历史核索引SIHC(Shortest Interval Historical Core Index).SIHC索引的基本思想是通过维护最短k核区间到顶点的倒排表,查询处理时,可基于用户给定的时间区间定位到SIHC索引中满足条件的区间,进而直接得到满足条件的k-core子图中的顶点,从而避免了基于PHC索引进行查询时所需的大量无效判断.我们从理论上证明了基于SIHC索引处理时态图上k-core子图查询的正确性,并设计了高效的索引构建算法.最后,基于真实世界的时态图进行了实验,实验结果表明本文提出的算法比现有算法快1~2个数量级.

多源多尺度地图数据的组织与管理

多源多尺度地图数据的组织与管理是多源地图数据处理、数据融合以及地图制图综合的基础。首先对多源地图数据处理的主要方法和技术进行了总结;进而讨论了多源多尺度地图数据的组织与管理的两个关键技术,即多源多尺度地图数据引擎的设计和多图幅地图数据的内存管理技术。

大规模图数据匹配技术综述

在大数据时代海量的多源异构数据间存在着紧密的关联性,图作为表示数据之间关系的基本结构在社交网络分析、社会安全分析、生物数据分析等领域有着广泛应用.在大规模图数据上进行高效地查询、匹配是大数据分析处理的基础问题.从应用角度对用于图查询的图数据匹配技术的研究进展进行综述,根据图数据的不同特征以及应用的不同需求对图匹配问题分类进行介绍.同时,将重点介绍精确图匹配,包括无索引的匹配和基于索引的匹配,以及相关的关键技术、主要算法、性能评价等进行了介绍、测试和分析.最后对图匹配技术的应用现状和面临的问题进行了总结,并对该技术的未来发展趋势进行了展望.

图数据表示与压缩技术综述

对包含亿万个节点和边的图数据进行高效、紧凑的表示和压缩,是大规模图数据分析处理的基础.图数据压缩技术可以有效地降低图数据的存储空间,同时支持在压缩形式的图数据上进行快速访问.通过深入分析该技术的发展现状,将该技术分为基于传统存储结构的压缩技术、网页图压缩技术、社交网络图压缩技术、面向特定查询的图压缩技术4类.分别对每类技术详细分析了其代表方法并比较了它们之间的性能差异.最后对该技术进行了总结和展望.

基于图模型的海量商品知识表示与管理

实现智能化的语义搜索需要强大的知识支持,因此大规模的知识存储和管理系统是目前一项迫切的需求。针对海量商品知识,提出一种基于RDF(Resource Description Framework)的知识表示模型。利用图模型对商品知识进行建模,在Neo4j的基础上设计一个支持多模式查询、具有高可扩展性的海量商品知识管理系统。一系列的实验验证该系统能够有效地支持百万级别节点的商品知识服务请求。

大规模时序图数据的查询处理与挖掘技术综述

时序图作为一种带有时间维度的图结构,在图数据的查询处理与挖掘工作中扮演着越来越重要的角色.与传统的静态图不同,时序图的结构会随时间序列发生改变,即时序图的边由时间激活.而且由于时序图上每条边都有记录时间的标签,所以时序图包含的信息量相较于静态图也更为庞大,这使得现有的数据查询处理方法不能很好地应用于时序图中.因此如何解决时序图上的数据查询处理与挖掘问题得到研究者们的关注.对现有的时序图上的查询处理与挖掘方法进行了综述,详细介绍了时序图的应用背景和基本定义,梳理了现有的时序图模型,并从图查询处理方法、图挖掘方法和时序图管理系统3个方面对时序图上现有的工作进行了详细的介绍和分析.最后对时序图上可能的研究方向进行了展望,为相关研究提供参考.

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

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