Gesellschaft für Informatik e.V.

Lecture Notes in Informatics


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


2007


Editors

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


Contents

Algebraic query optimization for distributed top-k queries

Thomas Neumann and Sebastian Michel

Abstract


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