6 ms·

My nitpicking was more about how they were presented. If you are simply using a bloom filter to avoid random disk access on the database, then no, you haven't l

by xaa 12y ago

My nitpicking was more about how they were presented. If you are simply using a bloom filter to avoid random disk access on the database, then no, you haven't lost accuracy in your system-as-a-whole. Also, and I guess this is more fuzzy, my perception is that set-membership algorithms, for very large sets, are largely used in search and recommendation. These problems have unique properties: if you get the top N right, the ordering of the rest hardly matters. Contrast this with regression or classification, where you are looking for a global result. Also, I agree that it is generally a bad idea to use linear data structures in streaming algorithms, but they are not automatically out in practice (as opposed to the CS literature). If you can keep the constant factor small.

tylertreat 12y ago
Fair criticism :) The reason I mostly focused on various Bloom filters was because I actually encountered a problem at work recently that required them to deduplicate messages in a distributed messaging system. Mostly was journaling my research. It would be fun to look at stochastic ways to approximate k-NN and other sketches.
- xaa 12y ago
  It was an interesting read for sure, and I appreciate it for what it is. Of course, this is HN, so we have to criticize ;) 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.

by xaa 12y ago

tylertreat 12y ago

Fair criticism :) The reason I mostly focused on various Bloom filters was because I actually encountered a problem at work recently that required them to deduplicate messages in a distributed messaging system. Mostly was journaling my research. It would be fun to look at stochastic ways to approximate k-NN and other sketches.

xaa 12y ago
It was an interesting read for sure, and I appreciate it for what it is. Of course, this is HN, so we have to criticize ;) 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.