Density-based indexing method for efficient execution of high dimensional nearest-neighbor queries on large databases

• US 6,263,334 B1
• Filed: 11/11/1998
• Issued: 07/17/2001
• Est. Priority Date: 11/11/1998
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bennett, Kristin P., Fayyad, Usama, Geiger, Dan
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): ALAM, SHAHID AL
• Application Number:
  US09/189,229
• Time in Patent Office: 979 Days
• Field of Search: 707/5, 707/6, 707/100, 707/101, 707/200, 707/102, 704/9, 704/222, 704/233, 704/245, 706/45, 706/50, 705/1, 705/10, 705/27, 702/179, 709/202
• US Class Current: 707/737
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06F 18/2321 using statistics or function optimisation, e.g. modelling of probability density functions
• CPC Class Codes: G06F 18/2414 Smoothing the distance, e.g. radial basis function networks [RBFN]
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Method and apparatus for efficiently performing nearest neighbor queries on a database of records wherein each record has a large number of attributes by automatically extracting a multidimensional index from the data. The method is based on first obtaining a statistical model of the content of the data in the form of a probability density function. This density is then used to decide how data should be reorganized on disk for efficient nearest neighbor queries. At query time, the model decides the order in which data should be scanned. It also provides the means for evaluating the probability of correctness of the answer found so far in the partial scan of data determined by the model. In this invention a clustering process is performed on the database to produce multiple data clusters. Each cluster is characterized by a cluster model. The set of clusters represent a probability density function in the form of a mixture model. A new database of records is built having an augmented record format that contains the original record attributes and an additional record attribute containing a cluster number for each record based on the clustering step. The cluster model uses a probability density function for each cluster so that the process of augmenting the attributes of each record is accomplished by evaluating each record'"'"'s probability with respect to each cluster. Once the augmented records are used to build a database the augmented attribute is used as an index into the database so that nearest neighbor query analysis can be very efficiently conducted using an indexed look up process. As the database is queried, the probability density function is used to determine the order clusters or database pages are scanned. The probability density function is also used to determine when scanning can stop because the nearest neighbor has been found with high probability.

Claims

1. A method for evaluating data records contained within a database wherein each record has multiple data attributes;

the method comprising the steps of;

a) clustering the data records contained in the database into multiple data clusters wherein each of the multiple data clusters is characterized by a cluster model; and

b) building a new database of records having an augmented record format that contains the original record attributes and an additional record attribute containing a cluster identifier for each record based on the clustering step.

2. The method of claim 1 wherein the cluster model includes a) a number of data records associated with that cluster, b) centroids for each attribute of the cluster model and c) a spread for each attribute of the cluster model.

3. The method of claim 1 additionally comprising the step of indexing the records in the database on the additional record attribute.

4. The method of claim 1 additionally comprising the step of finding a nearest neighbor of a query data record by evaluating database records indexed by means of the cluster identifiers found during the clustering step.

5. The method of claim 4 wherein the step of finding the nearest neighbor is performed by evaluating a probability estimate based upon a cluster model for the clusters that is created during the clustering step.

6. The method of claim 5 wherein the step of finding the nearest neighbor is performed by scanning the database records indexed by cluster identifiers having a greatest probability of containing a nearest neighbor.

7. The method of claim 6 wherein the step of scanning database records is performed for data records indexed on multiple cluster identifiers so long as a probability of finding a nearest neighbor within a cluster exceeds a threshold.

8. The method of claim 1 wherein the clustering process is performed using a scalable clustering process wherein a portion of the database is brought into a rapid access memory prior to clustering and then a portion of the data brought into the rapid access memory is summarized to allow other data records to be brought into memory for further clustering analysis.

9. The method of claim 1 wherein the number of data attributes is greater than 10.

10. The method of claim 4 wherein the step of finding the nearest neighbor is based upon quadratic distance metric between the query data record and the database records indexed by the cluster identifier.

11. A method for evaluating data records stored on a storage medium wherein each record has multiple data attributes that have been characterized by a probability function found by clustering the data in the database to produce a clustering model;

said method comprising the steps of assigning a cluster number for each of the records on the storage medium based upon the probability function, and finding a nearest neighbor from the data records for a query record by scanning data records from more than one based upon the probability function of the cluster model used to assign cluster numbers to the data records.

12. The method of claim 11 wherein records having the same index are written to a single file on the storage medium.

13. The method of claim 11 wherein the records are stored by a database management system and the index is used to form a record attribute of records stored within a database maintained on the storage medium.

14. The method of claim 11 wherein the clustering model for the database defines a probability function that is a mixture of Gaussians.

15. The method of claim 14 wherein the assigning of a cluster number comprises a Bayes decision for assigning each data record to a data cluster associated with one of said Gaussians.

16. The method of claim 11 wherein further comprising the step of subdividing data records within each cluster into cluster subcomponents and additionally comprising the step of finding a nearest neighbor of a query data by scanning records from a cluster subcomponent.

17. The method of claim 11 wherein the step of determining a nearest neighbor comprises the step determining a distance between the query data record and data records accessed in the database by means of the database index.

