一种面向图集合的相似性搜索技术

doi:10.12068/j.issn.1005-3026.2017.05.004

东北大学学报:自然科学版 ›› 2017, Vol. 38 ›› Issue (5): 625-629.DOI: 10.12068/j.issn.1005-3026.2017.05.004

一种面向图集合的相似性搜索技术

庞俊，谷峪，于戈

(东北大学计算机科学与工程学院，辽宁沈阳110819)

收稿日期:2015-12-10 修回日期:2015-12-10 出版日期:2017-05-15 发布日期:2017-05-11
通讯作者: 庞俊
作者简介:庞俊(1984-)，男，湖北咸宁人，东北大学博士研究生; 谷峪(1981-)，男，辽宁鞍山人，东北大学教授，博士生导师; 于戈(1962-)，男，辽宁大连人，东北大学教授，博士生导师.
基金资助:
国家重点基础研究发展计划项目(2012CB316201)；国家自然科学基金资助项目(61272179， 61472071).

A Similarity Search Technique for Graph Set

PANG Jun， GU Yu， YU Ge

School of Computer Science & Engineering， Northeastern University， Shenyang 110819， China.

Received:2015-12-10 Revised:2015-12-10 Online:2017-05-15 Published:2017-05-11
Contact: YU Ge
About author:-
Supported by:
-

摘要/Abstract

摘要：

目前图相似性的研究工作主要集中在子图的匹配，而没有充分关注图集合之间的匹配.针对这一问题，提出了一种基于过滤-求精框架的GSSS算法;提出了一种图集合距离定义，设计了Number，Size，Complete edge和Lower bound过滤器减小搜索空间，优化了图集合距离的计算;设计并优化了一种增量式的多层倒排索引，提高了查询效率，适应数据集的动态变化.真实数据集上的大量实验验证了GSSS算法的有效性和高效性.

关键词: 图集合, 相似性, 搜索, 索引, 过滤

Abstract:

Existing studies of graph similarity search mainly focus on the subgraph matching instead of the graph set matching. To tackle this issue， GSSS algorithm was proposed based on filtering-and-verify framework. A graph set distance was defined. In order to reduce the search space， Number filter， Size filter， Complete edge filter and Lower bound filter were proposed. Then， the computation of the graph set distance was optimized. An incremental multi-layer inverted index was designed to further improve the query efficiency. Extensive experiments on a real-world dataset show that GSSS algorithm is effective and efficient.

Key words: graph set, similarity, search, index, filter

中图分类号:

TP311

庞俊，谷峪，于戈. 一种面向图集合的相似性搜索技术[J]. 东北大学学报:自然科学版, 2017, 38(5): 625-629.

PANG Jun， GU Yu， YU Ge. A Similarity Search Technique for Graph Set[J]. Journal of Northeastern University:Natural Science, 2017, 38(5): 625-629.

参考文献

[1]Zheng Z，Tung A K H，Wang J，et al.Comparing stars:on approximating graph edit distance［C］//Proceedings of the VLDB Endowment.Lyon，2009:25-36.
[2]Wang G R，Wang B，Yang X C，et al.Efficiently indexing large sparse graphs for similarity search［J］.IEEE Transactions on Knowledge and Data Engineering，2012，24(3):440-451.
[3]Zhao X，Xiao C，Lin X M，et al.Efficient graph similarity joins with edit distance constraints［C］//Proceedings of the 28th International Conference on Data Engineering.Washington D C，2012:210-221.
[4]Zhao X，Xiao C，Lin X M，et al.A partition-based approach to structure similarity search［C］//Proceedings of the VLDB Endowment.Hangzhou，2013，7(3):169-180.
[5]Pang J，Gu Y，Xu J，et al.Efficient graph similarity join with scalable prefix-filtering using MapReduce［C］//Proceedings of the 15th International Conference on Web-Age Information Management.Macau，2014:415-418.
[6]Zheng W G，Zou L，Lian X，et al.Efficient graph similarity search over large graph databases［J］. IEEE Transactions on Knowledge and Data Engineering，2015，27(4):964-978.
[7]Li R H，Qin L，Yu X J，et al.Influential community search in large networks ［C］// Proceedings of the VLDB Endowment.Hawaii，2015，8(5):509-520.
[8]Huang X，Cheng H，Li R H，et al.Top-k structural diversity search in large networks［J］.International Journal on Very Large Data Bases，2015，24(3):319-343.
[9]Xu J，Zhang Z J，Anthony K H，et al.Efficient and effective similarity search over probabilistic data based on earth mover’s distance［C］//Proceedings of the VLDB Endowment.Singapore，2010，3(1):758-769.
[10]Li G L，Deng D，Feng J H.A partition-based method for string similarity joins with edit-distance constraints ［J］.ACM Transactions on Database Systems，2013，38(2):721-741.
[11]Yang X C，Wang Y S，Wang B，et al.Local filtering:improving the performance of approximate queries on string collections［C］ //Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data.Melbourne，2015:377-392.
[12]Wu J，Zhu X Q，Zhang C Q，et al.Bag constrained structure pattern mining for multi-graph classification ［J］. IEEE Transactions on Knowledge and Data Engineering，2014，26(10):2382-2396.

