计算机应用
計算機應用
계산궤응용
COMPUTER APPLICATION
2014年
12期
3475-3480
,共6页
关键字%查询%位图局部敏感哈希%n-gram
關鍵字%查詢%位圖跼部敏感哈希%n-gram
관건자%사순%위도국부민감합희%n-gram
graph%keyword%query%Bitmap and Locality-sensitive Hashing (BLH)%n-gram
针对目前基于倒排表的图关键字索引不能有效处理多个关键字查询,也不能对关键字拼写容错的问题,提出一种位图和局部敏感哈希(BLH)相结合的双层索引来支持图的多关键字查询:上层构建位图,依据关键字组合的n-gram映射到子图类簇,每个类簇存储相似的子图;下层在每个类簇上构建局部敏感哈希索引,根据关键字组合的n-gram定位到包含关键字组合的子图.该方法可显著减少图上关键字查询的I/O,查询时间缩减80%;并且,基于n-gram构建索引,可以避免索引对拼写错误敏感,在关键字容错的前提下返回用户期望的结果.实际数据集上的实验结果表明BLH索引的有效性,可以支持万维网、社会网络的高效查询.
針對目前基于倒排錶的圖關鍵字索引不能有效處理多箇關鍵字查詢,也不能對關鍵字拼寫容錯的問題,提齣一種位圖和跼部敏感哈希(BLH)相結閤的雙層索引來支持圖的多關鍵字查詢:上層構建位圖,依據關鍵字組閤的n-gram映射到子圖類簇,每箇類簇存儲相似的子圖;下層在每箇類簇上構建跼部敏感哈希索引,根據關鍵字組閤的n-gram定位到包含關鍵字組閤的子圖.該方法可顯著減少圖上關鍵字查詢的I/O,查詢時間縮減80%;併且,基于n-gram構建索引,可以避免索引對拼寫錯誤敏感,在關鍵字容錯的前提下返迴用戶期望的結果.實際數據集上的實驗結果錶明BLH索引的有效性,可以支持萬維網、社會網絡的高效查詢.
침대목전기우도배표적도관건자색인불능유효처리다개관건자사순,야불능대관건자병사용착적문제,제출일충위도화국부민감합희(BLH)상결합적쌍층색인래지지도적다관건자사순:상층구건위도,의거관건자조합적n-gram영사도자도류족,매개류족존저상사적자도;하층재매개류족상구건국부민감합희색인,근거관건자조합적n-gram정위도포함관건자조합적자도.해방법가현저감소도상관건자사순적I/O,사순시간축감80%;병차,기우n-gram구건색인,가이피면색인대병사착오민감,재관건자용착적전제하반회용호기망적결과.실제수거집상적실험결과표명BLH색인적유효성,가이지지만유망、사회망락적고효사순.