CAJ | 학술논문

现实世界中的图往往在结点和边上包含描述信息，可达性查询是图数据管理和挖掘中的基本操作之一。针对图数据中标签约束的可达性计算问题，提出一种基于递归划分的可达性计算方法RP-Hop。该算法基于层次划分思想，利用独立集性质，在保持标签和可达性前提下对大规模图进行递归划分，并结合贪婪扩展思想和递归编码，为标签约束的可达性查询提供压缩索引。经过合成和真实数据集上的实验，结果表明，RP-Hop算法不仅降低了索引大小和构建时间，而且提高了查询效率。
현실세계중적도왕왕재결점화변상포함묘술신식，가체성사순시도수거관리화알굴중적기본조작지일。침대도수거중표첨약속적가체성계산문제，제출일충기우체귀화분적가체성계산방법RP-Hop。해산법기우층차화분사상，이용독립집성질，재보지표첨화가체성전제하대대규모도진행체귀화분，병결합탐람확전사상화체귀편마，위표첨약속적가체성사순제공압축색인。경과합성화진실수거집상적실험，결과표명，RP-Hop산법불부강저료색인대소화구건시간，이차제고료사순효솔。
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.