Re: [Caml-list] Keeping A big data optimization problem functional

[Francois Berenger <berenger@riken.jp>]

And that's when I realize that "Oh! No! We don't have bindings to 
Berkeley DB in OPAM!". That's unfortunate. :(

On 2014年04月14日 14:25, Arthur Breitman wrote:
> Hello all,
>
> This is my first post to the mailing list, I hope it will be relevant and
> in line with the posting guidelines. If not, please let me know and pardon
> my ignorance.
>
> I am working on a large problem that I'm attempting to tackle in Ocaml. It
> requires me to optimize a function over a tree
>
> - the tree has on the order of 100,000 to 1,000,000 nodes
> - each node on the tree contains on the order of 100kB to 1MB of data
>
> So total, I'm looking at 10GB to 1TB one data which is typically stored in
> a database on disk. The tree is loaded in memory using keys that represent
> entries in the database.
>
> Another structure I'm dealing with is a key value store, whose size is on
> the same order of magnitude as the size of the data above. Initially, this
> key-value store is empty.
>
> I am given an "apply" function that, for a given key-value store and for a
> given node in the tree produces a new key-value store. Typically by
> modifying a few keys in the key-value store. The amount of bits changed is
> on the same order of magnitude as the size of the node. When I reach a leaf
> of the tree, I can compute the optimality of that leaf from the state of
> the key-value store. I want to find the best leaf.
>
> Here's my problem...
> If I write the following in a imperative fashion, it seems straightforward
> enough. I should be doing a DFS over my tree, mutating my key=value store
> as I go, and saving on disk "backup" information to backtrack through the
> tree. This doesn't feel very elegant. I've been considering two solutions
>
> 1) since there is a one to one mapping between nodes in the tree and
> key-value stores, I could make my key-value store type to actually be the
> same as a node in the tree. I would put it in a module along with a
> reference to the node representing which key-value store is being
> represented on disk. The "apply" function would be straightforward and
> lazy, but whenever the keys of a key-value store are to be accessed, the
> following would happen
>
> a) Check if the key-value store on disk is the same as the one requested,
> if so read the key
> b) If that's not the case, find the least common ancestor in the tree,
> migrate the disk cache to that version then down to the one requested. This
> would require me to have an "undo" function to complement the "apply"
> function, which is an acceptable compromise.
>
> 2) the second solution would be to represent the key-value store as a
> binary tree. Since each operation changes only a few keys, I wouldn't be
> making a dumb copy of the entire key-value store at each step, only of the
> keys that matter. The problem is that though that works great in memory,
> I'm not sure how to make it work with an on-disk storage, a necessity given
> the size of it.
>
> Thanks,
> Arthurto
>


-- 
Best regards,
Francois Berenger.