Gesellschaft für Informatik e.V.

Lecture Notes in Informatics

Datenbanksysteme in Business, Technologie und Web (BTW 2007) P-103, 324-343 (2007).



Alfons Kemper (ed.), Harald Schöning (ed.), Thomas Rose (ed.), Matthias Jarke (ed.), Thomas Seidl (ed.), Christoph Quix (ed.), Christoph Brochhaus (ed.)


Algebraic query optimization for distributed top-k queries

Thomas Neumann and Sebastian Michel


Distributed top-k query processing is increasingly becoming an essential functionality in a large number of emerging application classes. This paper addresses the efficient algebraic optimization 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 use a dynamic programming approach to find the optimal execution plan using compact data synopses for selectivity estimation that is the basis for our cost model. The optimized query is executed in a hierarchical way involving a small and fixed number of communication phases. We have performed experiments on real web data that show the benefits of distributed top-k query optimization both in network resource consumption and query response time.

Full Text: PDF

ISBN 978-3-88579-197-3

Last changed 04.10.2013 18:13:33