计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2012年
3期
144-148
,共5页
舒虎%崇志宏%倪巍伟%卢山%徐立臻
舒虎%崇誌宏%倪巍偉%盧山%徐立臻
서호%숭지굉%예외위%로산%서립진
X-Hop%可达性查询%2-Hop标记%传递闭包压缩
X-Hop%可達性查詢%2-Hop標記%傳遞閉包壓縮
X-Hop%가체성사순%2-Hop표기%전체폐포압축
海量图数据上的可达性查询是图数据管理的基本问题.目前解决这个问题的基本方法是对可达关系传递闭包进行压缩存储,再辅以快速查询算法来回答两顶点是否可达.在此基础上,重点研究了稠密图条件下可达传递闭包的高压缩比存储和有效查询算法,提出了多跳(简称为X-Hop)压缩存储方法.通过采用生成树的结构对2-Hop中的中心顶点进行组织,X-Hop存储有效地降低了2-Hop方法中需要记录的索引点数量,从而极大地提高了压缩比.实验证明,X-Hop在索引的规模上要远远小于2-Hop存储,并且在查询效率上也取得优势.
海量圖數據上的可達性查詢是圖數據管理的基本問題.目前解決這箇問題的基本方法是對可達關繫傳遞閉包進行壓縮存儲,再輔以快速查詢算法來迴答兩頂點是否可達.在此基礎上,重點研究瞭稠密圖條件下可達傳遞閉包的高壓縮比存儲和有效查詢算法,提齣瞭多跳(簡稱為X-Hop)壓縮存儲方法.通過採用生成樹的結構對2-Hop中的中心頂點進行組織,X-Hop存儲有效地降低瞭2-Hop方法中需要記錄的索引點數量,從而極大地提高瞭壓縮比.實驗證明,X-Hop在索引的規模上要遠遠小于2-Hop存儲,併且在查詢效率上也取得優勢.
해량도수거상적가체성사순시도수거관리적기본문제.목전해결저개문제적기본방법시대가체관계전체폐포진행압축존저,재보이쾌속사순산법래회답량정점시부가체.재차기출상,중점연구료주밀도조건하가체전체폐포적고압축비존저화유효사순산법,제출료다도(간칭위X-Hop)압축존저방법.통과채용생성수적결구대2-Hop중적중심정점진행조직,X-Hop존저유효지강저료2-Hop방법중수요기록적색인점수량,종이겁대지제고료압축비.실험증명,X-Hop재색인적규모상요원원소우2-Hop존저,병차재사순효솔상야취득우세.
