[OT] Efficient file structure for very large lookup tables?

[H. S. Teoh]

On Tue, Dec 17, 2013 at 09:02:41PM +0100, digitalmars-d-bounces at puremagic.com wrote:
> On Tuesday, 17 December 2013 at 19:09:49 UTC, H. S. Teoh wrote:
> >What's a good, efficient file structure for storing extremely large
> >lookup tables? (Extremely large as in > 10 million entries, with keys
> >and values roughly about 100 bytes each.) The structure must support
> >efficient adding and lookup of entries, as these two operations will
> >be very frequent.
> 
> But 200*10million = 2GB. Can't you use an existing KD-tree and tweak
> it to fit memory pages and rely on paging for a start?

Hmm. You're right, I think I underestimated my data size. :P  The 10
million figure is based on problems that my current program successfully
solved (with an in-memory hashtable). I guess that larger problems must
far exceed that number (I ran out of memory so I couldn't check just how
big it got before I killed the process). Suffice it to say that this is
a combinatorial problem, so the number of entries grow exponentially;
anything that can help reduce the storage requirements / I/O latency
would be a big help.


T

-- 
VI = Visual Irritation