A Review for Weighted MinHash Algorithms <s> CONCLUSION AND FUTURE WORK <s> Topic or feature extraction is often used as an important step in document classification and text mining. Topics are succinct representation of content in a document collection and hence are very effective when used as content identifiers in peer-to-peer systems and other large scale distributed content management systems. Effective topic extraction is dependent on the accuracy of term clustering that often has to deal with problems like synonymy and polysemy. Retrieval techniques based on spectral analysis like Latent Semantic Indexing (LSI) are often used to effectively solve these problems. Most of the spectral retrieval schemes produce term similarity measures that are symmetric and often, not an accurate characterization of term relationships. Another drawback of LSI is its running time that is polynomial in the dimensions of the m x n matrix, A. This can get prohibitively large for some IR applications. In this paper, we present efficient algorithms using the technique of Locality-Sensitive Hashing (LSH) to extract topics from a document collection based on the asymmetric relationships between terms in a collection. The relationship is characterized by the term co-occurrences and other higher-order similarity measures. Our LSH based scheme can be viewed as a simple alternative to LSI. We show the efficacy of our algorithms via experiments on a set of large documents. An interesting feature of our algorithms is that it produces a natural hierarchical decomposition of the topic space instead of a flat clustering. <s> BIB001 </s> A Review for Weighted MinHash Algorithms <s> CONCLUSION AND FUTURE WORK <s> A modular drywall is erected wherein a metallic framework is initially formed including spaced vertical rails integrally and orthogonally mounting respective horizontal and vertical rails at upper and lower terminal ends respectively of the vertical rails. Drywall panels are subsequently fastened to forwardly projecting ends of the framework and subsequently filler strips are provided wherein the filler strips are formed to encompass and bridge gaps between drywall panels. The filler strips include a planar forward strip mouting a rearwardly extending longitudinally aligned projecting strip with a magnetic strip mounted to a rear end surface of the projecting strip to secure each filler strip to an associated metallic rail. <s> BIB002 </s> A Review for Weighted MinHash Algorithms <s> CONCLUSION AND FUTURE WORK <s> Weighted minwise hashing (WMH) is one of the fundamental subroutine, required by many celebrated approximation algorithms, commonly adopted in industrial practice for large -scale search and learning. The resource bottleneck with WMH is the computation of multiple (typically a few hundreds to thousands) independent hashes of the data. We propose a simple rejection type sampling scheme based on a carefully designed red-green map, where we show that the number of rejected sample has exactly the same distribution as weighted minwise sampling. The running time of our method, for many practical datasets, is an order of magnitude smaller than existing methods. Experimental evaluations, on real datasets, show that for computing 500 WMH, our proposal can be 60000x faster than the Ioffe's method without losing any accuracy. Our method is also around 100x faster than approximate heuristics capitalizing on the efficient ``densified" one permutation hashing schemes~\cite{Proc:OneHashLSH_ICML14,Proc:Shrivastava_UAI14}. Given the simplicity of our approach and its significant advantages, we hope that it will replace existing implementations in practice. <s> BIB003 </s> A Review for Weighted MinHash Algorithms <s> CONCLUSION AND FUTURE WORK <s> Capturing place semantics is critical for enabling location-based applications. Techniques for assigning semantic labels (e.g., "bar" or "office") to unlabeled places mainly resort to mining user activity logs by exploiting visiting patterns. However, existing approaches focus on inferring place labels with a static user activity dataset, and ignore the visiting pattern dynamics in user activity streams, leading to the rapid decrease of labeling accuracy over time. In this paper, we tackle the problem of semantic place labeling over user activity streams. We formulate this problem as a classification problem by characterizing each place through its fine-grained visiting patterns, which encode the visiting frequency of each user in each typical time slot. However, with the incoming activities of new users in data streams, such fine-grained visiting patterns constantly grow, leading to a continuously expanding feature space. To solve this issue, we propose an updatable sketching technique that creates and incrementally updates a set of compact and fixed-size sketches to approximate the similarity between fine-grained visiting patterns of ever-growing size. We further consider the discriminative weights of user activities in place labeling, and seamlessly incorporate them into our sketching method. Our empirical evaluation on real-world datasets demonstrates the validity of our approach and shows that sketches can be efficiently and effectively used to infer place labels over user activity streams. <s> BIB004 </s> A Review for Weighted MinHash Algorithms <s> CONCLUSION AND FUTURE WORK <s> Histogram-based similarity has been widely adopted in many machine learning tasks. However, measuring histogram similarity is a challenging task for streaming data, where the elements of a histogram are observed in a streaming manner. First, the ever-growing cardinality of histogram elements makes any similarity computation inefficient. Second, the concept-drift issue in the data streams also impairs the accurate assessment of the similarity. In this paper, we propose to overcome the above challenges with HistoSketch, a fast similarity-preserving sketching method for streaming histograms with concept drift. Specifically, HistoSketch is designed to incrementally maintain a set of compact and fixed-size sketches of streaming histograms to approximate similarity between the histograms, with the special consideration of gradually forgetting the outdated histogram elements. We evaluate HistoSketch on multiple classification tasks using both synthetic and real-world datasets. The results show that our method is able to efficiently approximate similarity for streaming histograms and quickly adapt to concept drift. Compared to full streaming histograms gradually forgetting the outdated histogram elements, HistoSketch is able to dramatically reduce the classification time (with a 7500x speedup) with only a modest loss in accuracy (about 3.5%). <s> BIB005
In this paper, we have reviewed the existing works of weighted MinHash algorithms. The weighted MinHash algorithms can be categorized into quantization-based and "active index"-based approaches and others. Currently, most of algorithms come from "active index"-based methods because they generally improve efficiency by sampling special subelements called "active indices".  . The formula is in Section 5 of BIB003 . Furthermore, the CWS scheme is remarkable in both theory and practice, and considered as the state-of-the-art methods. Particularly, ICWS and its derivation keep good balance between accuracy and runtime and furthermore, I 2 CWS and PCWS perform best in terms of accuracy and runtime, respectively  Therefore, they can be applied in large-scale data analytics. Furthermore, the above methods are designed for static data. However, streaming data, where the elements of a data instance are continuously received in an arbitrary order from the data stream, have been becoming increasingly popular in a wide range of applications such as similarity search in a streaming database and classification over data streams, etc. In this case, some important research issues need to be addressed. First, how to efficiently encode the expandable feature space? The feature space is rapidly expanding due to the fact that the elements continuously arrive. BIB001 (2) and BIB003 need to construct the complete feature space by pre-scanning, so they are infeasible in streaming data. ICWS and its variations are good solutions, but they require a set of random variables for each element. BIB002 ] is efficiently applied to the problem of user activity streams in BIB004 . Although it is efficient because only one random variable is required for each element, it cannot unbiasedly estimate the Jaccard similarity, and give the error bound in terms of theory, either. An interesting challenge is whether we are able to further improve the CWS scheme for the purpose of memory-efficiency. In addition, concept drift should be considered in streaming data because the underlying distribution of streaming data changes over time. The above methods assume that the historical data and the latest data are equally important. However, in the real scenarios, we wish that the algorithms pay more attention to the latter than the former because the latter are commonly more important than the former. So far HistoSketch BIB005 has been proposed to solve the problem by employing the strategy of gradual forgetting. Therefore, it is worth exploring a combination of the weighted MinHash algorithms and various strategies of conquering concept drift.