2009/10/5 Mikkel Kamstrup Erlandsen <mikkel.kamst...@gmail.com>: > 2009/10/5 Dana Jansens <d...@cg.scs.carleton.ca>: >> 2009/10/5 Mikkel Kamstrup Erlandsen <mikkel.kamst...@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 _______________________________________________ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list