[1]	李占山，杨云凯，张家晨. 基于熵权法的过滤式特征选择算法[J]. 东北大学学报（自然科学版）, 2022, 43(7): 921-929.
[2]	林秀丽，赵一璇，柳静献. 荷尘速率对非高效过滤材料阻力特性的影响[J]. 东北大学学报（自然科学版）, 2022, 43(7): 1056-1064.
[3]	于长永，王雯函，温秀静，赵宇海. 基于动态双重前缀的模糊相似性连接算法[J]. 东北大学学报（自然科学版）, 2022, 43(3): 321-327.
[4]	张晶，李传文. 一种基于安全索引的位置隐私保护方法[J]. 东北大学学报（自然科学版）, 2022, 43(12): 1702-1708.
[5]	葛悦，李宇溪，周福才，张鑫月. 具有前向安全特性的密态图像搜索方案[J]. 东北大学学报（自然科学版）, 2021, 42(8): 1079-1085.
[6]	王姝，关展旭，王晶，孙晓辉. 基于迁移学习的贝叶斯网络参数学习方法[J]. 东北大学学报（自然科学版）, 2021, 42(4): 509-515.
[7]	李占山，姚鑫，刘兆赓，张家晨. 基于LightGBM的特征选择算法[J]. 东北大学学报（自然科学版）, 2021, 42(12): 1688-1695.
[8]	杨宜舟，吴立新，郭甲腾，刘善军. 基于并行叠加的国土空间开发适宜性评价[J]. 东北大学学报（自然科学版）, 2021, 42(11): 1585-1590.
[9]	厉鹏，周福才，张帅. 基于BSSEVD的可搜索加密方案原型系统设计与实现[J]. 东北大学学报:自然科学版, 2020, 41(9): 1244-1250.
[10]	郑佳文，赫伟东，郭颖赫，柳静献. 过滤强化用极性硅盐粉末的鉴别优选[J]. 东北大学学报:自然科学版, 2020, 41(3): 430-437.
[11]	袁中臣，马宗民. 基于语义和结构的UML类图的检索[J]. 东北大学学报:自然科学版, 2020, 41(1): 23-28.
[12]	陈东明，袁泽枝，黄新宇，王冬琦. 时态网络节点相似性度量及链路预测算法[J]. 东北大学学报:自然科学版, 2020, 41(1): 29-35.
[13]	孔芝，杨青峰，赵杰，熊浚钧. 基于自适应调整权重和搜索策略的鲸鱼优化算法[J]. 东北大学学报:自然科学版, 2020, 41(1): 35-43.
[14]	张云洲，郑瑞，暴吉宁，朱尚栋. 基于多个相关滤波器的行人跟踪尺度算法[J]. 东北大学学报:自然科学版, 2019, 40(9): 1228-1234.
[15]	贾强，张帅，周福才. 一种面向密文大型数据集的可搜索加密方案[J]. 东北大学学报:自然科学版, 2019, 40(7): 913-919.

一种面向图集合的相似性搜索技术

A Similarity Search Technique for Graph Set

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价