Connected bit minwise hashing for large-scale linear SVM

In this paper, we propose to integrate linear SVM with connected bit minwise hashing to improve the training and testing efficiency practically without notable loss of accuracy. Although the resemblance kernel is nonlinear and appears not directly to be used for linear SVM, our proof of positive definiteness of the connected bit minwise hashing kernel provide a reasonable and effective foundation for integration, which merely requires a minor modification of LIBLINEAR and the original b-bit minwise hashing scheme. Moreover, connected bit is convenient to be constructed and the performance increases preferably with a far-reaching practical significance in the largescale data environment. Theoretical analysis and experimental results illustrate the effectiveness of this algorithm.