基于连接位Minwise Hash的三者相似性估计算法

上海交通大学学报（自然版） ›› 2014, Vol. 48 ›› Issue (07): 936-941.

• 自动化技术、计算机技术 • 上一篇下一篇

基于连接位Minwise Hash的三者相似性估计算法

袁鑫攀1,盛鑫海1,龙军2,张祖平2,桂卫华2

（1.湖南工业大学计算机与通信学院, 湖南株洲 412000; 2.中南大学信息科学与工程学院,长沙 410083）

收稿日期:2013-08-19 出版日期:2014-07-28 发布日期:2014-07-28
基金资助:
国家自然科学基金(61121008，60970095，60873081，61350011)，科技部科技支撑计划（2013BAJ10B145），湖南省杰出青年基金(11JJ1012)，湖南省自然科学基金重点项目（12JJ2036），湖南省自然科学基金面上项目（14JJ2115）资助

Estimation of Three-Way Similarities Based on Connected Bit Minwise Hash

YUAN Xinpan1,SHENG Xinhai1,LONG Jun2,ZHANG Zuping2,GUI Weihua2

（1. College of Computer and Communication, Hunan University of Technology， Zhuzhou 412000, Hunan, China; 2. School of Information Science and Engineering, Central South University, Changsha 410083, China）

Received:2013-08-19 Online:2014-07-28 Published:2014-07-28

摘要/Abstract

摘要：

计算相似性是信息检索的一个核心基础问题，二者、三者甚至更多集合的相似性估计在相似文档检测、词语相关性、聚类、数据清理等领域有着广泛的应用. 连接位Minwise Hash算法作为一种高效、准确的相似性估计算法，能够成倍地减少比对的次数，提升算法性能. 通过理论推导，给出基于连接位Minwise Hash的三者相似度无偏估计公式.实验结果显示，在样本大小k=500、相似度阈值R0=0.8时，算法的准确率和召回率均能达到95%以上，并且所需的CPU运行时间仅为b位Minwise Hash三者估计算法的50%.

关键词: 三者相似度, 三者相似性估计, 连接位, 信息检索

Abstract:

Compution of two-way and multi-way set similarities is a fundamental problem in information retrieval. This paper focused on estimation of threeway resemblance using connected bit Minwise Hash. As an efficient and accurate method for similarity measurement, connected bit Minwise Hash can reduce the number of comparison, and exponentially improve the performance. The unbiased estimator of the threeway resemblance was provided theoretically. In experimental result analysis, several key parameters (e.g., precision, recall and efficiency) were analyzed. Experimental results demonstrate that when the sample size k=500 and similarity threshold R0=0.8, the accuracy and recall of the algorithm could reach 95% or more, using just 50% of CPU running time of b-bit Minwise Hash for the three-way estimation.

Key words: three-way resemblance； similarity estimation for three way； connected bit, information retrieval

中图分类号:

TP 301.6

袁鑫攀1,盛鑫海1,龙军2,张祖平2,桂卫华2. 基于连接位Minwise Hash的三者相似性估计算法[J]. 上海交通大学学报（自然版）, 2014, 48(07): 936-941.

YUAN Xinpan1,SHENG Xinhai1,LONG Jun2,ZHANG Zuping2,GUI Weihua2. Estimation of Three-Way Similarities Based on Connected Bit Minwise Hash[J]. Journal of Shanghai Jiaotong University, 2014, 48(07): 936-941.

参考文献

［1］Wilson R A, Keil F C. The MIT encyclopedia of the cognitive sciences ［M］. Cambridge, MA, USA：MIT Press, 2006: 763765.

［2］Broder A Z. On the resemblance and containment of documents ［C］∥ Proceedings of Compression and Complexity of Sequences. Washington, DC, USA: IEEE Computer Society, 1997: 2129.

［3］Church K, Hanks P. Word association norms, mutual information and lexicography［J］. Computational Linguistics, 1991, 16(1): 2229.

［4］Zhou D Y, Huang J Y, Scholkopf B. Beyond pairwise classification and clustering using hypergraphs［R］. 143, Tubingen: Max Plank Institute for Biological Cybernetics, 2005.

［5］Chaudhuri S, Ganti V, Kaushik R. A primitive operator for similarity joins in data cleaning［C］∥ICDE′06 Proc.eedings of the 22nd International Conference on Data Engineering. New York, USA: IEEE, 2006: 5.

［6］Cohen E, Datar M, Fujiwara S, et al. Finding interesting associations without support pruning［J］. IEEE Transactions on Knowledge and Data Engineering, 2001, 13(1): 6478.

［7］Broder A Z, Charikar M, Frieze A M, et al. Minwise independent permutations ［J］. Journal of Computer Systems and Sciences, 2000, 60(3): 630659.

［8］Kalpakis K, Tang S. Collaborative data gathering in wireless sensor networks using measurement cooccurrence ［J］. Computer Communications, 2008, 31(10): 19791992.

［9］Dourisboure Y, Geraci F, Pellegrini M. Extraction and classification of dense implicit communities in the web graph ［J］. ACM Transactions on the Web (TWEB), 2009, 3(2): 136.

