DotHash: Estimating Set Similarity Metrics for Link Prediction and Document Deduplication
Open Access
- 4 August 2023
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1758-1769
Abstract
Metrics for set similarity are a core aspect of several data mining tasks. To remove duplicate results in a Web search, for example, a common approach looks at the Jaccard index between all pairs of pages. In social network analysis, a much-celebrated metric is the Adamic-Adar index, widely used to compare node neighborhood sets in the important problem of predicting links. However, with the increasing amount of data to be processed, calculating the exact similarity between all pairs can be intractable. The challenge of working at this scale has motivated research into efficient estimators for set similarity metrics. The two most popular estimators, MinHash and SimHash, are indeed used in applications such as document deduplication and recommender systems where large volumes of data need to be processed. Given the importance of these tasks, the demand for advancing estimators is evident. We propose DotHash, an unbiased estimator for the intersection size of two sets. DotHash can be used to estimate the Jaccard index and, to the best of our knowledge, is the first method that can also estimate the Adamic-Adar index and a family of related metrics. We formally define this family of metrics, provide theoretical bounds on the probability of estimate errors, and analyze its empirical performance. Our experimental results indicate that DotHash is more accurate than the other estimators in link prediction and detecting duplicate documents with the same complexity and similar comparison time.Keywords
All Related Versions
This publication has 38 references indexed in Scilit:
- Challenges of Big Data analysisNational Science Review, 2014
- From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networksScientific Reports, 2013
- Network sciencePhilosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2013
- Link Prediction Based on Local Information2011
- Hyperdimensional Computing: An Introduction to Computing in Distributed Representation with High-Dimensional Random VectorsCognitive Computation, 2009
- Detecting near-duplicates for web crawling2007
- A Network Analysis Model for Disambiguation of Names in ListsComputational and Mathematical Organization Theory, 2005
- Using Markov models for web site link prediction2002
- Similarity estimation techniques from rounding algorithms2002
- Min-Wise Independent PermutationsJournal of Computer and System Sciences, 2000