计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2011年
z2期
721-727
,共7页
子图包含查询%有向无环图%拓扑序列%子图同构%图索引
子圖包含查詢%有嚮無環圖%拓撲序列%子圖同構%圖索引
자도포함사순%유향무배도%탁복서렬%자도동구%도색인
图模型具有强大的表达能力,被广泛用于各种应用领域的数据建模.如何在大规模图数据库中进行高效子图包含查询是当前的研究难点之一.由于子图同构是一个NP完全问题,在现有的子图包含查询算法中,基于图特征的索引技术被广泛用来提高查询处理性能,但是这些索引结构的维护代价较高.针对有向无环图提出了一种基于拓扑序列的子图包含查询算法,首先根据图中节点的偏序关系将有向图分层拓扑为一个序列,然后利用序列间的匹配关系过滤出候选结果集,最后通过子图同构检测验证得到最终结果集.相关性能测试表明,该算法无需构造复杂的索引结构,便于图数据库的动态维护,在有向无环图在线查询性能上表现出色.
圖模型具有彊大的錶達能力,被廣汎用于各種應用領域的數據建模.如何在大規模圖數據庫中進行高效子圖包含查詢是噹前的研究難點之一.由于子圖同構是一箇NP完全問題,在現有的子圖包含查詢算法中,基于圖特徵的索引技術被廣汎用來提高查詢處理性能,但是這些索引結構的維護代價較高.針對有嚮無環圖提齣瞭一種基于拓撲序列的子圖包含查詢算法,首先根據圖中節點的偏序關繫將有嚮圖分層拓撲為一箇序列,然後利用序列間的匹配關繫過濾齣候選結果集,最後通過子圖同構檢測驗證得到最終結果集.相關性能測試錶明,該算法無需構造複雜的索引結構,便于圖數據庫的動態維護,在有嚮無環圖在線查詢性能上錶現齣色.
도모형구유강대적표체능력,피엄범용우각충응용영역적수거건모.여하재대규모도수거고중진행고효자도포함사순시당전적연구난점지일.유우자도동구시일개NP완전문제,재현유적자도포함사순산법중,기우도특정적색인기술피엄범용래제고사순처이성능,단시저사색인결구적유호대개교고.침대유향무배도제출료일충기우탁복서렬적자도포함사순산법,수선근거도중절점적편서관계장유향도분층탁복위일개서렬,연후이용서렬간적필배관계과려출후선결과집,최후통과자도동구검측험증득도최종결과집.상관성능측시표명,해산법무수구조복잡적색인결구,편우도수거고적동태유호,재유향무배도재선사순성능상표현출색.
