View article

An improved multidimensional data indexing technique that generates compact indexes such that most or all of the index can reside in main memory at any time. During the cluster ing and dimensionality reduction, clustering information and dimensionality reduction information are generated for use in a subsequent search phase. The indexing technique can be effective even in the presence of variables Which are not highly correlated. Other features provide for efficiently performing exact and nearest neighbor searches using the clustering information and dimensionality reduction infor mation. One example of the dimensionality reduction uses a singular value decomposition technique. The method can also be recursively applied to each of the reduced dimensionality clusters. The dimensionality reduction also can be applied to the entire database as a? rst step of the index generation.