Research On Algorthms Of High-dimensional Multimedia Data Indexing

With the growing of data acquisition equipment, it is increasingly easy to produce images, graphics, audio, video, animation and 3D models and other multimedia data, these multimedia data is heterogeneous, unstructured, and dynamic changes, these features case big problem to the subsequent processing such as classification, clustering, mining and query retrieval. Content-based information retrieval (CBIR) opens up a new way of multimedia data retrieval. High-dimensional data index is not only one of the key technologies of similarity retrieval,but also the hot and difficult research area of multimedia and database.This thesis makes a deeply research for hight-dimensional index, and achives certain results,mainly include the following two aspects:1. Motivated by the urgent need to improve the efficiency, approximate similarity retrieval is investigated in high-dimensional index structure M-tree, approximate range query(ARQ) algorithm and approximate KNN query( AKNNQ) algorithm is proposed. M-tree used filter to prune the subtree which is not important to reduce the computation. It had good performance in some cases, however, as the dimension of a data set increases, the performance of M-tree is decrease exponentially. Approximate retrieval is considered to good for high-dimensional algorithms, therefore, the approximate retrieval algorithm based on M-tree would improve the efficiency by losing accuracy. ARQ algorithm expands query filtering condition, fitering branch and reduce unnecessary computing.AKNNQ algorithm also improves filter condition, and the chosen node is added into the priority queue PR with sorting the position of sub-trees, and accelerate convergence dynamic query radius. Then, experiments proved efficiency of ARQ alogorithm and AKNNQ alogorithm.2. The optimization of permutant selection method, and dimension partition mothed to determine permutant's number in permutation index (PI) approximate high-dimension structure. PI has high efficient query efficiency, it precomputers the permutation of permutant distance to the data object in date set, the similarity of the permutation is a prominent and efficient forcast for correlated objects. Most of the results have been retrivaled by only calcuting small amounts of the data set after structuring and predicting the database.The selection of permutants largely affacts the efficiency of index structure, the random selection methods propose in the PI can't ensure the reliability of efficiency,so some permutant selection technique are proposed in this paper, and the experiments verify the efficiency and the feasibility. Dimension Partition methods are proposed in order to obtain the best number of permtant, and the experiment shows that we can get a higher efficiency by getting an acceptable accuracy under minimum number of selected permutant.