Design and Evaluation of Data Allocation Algorithms for Distributed Multimedia Database Systems
Design and Evaluation of Data Allocation Algorithms for Distributed Multimedia Database Systems
复制标题
分布式多媒体数据库系统数据分配算法的设计与评估
DOI：
10.1109/49.536483
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
Ng Moon Pun
中科院分区：
文献类型：
--
作者：
Yu;K. Karlapalem;I. Ahmad;Ng Moon Pun
从多个站点检索多媒体数据的主要成本是将多媒体数据对象(MDO)从不同站点传输到发起查询的站点所产生的成本。数据分配算法的目标是将 MDO 定位在不同站点，以便最大限度地减少执行给定查询集时产生的总数据传输成本。 MDO 的最佳分配取决于分布式多媒体系统所采用的查询执行策略，而查询执行策略则基于此分配来优化查询。我们修复了查询执行策略并开发了一种独立于站点的 MDO 依赖关系图表示，以对查询访问的 MDO 之间的依赖关系进行建模。给定 MDO 依赖关系图以及多媒体数据库站点集、站点之间的数据传输成本、站点上可分配的 MDO 数量的分配限制以及站点的查询执行频率，生成分配方案。我们将数据分配问题表述为优化问题。我们使用许多技术来解决这个问题，这些技术大致属于三类：最大流最小割、状态空间搜索和图分区启发式。最大流最小割技术将数据分配问题表述为网络流问题，并使用爬山方法来尝试找到最优解决方案。对于状态空间搜索方法，使用最佳优先搜索算法来解决问题。图划分方法使用两种聚类启发式：凝聚聚类和分裂聚类。我们评估和比较这些方法，并评估它们的成本性能权衡。所有算法还与通过穷举搜索获得的最优解进行比较。还就这些方法对不同场景的适用性得出了结论。
A major cost in retrieving multimedia data from multiple sites is the cost incurred in transferring multimedia data objects (MDOs) from different sites to the site where the query is initiated. The objective of a data allocation algorithm is to locate the MDOs at different sites so as to minimize the total data transfer cost incurred in executing a given set of queries. The optimal allocation of MDOs depends on the query execution strategy employed by a distributed multimedia system while the query execution strategy optimizes a query based on this allocation. We fix the query execution strategy and develop a site-independent MDO dependency graph representation to model the dependencies among the MDOs 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 MDOs 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.