Similar issue in doing LNP lookups in the US. There's about 500M entries, each mapping to a different LRN. Naively, that's 16 bytes per entry (8 for the number, 8 for the LRN), so 8GB.
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.
Comments
Similar issue in doing LNP lookups in the US. There's about 500M entries, each mapping to a different LRN. Naively, that's 16 bytes per entry (8 for the number, 8 for the LRN), so 8GB.
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.