［10］Bendersky M, Croft W B. Finding text reuse on the web ［C］∥ WSDM’09 Proceedings of the Second ACM

International Conference on Web Search and Data Mining. New York, USA: ACM, 2009: 262271.

［11］Buehrer G, Chellapilla K. A scalable pattern mining approach to web graph compression with communities ［C］∥ WSDM’08 Proceedings of the International Conference on Web Search and Web Data Mining. New York, USA: ACM, 2008: 95106.

［12］Indyk P. A small approximately minwise independent family of Hash functions ［J］. Journal of Algorithm, 2001, 38(1): 8490.

［13］Charikar M S. Similarity estimation techniques from rounding algorithms ［C］∥ STOC’02 Proceedings of the Thiryfourth Annual ACM Symposium on Theory of Computing. New York, USA: ACM, 2002: 380388.

［14］Li P, Knig A C. bbit minwise hashing ［C］∥ WWW’10 Proceedings of the 19th International Conference on World Wide Web. New York, USA: ACM, 2010: 671680.

［15］Li P, Knig A C. Theory and applications of bbit minwise hashing ［J］. Communications of the ACM, 2011, 54(8): 101109.

［16］Yuan X P, Long J, Zhang Z P, et al. ffractional bit minwise hashing ［J］. Journal of Software, 2012, 7(1): 228236.

［17］袁鑫攀，龙军，张祖平，等．连接位Minwise Hash算法的研究［J］．计算机研究与发展, 2013, 50(4): 883890.

YUAN Xinpan, LONG Jun, ZHANG Zuping, et al. Connected bit Minwise Hashing［J］. Journal of Computer Research and Development, 2013, 50(4): 883890.

［18］Li P， Knig A， Gui W B．bbit minwise hashing for estimating threeway similarities［C］∥ Neural Information Processing Systems (NIPS). BC, Canada：Vancouver， 2010.

[1]	杨振，付庄，管恩广，徐建南，田仕禾，郑辉. MLattice模块机器人的运动学分析及构型优化[J]. 上海交通大学学报（自然版）, 2017, 51(10): 1153-1159.
[2]	赵君1,余海东2. 基于绝对节点坐标法的柔性双臂机构动力学分析[J]. 上海交通大学学报（自然版）, 2017, 51(10): 1160-1165.
[3]	赵子任1,杜世昌1,黄德林1，任斐2，梁鑫光2. 多工序制造系统暂态阶段产品质量马尔科夫建模与瓶颈分析[J]. 上海交通大学学报（自然版）, 2017, 51(10): 1166-1173.
[4]	黄炫圭. 小边概率条件下较小植入团的算法[J]. 上海交通大学学报（自然版）, 2017, 51(10): 1202-1206.
[5]	罗晶晶a,余海东a,赵春璋a,b,王皓a,b. 基于绝对节点坐标法变截面柔性梁运动稳定性研究[J]. 上海交通大学学报（自然版）, 2017, 51(10): 1174-1180.
[6]	汪一波1，黄亦翔1，李炳初1，凌晓1，赵帅1，刘成良1,张大庆2. 一种基于静力学预计算的开关磁阻电机模态仿真方法[J]. 上海交通大学学报（自然版）, 2017, 51(10): 1181-1188.
[7]	周炳海,黎明. 考虑机器人约束加工的制造单元调度方法[J]. 上海交通大学学报（自然版）, 2017, 51(10): 1214-1219.
[8]	陈进平1，张树生1，何卫平1，王明微1，黄晖2. 基于驱动参数建模的可行更改路径搜索和优选方法[J]. 上海交通大学学报（自然版）, 2017, 51(10): 1220-1227.
[9]	周鹏辉，马红占，陈东萍，陈梦月，褚学宁. 基于模糊随机故障模式与影响分析的产品再设计模块识别[J]. 上海交通大学学报（自然版）, 2017, 51(10): 1189-1195.
[10]	彭程,朱剑昀,陈俐. 基于模型参考控制的混合动力汽车模式切换 [J]. 上海交通大学学报（自然版）, 2017, 51(10): 1196-1201.
[11]	柳伟，杨超. 基于反向传播神经网络的注塑模具用零件报价模型[J]. 上海交通大学学报（自然版）, 2017, 51(10): 1207-1213.
[12]	陈苏婷，王卓，王奇. 基于非线性尺度空间的航拍场景分类[J]. 上海交通大学学报（自然版）, 2017, 51(10): 1228-1234.
[13]	陈宁，贺小滨，桂卫华，阳春华. 基于混沌离散序列的图像加密算法研究[J]. 上海交通大学学报（自然版）, 2017, 51(10): 1273-1280.
[14]	刘凯a，张立民b，周立军a. 随机受限玻尔兹曼机组设计[J]. 上海交通大学学报（自然版）, 2017, 51(10): 1235-1240.
[15]	朱信尧1，宋保维2，徐刚1，杨松林1. 支撑机构驻留水下航行器着陆策略及影响因素[J]. 上海交通大学学报（自然版）, 2017, 51(10): 1241-1251.

基于连接位Minwise Hash的三者相似性估计算法

Estimation of Three-Way Similarities Based on Connected Bit Minwise Hash

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价