Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I've got a catalog at work and I want to juke it up a bit because I'm tired of it being extremely slow. I'd like to support the modified preorder tree traversal storage method for the category tree of the catalog but i'd have to support dated versionning.

I've thought about creating versions of trees based on dates, so as soon as something changes I create a copy of the tree at hand at current date and then create my modifications. But the problem with that is that an import of a catalog that occurs every night would create, at long range, an extremely heavy table of tree traversal elements. Combined with the fact that a user could go and change a date anytime in the admin, it could then again generate another tree version.

Most of our catalogs are comprised of 100-250 categories, so a few versions would not create more than a few thousand elements, but mix that to a year of operation, that would easily go up to 90000 entries just to store the tree that can change.

So my question is this:

Is there a way you'd implement a fast tree traversal method (preferably modified preorder with left and right columns) that would support dated versioning?

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

Confluently Persistent Tries for Efficient Version Control
http://erikdemaine.org/papers/ConfluentTries_Algorithmica/

We consider a data-structural problem motivated by version control of a hierarchical directory structure in a system like Subversion. The model is that directories and files can be moved and copied between two arbitrary versions in addition to being added or removed in an arbitrary version. Equivalently, we wish to maintain a confluently persistent trie (where internal nodes represent directories, leaves represent files, and edge labels represent path names), subject to copying a subtree between two arbitrary versions, adding a new child to an existing node, and deleting an existing subtree in an arbitrary version.

share|improve this answer
    
This is by far one the best possible answers (even if it's the only one) i'll study this carefuly, than you Robert –  Mathieu Dumoulin Feb 16 '12 at 13:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.