Efficient identification of Tanimoto nearest neighbors: All-pairs similarity search using the extended Jaccard coefficient

David C. Anastasiu, George Karypis

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


Tanimoto, or extended Jaccard, is an important similarity measure which has seen prominent use in fields such as data mining and chemoinformatics. Many of the existing state-of-the-art methods for market basket analysis, plagiarism and anomaly detection, compound database search, and ligand-based virtual screening rely heavily on identifying Tanimoto nearest neighbors. Given the rapidly increasing size of data that must be analyzed, new algorithms are needed that can speed up nearest neighbor search, while at the same time providing reliable results. While many search algorithms address the complexity of the task by retrieving only some of the nearest neighbors, we propose a method that finds all of the exact nearest neighbors efficiently by leveraging recent advances in similarity search filtering. We provide tighter filtering bounds for the Tanimoto coefficient and show that our method, TAPNN, greatly outperforms existing baselines across a variety of real-world datasets and similarity thresholds.

Original languageEnglish (US)
Pages (from-to)153-172
Number of pages20
JournalInternational Journal of Data Science and Analytics
Issue number3
StatePublished - Nov 1 2017

Bibliographical note

Funding Information:
This work was supported in part by NSF (IIS-0905220, OCI-1048018, CNS-1162405, IIS-1247632, IIP-1414153, IIS-1447788), Army Research Office (W911NF-14-1-0316), Intel Software and Services Group, and the Digital Technology Center at the University of Minnesota. Access to research and computing facilities was provided by the Digital Technology Center (DTC) and the Minnesota Supercomputing Institute (MSI).

Publisher Copyright:
© 2017, Springer International Publishing AG.


  • All-pairs similarity search
  • Extended Jaccard
  • Graph construction
  • Nearest neighbors
  • Tanimoto similarity


Dive into the research topics of 'Efficient identification of Tanimoto nearest neighbors: All-pairs similarity search using the extended Jaccard coefficient'. Together they form a unique fingerprint.

Cite this