X-Hop:传递闭包的多跳数压缩存储和快速可达性查询

• 作者: 倪巍伟 卢山 崇志宏 徐立臻 舒虎
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: X-Hop 可达性查询 2-Hop标记 传递闭包压缩
• 年，卷（期）: 2012,（3）
• 所属期刊栏目: 数据库与数据挖掘
• 页码范围: 144-148
• 分类号: TP392
• 字数: 7618字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2012.03.033

摘要

海量图数据上的可达性查询是图数据管理的基本问题.目前解决这个问题的基本方法是对可达关系传递闭包进行压缩存储,再辅以快速查询算法来回答两顶点是否可达.在此基础上,重点研究了稠密图条件下可达传递闭包的高压缩比存储和有效查询算法,提出了多跳(简称为X-Hop)压缩存储方法.通过采用生成树的结构对2-Hop中的中心顶点进行组织,X-Hop存储有效地降低了2-Hop方法中需要记录的索引点数量,从而极大地提高了压缩比.实验证明,X-Hop在索引的规模上要远远小于2-Hop存储,并且在查询效率上也取得优势.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	倪巍伟	东南大学计算机科学与工程学院	48	851	19.0	27.0
2	徐立臻	东南大学计算机科学与工程学院	52	1042	17.0	31.0
3	卢山	东南大学计算机科学与工程学院	12	140	7.0	11.0
4	崇志宏	东南大学计算机科学与工程学院	15	181	7.0	13.0
5	舒虎	东南大学计算机科学与工程学院	1	3	1.0	1.0