×

Fast query search in large dimension database

  • US 5,848,404 A
  • Filed: 03/24/1997
  • Issued: 12/08/1998
  • Est. Priority Date: 03/24/1997
  • Status: Expired due to Fees
First Claim
Patent Images

1. A computer including a data storage device including a computer usable medium having computer usable code means for identifying data points that are similar to a query, the data points being stored in a database accessible by the computer, the computer usable code means having:

  • computer readable code means for arranging the database in a tree structure having at least an internal node level including internal nodes, a leaf-parent node level including leaf-parent nodes, and a leaf level including leaves, each internal node and leaf-parent node representing clusters of data points, each cluster being defined by (1) a respective randomly selected representative data point and (2) respective dependent data points, the distance between each representative data point in a level and its dependent data points being less than the distance between the dependent data point and the respective representative data point of any other cluster in the level;

    computer readable code means for receiving a query Q and in response determining respective query distances between the query Q and at least some of the representative data points;

    computer readable code means for arranging the internal nodes of the respective at least some of the representative data points in a sequence from smallest query distance to greatest query distance; and

    computer readable code means for returning a subsequence having a predetermined number of internal nodes, starting with the first node in the sequence.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×