hide
Free keywords:
-
Abstract:
Top-$k$ query processing is a fundamental building block for efficient ranking
in a large number of applications. Efficiency is a central issue, especially
for distributed settings, when the data is spread across different nodes in a
network. This paper introduces novel optimization methods for top-$k$
aggregation queries in such distributed environments. The optimizations can be
applied to all algorithms that fall into the frameworks of the prior TPUT and
KLEE methods. The optimizations address three degrees of freedom: 1)
hierarchically
grouping input lists into top-$k$ operator trees and optimizing the tree
structure, 2) computing data-adaptive scan depths for different input sources,
and 3) data-adaptive sampling of a small subset of input sources in scenarios
with hundreds or thousands of query-relevant network nodes. All optimizations
are based on a statistical cost model that utilizes local synopses, e.g., in
the form of histograms, efficiently computed convolutions, and estimators based
on order statistics. The paper presents comprehensive experiments, with three
different real-life datasets and using the ns-2 network simulator for
a packet-level simulation of a large Internet-style network.
