TY - GEN
T1 - Algebraic query optimization for distributed top-k queries
AU - Neumann, Thomas
AU - Michel, Sebastian
PY - 2007
Y1 - 2007
N2 - Distributed top-κ 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-κ 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-κ query optimization both in network resource consumption and query response time.
AB - Distributed top-κ 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-κ 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-κ query optimization both in network resource consumption and query response time.
UR - http://www.scopus.com/inward/record.url?scp=78650418111&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:78650418111
SN - 9783885791973
T3 - Datenbanksysteme in Business, Technologie und Web, BTW 2007 - 12th Fachtagung des GI-Fachbereichs "Datenbanken und Informationssysteme" (DBIS), Proceedings
SP - 324
EP - 343
BT - Datenbanksysteme in Business, Technologie und Web, BTW 2007 - 12th Fachtagung des GI-Fachbereichs "Datenbanken und Informationssysteme" (DBIS), Proceedings
T2 - 12th Symposium of the German Informatics Society Section "Databases and Information Systems" (DBIS) on Database Systems in Business, Technology and Web, BTW 2007
Y2 - 7 March 2007 through 9 March 2007
ER -