An Intersection Inequality Sharper than the Tanimoto Triangle Inequality for Efficiently Searching Large Databases.
Saved in:
| Title: | An Intersection Inequality Sharper than the Tanimoto Triangle Inequality for Efficiently Searching Large Databases. |
|---|---|
| Authors: | Pierre Baldi1, Daniel S. Hirschberg1 |
| Source: | Journal of Chemical Information & Modeling. Aug2009, Vol. 49 Issue 8, p1866-1870. 5p. |
| Subjects: | Database searching, Mathematical inequalities, Homology theory, Similarity (Geometry), Representations of algebras, Partitions (Mathematics), Integers |
| Abstract: | Bounds on distances or similarity measures can be useful to help search large databases efficiently. Here we consider the case of large databases of small molecules represented by molecular fingerprint vectors with the Tanimoto similarity measure. We derive a new intersection inequality which provides a bound on the Tanimoto similarity between two fingerprint vectors and show that this bound is considerably sharper than the bound associated with the triangle inequality of the Tanimoto distance. The inequality can be applied to other intersection-based similarity measures. We introduce a new integer representation which relies on partitioning the fingerprint components, for instance by taking components modulo some integer Mand reporting the total number of 1-bits falling in each partition. We show how the intersection inequality can be generalized immediately to these integer representations and used to search large databases of binary fingerprint vectors efficiently. [ABSTRACT FROM AUTHOR] |
| Copyright of Journal of Chemical Information & Modeling is the property of American Chemical Society and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
Be the first to leave a comment!
