Hey cool, thanks for digging that up, it certainly looks similar at first glance.
I can't tell you how many times I've had the feeling that finally I was doing anything at all that was original and then to find out (usually within five minutes, but this time at least a lot of years later) that it was already old hat when I was a toddler.
Oh well. Keep trying I guess.
One problem with stuff like this is simply to find what is out there given a problem description.
The name of it was on the tip of my tongue as I read your description, so I googled for "probabilistic constant-space test for membership", and voila, first result.
I bow to your google fu, that would have taken me a week.
At least.
If I would have found it at all. This is one of those areas where I think I can really feel that having English as a first language - or at least a degree in computer science - would have helped tremendously, just knowing the right terminology can be such a huge advantage.
I can parse your description of it but I could never come up with it in those terms. I'd be looking for "compressed index" or "candidate records algorithm" or something like that.
I thought "Bloom filter" too as soon as I read his description. They're used all over information retrieval. It's very common to need to hit the disk to say for sure whether an element satisfies your query, but the vast majority of elements don't. If you can eliminate those seeks entirely with a Bloom filter, your algorithm as a whole will run much faster.
Comments
Sounds like you invented something like a Bloom filter, kudos!
http://en.wikipedia.org/wiki/Bloom_filter
Hey cool, thanks for digging that up, it certainly looks similar at first glance.
I can't tell you how many times I've had the feeling that finally I was doing anything at all that was original and then to find out (usually within five minutes, but this time at least a lot of years later) that it was already old hat when I was a toddler.
Oh well. Keep trying I guess.
One problem with stuff like this is simply to find what is out there given a problem description.
The name of it was on the tip of my tongue as I read your description, so I googled for "probabilistic constant-space test for membership", and voila, first result.
I bow to your google fu, that would have taken me a week.
At least.
If I would have found it at all. This is one of those areas where I think I can really feel that having English as a first language - or at least a degree in computer science - would have helped tremendously, just knowing the right terminology can be such a huge advantage.
I can parse your description of it but I could never come up with it in those terms. I'd be looking for "compressed index" or "candidate records algorithm" or something like that.
I thought "Bloom filter" too as soon as I read his description. They're used all over information retrieval. It's very common to need to hit the disk to say for sure whether an element satisfies your query, but the vast majority of elements don't. If you can eliminate those seeks entirely with a Bloom filter, your algorithm as a whole will run much faster.