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]	ZHAO Ziren1, DU Shichang1, HUANG Delin1, REN Fei2, LIANG Xinguang2. Modelling and Bottleneck Analysis of Product Quality in Transient Phase#br# of MultiStage Manufacturing Systems Based on Markovian Chains [J]. Journal of Shanghai Jiao Tong University, 2017, 51(10): 1166-1173.
[2]	ZHOU Penghui, MA Hongzhan, CHEN Dongping, CHEN Mengyue, CHU Xuening. Identification of Product Redesign Modules Based on#br# Fuzzy Random Failure Mode and Effects Analysis [J]. Journal of Shanghai Jiao Tong University, 2017, 51(10): 1189-1195.
[3]	LI Changxi1, 2, ZHOU Yan1, LIN Han3, LI Lingzhi1, GUO Ge1. TemporalSpatial Sequential Fusion Recognition Method of#br# Ballistic Missile Target Based on MIMOFNN Model [J]. Journal of Shanghai Jiao Tong University, 2017, 51(9): 1138-.
[4]	FENG Mingyue, HE Minghao, HAN Jun, YU Chunlai. High Resolution Direction of Arrival Estimation Based on#br# Covariance Fitting Estimation of Signal Parameters by#br# Rotational Invariance Technique Algorithm [J]. Journal of Shanghai Jiao Tong University, 2017, 51(9): 1145-.
[5]	?YANG Ping1,SHENG Jie1,WANG Yucheng2,LI Zhuyong1,JIN Zhijian1,HONG Zhiyong1. Quench Propagation Characteristics Influenced by NonUniform Properties of YBa2Cu3O7δ High Temperature Superconducting Tape [J]. Journal of Shanghai Jiaotong University, 2017, 51(9): 1090-1096.
[6]	WANG Xing, ZHOU Yipeng, TIAN Yuanrong, CHEN You, ZHOU Dongqing, HE Jiyuan. Sparse Decomposition for Frequency Modulation Radar Signal Based on#br# Advanced Genetic Algorithm and SinChirplet Atom [J]. Journal of Shanghai Jiao Tong University, 2017, 51(9): 1124-1130.
[7]	ZHANG Liangjun1, 2, LI Xiaoci1, WU Jingyi1, CAI Aifeng1. ThermalStructure Coupling Analysis of #br# Microgravity Environment Simulation Suspension Structure for #br# Large Space Deployable Mechanisms [J]. Journal of Shanghai Jiao Tong University, 2017, 51(8): 954-961.
[8]	XIA Hailiang1, 2, LIU Yakun1, 2, LIU Quanzhen3, LIU Baoquan3, FU Zhengcai1, 2. Metal Ablation Affected by Electrode Shapes Under#br# Long Continuing Lightning Current [J]. Journal of Shanghai Jiao Tong University, 2017, 51(8): 903-908.
[9]	LIN Da, ZHU Yijia, WEI Xiaodong, WANG Zhiyu, ZHANG Wugao. Combustion and Particle Emission Characteristics Affected by#br# Fuel Supply Parameters for a Diesel Engine Fuelled with#br# Polyoxymethylene Dimethyl Ethers/Diesel [J]. Journal of Shanghai Jiao Tong University, 2017, 51(7): 787-795.
[10]	GU Jiayang, XIE Yulin, TAO Yanwu, HUANG Xianghong, WU Jie. Numerical Simulation and Experimental Study on VortexInduced#br# Motion of a New Type of Floating Drilling Production Storage Offloading [J]. Journal of Shanghai Jiao Tong University, 2017, 51(7): 878-885.
[11]	MENG Qingyang1, YAN Weiwu1, HU Yong1, CHENG Jianlin1, CHEN Shihe2, ZHANG Xi2. Model Identification Based on Subspace Model Identification of#br# Superheated Steam System in UltraSupercritical CoalFired Power Unit [J]. Journal of Shanghai Jiao Tong University, 2017, 51(6): 672-678.
[12]	JIANG Huajuna, CAI Yana, b, LI Chaohaoa, LI Fanga, b, HUA Xueminga, b. Recognition Method for Gas Pores on XRay Image of Lap Joints#br# Based on the Improved Sobel Algorithm [J]. Journal of Shanghai Jiao Tong University, 2017, 51(6): 665-671.
[13]	DONG Guanhua,YIN Qin,YIN Guofu,XIANG Zhaowei. Identification and Modeling of Coupling Dynamic Stiffness in Joints of Machine Tool [J]. Journal of Shanghai Jiaotong University, 2015, 49(09): 1263-1434.
[14]	XIE Qijiang,YU Haidong. Coupling Relationship Between Loads on Cutterhead of Tunnel Boring Machine and Contact Stiffness of Gripper Shoes and Rocks [J]. Journal of Shanghai Jiaotong University, 2015, 49(09): 1269-1275.
[15]	ZHONG Jianlin1,MA Dawei1,REN Jie1,LI Shijun2,WANG Xu3. Static Compression Analysis of Rubber Hollow Cylinder Based on Plane Strain Assumption [J]. Journal of Shanghai Jiaotong University, 2015, 49(09): 1276-1280.