[OT] Efficient file structure for very large lookup tables?
Craig Dillabaugh
craig.dillabaugh at gmail.com
Tue Dec 17 11:54:17 PST 2013
On Tuesday, 17 December 2013 at 19:24:30 UTC, tn wrote:
> On Tuesday, 17 December 2013 at 19:09:49 UTC, H. S. Teoh wrote:
>> However,
>> they do exhibit good spatial locality in higher-dimensional
>> space (i.e.,
>> if entry X is accessed first, then the next entry Y is quite
>> likely to
>> be close to X in that space). Does anybody know of a good data
>> structure that can take advantage of this fact to minimize disk
>> accesses?
>
> Perhaps some kind of k-d tree? Maybe even some sort of cache
> oblivious k-d tree to make it more suitable for storage on the
> disk?
Its not cache-oblivious buy he could try the KDB tree:
http://dl.acm.org/citation.cfm?id=582321
or, again for batched queries the is the
Bkd-tree (search on Bkd-tree and Lars Arge) - this paper is a
type of buffer tree so the operations need to be able to be run
as a batch.
More information about the Digitalmars-d
mailing list