×

Heirarchical indexing of multi-attribute data by sorting, dividing and storing subsets

  • US 6,381,605 B1
  • Filed: 05/29/1999
  • Issued: 04/30/2002
  • Est. Priority Date: 05/29/1999
  • Status: Expired due to Term
First Claim
Patent Images

1. A computer readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method of constructing a hierarchical index from a set of multi-dimensional data, the method comprising:

  • (a) calculating a number of members of a set of multi-dimensional data items;

    (b) determining whether said number of members exceeds a node capacity of a hierarchical index configured to index said data items;

    (c) determining a variance of values in one or more dimensions of said data items;

    (d) identifying a first dimension of said one or more multi dimensions in which to divide said set of multi-dimensional data items;

    (e) sorting said data items in said first dimension;

    (f) dividing said sorted data items in said first dimension into two or more subsets by;

    (f′

    ) determining whether said number of members is less than double said node capacity; and

    (f″

    ) calculating the floor of the quotient of said node capacity divided by two;

    (g) repeating (a)-(f) for each said subset in order to divide said set of data items into a plurality of data item clusters, wherein each cluster comprises a number of data items no greater than said node capacity; and

    (h) configuring a leaf node of said hierarchical index for data items in a first cluster.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×