Incremental Approximate Computing

Dhanya R. Krishnan, Do Le Quoc, Pramod Bhatotia, Christof Fetzer, Rodrigo Rodrigues

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)peer-review

Abstract

Approximate computing is increasingly used for speeding up computations and efficiently utilizing the computing resources. The idea behind approximate computing is to return an approximate answer instead of the exact answer for user queries. The trick is to choose a representative sample of the data for computing instead of using the entire data. As a result, it allows users to trade-off query accuracy for response time, enabling interactive queries over massive data by running queries on data samples and presenting results annotated with meaningful error bars. At the same time, another technique called incremental computing tries to achieve the same goals as approximate computing, i.e., speeding up job execution and utilizing resource efficiently. Incremental computing relies on the memoization of intermediate results of sub-computations, and reusing these memoized results across jobs.

This work makes the observation that these two computing paradigms are complementary, and can be married together! The idea is quite simple: design a sampling algorithm that biases the sample selection to the memoized data items from previous runs. To realize this idea, an online stratified sampling algorithm is designed.

The algorithm uses self-adjusting computation to produce an incrementally updated approximate output with bounded error. The algorithm is implemented in a data analytics system called INCAPPROX.
Original languageEnglish
Title of host publicationEncyclopedia of Big Data Technologies
EditorsSherif Sakr, Albert Zomaya
PublisherSpringer-Verlag
ChapterI
Pages1000-1007
Number of pages8
Edition1
ISBN (Electronic)978-3-319-77525-8
ISBN (Print)3319775243, 978-3319775241, 978-3-319-77526-5
DOIs
Publication statusPublished - 1 Mar 2019

Fingerprint Dive into the research topics of 'Incremental Approximate Computing'. Together they form a unique fingerprint.

Cite this