hide
Free keywords:
-
Abstract:
Efficient query processing in traditional database management systems relies on
statistics on base data. For centralized systems, there is a rich body of
research results on such statistics, from simple aggregates to more elaborate
synopses such as sketches and histograms. For Internet-scale distributed
systems, on the other hand, statistics management still poses major challenges.
With the work in this paper we aim to endow peer-to-peer data management over
structured overlays with the power associated with such statistical
information, with emphasis on meeting the scalability challenge. To this end,
we first contribute efficient, accurate, and decentralized algorithms that can
compute key aggregates such as Count, CountDistinct, Sum, and Average. We show
how to construct several types of histograms, such as simple Equi-Width,
Average-Shifted Equi-Width, and Equi-Depth histograms. We present a
full-fledged open-source implementation of these tools for distributed
statistical synopses, and report on a comprehensive experimental performance
evaluation, evaluating our contributions in terms of efficiency, accuracy, and
scalability
