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

Abstract

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

CLC Number:

TP 301.6

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.

References

［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]	YANG Zhen,FU Zhuang,GUAN Enguang,XU Jiannan,TIAN Shihe,ZHENG Hui. The Kinematic Analysis and Structure Optimization of MLattice Modular Robot [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1153-1159.
[2]	ZHAO Jun1,YU Haidong2. Dynamic Analysis of TwoLink Flexible Manipulators Based on the Absolute Nodal Coordinate Formulation [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1160-1165.
[3]	ZHAO Ziren1,DU Shichang1,HUANG Delin1,REN Fei2,LIANG Xinguang2. Modelling and Bottleneck Analysis of Product Quality in Transient Phase of MultiStage Manufacturing Systems Based on Markovian Chains [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1166-1173.
[4]	HUANG Xuangui. Algorithm for Relatively Small Planted Clique with Small Edge Probability [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1202-1206.
[5]	LUO Jingjinga,YU Haidonga,ZHAO Chunzhanga,b,WANG Haoa,b. Study on Motion Stability of Variable CrossSection Flexible Beams Based on the Absolute Nodal Coordinate Formulation [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1174-1180.
[6]	WANG Yibo1,HUANG Yixiang1,LI Bingchu1,LING Xiao1 ZHAO Shuai1,LIU Chengliang1,ZHANG Daqing2. An Improved Modal Simulation Method for Switched Reluctance Motor Based on Static PreComputation [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1181-1188.
[7]	ZHOU Binghai,LI Ming. Scheduling Method of Manufacturing Cells with Robot Restricted Processing [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1214-1219.
[8]	CHEN Jinping1,ZHANG Shusheng1,HE Weiping1,WANG Mingwei1,HUANG Hui2. Feasible Change Path Search and Optimization Method Based on Driving Parameter Modeling [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1220-1227.
[9]	ZHOU Penghui,MA Hongzhan,CHEN Dongping,CHEN Mengyue,CHU Xuening. Identification of Product Redesign Modules Based on Fuzzy Random Failure Mode and Effects Analysis [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1189-1195.
[10]	PENG Cheng,ZHU Jianyun,CHEN Li. Mode Transition for a Hybrid Electric Vehicle Based on Model Reference Control [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1196-1201.
[11]	LIU Wei,YANG Chao . A Study on Injection Mould Part Quotation Model Based on Back Propagation Neural Network [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1207-1213.
[12]	CHEN Suting，WANG Zhuo，WANG Qi. Aerial Scene Classification Based on Nonlinear Scale Space [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1228-1234.
[13]	CHEN Ning,HE Xiaobin,GUI Weihua,YANG Chunhua. Research on Image Encryption System Based on Chaotic Discrete Sequence [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1273-1280.
[14]	LIU Kaia，ZHANG Liminb，ZHOU Lijuna. Design of Random Restricted Boltzmann Machine Group [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1235-1240.
[15]	ZHU Xinyao1，SONG Baowei2,XU Gang1,YANG Songlin1. Research on Landing Strategy and Influencing Factors of an Autonomous Underwater Vehicle with Supporting Mechanism [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1241-1251.