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

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

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

韩京宇,杨健

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

收稿日期:2014-07-08 修回日期:2014-09-15 出版日期:2014-12-01 发布日期:2014-12-31
通讯作者: 韩京宇
作者简介:韩京宇(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-01 Published:2014-12-31
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]. 计算机应用, 2021, 41(8): 2396-2405.
[2]	冯钧王秉发陆佳民. 分布式资源描述框架数据管理系统查询性能评价[J]. 计算机应用, 0, (): 0-0.
[3]	李国荣, 冶继民, 甄远婷. 基于新的鲁棒相似性度量的时间序列聚类[J]. 计算机应用, 2021, 41(5): 1343-1347.
[4]	林定康颜嘉麒巴·楠登符朕皓姜皓晨. 门罗币匿名及追踪技术综述[J]. 计算机应用, 0, (): 0-0.
[5]	沈忱, 邰凌翔, 彭煜玮. 面向自动参数调优的动态负载匹配方法[J]. 计算机应用, 2021, 41(3): 657-661.
[6]	杨程, 陆佳民, 冯钧. 分布式环境下大规模资源描述框架数据划分方法综述[J]. 计算机应用, 2020, 40(11): 3184-3191.
[7]	兰海, 韩珂, 申砾, 崔秋, 彭煜玮. TiDB的多索引访问优化[J]. 计算机应用, 2020, 40(2): 410-415.
[8]	崔艺馨, 陈晓东. Spark框架优化的大规模谱聚类并行算法[J]. 计算机应用, 2020, 40(1): 168-172.
[9]	万静, 郑龙君, 何云斌, 李松. 高维不确定数据的子空间聚类算法[J]. 计算机应用, 2019, 39(11): 3280-3287.
[10]	李博, 张晓, 颜靖艺, 李可威, 李恒, 凌玉龙, 张勇. 基于值差度量和聚类优化的K最近邻算法在银行客户行为预测中的应用[J]. 计算机应用, 2019, 39(9): 2784-2788.
[11]	李耘书, 滕飞, 李天瑞. 基于微操作的Hadoop参数自动调优方法[J]. 计算机应用, 2019, 39(6): 1589-1594.
[12]	霍峥, 张坤, 贺萍, 武彦斌. 满足本地化差分隐私的众包位置数据采集[J]. 计算机应用, 2019, 39(3): 763-768.
[13]	朱跃龙, 朱晓晓, 王继民. 基于子序列全连接和最大团的时间序列模体发现算法[J]. 计算机应用, 2019, 39(2): 414-420.
[14]	尹远, 张昌, 文凯, 郑云俊. 基于DiffNodeset结构的最大频繁项集挖掘算法[J]. 计算机应用, 2018, 38(12): 3438-3443.
[15]	曲立平, 吴家喜. 基于评分可靠性的跨域个性化推荐方法[J]. 计算机应用, 2018, 38(11): 3081-3083.