×

Transformation-based method for indexing high-dimensional data for nearest neighbour queries

  • US 6,834,278 B2
  • Filed: 04/05/2001
  • Issued: 12/21/2004
  • Est. Priority Date: 04/05/2001
  • Status: Expired due to Fees
First Claim
Patent Images

1. A computerized method for indexing in a database of stored objects, the method comprising:

  • applying a clustering algorithm to organize high-dimensional points into partitions;

    selecting a reference point for each partition;

    applying a transformation function to map a high-dimensional point to a one-dimensional space;

    indexing the transformed point using a single dimensional index structure; and

    wherein the transforming includes mapping a high dimensional point p to a single dimensional value y under the transformation function, y=i*c+dist(p,o), where point o is the closest reference point to p, and dist(p,o) represent the distance between p and o, c is an arbitrary constant greater than 1, i is an integer that uniquely identifies o.

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