View in EDS

An Intersection Inequality Sharper than the Tanimoto Triangle Inequality for Efficiently Searching Large Databases.

Saved in:
Bibliographic Details
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
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 44509632
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: An Intersection Inequality Sharper than the Tanimoto Triangle Inequality for Efficiently Searching Large Databases.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Pierre+Baldi%22">Pierre Baldi</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Daniel+S%2E+Hirschberg%22">Daniel S. Hirschberg</searchLink><relatesTo>1</relatesTo>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Journal+of+Chemical+Information+%26+Modeling%22">Journal of Chemical Information & Modeling</searchLink>. Aug2009, Vol. 49 Issue 8, p1866-1870. 5p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Database+searching%22">Database searching</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+inequalities%22">Mathematical inequalities</searchLink><br /><searchLink fieldCode="DE" term="%22Homology+theory%22">Homology theory</searchLink><br /><searchLink fieldCode="DE" term="%22Similarity+%28Geometry%29%22">Similarity (Geometry)</searchLink><br /><searchLink fieldCode="DE" term="%22Representations+of+algebras%22">Representations of algebras</searchLink><br /><searchLink fieldCode="DE" term="%22Partitions+%28Mathematics%29%22">Partitions (Mathematics)</searchLink><br /><searchLink fieldCode="DE" term="%22Integers%22">Integers</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>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.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=44509632
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1021/ci900133j
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 5
        StartPage: 1866
    Subjects:
      – SubjectFull: Database searching
        Type: general
      – SubjectFull: Mathematical inequalities
        Type: general
      – SubjectFull: Homology theory
        Type: general
      – SubjectFull: Similarity (Geometry)
        Type: general
      – SubjectFull: Representations of algebras
        Type: general
      – SubjectFull: Partitions (Mathematics)
        Type: general
      – SubjectFull: Integers
        Type: general
    Titles:
      – TitleFull: An Intersection Inequality Sharper than the Tanimoto Triangle Inequality for Efficiently Searching Large Databases.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Pierre Baldi
      – PersonEntity:
          Name:
            NameFull: Daniel S. Hirschberg
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 24
              M: 08
              Text: Aug2009
              Type: published
              Y: 2009
          Identifiers:
            – Type: issn-print
              Value: 15499596
          Numbering:
            – Type: volume
              Value: 49
            – Type: issue
              Value: 8
          Titles:
            – TitleFull: Journal of Chemical Information & Modeling
              Type: main
ResultId 1