Something for (Almost) Nothing: New Advances in Sublinear-Time Algorithms

Authored by: Ronitt Rubinfeld , Eric Blais

Handbook of Big Data

Print publication date:  February  2016
Online publication date:  February  2016

Print ISBN: 9781482249071
eBook ISBN: 9781482249088
Adobe ISBN:

10.1201/b19567-14

 Download Chapter

 

Abstract

What computational problems can we solve when we only have time to look at a tiny fraction of the data? This general question has been studied from many different angles in statistics. More recently, with the recent proliferation of massive datasets, it has also become a central question in computer science as well. Essentially, all of the research on this question starts with a simple observation: Except for a very small number of special cases, the only problems that can be solved in this very restrictive setting are those that admit approximate solutions.

 Cite
Search for more...
Back to top

Use of cookies on this website

We are using cookies to provide statistics that help us give you the best experience of our site. You can find out more in our Privacy Policy. By continuing to use the site you are agreeing to our use of cookies.