StreamApprox: Approximate computing for stream analytics

Do Le Quoc, Ruichuan Chen, Pramod Bhatotia, Christof Fetzer, Volker Hilt, Thorsten Strufe

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

34 Scopus citations

Abstract

Approximate computing aims for efficient execution of workflows where an approximate output is sufficient instead of the exact output. The idea behind approximate computing is to compute over a representative sample instead of the entire input dataset. Thus, approximate computing - based on the chosen sample size - can make a systematic trade-off between the output accuracy and computation efficiency. Unfortunately, the state-of-the-art systems for approximate computing primarily target batch analytics, where the input data remains unchanged during the course of computation. Thus, they are not well-suited for stream analytics. This motivated the design of StreamApprox- a stream analytics system for approximate computing. To realize this idea, we designed an online stratified reservoir sampling algorithm to produce approximate output with rigorous error bounds. Importantly, our proposed algorithm is generic and can be applied to two prominent types of stream processing systems: (1) batched stream processing such as Apache Spark Streaming, and (2) pipelined stream processing such as Apache Flink. To showcase the effectiveness of our algorithm, we implemented StreamApprox as a fully functional prototype based on Apache Spark Streaming and Apache Flink. We evaluated StreamApprox using a set of microbenchmarks and real-world case studies. Our results show that Spark- and Flink-based StreamApprox systems achieve a speedup of 1.15×-3× compared to the respective native Spark Streaming and Flink executions, with varying sampling fraction of 80% to 10%. Furthermore, we have also implemented an improved baseline in addition to the native execution baseline - a Spark-based approximate computing system leveraging the existing sampling modules in Apache Spark. Compared to the improved baseline, our results show that StreamApprox achieves a speedup of 1.1×-2.4× while maintaining the same accuracy level.

Original languageEnglish
Title of host publicationMiddleware 2017 - Proceedings of the 2017 International Middleware Conference
PublisherAssociation for Computing Machinery, Inc
Pages185-197
Number of pages13
ISBN (Electronic)9781450347204
DOIs
StatePublished - 11 Dec 2017
Externally publishedYes
Event18th ACM/IFIP/USENIX Middleware Conference, Middleware 2017 - Las Vegas, United States
Duration: 11 Dec 201715 Dec 2017

Publication series

NameMiddleware 2017 - Proceedings of the 2017 International Middleware Conference

Conference

Conference18th ACM/IFIP/USENIX Middleware Conference, Middleware 2017
Country/TerritoryUnited States
CityLas Vegas
Period11/12/1715/12/17

Keywords

  • Approximate Computing
  • Distributed Systems
  • Online Adaptive Sampling
  • Stratified Sampling
  • Stream Analytics

Fingerprint

Dive into the research topics of 'StreamApprox: Approximate computing for stream analytics'. Together they form a unique fingerprint.

Cite this