Dimensional reduction using data matching in high dimensional space
AssigneeMicrosoft Corporation
InventorsMarc Daskalovic, Eugene Zarakhovsky, Christian Eric Schrock
Life of this patent
Estimating the term…
Abstract
A method is provided to match an unknown data point with a known data point contained in a multi-dimensional data structure. The method may include receiving data from any multi-dimensional source where a query may be used to locate specific data points within that source. The method receives a number of inputs, including a Euclidean error distance and a number of reference points to use. Furthermore, the method determines optimal reference points to locate a relatively small number of data points within the data structure that possibly match the unknown point. Once possible match points are located, the method then determines the unknown point's match.
Claims12
A computer-implemented method for matching a first data point representing an unknown audio file with a second data point representing a known audio file within a multi-dimensional database, comprising:
- receiving at least one data structure, said at least one data structure containing said second data point and one or more third data points;
- determining an optimal set of least two reference points so as to dimensionally reduce said at least one data structure,
- wherein determining said optimal set of at least two reference points comprises:
- (1) retrieving a Euclidean distance for said at least one data structure˜
- (2) choosing a first set of at least two reference points,
- (3) computing the distance from each data point in said at least one data structure to each reference point in said first set of at least two reference points,
- (4) determining the quantity of data points having substantially the same distance, within the absolute value of said Euclidean distance, to each reference point in said first set of at least two reference points as said first data point, and
- (5) determining whether another set of at least two reference points would identify fewer data points in said data structure as possible match points to said first data point as said first set of at least two reference points;
- and based on said optimal set of at least two reference points, matching said first data point with said second data point.
A computer-implemented method for matching an unknown audio file with a second audio file, comprising:
- processing said unknown audio file into a numerical data point;
- receiving at least one data structure, said at least one data structure containing a data point identifying said second audio file and one or more data points identifying one or more third audio files;
- determining an optimal set of at least two reference points so as to dimensionally reduce said at least one data structure, wherein determining said optimal set of at least two reference points comprises;
- (1) retrieving a Euclidean distance for said at least one data structure,
- (2) choosing a first set of at least two reference points,
- (3) adding said Euclidean distance to said at least two reference points,
- (4) computing the distance from each data point in said data structure to each reference point in said first set of at least two reference points,
- (5) determining the quantity of data points having substantially the same distance to each reference point in said first set of at least two reference points as said unknown audio file data point, and
- (6) determining whether another set of at least two reference points would identify fewer data points in said data structure as possible match points to said unknown audio file data point as said first set of at least two reference points;
- and
- based on said optimal set of at least two reference points, matching said unknown audio file data point with said second audio file data point.
Dependencies are inferred from the claim text.