关键词:
知识图谱存储
分布式系统
简洁数据结构
自索引压缩
摘要:
知识图谱可为语义化的检索和推理等方法提供重要支撑,近年来,知识图谱数据规模出现了大规模增长。随着对知识图谱数据离线处理能力要求的日益提升,应用端要求存储系统具有更高的读写效率和检索性能。就此,本文提出了一种为批量构建优化一种半静态知识图谱存储系统,同时实现热点数据分区和水平扩展;随后通过自索引压缩技术实现数据的紧凑编码,进一步优化其存储方案和数据重整方法。首先,提出一种半静态知识图谱存储系统,优化图谱数据批量构建效率,解决数据热点和负载均衡等问题。通过实现一种介于数据仓库和图数据库的图谱数据中间表示,缓解数据处理链路复杂,数据更新不及时和数据热点等问题。首先使用属性图模型对知识图谱进行建模,采用一跳子图作为基本的图存储单位;再使用基于随机采样的策略实现稠密边的分片存储和数据全局有序分区;最后通过支持全量数据构建和两种异步数据重整模式,实现静态存量数据的更新,提升增量数据的时效性。其次,提出了一种基于自索引压缩技术的图谱数据存储方法,实现了图索引及属性数据的专用压缩和存储。首先基于rmM-tree和深度优先紧凑树编码,以简洁数据结构为基础,提出DFUDS Trie作为一跳子图索引和点边属性的紧凑表示结构,使用压缩位向量实现底层位域的存储和索引;再使用一种基于紧凑表示的枚举数组实现有序属性和一跳子图双向关系的精简存储。相较于通用压缩方法,该方法能够在牺牲部分编码和检索效率的前提下,保证图谱数据的压缩率并大幅下降的反序列化开销,实现数据的自索引压缩,进而提升系统的冷启动效率。最后,提出一种多路DFUDS Trie的高效归并方法。该方法基于图谱数据紧凑存储的特性,进一步优化了多路数据重整流程。该方法利用DFUDS编码的子树物理连续的特性,在归并过程中实现面向DFUDS Trie的动态内存换入换出策略,可以根据归并进度动态归还内存并持久化结点,可以较好的优化图谱数据重整流程中由于多路DFUDS Trie归并导致临时空间过大的问题。综上,本文首先提出一种半静态知识图谱存储系统,优化了知识图谱数据构和存储方法;随后在其中进一步引入自索引压缩技术,实现了图数据的专用压缩;最后提出了一种多路归并方法,解决了数据更新过程中内存开销过大的问题。