KLEE: A Framework for Distributed Top-k Query Algorithms
KLEE: A Framework for Distributed Top-k Query Algorithms
复制标题
DOI：
--
复制
发表时间：
2005-08
期刊：
影响因子：
--
通讯作者：
S. Michel;P. Triantafillou;G. Weikum
中科院分区：
文献类型：
--
作者：
S. Michel;P. Triantafillou;G. Weikum
本文讨论了在广域分布式数据库中高效处理top-k查询的问题，其中查询的属性值（或文本项）的索引列表分布在多个数据对等体上，计算成本包括网络延迟、带宽消耗和本地对等体工作。我们提出了KLEE，一种新的算法框架，分布式top-k查询，设计高性能和灵活性。KLEE为广泛分布的数据源上的近似top-k算法提供了强有力的案例。它显示了如何在低结果质量惩罚的情况下获得巨大的效率收益。此外，KLEE提供查询发起对等体的灵活性，以权衡结果质量和预期的性能，并权衡在查询执行期间参与的通信阶段的数量与网络带宽性能。我们已经实现了KLEE和相关算法，并进行了全面的性能评估。我们的评估采用了真实世界和合成的大型网络数据集和查询基准。我们的实验结果表明，KLEE可以实现重大的性能增益，在网络带宽，查询响应时间，和更轻的对等负载，所有的结果精度和其他结果质量的措施小的错误。
This paper addresses the efficient processing of top-k queries in wide-area distributed data repositories where the index lists for the attribute values (or text terms) of a query are distributed across a number of data peers and the computational costs include network latency, bandwidth consumption, and local peer work. We present KLEE, a novel algorithmic framework for distributed top-k queries, designed for high performance and flexibility. KLEE makes a strong case for approximate top-k algorithms over widely distributed data sources. It shows how great gains in efficiency can be enjoyed at low result-quality penalties. Further, KLEE affords the query-initiating peer the flexibility to trade-off result quality and expected performance and to trade-off the number of communication phases engaged during query execution versus network bandwidth performance. We have implemented KLEE and related algorithms and conducted a comprehensive performance evaluation. Our evaluation employed real-world and synthetic large, web-data collections, and query benchmarks. Our experimental results show that KLEE can achieve major performance gains in terms of network bandwidth, query response times, and much lighter peer loads, all with small errors in result precision and other result-quality measures.