This paper proposes a centroid-slice-based uncertain high-dimensional indexing algorithm

called CU-Tree.In the CU-Tree

all (

n

)data objects are first grouped into some clusters by a

k

-Means clustering algorithm.Then each object’s corresponding uncertain sphere is "sliced" in terms of the centroid-distance.Finally a unified key of each data object is computed by adopting composite encoding scheme

which are inserted by a B

+

-tree.Thus

given a query object

its probabilistic range search in high-dimensional spaces is transformed into the search in the single dimensional space with the aid of the CU-Tree.Extensive performance studies are conducted to evaluate the effectiveness and efficiency of the proposed scheme.