Knowledge-driven multidimensional indexing for content-based information retrieval

Abstract

[ACCESS RESTRICTED TO THE UNIVERSITY OF MISSOURI AT REQUEST OF AUTHOR.] Media data are being generated at rates unimaginable only years ago. We face challenges in providing efficient and accurate access to media content, using minimal manual human effort during the creation of a media repository. Much of content-based retrieval (CBR) research focuses on feature extraction and content analysis; very little deals with efficient access methods from large-scale data set, such as indexing. Many existing CBR systems apply one-against-all for ranking relevant results. Such an approach lacks scalability in real-world applications. Furthermore, dynamic manipulation of these media databases is rarely considered. To this end, we present the Entropy Balanced Statistical (EBS) k-d tree and the Entropy Balanced Bitmap (EBB) tree for knowledge-driven indexing of media. These indexing structures exploit domain knowledge present in a media database through analysis of the statistical entropy of the database with balanced entropy reduction algorithms. The EBS is capable of handing general-purpose, continuous-valued feature sets for CBR. Similar content is clustered in the leaves that are linked with feature-space specific methods. Additionally, the EBB is a bitmap indexing mechanism that relies on fast bit-wise operations, includes leaf clustering, highly efficient access methods, and supports application-specific bit weighting for increased accuracy during retrieval. We have defined a set of algorithms that enable dynamic inserts, deletes, and updates of the EBS and EBB. These indexes have been empirically proven efficient and accurate in biomedical and geospatial domains. The EBS and EBB can be applied to various additional CBR domains, and extended to exploit further domain specific knowledge, such as temporal and spatial media correlations.