Responses in-line

On Mon, Apr 14, 2014 at 2:12 AM, Goswin von Brederlow <goswin-v-b@web.de>wrote:

> On Sun, Apr 13, 2014 at 11:25:18PM -0600, Arthur Breitman wrote:
> > Hello all,
>
> 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.
>
> You probably don't expect to keep 1TB data in ram. Does the key-value
> store just reference values in the DB?


Indeed it does. That's part of the difficulty.


 > 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.
>
> Not sure what you mean there. Maybe you could give an example with a
> small data set (maybe 10 keys).
>

It would be hard to make it a small example, but abstractly I have:

type node = {value: string; children: node list option}
module type Context = begin
  type t
  val apply: t -> node -> t
  val get: t -> string -> string option
  val set: t -> string -> string -> t
  val fitness -> int
  val empty -> t
end

Given a tree of nodes, and starting with Context.empty find the leaf node
with the highest fitness. You can think of every node in the tree as an
operation acting on the context.


>
> Wouldn't a simple Map work as your key-value store? The apply function
> would then modify the map, creating a new map that shares most of the
> unchanged data with the original map. That way keeping the results of
> many apply functions in memory should be possible and applying should
> be fast.
>

It would if I didn't potentially have a terabyte of data.



>
> But if memory becomes a problem then you probably want to use some
> form of B-Tree to.
>
> MfG
>         Goswin
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>



-- 
Arthur Breitman