Given a distributed multimedia database system and a set of queries as well as their querying frequencies from each site, the goal of a data allocation algorithm is to locate the multimedia data objects (MDOs)at different sites so as to minimize the cost incurred in executing the queries. In this research, the data allocation problem is investigated from two different perspectives, one is system-oriented and the other is user-oriented....[ Read more ]

Given a distributed multimedia database system and a set of queries as well as their querying frequencies from each site, the goal of a data allocation algorithm is to locate the multimedia data objects (MDOs)at different sites so as to minimize the cost incurred in executing the queries. In this research, the data allocation problem is investigated from two different perspectives, one is system-oriented and the other is user-oriented.

The objective of the first part is on generating data allocation scheme with least total data transmission cost. This is equivalent to minimizing the average query execution time, which is of primary importance in a wide class of distributed multimedia systems. The data allocation problem, however, is NP-complete, and thus, requires fast heuristics to generate efficient solutions. We propose a novel approach based on an evolutionary process. Our algorithm is compared with three existing algorithms which are based on a genetic technique, neural networks, and a graph partitioning heuristic. We have implemented and evaluated these algorithms on our distributed multimedia database system test-bed. Using a variety of multimedia queries on our test-bed, we measured the query execution times based on the data allocation schema generated by the algorithms. Compared to the optimal solutions obtained through exhaustive search, the proposed algorithm outer-perform the others in terms of solution quality with a trade-off of longer execution time.

Distributed information processing, in many world wide web applications, requires access, transfer and synchronization of large MDOs, such as audio, video and images, across the communication network. Moreover, the end users have started expecting very fast response times and high quality of service. Since the transfer of large MDOs across the communication network contributes to the response time observed by the end users, the problem of allocating these MDOs so as to minimize the response time becomes very challenging. This problem becomes more complex in the context of hypermedia documents (web pages), wherein the MDOs need to be synchronized during presentation to the end users. Since the basic problem of data allocation in distributed database environments is NP-complete, therefore, there is a need to pursue and evaluate solutions based on heuristics which generate near-optimal MDO allocations. We address this problem by: i) conceptualizing this problem by using a navigation model to represent hypermedia documents and their access behavior from end users, and by capturing the synchronization requirements on MDOs, ii) formulating the problem by developing a base case cost model for response time, and generalizing it to incorporate user interaction and buffer memory constraints, iii) designing two algorithms to find near-optimal solutions for allocating MDOs of the hypermedia documents while adhering to the synchronization requirements, and iv) evaluating the trade-off between the time complexity to obtain the solution and the quality of solution by comparing the solutions generated by the algorithms with the optimal solutions generated through an exhaustive search.