[Date Prev][Date Next][Thread Prev][Thread Next][Author Index][Date Index][Thread Index]
[zzdev] Re: [zzdev] Persistent data structures
- To: zzdev@xxxxxxxxxx
- Subject: [zzdev] Re: [zzdev] Persistent data structures
- From: "David G. Durand" <david@xxxxxxxxxxxxxxxxxxx>
- Date: Fri, 2 Mar 2001 16:51:20 -0500
- In-reply-to: <20010302142048.A6738@xxxxxxxxxxx>
- References: <20010302103638.C17162@xxxxxxxxxxxxxx> <20010302142048.A6738@xxxxxxxxxxx>
At 2:20 PM +0200 3/2/01, Antti-Juhani Kaijanaho wrote:
On 20010302T103638+0200, Tuomas Lukka wrote:
Driscoll, Sarnak, Sleator and Tarjan
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
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
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
VP Software Architecture
Dynamic Diagrams / Ingenta plc