通信学报
通信學報
통신학보
Journal on Communications
2015年
8期
50-60
,共11页
周军锋%陈伟%费春苹%陈子阳
週軍鋒%陳偉%費春蘋%陳子暘
주군봉%진위%비춘평%진자양
k步可达性查询%双向搜索%广度层数%拓扑层数
k步可達性查詢%雙嚮搜索%廣度層數%拓撲層數
k보가체성사순%쌍향수색%엄도층수%탁복층수
k-step reachability query%bidirectional search%breadth level%topological level
针对现有方法低效或索引规模庞大的问题,提出一种双向搜索算法BiRch.当判断顶点u是否满足k步可达顶点v时,首先比较u的出度和v的入度,优先处理度小的顶点.其优点体现在使用较小的索引,同时避免由于u的出度过大所带来的效率下降问题;提出基于双向广度层数和双向拓扑层数的剪枝策略来辅助过滤,减少需要访问的顶点数量.基于19个真实数据集进行测试,实验结果从索引构建时间、索引大小、查询响应时间、处理顶点数量以及扩展性方面验证了所提方法相对于现有方法的高效性.
針對現有方法低效或索引規模龐大的問題,提齣一種雙嚮搜索算法BiRch.噹判斷頂點u是否滿足k步可達頂點v時,首先比較u的齣度和v的入度,優先處理度小的頂點.其優點體現在使用較小的索引,同時避免由于u的齣度過大所帶來的效率下降問題;提齣基于雙嚮廣度層數和雙嚮拓撲層數的剪枝策略來輔助過濾,減少需要訪問的頂點數量.基于19箇真實數據集進行測試,實驗結果從索引構建時間、索引大小、查詢響應時間、處理頂點數量以及擴展性方麵驗證瞭所提方法相對于現有方法的高效性.
침대현유방법저효혹색인규모방대적문제,제출일충쌍향수색산법BiRch.당판단정점u시부만족k보가체정점v시,수선비교u적출도화v적입도,우선처리도소적정점.기우점체현재사용교소적색인,동시피면유우u적출도과대소대래적효솔하강문제;제출기우쌍향엄도층수화쌍향탁복층수적전지책략래보조과려,감소수요방문적정점수량.기우19개진실수거집진행측시,실험결과종색인구건시간、색인대소、사순향응시간、처리정점수량이급확전성방면험증료소제방법상대우현유방법적고효성.
