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

splaying, apps for & incr-izing w/enfs, Delaunay

Title: splaying, apps for & incr-izing w/enfs, Delaunay
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