Re: Persistent Binary Search Trees

[Mikkel Kamstrup Erlandsen <mikkel kamstrup gmail com>]

2009/10/5 Mikkel Kamstrup Erlandsen <mikkel kamstrup gmail com>:
> 2009/10/5 Dana Jansens <dana cg scs carleton ca>:
>> 2009/10/5 Mikkel Kamstrup Erlandsen <mikkel kamstrup gmail com>:
>>> Don't let that hold you back. As far as I can imagine I don't have any
>>> use case ready, but that is probably because I've never had a
>>> persistent BST at hand :-)
>>>
>>> If I where you I'd probably just develop on out-of-tree library for
>>> the datastructure, keeping the API aligned with glib, and making an
>>> effort to make it easy to merge to glib should the desire arise.
>>>
>>> Then do some lobbying for the lib in some areas where you can see use
>>> cases. If you can get tracktion from some real world apps, the chances
>>> of getting into glib are higher. As an alternative you could develop
>>> the datastructure for the collections library used by Vala; libgee.
>>> They have a much more rich collections API and are also still less
>>> frozen API-wise.
>>
>> Thanks for your suggestions.
>>
>>> I also have a few questions:
>>> What is the relation to the copy-on-write B-trees like used in Btrfs?
>>> Can I version sub-trees or is it always the entire tree?
>>
>> I'm not very familiar with the copy-on-write trees in Btrfs, but from
>> reading about it briefly, and from general intuition, it doesn't sound
>> quite like the same idea, though with the same effect. A simpler
>> implementation of a persistent BST can simply copy the path from the
>> root down along any changes for each insert/delete.  However this
>> requires a lot more space than the implementation I am suggesting.
>> Instead, each node in the tree can keep a history of pointers to its
>> children, which are changed (and remembered) over time.  Only one copy
>> of any node in the tree ever exists, and only O(1) pointers are
>> changed to perform an insert/delete.
>>
>> The difference to the Btrfs trees is that, in that case, the data is
>> changing within a node, so you need to copy the old data.  In a
>> persistent BST as proposed, the data within a node is not what is
>> preserved, but the structure of the tree itself, as the tree evolves
>> with time.  The persistence mechanism is described in this paper [1].
>
> Aha - now I get it :-) Thanks for clearing it up. This sounds mighty
> interesting; now I just need to figure out what cool things I can use
> it for :-)

I might as well reveal that I have one specific use case in mind, but
I can't really get my head around if we can use PBSTs to brew a bucket
of awesome. The application is the Zeitgeist engine where we extract
event graphs from desktop usage; Seif Lotfy's old blog post is still
relevant: http://seilo.geekyogre.com/2009/08/a-better-sample-of-connect-the-dots/.

Naturally a normal event graph based on user actions will be "append
only" and not change nodes up the tree, which to my understanding is a
simple edge case of PBSTs. But I am thinking about some funky stuff
where we could utilize the general PBST, but my thoughts right now are
not coherent enough for me to write down :-)

Cheers,
Mikkel
-- 
Cheers,
Mikkel