Clustering Declustered Data for Efficient Retrieval

As databases increasingly integrate multimedia information in the form ofimage, video, and audio data, both the dimensionality and the amount of datathat need to be processed is increasing rapidly. It becomes necessary tosupport the efficient retrieval of large amounts of multimedia data.Declustering techniques for multi-disk architectures have been effectively usedfor storage in relational databases. In this paper, we first establish thatbesides exploiting the parallelism, a careful organization of each disk must beconsidered for fast searching. We introduce the notion of page allocation anddata space mapping which can be used to organize and retrieve multidimensionaldata. We work on these notions based on three different partitioningstrategies: regular grid partitioning, concentric hypercubes andhyperpyramids. We develop techniques that satisfy efficient retrieval byoptimizing the number of buckets retrieved by the query, disk arm movement andI/O parallelism. We prove that concentric hypercube based mapping satisfiesthe optimal clustering and optimal parallelism. We develop techniques based onhyperpyramid partitioning which reduces the number of buckets retrieved by thequery and has very efficient inter and intra disk organizations. We evaluatethe performance of proposed techniques by comparing it with the current bestapproaches. The new techniques lead to very significant improvement, up to 43times, over the existing techniques, therefore resulting in fast retrieval ofmultimedia data.