一種基于圖測度的子圖相似查詢方法

基本信息

申請?zhí)?/td> CN201610159306.0 申請日 -
公開（公告）號 CN105825237B 公開（公告）日 2019-03-01
申請公布號 CN105825237B 申請公布日 2019-03-01
分類號 G06K9/62;G06F16/56 分類 計算；推算；計數(shù);
發(fā)明人 呂雪嶺;彭云 申請（專利權(quán)）人 山東聯(lián)科云計算股份有限公司
代理機構(gòu) - 代理人 -
地址 250101 山東省濟南市高新區(qū)新濼大街1299號鑫盛大廈2號樓1004-1
法律狀態(tài) -

摘要

摘要 本發(fā)明屬于數(shù)據(jù)庫技術(shù)領(lǐng)域，具體涉及一種基于圖測度的子圖相似查詢方法。本方案所描述子圖相似為：給定數(shù)據(jù)圖的集合D={G1,G2,…,Gn}、查詢圖q和子圖相似距離閾值s，從D中找出所有和q的子圖相似距離小于s的數(shù)據(jù)圖。本方案先將不同測度的子圖相似距離的估算轉(zhuǎn)化為圖測度距離的估算，再根據(jù)圖測度距離的估算進行過濾，完成子圖相似查詢，進一步構(gòu)建圖測度樹，基于圖測度樹進行子圖相似查詢。將非同意測度的子圖相似距離的估計轉(zhuǎn)化為圖測度距離的估計，進而可使用三角不等式進行過濾；既支持連通子圖的相似查詢，也可以支持不連通的子圖相似查詢；設(shè)計一個圖測度樹來對數(shù)據(jù)圖合集中的數(shù)據(jù)圖進行索引，大大提高查詢的效率。