Doing the Impossible, Almost (A survey of approximation algorithms that make queries vastly faster)

Ted Dunning (MapR)
Data Science
Location: 115
Average rating: ****.
(4.88, 17 ratings)

Computing various quantities such as medians or the number of unique elements requires a lot of time or a lot of memory or both. It is, however, possible to get really close to the exact answer with much less time and much less memory. Some of these algorithms are much simpler than you might expect. I will describe a selection of these algorithms including some not yet published results.

I will also outline how these algorithms can be applied to practical problems like anomaly detection.

Photo of Ted Dunning

Ted Dunning

MapR

Ted Dunning is Chief Application Architect at MapR Technologies and committer and PMC member for the Apache Mahout project. He contributing to the Mahout clustering, classification and matrix decomposition algorithms. He was the chief architect behind the MusicMatch, (now Yahoo Music) and Veoh recommendation systems and built fraud detection systems for ID Analytics.