计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2013年
4期
172-176,192
,共6页
图%标签集约束路径查询%标签集约束路径的集合查询%倒排索引
圖%標籤集約束路徑查詢%標籤集約束路徑的集閤查詢%倒排索引
도%표첨집약속로경사순%표첨집약속로경적집합사순%도배색인
图数据模型被广泛用于社交网络、生物技术、语义网络等开放、异构环境下的数据建模.标签集约束路径查询是基本路径查询问题之一,因其具有路径描述的灵活性而受到目前研究的重视.目前重点研究布尔查询问题:判断给定顶点对间是否有满足标签集约束的路径,返回是或否.现研究布尔查询问题的正交问题,称为集合查询问题:给定标签约束集,返回满足标签集约束可达的顶点对.集合查询问题面临两个困难:1)简单地将集合查询问题简化为布尔查询问题的迭代会陷入穷举困境；2)压缩传递闭包的生成树结构虽然能够有效地回答布尔查询问题,但是,这种压缩结构不能有效支持集合查询,因为集合查询需要搜索满足约束连通的所有顶点对.为此,继续采用生成树来压缩标签路径传递闭包,用倒排索引表来加快集合查询所导致的搜索,并进一步给出两个优化算法.在大规模的数据集上的测试表明,本方法在时间和空间效率方面都具有优势.
圖數據模型被廣汎用于社交網絡、生物技術、語義網絡等開放、異構環境下的數據建模.標籤集約束路徑查詢是基本路徑查詢問題之一,因其具有路徑描述的靈活性而受到目前研究的重視.目前重點研究佈爾查詢問題:判斷給定頂點對間是否有滿足標籤集約束的路徑,返迴是或否.現研究佈爾查詢問題的正交問題,稱為集閤查詢問題:給定標籤約束集,返迴滿足標籤集約束可達的頂點對.集閤查詢問題麵臨兩箇睏難:1)簡單地將集閤查詢問題簡化為佈爾查詢問題的迭代會陷入窮舉睏境；2)壓縮傳遞閉包的生成樹結構雖然能夠有效地迴答佈爾查詢問題,但是,這種壓縮結構不能有效支持集閤查詢,因為集閤查詢需要搜索滿足約束連通的所有頂點對.為此,繼續採用生成樹來壓縮標籤路徑傳遞閉包,用倒排索引錶來加快集閤查詢所導緻的搜索,併進一步給齣兩箇優化算法.在大規模的數據集上的測試錶明,本方法在時間和空間效率方麵都具有優勢.
도수거모형피엄범용우사교망락、생물기술、어의망락등개방、이구배경하적수거건모.표첨집약속로경사순시기본로경사순문제지일,인기구유로경묘술적령활성이수도목전연구적중시.목전중점연구포이사순문제:판단급정정점대간시부유만족표첨집약속적로경,반회시혹부.현연구포이사순문제적정교문제,칭위집합사순문제:급정표첨약속집,반회만족표첨집약속가체적정점대.집합사순문제면림량개곤난:1)간단지장집합사순문제간화위포이사순문제적질대회함입궁거곤경；2)압축전체폐포적생성수결구수연능구유효지회답포이사순문제,단시,저충압축결구불능유효지지집합사순,인위집합사순수요수색만족약속련통적소유정점대.위차,계속채용생성수래압축표첨로경전체폐포,용도배색인표래가쾌집합사순소도치적수색,병진일보급출량개우화산법.재대규모적수거집상적측시표명,본방법재시간화공간효솔방면도구유우세.
