DataSketches - The Required Toolkit for the Analysis of Big Data

Lee Rhodes

2019-09-11 15:15 #bigdata

In​ the analysis of b​ig data there are often problem queries that don’t scale because they require huge compute resources to generate exact results, or don’t parallelize well. Examples include c​ount-distinct, ​quantiles, most frequent items, joins, matrix computations, and graph analysis. Algorithms that can produce accuracy guaranteed approximate answers for these problem queries are a required toolkit for modern analysis systems that need to process massive amounts of data​ quickly. For interactive queries there may not be other viable alternatives, and in the case of real­-time streams, these specialized algorithms, called stochastic, s​treaming, sublinear algorithms,​ or ‘s​ketches’,​ are the only known solution. This technology has helped Yahoo successfully reduce data processing times from days to hours or minutes on a number of its internal platforms and has enabled subsecond queries on real-time platforms that would have been infeasible without sketches. This article provides a short introduction to sketching and to DataSketches, an open source library of a core set of these algorithms designed for large production analysis systems.