File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Design and evaluation of data allocation algorithms for distributed multimedia database systems

TitleDesign and evaluation of data allocation algorithms for distributed multimedia database systems
Authors
KeywordsBest-First Search Algorithm
Clustering
Data Allocation
Distributed Database Systems
Hill-Climbing Heuristics
Max-Flow Min-Cut Problem
Multimedia Database Systems
Network Flow Algorithm
Optimal Allocation
Query Processing
Issue Date1996
Citation
Ieee Journal On Selected Areas In Communications, 1996, v. 14 n. 7, p. 1332-1348 How to Cite?
AbstractA major cost in retrieving multimedia data from multiple sites is the cost incurred in transferring multimedia data objects (MDO's) from different sites to the site where the query is initiated. The objective of a data allocation algorithm is to locate the MDO's at different sites so as to minimize the total data transfer cost incurred in executing a given set of queries. There is a mutual dependency between data allocation and query execution strategies in that the optimal allocation of MDO's depends on the query execution strategy employed by a distributed multimedia system while the query execution strategy optimizes a query based on this allocation. In this paper, we fix the query execution strategy and develop a site-independent MDO dependency graph representation to model the dependencies among the MDO's accessed by a query. Given the MDO dependency graphs as well as the set of multimedia database sites, data transfer costs between the sites, the allocation limit on the number of MDO's that can be allocated at a site, and the query execution frequencies from the sites, an allocation scheme is generated. We formulate the data allocation problem as an optimization problem. We solve this problem with a number of techniques that broadly belong to three classes: max-flow min-cut, state-space search, and graph partitioning heuristics. The max-flow min-cut technique formulates the data allocation problem as a network-flow problem, and uses a hill-climbing approach to try to find the optimal solution. For the state-space search approach, the problem is solved using a best-first search algorithm. The graph partitioning approach uses two clustering heuristics, the agglomerative clustering and divisive clustering. We evaluate and compare these approaches, and assess their cost-performance trade-offs. All algorithms are also compared with optimal solutions obtained through exhaustive search. Conclusions are also made on the suitability of these approaches to different scenarios.
Persistent Identifierhttp://hdl.handle.net/10722/155041
ISSN
2015 Impact Factor: 3.672
2015 SCImago Journal Rankings: 2.915
References

 

DC FieldValueLanguage
dc.contributor.authorKwok, YKen_US
dc.contributor.authorKarlapalem, Ken_US
dc.contributor.authorAhmad, Ien_US
dc.contributor.authorPun, NMen_US
dc.date.accessioned2012-08-08T08:31:37Z-
dc.date.available2012-08-08T08:31:37Z-
dc.date.issued1996en_US
dc.identifier.citationIeee Journal On Selected Areas In Communications, 1996, v. 14 n. 7, p. 1332-1348en_US
dc.identifier.issn0733-8716en_US
dc.identifier.urihttp://hdl.handle.net/10722/155041-
dc.description.abstractA major cost in retrieving multimedia data from multiple sites is the cost incurred in transferring multimedia data objects (MDO's) from different sites to the site where the query is initiated. The objective of a data allocation algorithm is to locate the MDO's at different sites so as to minimize the total data transfer cost incurred in executing a given set of queries. There is a mutual dependency between data allocation and query execution strategies in that the optimal allocation of MDO's depends on the query execution strategy employed by a distributed multimedia system while the query execution strategy optimizes a query based on this allocation. In this paper, we fix the query execution strategy and develop a site-independent MDO dependency graph representation to model the dependencies among the MDO's accessed by a query. Given the MDO dependency graphs as well as the set of multimedia database sites, data transfer costs between the sites, the allocation limit on the number of MDO's that can be allocated at a site, and the query execution frequencies from the sites, an allocation scheme is generated. We formulate the data allocation problem as an optimization problem. We solve this problem with a number of techniques that broadly belong to three classes: max-flow min-cut, state-space search, and graph partitioning heuristics. The max-flow min-cut technique formulates the data allocation problem as a network-flow problem, and uses a hill-climbing approach to try to find the optimal solution. For the state-space search approach, the problem is solved using a best-first search algorithm. The graph partitioning approach uses two clustering heuristics, the agglomerative clustering and divisive clustering. We evaluate and compare these approaches, and assess their cost-performance trade-offs. All algorithms are also compared with optimal solutions obtained through exhaustive search. Conclusions are also made on the suitability of these approaches to different scenarios.en_US
dc.languageengen_US
dc.relation.ispartofIEEE Journal on Selected Areas in Communicationsen_US
dc.subjectBest-First Search Algorithmen_US
dc.subjectClusteringen_US
dc.subjectData Allocationen_US
dc.subjectDistributed Database Systemsen_US
dc.subjectHill-Climbing Heuristicsen_US
dc.subjectMax-Flow Min-Cut Problemen_US
dc.subjectMultimedia Database Systemsen_US
dc.subjectNetwork Flow Algorithmen_US
dc.subjectOptimal Allocationen_US
dc.subjectQuery Processingen_US
dc.titleDesign and evaluation of data allocation algorithms for distributed multimedia database systemsen_US
dc.typeArticleen_US
dc.identifier.emailKwok, YK:ykwok@eee.hku.hken_US
dc.identifier.authorityKwok, YK=rp00128en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1109/49.536483en_US
dc.identifier.scopuseid_2-s2.0-0030244802en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0030244802&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume14en_US
dc.identifier.issue7en_US
dc.identifier.spage1332en_US
dc.identifier.epage1348en_US
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridKwok, YK=7101857718en_US
dc.identifier.scopusauthoridKarlapalem, K=8918944200en_US
dc.identifier.scopusauthoridAhmad, I=7201878459en_US
dc.identifier.scopusauthoridPun, NM=6508034129en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats