Matching engine

• US 20050246317A1
• Filed: 02/07/2005
• Published: 11/03/2005
• Est. Priority Date: 02/19/1999
• Status: Abandoned Application

• Current Assignee: Square PI Limited
• Original Assignee: Square PI Limited
• Inventors: Moss, Simon, Zanelli, Paul, Turner, Michael
• Application Number:
  US11/053,183
• Publication Number:
  US 20050246317A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3346 using probabilistic model
• CPC Class Codes: G16B 15/00 ICT specially adapted for analysing two-dimensional or three-dimensional molecular structures, e.g. structural or functional relations or structure alignment
• CPC Class Codes: G16C 20/40 Searching chemical structures or physicochemical data
• CPC Class Codes: G16C 20/70 Machine learning, data mining or chemometrics

Abstract

A method of identifying the best matches or sets of matches between a query item and an item or items from a data set. The method includes the steps of: (i) providing a data representation for each item in the data set; (ii) providing a query representation of the query item; (iii) defining a transformation space; (iv) for each of a number of regions spanning the entire transformation space, determining an upper bound to the probability of a match between the query representation and a data representation under any transformation in the region; (v) determining a threshold probability; (vi) comparing the upper probability bound of each region with the threshold probability; and (vii) determining regions having an upper probability bound greater than the threshold probability, so as to identify solution regions.

Claims

1. A method of identifying the best matches or sets of matches between a query item and an item or items from a data set, the method comprising the steps of:

(i) providing a data representation for each item in the data set;

(ii) providing a query representation of the query item;

(iii) defining a transformation space;

(iv) for each of a number of regions spanning the entire transformation space, determining an upper bound to the probability of a global match between the query representation and a data representation under any global transformation in the region;

(v) automatically determining a global threshold probability based on the upper bound determined in (iv);

(vi) comparing the upper probability bound of each region with the global threshold probability;

(vii) determining regions having an upper probability bound greater than the global threshold probability, so as to identify solution regions;

(viii) sub-dividing the solution regions into further regions which span the solution regions;

(ix) determining a new upper bound to the probability of a global match between the query representation and a data representation under any global transformation in the further regions;

(x) determining a new global threshold probability based on the new upper bound; and

(xi) determining new solution regions.

2. A method as claimed in claim 1, including the step of iterating steps (viii) to (xi) so as to identify the solution region containing the best matching solution or to identify a set of solution regions containing a set of best matching solutions.

3. A method as claimed in claim 1, in which the data representations are topological representations of the data items and the query representation is a topological representation of the query item.

4. A method as claimed in claim 3, in which the topological representation of the data items and query item comprises a set of node measurement vectors, each node measurement vector being associated with a node of a topological arrangement of nodes defining the items.

5. A method as claimed in claim 1, in which the upper bound is determined using Bayesian probability theory.

7. A computer program which when running on a computer carries out a method as claimed in claim 1.

6. A matching engine for identifying an item or items from a data set, the engine comprising electronic data processing apparatus including:

a memory storing a data representation for each item in the data set;

an input for inputting a query representation of the query item; and

a processor configured to

define a transformation space,

generate a number of regions of the transformation space spanning the entire transformation space,

determine for each region an upper bound to the probability of a global match between the query representation and a data representation under any global transformation in the region,

determine a global threshold probability based on the upper bound,

compare the upper probability bound for each region with the global threshold probability,

identify solution regions having an upper probability bound greater than the global threshold probability,

sub-divide the solution regions into further regions which span the solution regions,

determine a new upper bound to the probability of a global match between the query representation and a data representation under any global transformation in the further regions,

determine a new global threshold probability based on the new upper bound;

determine new solution regions; and

store an identification of a match between the query item and the item of the data set in a memory.

8. A computer readable medium bearing computer program code providing instructions causing a computer to carry out the data processing operations of:

(i) provide a data representation for each item in the data set;

(ii) provide a query representation of the query item;

(iii) define a transformation space;

(iv) for each of a number of regions spanning the entire transformation space, determine an upper bound to the probability of a global match between the query representation and a data representation under any global transformation in the region;

(v) automatically determine a global threshold probability based on the upper bound determined in (iv);

(vi) compare the upper probability bound of each region with the global threshold probability;

(vii) determine regions having an upper probability bound greater than the global threshold probability, so as to identify solution regions;

(viii) sub-divide the solution regions into further regions which span the solution regions;

(ix) determine a new upper bound to the probability of a global match between the query representation and a data representation under any global transformation in the further regions;

(x) determine a new global threshold probability based on the new upper bound; and

(xi) determine new solution regions.