Title :
HG-tree: an index structure for multimedia databases
Author :
Cha, Guang-Ho ; Chung, Chin-Wan
Author_Institution :
Dept. of Inf. & Commun. Eng., Korea Adv. Inst. of Sci. & Technol., Seoul, South Korea
Abstract :
We propose a new index structure called the HG-tree, to support content-based retrieval in multimedia databases. Our goals are twofold: increasing the storage utilization and decreasing the directory coverage of the index tree. The first goal is achieved by absorbing splitting if possible, and when splitting is necessary, converting two nodes to three. This is done by proposing a good ordering on the directory nodes. The second goal is achieved by representing the directory regions compactly. We note that there is a trade-off between the two design goals, but the HG-tree is so flexible that it can control the trade-off. We present the design of our index tree and associated algorithms. In addition, we report the results of a series of tests, comparing the proposed index tree with the buddy-tree, which is one of the most successful access methods for a multidimensional space. The results show the superiority of our method
Keywords :
database theory; multimedia computing; query processing; systems analysis; tree data structures; visual databases; HG-tree; buddy-tree; content-based retrieval; directory coverage; directory nodes; directory regions; index structure; multidimensional space; multimedia databases; splitting; storage utilization; Algorithm design and analysis; Content based retrieval; Data engineering; Image retrieval; Indexes; Indexing; Information retrieval; Multidimensional systems; Multimedia databases; Nearest neighbor searches;
Conference_Titel :
Multimedia Computing and Systems, 1996., Proceedings of the Third IEEE International Conference on
Conference_Location :
Hiroshima
Print_ISBN :
0-8186-7438-5
DOI :
10.1109/MMCS.1996.535012