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

*To*: udanax@xxxxxxxxxx*Subject*: splaying, apps for & incr-izing w/enfs, Delaunay*From*: Steve Witham <sw@xxxxxxxx>*Date*: Fri, 1 Feb 2002 13:51:20 -0500

Title:

An early-January 2002 exchange between Steve Witham & Roger
Gregory:

Steve (abbreviating):

a basic tutorial on enfilades:http://www.sunless-sea.net/wiki/EnfiladeTheory

some bold surmises about Ents:http://www.sunless-sea.net/wiki/Definitions/ent

Roger (quoted w/permission):

This is a very good explanation.

Several points;

There is an algorithm published in DrDobbs that is equivalent to Model T, does anyone have a reference,

it was many years ago and I've lost it.

The algorithm in Dr. Dobb's was about "K-trees,"

I think there's a ref somewhere on sunless-sea.net already.
-sw

Roger continued:

The inclusion of self balancing trees in gold was a mistake or at best a temporary hack, as they screw up

when confronted with the disk/memory division. They will have to be replaced with something that

doesn't require disk writes for every read operation, the code structuring should make this

an easy enough task and lots better than any hack that tries to preserve the splay tree stuff (I can prove this I think)

And most importantly, lets start a discussion on the problems that might benefit form ent&enf theory.

Solving the theory is 1000 times easier than programming and selling a solution.

So steve can you explain your intuition? I'll look up "Delaunay triangulation" but I've got to run now.

any other suspected problems that might yield to this are welcome. This could be most rewarding and educational.

Steve:

At 8:20 AM -0800 1/11/02, roger gregory wrote:

The inclusion of self balancing trees in gold was a mistake or at best a temporary hack,

My page on the Ent implies that they're unbalanced, I forgot about the

splaying. [Thanks, John, for reading & adding the comment.]

And most importantly, lets start a discussion on the problems that might benefit form ent&enf theory.Solving the theory is 1000 times easier than programming and selling a solution.

I'm lazy & at this point only wanted to make sure the basic intro stuff

was on that site so that smart browsers might get interested (& have some

help understanding more of what's there).

So steve can you explain your intuition? I'll look up "Delaunay triangulation" but I've got to run now.

I guess you mean my saying that algorithms can be incrementalized with enfilades? [Editing myself a bit: I think it's a lot like arranging

an algorithm to run on parallel processors.]

Breaking up the problem & assigning work corresponds to going

down the tree; finishing, summarizing and reporting back corresponds

to widding; and the *change* in the computation that would

happen if some of the inputs were changed corresponds to an edit operation

on the enfilade. Rebalancing corresponds to pretending that the work

was split more fairly--or presciently!

The Delaunay triangulation and the Voronoi diagram--I still don't remember

which is which--are "duals" of each other. They both relate to finding

the point in a set of points that is closest to a given location. One

draws line segments between nearest-neighbor points, the other draws

borders between the neighborhoods around the points. By the way,

I'm told this is one of a million cool pluggins available (for a

charge) from Oracle for their database. This is "interesting" (in the

curse sense maybe) because the point is to divide a space into *non*-

overlapping areas.

I roughly designed a word-wrap and pagination enfilade in the mid-1980s.

The wids are lookup tables, and the widding operation is

function composition on the tables (basically the [ operator in APL!).

I wrote an in-memory enfilade that wids counts of instances of each ascii

character, & used it in in a compression algorithm, this year.

I followed up with a reference to a paper by Omohundro on
both

k-d trees and the Delaunay triangulation; it's on the page:

http://www.sunless-sea.net/wiki/KDTrees

--Steve

--

Hidden file extensions for the Mac?
C:\Ngrtltns.App.Le

see http://siracusa.home.mindspring.com/john/articles/metadata.html

see http://siracusa.home.mindspring.com/john/articles/metadata.html

- Prev by Date:
**Re: Regulations re Potential Xanadu microTransaction Currencies** - Next by Date:
**Abora hypertext system** - Previous by thread:
**Re: Regulations re Potential Xanadu microTransaction Currencies** - Next by thread:
**Abora hypertext system** - Index(es):