Patent ID: 6859455

Claim:
A method of building a multi-dimensional index tree for use in searching for data objects; said method comprising: a) placing a data object into an appropriate leaf node, said leaf node having a predetermined capacity for data objects, each of said data objects having a plurality of keys, each of said keys being associated with a split dimension; b) dividing said leaf node into N subtrees when said leaf node is filled with a number of data objects exceeding said capacity, each of said subtrees having a predetermined capacity for data objects, wherein N is at least two; c) indexing said data objects in said excessively-filled leaf node into an appropriate subtree on the basis of a first split dimension if said data objects in said excessively-filled leaf node can be identifiably separated on the basis of said first split dimension or on the basis of a different split dimension if said data objects in said excessively-filled leaf node cannot be identifiably separated on the basis of said first split dimension; and d) repeating steps a) through c) until all data objects presented for placement have been indexed, wherein each of said subtrees is treated as a leaf node on each successive pass.