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

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.

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.

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.

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.