[zzdev] Re: [zzdev] Persistent data structures

["David G. Durand" <david@xxxxxxxxxxxxxxxxxxx>]

At 2:20 PM +0200 3/2/01, Antti-Juhani Kaijanaho wrote:
> On 20010302T103638+0200, Tuomas Lukka wrote:
> >  Driscoll, Sarnak, Sleator and Tarjan[53]
> > 	Making data structures persistent, J.Comput.System.Sci 28(1989)86-124
>
> I just read the first few pages and it looks MASSIVELY interesting.

There's a lot of this stuff floating around.

Sarnak may have been on another paper or two.

I'd do a citation search on driscoll, sleator, et. al. as there were 
some improvements to their results, but I can't lay hands on the 
citations/papers.

Also worth looking at is Bernard Chazelle. How to search in history. 
Information and Control, 64(1--3):77--99, 1985.

These algorithms are  often seen as geometric algorithms, as they are 
useful in a variety of scanning search scenarios, and because they 
are specialized versions of multidimensional searching. So 
computational geometry books often have useful information on 
persistent data structure maintenance.

At some point, as the runtimes improve the algorithms become complex 
to the point of insanity, as is often the case.

Edelsbrunner and Overmars published monographs with algorithm 
descriptions and more citations.

Of course, the structures implemented in the code at udanax.com are 
relevant, if hard to decipher.

I'll be obnoxious enough to mention my dissertation, which discusses 
alternative approaches to searching in time (and has some 
bibliography).
http://cs-people.bu.edu/dgd/

Some other citations that I can find easily in my files (not all in the diss):

"Version control in hypertext systems" Hicks, Leggett, Schnase tech 
report available from cs.tamu.edu. Was published in TOIS.
This relates more to configuration management issues that come up in 
HT systems. There's also a tremendous literature in software 
engineering.

--
-------------------------------
David Durand
david@xxxxxxxxxxxxxxxxxxx
VP Software Architecture
Dynamic Diagrams / Ingenta plc
http://www.dynamicDiagrams.com/ http://www.ingenta.com/