Given the standard North American phone number format: (Area Code) Exchange - Subscriber, the set of possible numbers is about 6 billion. However, efficiently breaking down the nodes into the sections listed above would yield less than 12000 distinct nodes that can be arranged in groupings to get all the possible numbers.
This seems like a problem already solved.
Would it done via a graph or tree?
A comment you placed on the question:
It was an easier question to ask, instead of qualifying. Let's just say that there are much more than 5, but still less than 6 billion. :-)
So it sounds like you intend to store all current valid phone numbers, in the range of (000) 000-0000 through (999) 999-9999. So the set of possible numbers is 10,000,000,000, or, 10 billion.
This number can immediately be reduced to less than 8 billion, since the first digit in an area code cannot be a 0 or 1, area code cannot end in "11", and 555 numbers are reserved, as well as a few other rules.
Since only a maximum of 8 billion are available, and you mention storing 5-6 billion, I propose the much more space-efficient storage of the 2-3 billion unused numbers.
To generate a list of valid numbers, you would then numerically loop through all combinations, and skip numbers in the list of invalid numbers. Or, simply check to see that a number is not in the store invalid numbers, to know if it is valid.
A Trie tree or a Radix tree are most likely going to be the most space efficient while still having fast lookup/insert/remove speeds.
If my calculations are correct, a bit array for each phone number should take about 1.2 GB of memory. Simply set the bit for each phone number that is valid.
If you were doing this for ultimate memory efficency you could do better.
Start with the area code - I don't know how many are actually used but assuming you need to store all 3 digit values.
Presumably exchange codes are filled in order, so you would expect the lower ones to be used in more areas than the higher ones. So you could use a run-length coding to flag the sequences that are in use.
Finally actual phone numbers will be used or not at random so I would use a bit field to flag which of the 9999 possible last numbers are on. At one bit/number you need only 1K to store each set.
Graph isn't suitable for this, the implementation requires more memory than tree and it doesn't provide any additional features in this case.
Prefix trees? These are very efficient for search but memory representation isn't optimized for size. They're in fact very memory inefficient. They can also be used to compress data and write it to disk but memory representation takes much more memory than the data itself.
If you arrange by groups so only 3 last digits would be stored in the tree-like struct it'd be 3x4 + 1 bytes for each number anyway (3x4 byte pointer + 1 byte for data). ~78 GB just for 3 last digits of each number (if i remember the implementation details correctly). Which will require 64 bit pointers instead of 32b... so ~140GB of ram.
So the problem (in my opinion) is that for tree for each suffix in each group you still need at least one 32 bit pointer (which will probably turn out to be 64 bits because you'd need to allocate > 4GB for the data).
In my opinion most efficient way will be an array or 12000 pointers to structure like
char[x] prefix;
DWORD* suffixes;
int n_count;
so prefix, eg. 43333 suffix eg. 19821982 => number is 4333319821982 (n_count -> count of numbers)
You store the numbers without separators to save space, one suffix after the other (eg. number 1 is suffixes+0, number 2 is suffixes+1) and you can search efficiently too, if you have it sorted.
This way it'd take just 4(DWORD)*6 billion suffixes = 24GB of memory + size of 12k pointers + prefixes which is irrelevant
So instead of (at least!) 6 billion 64 bit pointers you'd just have (at most!) 6b of 32 bit suffixes.
But probably the numbers are continuous, so you can try array of (start_suffix, end_suffix) instead of just storing all suffixes should take much less.
