f-Fractional Bit Minwise Hashing for Large-Scale Learning

Recently, document similarity detection technology captures a host of researchers´ attention. In this paper, we propose to integrate linear SVM with f-fractional bit minwise hashing to make a wide range of choices for accuracy and storage space requirements. According to the derived properties of f-fractional bit minwise hashing, we obtained the optimal combination of fractional bit with the minimum estimator of variances and ultimately applied it to the process of integration. The innovation of this algorithm is the continuous selectivity of bit instead of the discrete integer value, which not only improves the theoretical system of b-bit minwise hashing SVM algorithm, but also satisfies the various needs of accuracy and storage space in the practical system. Due to the nonlinear of the resemblance matrix considered as kernel matrix, it can not be used in linear SVM training directly. However, in the theoretical analysis, we provide the proof of positive definiteness for resemblance matrix generated by f-fractional bit minwise hashing scheme, which is a logical and feasible basis for the integration. Meanwhile, experimental results on publicly available large-scale datasets validate the effectiveness of this algorithm.