ADAPTIVE APPROXIMATION TREE

The study of high dimensional data index method is the key problem of content based search in large scale multimedia databases. In this paper, an efficient high dimensional index structure called adaptive approximation tree （AA tree） is proposed. Its structure, the algorithm of its construction and searching are given in detail. The merits of both tree structures and sequential scan structures are effectively combined in AA tree so that it can adjust its structure adaptively according to data distribution to make search more efficient. Tree structure is used in low dimensionality or large data distribution skew, while it’s of sequential scan structure when the dimensionality or data distribution density is high. In structure, a compressed method is used for MBR in order to save storage spaces. Because MBS and MBR are used simultaneously in AA tree’s data space partition, a lot of complex calculations are decreased so that the search is accelerated obviously.