计算机学报
計算機學報
계산궤학보
CHINESE JOURNAL OF COMPUTERS
2011年
10期
1885-1896
,共12页
不确定图%近邻查询%可靠期望距离%近邻关系图
不確定圖%近鄰查詢%可靠期望距離%近鄰關繫圖
불학정도%근린사순%가고기망거리%근린관계도
图的不确定性普遍存在,研究不确定图的高效查询处理具有重要意义.文中提出了不确定图上一种新型查询——近邻查询.给定一个查询标签集R和距离约束σ,在不确定图G上进行近邻查询是要找到标签集包含R并且任意两个顶点间距离不超过σ的匹配顶点集.为解决该问题,文中首先提出了“可靠期望距离”,然后基于可靠期望距离建立了高效的近邻关系图索引,将不确定图上的近邻查询等价地转化为近邻关系图上的团查询问题,最后使用树搜索算法解决近邻关系图上的团查询问题.理论分析和实验结果表明文中提出的算法能够高效地完成不确定图上的top-k近邻查询.
圖的不確定性普遍存在,研究不確定圖的高效查詢處理具有重要意義.文中提齣瞭不確定圖上一種新型查詢——近鄰查詢.給定一箇查詢標籤集R和距離約束σ,在不確定圖G上進行近鄰查詢是要找到標籤集包含R併且任意兩箇頂點間距離不超過σ的匹配頂點集.為解決該問題,文中首先提齣瞭“可靠期望距離”,然後基于可靠期望距離建立瞭高效的近鄰關繫圖索引,將不確定圖上的近鄰查詢等價地轉化為近鄰關繫圖上的糰查詢問題,最後使用樹搜索算法解決近鄰關繫圖上的糰查詢問題.理論分析和實驗結果錶明文中提齣的算法能夠高效地完成不確定圖上的top-k近鄰查詢.
도적불학정성보편존재,연구불학정도적고효사순처리구유중요의의.문중제출료불학정도상일충신형사순——근린사순.급정일개사순표첨집R화거리약속σ,재불학정도G상진행근린사순시요조도표첨집포함R병차임의량개정점간거리불초과σ적필배정점집.위해결해문제,문중수선제출료“가고기망거리”,연후기우가고기망거리건립료고효적근린관계도색인,장불학정도상적근린사순등개지전화위근린관계도상적단사순문제,최후사용수수색산법해결근린관계도상적단사순문제.이론분석화실험결과표명문중제출적산법능구고효지완성불학정도상적top-k근린사순.
