[Date Prev][Date Next][Thread Prev][Thread Next][Author Index][Date Index][Thread Index]

[zzdev] Re: [zzdev] Persistent data structures

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).

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
VP Software Architecture
Dynamic Diagrams / Ingenta plc
http://www.dynamicDiagrams.com/ http://www.ingenta.com/