18. The method of claim 11 wherein a multiple number of data records are stored as a set of nearest neighbors.

19. The method of claim 11 wherein the nearest neighbor determination is based on a distance determination between a query record and a data record that comprises a quadratic normal form of distance.

20. The method of claim 11 wherein the storage medium stores a database of data records and further comprises a step of finding a nearest neighbor to a query record from the data records of the database, said step of finding the nearest neighbor comprising the step of choosing between a sequential scan of the database to find the nearest neighbor or searching for the nearest neighbor using the index derived from the probability function thereby optimizing the step of finding the nearest neighbor.

21. A process for use in answering queries comprising the steps of:

a) clustering data stored in a database using a clustering technique to provide an estimate of the probability density function of the sample data;

b) adding an additional column attribute to the database that represents the predicted cluster membership for each data record within the database; and

c) rebuilding a data table of the database using the newly added column as an index to records in the table.

22. The process of claim 21 wherein an index for the data in the database is created on the additional column.

23. The process of claim 21 comprising the additional step of performing a nearest neighbor query to identify a nearest neighbor data point to a query data point.

24. The process of claim 22 wherein the nearest neighbor query is performed by finding a nearest cluster to the query data point.

25. The process of claim 24 additionally comprising the step of scanning data in a cluster identified as most likely to contain nearest neighbor based on a probability estimate for said cluster.

26. The process of claim 25 wherein if the probability that the nearest neighbor estimate is correct is above a certain threshold, the scanning is stopped, but if it is not, then scanning additional clusters to find the nearest neighbor.

27. In a computer data mining system, apparatus for evaluating data in a database comprising:

a) one or more data storage devices for storing data records on a storage medium;

the data records including data attributes; and

b) a computer having a rapid access memory and an interface to the storage devices for reading data from the storage medium and bringing the data records from the storage medium into the rapid access memory for subsequent evaluation;

c) the computer comprising a processing unit for evaluating at least some of the data records and for determining a probability density function for the records based on a clustering of data from data in the database into multiple numbers of data clusters, and said computer programmed to build an index for the data records in the database based on the probability density function, wherein said computer performs an approximate nearest neighbor analysis by choosing a specified cluster based on the index and evaluating records of the specified cluster for nearness to a given data record.

28. The apparatus of claim 27 wherein said computer stores data records having a common index based on cluster number in a file of records not part of database table.

29. The apparatus of claim 27 wherein the computer includes a database management component for setting up a database and using the index to organize data records in the database.

30. The apparatus of claim 29 wherein the computer builds an additional database of records for storage on the one or more data storage devices and wherein the data records of the additional database are augmented with a cluster attribute.

31. A computer-readable medium having computer-executable components comprising:

a) a database component for interfacing with a database that stores data records made up of multiple data attributes;

b) a modeling component for constructing and storing a clustering model that characterizes multiple data clusters wherein the modeling component constructs a model of data clustering that corresponds to a mixture of probability functions; and

c) an analysis component for indexing the database on a cluster number for each record in the database wherein the indexing is performed based on a probability assessment of each record to the mixture of probability functions and for approximating a nearest neighbor query by determining an index for a sample record and scanning data records previously assigned a similar index.

32. The computer readable medium of claim 31 wherein said indexing component generates an augmented data record having a cluster number attribute for storage by the database component.

33. The computer readable medium of claim 31 wherein said modeling component is adapted to compare a new model to a previously constructed model to evaluate whether further of said data records should be moved from said database into said rapid access memory for modeling.

34. The computer readable medium of claim 31 wherein said modeling component is adapted to update said cluster model by calculating a weighted contribution by each of said data records in said rapid access memory.

35. A method for evaluating data records stored on a storage medium wherein each record has multiple data attributes that have been clustered to define a probability function of the data records stored on the storage medium;

said method comprising the steps of evaluating the clusters of a clustering model and if the cluster separation between cluster centroids is of a sufficient size, assigning an index for each of the records on the storage medium based upon the probability function that is derived from the clustering model.

36. A method for evaluating data records stored on a storage medium wherein each record has multiple data attributes that have been characterized by a probability function found by clustering the data in the database to produce a clustering model;

said method comprising the steps of assigning a cluster number for each of the records on the storage medium based upon the probability function, and finding a nearest neighbor from the data records for a query record by choosing between a scan of a subset of the database and a complete scan of the database based on the probability estimate generated by a statistical model of the data.

37. A method for performing an approximate nearest neighbor search of data records in a database stored on a storage medium wherein each record has multiple data attributes comprising:

a) clustering the data records to define a cluster model having multiple clusters made up of probability functions to form a compressed characterization of the data records of the database;

b) assigning clusters numbers as indexes to the data records based on the probability functions; and

c) searching data records from a cluster to find a nearest neighbor within said cluster of a sample data record based on a nearness of the sample data record to the clusters that make up the cluster model.

38. The method of claim 37 wherein records from multiple numbers of clusters are searched to find a nearest neighbor to a sample data record.

39. The method of claim 38 wherein the number of clusters searched is based on a probability that an actual nearest neighbor is contained within an as yet unscanned cluster.