Probabilistic M2M Relationships Using Bloom Filters

Re:Probabilistic M2M Relationships Using Bloom Filters by Smerity on Friday May 01, 2015 @09:49PM (#9475554)

You're indeed correct as this is built upon bloom filters and standard bloom filters don't support deletion[1]. You could reconstruct the bloom filter minus the deleted element from each of the individual relations but then you'd need the relation table.

The other substantial issue with the proposed scheme is false positives. In this situation, you have no way to ensure that a given relation is not an accidental match. For that you would again need the relations table.

What's fun about this story is that the author has inadvertently re-discovered the bloom join[2] - he's just missing one of the important steps. Traditionally bloom filters are used for a fast, initial check which is then followed by a full check to remove false positives.

[1]: There are some modifications to bloom filters that support deletion but they're all more complex than bitstrings.

[2]: http://www.databasejournal.com/features/oracle/oracle-bloom-...

[ Parent | on HN ]

Re:Probabilistic M2M Relationships Using Bloom Filters by brudgers on Friday May 01, 2015 @11:23PM (#9475747)

Sometimes a few false positives don't matter. Or matter less than latency. Nobody dies if a query returns Daniel Day Lewis as the star of Ernest Goes to Camp and many people might just write it off as human error...even if it isn't.

[ Parent | on HN ]