21–30 of 59 posts
Thanks for posting this article. Would this be a good use case for a bloom filter?
Basically you'd waste more time (and money) than it could possibly be worth.
Thanks for posting this article. Would this be a good use case for a bloom filter?
Maybe, probably not thought as a completely naive solution to this problem an array of 400M elements which is sorted, only takes 2.4 GB of RAM, or about $50 worth of RAM. Basically you'd waste more time (and money) than it could possibly be worth.
Thanks for posting this article. Would this be a good use case for a bloom filter?
Maybe, probably not thought as a completely naive solution to this problem an array of 400M elements which is sorted, only takes 2.4 GB of RAM, or about $50 worth of RAM. Basically you'd waste more time (and money) than it could possibly be worth.
The thing that strikes me is that while the data being searched for has been optimized down to 2 bytes of bitfields, the same hasn't been done with the phone numbers - area codes in India appear to be variable-length (2, 3, ? digits) with that length being part of the 10 digits, and presumably mobile numbers are handled similarly either with their own area codes or overlapping. Breaking the data by area code would al…
And separately, depending on the hit rate and particularly in the sparse sections, there might be situations where it would make sense to have a preliminary lookup that simply indicated whether there were any possible matches within a prefix range - before searching, get an overview of whether there's anything to search.
Overall this strikes me as something that could demonstrate the importance of having developers aware of the environment in which something will be used. If there are going to be 2 of something, throw hardware at it. If there are going to be 2,000 of "something" instead, an extra $1000 each in "throw hardware at it" could become a real issue.
Earlier quoted context omitted.
Maybe, probably not thought as a completely naive solution to this problem an array of 400M elements which is sorted, only takes 2.4 GB of RAM, or about $50 worth of RAM. Basically you'd waste more time (and money) than it could possibly be worth.
I mean, a bloom filter isn't super difficult, but it's also probabilistic instead of deterministic.
Also, typically bloom filters don't come out of the box with the language you're using, so it's just more potential for bugs.
A lookup on a sorted array should take 8.6 comparisons anyway, I bet the hashing takes longer...
Thanks for posting this article. Would this be a good use case for a bloom filter?
Maybe, probably not thought as a completely naive solution to this problem an array of 400M elements which is sorted, only takes 2.4 GB of RAM, or about $50 worth of RAM. Basically you'd waste more time (and money) than it could possibly be worth.
First optimization is changing the LRNs to a lookup, as there's only ~30K uniques. So that cuts the data to 5GB. That's OK but it'd be better if it was smaller and quicker to load.
I implemented a delta-encoding system with multi-level indexing, ISAM style. Data's compressed on a "page" basis, like 4KB or so of data at a time. That way all data is compressed while in memory and lookups can be done on the compressed data directly. A header on each page provides the range it covers, so you can quickly skip to the next page if the index wasn't precise enough.
Delta encoding is neat here, because on average, there'll only be gap of 18 numbers from one entry to the next (~9B possible numbers / 500M). I used base128 encoding but simple16 or another way (there's SIMD-optimized formats) would have been even better.
Using this method, the entire dataset only requires about 600-800MB of RAM.
Does it worth mentioning? Straightforward approach of storing numbers in a hash map in memory solves the problem. This may require say 40 Gb of ram w/o ANY optimizations.
Earlier quoted context omitted.
Because the interesting part of the effort is doing it fast in anticipation of translating the optimization tricks to cases where you can't just go buy more RAM anymore. A lot of problems can be "solved" with current hardware because accesses or comparisons or whatnot become ridiculously cheap but that's not what computer science is about.
This is one of the biggest problems I run into in 'software engineering', people building way to complex systems because they are 'interesting' rather than buying $50 of RAM and being done with it, and then poo-poo'ing systems that cost $50 and work. Querying a DNC list is not a problem in which you will ever not be able to buy more RAM, it's trivially parallel, if for some reason DNC lists ever outpace Moore's law,…