Patent ID: 7117217

Claim:
A method of managing a database which stores high-dimensional data items, comprising: (a) applying a transform function to a high-dimensional data item to map the high-dimensional data item to single-dimensional space, thereby obtaining a single-dimensional value which represents the high-dimensional data item; (b) indexing the single-dimensional value obtained by said applying step using a single-dimensional index structure; wherein (i) the high-dimensional data item includes a plurality of attribute values, each attribute value corresponding to a different dimension of the high-dimensional data item; (ii) said step of applying a transform function maps each attribute value of the high-dimensional data item to a predetermined range, thereby obtaining a mapped attribute value for each attribute value, and calculates the single-dimensional value which represents the high-dimensional data item as d min +x min or d max +x max , where x min is the smallest mapped attribute value associated with the high-dimensional data item, d min is a value associated with the dimension which corresponds to the smallest mapped attribute value, x max is the largest mapped attribute value associated with the high-dimensional data item, and d max is a value associated with the dimension which corresponds to the largest mapped attribute value; and (iii) said applying and indexing steps are performed for a plurality of high-dimensional data items to form an indexed set of single-dimensional values; and (c) performing a search on the indexed set of single-dimensional values to retrieve a set of points, wherein said performing includes transforming a range query into a set of d subqueries in the single-dimensional space represented as q 1 ,q 2 , . . . ,q d , where q i =[I i ,h j ], 1≦i≦d and for a jth query subrange in q, [x j1 ,x j2 ]: q j = { [ j + max i = 1 d ⁢ x i1 , j + x j2 ] if ⁢ ⁢ min i = 1 d ⁢ x i1 + θ ≥ 1 - max i = 1 d ⁢ x i1 [ j + x j1 , j + min i = 1 d ⁢ x i2 ] if ⁢ ⁢ min i = 1 d ⁢ x i2 + θ < 1 - max i = 1 d ⁢ x i2 [ j + x j1 , j + x j2 ] otherwise , where | is a tuning parameter, and evaluating each subquery in said set of subqueries using the single-dimensional index structure.