| 引用本文: | 吴烨,钟志农,熊伟,等.递归划分的标签约束可达性计算方法.[J].国防科技大学学报,2014,36(5):98-104.[点击复制] |
| WU Ye,ZHONG Zhinong,XIONG Wei,et al.A label constraint reachability computation method on recursive partition[J].Journal of National University of Defense Technology,2014,36(5):98-104[点击复制] |
|
| |
|
|
| 本文已被：浏览 10860次 下载 7126次 |
| 递归划分的标签约束可达性计算方法 |
| 吴烨, 钟志农, 熊伟, 景宁 |
|
(国防科技大学 电子科学与工程学院， 湖南 长沙 410073)
|
| 摘要: |
| 现实世界中的图往往在结点和边上包含描述信息，可达性查询是图数据管理和挖掘中的基本操作之一。针对图数据中标签约束的可达性计算问题，提出一种基于递归划分的可达性计算方法RP-Hop。该算法基于层次划分思想，利用独立集性质，在保持标签和可达性前提下对大规模图进行递归划分，并结合贪婪扩展思想和递归编码，为标签约束的可达性查询提供压缩索引。经过合成和真实数据集上的实验，结果表明，RP-Hop算法不仅降低了索引大小和构建时间，而且提高了查询效率。 |
| 关键词: 标签约束可达性 递归划分 2-hop编码 |
| DOI：10.11887/j.cn.201405017 |
| 投稿日期：2014-01-02 |
| 基金项目:国家自然科学基金资助项目（61070035）；湖南省自然科学基金资助项目（11JJ4028） |
|
| A label constraint reachability computation method on recursive partition |
| WU Ye, ZHONG Zhinong, XIONG Wei, JING Ning |
|
(College of Electronic Science and Engineering, National University of Defense Technology, Changsha 410073, China)
|
| Abstract: |
| Many of the real-world graphs are edge-labeled or node-labeled. A foundational operation on these labeled graphs is how to answer reachability queries fast. For the label-constraint reachability computation problem, a computation method called RP-Hop based on recursive partition was proposed. RP-Hop first utilized the hierarchical structure and independent set property to partition the origin large graph recursively, while keeping reachability and labels on paths between node pairs simultaneously. Combined with greedy and recursive labeling strategies, RP-Hop produced a compressed index for label-constraint reachability queries. Experiments on synthetic and real-world graph data sets demonstrate that RP-Hop can reduce index size and construction time, and guarantee the query efficiency. |
| Keywords: label constraint reachability recursive partition 2-hop labeling |
|
|
