图上基于局部敏感哈希的多关键字索引

计算机应用 ›› 2014, Vol. 34 ›› Issue (12): 3475-3480.

图上基于局部敏感哈希的多关键字索引

韩京宇,杨健

南京邮电大学计算机学院, 南京 210003

收稿日期:2014-07-08 修回日期:2014-09-15 发布日期:2014-12-31 出版日期:2014-12-01
通讯作者: 韩京宇
作者简介:韩京宇(1976-),男,吉林白山人,副教授,博士,CCF会员,主要研究方向:数据管理、知识库；杨健(1978-),男,江苏徐州人,副教授,博士,主要研究方向:信息系统、知识库。
基金资助:
国家自然科学基金资助项目

Locality-sensitive hashing index for multiple keywords over graphs

HAN Jingyu,YANG Jian

School of Computer Science and Technology, Nanjing University of Posts and Telecommunications, Nanjing Jiangsu 210003, China

Received:2014-07-08 Revised:2014-09-15 Online:2014-12-31 Published:2014-12-01
Contact: HAN Jingyu

摘要/Abstract

摘要：

针对目前基于倒排表的图关键字索引不能有效处理多个关键字查询,也不能对关键字拼写容错的问题,提出一种位图和局部敏感哈希(BLH）相结合的双层索引来支持图的多关键字查询:上层构建位图,依据关键字组合的n-gram映射到子图类簇,每个类簇存储相似的子图；下层在每个类簇上构建局部敏感哈希索引,根据关键字组合的n-gram定位到包含关键字组合的子图。该方法可显著减少图上关键字查询的I/O,查询时间缩减80%；并且,基于n-gram构建索引,可以避免索引对拼写错误敏感,在关键字容错的前提下返回用户期望的结果。实际数据集上的实验结果表明BLH索引的有效性,可以支持万维网、社会网络的高效查询。

Abstract:

As existing inverted index not only cannot efficiently handle multiple-keyword query, but also cannot find results for misspelled keywords, a bi-level index leveraging Bitmap and Locality-sensitive Hashing (BLH) was proposed to support multiple-keyword queries. The upper-level of BLH is bitmaps, which map keywords onto clusters of sub-graphs based on the n-grams in the keywords. Each cluster stores the similar sub-graphs. On the lower-level, each cluster has a locality-sensitive hashing index, which helps identify the sub-graphs that contain the keywords based on their n-grams. The indexing scheme of BLH can dramatically decrease query I/Os, thus reducing the query time by 80%. Furthermore, the index based on n-gram can avoid the sensitivity to spelling mistakes of keywords, guaranteeing to return expected results in any case. The experimental results on real data sets demonstrate the effectiveness of the BLH index, which can efficiently support the querying of Web and social network.

中图分类号:

TP311.13

韩京宇杨健. 图上基于局部敏感哈希的多关键字索引[J]. 计算机应用, 2014, 34(12): 3475-3480.

HAN Jingyu YANG Jian. Locality-sensitive hashing index for multiple keywords over graphs[J]. Journal of Computer Applications, 2014, 34(12): 3475-3480.

参考文献

［1］MA S, LI J, LIU X, et al. graph search: a new searching approach in the social computing era［J］. Communications of the CCF,2012,8(11):26-31.(马帅,李佳,刘旭东,等.图查询:社会计算时代的新型搜索［J］.计算机学会通讯,2012,8(11):26-31.)

［2］WANG N, WANG B, LI X, et al. Subgraph queries over dynamic graph data［J］. Journal of Frontiers of Computer Science and Technology, 2014,8(2):139-149.(王楠,王斌,李晓华,等. 支持动态图数据的子图查询方法［J］.计算机科学与探索,2014,8(2):139-149.)
［3］YU G, GU Y, BAO Y, et al.Large scale graph processing on cloud computing environments［J］. Chinese Journal of Computers, 2011, 34(10): 1753-1767.(于戈.谷峪,鲍玉斌,等.云计算环境下的大规模图数据处理技术［J］.计算机学报,2011,34(10):1753-1767.)
［4］ADIYA B, BHALOTIA G, CHAKRABARTI S, et al. BANKS: browsing and keyword searching in relational databases［C］// Proceedings of the 28th International Conference on Very Large Databases. New York: VLDB Endowment, 2002:1083-1086.
［5］AGRAWAL S, CHAUDHURI S, DAS G. DBXplorer: a system for keyword-based search over relational databases［C］// Proceedings of the 18th International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2002: 5-16.
［6］DING B, XU J, YU S, et al. Finding top-k min-cost connected trees in databases［C］// Proceedings of the 23rd International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2007:836-845.
［7］GOLENBERG K, KIMELFELD B, SAGIV Y. Keyword proximity search in complex data graphs［C］// Proceedings of the 2008 ACM Special Interest Group on Management of Data. New York: ACM, 2008:927-940.
［8］GUO L, SHAO F, BOTEV C, et al. Xrank: ranked keyword search over XML documents［C］// Proceedings of the 2006 ACM Special Interest Group on Management of Data. New York: ACM, 2003:16-27.
［9］LI G, FENG J, BENG C O,et al. EASE: an effective 3-in-1 keyword search method over heterogeneous sources［J］. Information Systems, 2011, 36(2): 248-266.
［10］KIM S, LEE W, ARORA N R, et al. Retrieving keyworded subgraphs with graph ranking score［J］. Expert Systems with Applications, 2012, 39(5):4647-4656.

[1]	高威刘丽华和斌涛邓方安. 区块链共识机制与改进算法研究进展[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[2]	陈姿芊, 牛科迪, 姚中原, 斯雪明. 适用于物联网的区块链轻量化技术综述[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3688-3698.
[3]	高婷婷, 姚中原, 贾淼, 斯雪明. 链上链下一致性保护技术综述[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3658-3668.
[4]	贾淼, 姚中原, 祝卫华, 高婷婷, 斯雪明, 邓翔. 零知识证明赋能区块链的进展与展望[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3669-3677.
[5]	牛科迪, 李敏, 姚中原, 斯雪明. 面向物联网的区块链共识算法综述[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3678-3687.
[6]	杨巍白璐宁俊义董建军单春海信俊昌. 异构环境感知的幂律图流划分方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[7]	秦学程刘春颜李宝赵蕴龙. 面向工业场景的云边协同数据存储与检索架构[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[8]	蒋辉, 闫秋艳, 姜竹郡. 面向多元时间序列异常检测的对称正定自编码器方法[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3294-3299.
[9]	宋洪涛, 于江生, 韩启龙. 工业多元时序数据质量评估方法[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1743-1750.
[10]	孟玉飞, 武优西, 王珍, 李艳. 对比保序模式挖掘算法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3740-3746.
[11]	王佳鑫, 颜嘉麒, 毛谦昂. 加密数字货币监管技术研究综述[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 2983-2995.
[12]	黄硕, 李艳辉, 曹建秋. 本地化差分隐私下的频繁序列模式挖掘算法PrivSPM[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2057-2064.
[13]	金泳, 高扬华, 潘晓华, 沈诗婧, 朱心洲. 采用数据血缘的数据热度预测方法[J]. 《计算机应用》唯一官方网站, 2023, 43(S1): 119-125.
[14]	马志峰, 于俊洋, 王龙葛. 多样性表示的深度子空间聚类算法[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 407-412.
[15]	王旭, 申玉民, 熊晓芸, 李鹏, 王金龙. 基于哈希图的建筑物联网数据管理方法[J]. 《计算机应用》唯一官方网站, 2022, 42(8): 2471-2480.