It would be fun to look at stochastic ways to approximate k-NN and other sketches.
Vowpal Wabbit is a great project that implements approximate, streaming versions of a lot of basic machine learning algorithms. And it has incredibly high throughput even when run as a single process. VW by itself has made me greatly skeptical of the "need" for systems like Spark.
Locality-sensitive hashing is a cool approximate kNN algorithm, along with others on the Wikipedia kNN page. kNN I think is especially suitable for approximate techniques because often the "nearest neighbors" are a little unstable and highly dependent on the distance metric anyway, so you lose little by moving to an approximate algorithm. When you approximate regression, OTOH, you complicate your ability to make statistically valid statements on the model.