Method for Rapidly Approximating Similarities
AssigneeThe Board of Trustees of the Leland Stanford Junior University
InventorsImran Haque, Vijay Pande
Life of this patent
Estimating the term…
Abstract
Methods and algorithms are presented that implement linear algebraic techniques for rapidly estimating chemical similarities for several popular measures. The methods of the present invention reflect source similarity measures for both Tanimoto calculation and rank ordering. After a precalculation step on a database, the methods of the present invention afford several orders of magnitude of speedup in database screening. The present invention also provides an asymptotic speedup for large similarity matrix construction problems, reducing the number of conventional slow similarity evaluations required from quadratic to linear scaling.
Claims22
A method for estimating similarities comprising:
- receiving a set of data;
- dividing the set of data into a first subset and a second subset, wherein the second subset is larger than the first subset;
- computing similarity calculations for an element of the second subset and the elements of the first subset;
- computing an approximation matrix from the computed similarity calculations;
- generating a similarity measure for a second element of the second subset based on the approximation matrix.
A method for estimating similarities comprising:
- receiving a set of data;
- dividing the set of data into a first subset and a second subset, wherein the second subset is larger than the first subset;
- computing a first subset vector approximation;
- computing second subset vector approximation;
- and
- computing a query for a first element of the second subset against the first subset vector approximation.
Dependencies are inferred from the claim text.