udanax-some_progress_on_the_road_to_xanadu

This is part of The Pile, a partial archive of some open source mailing lists and newsgroups.



To: tompoe@renonevada.net
From: Jeff Rush <jrush@taupro.com>
Subject: Re: Greetings
Date: Tue, 08 Jan 2002 17:25:44 -0600

Yes, you're on the right list, but there is little traffic.  You
can find an archive of the messages at:

    http://www.xanadu.com.au/mail/udanax/

though it does not appear to have had any postings since October 2000.

I run the www.sunless-sea.net website, which also has little new
discussion, but I have worked (and still am) to put up old message
archives from the original development of Xanadu, to try to
stimulate ideas.  I have some limited contact with the original
developers who feed me source and documentation as their time
permits, which I then cleanup and put on my site.

Admittedly there is no shiny new Xanadu software at sunless but
I think you will find it at least some solid technical reading.

-Jeff Rush



tom poe wrote:
> 
> Hello:  Am I on the right list for general discussion of Xanadu?
> 
> If so, is there an archive of recent messages?  Thanks, Tom
===

To: udanax@udanax.com
From: Andrew Pam <xanni@glasswings.com.au>
Subject: Re: Greetings
Date: Wed, 9 Jan 2002 12:22:29 +1100

On Tue, Jan 08, 2002 at 01:11:57PM -0800, tom poe wrote:
> Hello:  Am I on the right list for general discussion of Xanadu?

Not quite - this list is for the discussion of the 1980s-1990s Xanadu
software originally developed at Autodesk and now released under
an open source license under the name "Udanax".  General discussion
of Xanadu occurs on the xanadu@xanadu.net mailing list and news and
announcements are on the xanews@xanadu.net mailing list.  To subscribe
to these lists, send any email to xanadu-subscribe@xanadu.net and
xanews-subscribe@xanadu.net respectively.

> If so, is there an archive of recent messages?  Thanks, Tom

There are searchable archives of all the Xanadu related mailing lists at:
http://www.xanadu.com.au/mail/

Hope that helps,
		Andrew Pam
===

To: udanax@udanax.com, xanadu@xanadu.net
From: Andrew Pam <xanni@glasswings.com.au>
Subject: Re: Introduction
Date: Wed, 9 Jan 2002 13:30:31 +1100

This message has been moved to the Xanadu mailing list, xanadu@xanadu.net.
Please reply on that list rather than on the Udanax mailing list.
Apologies to those who are on both lists and got two copies.

On Tue, Jan 08, 2002 at 05:35:57PM -0800, tom poe wrote:
> Hello:  I am interested in the work surrounding hypertext.  I would very much 
> like to get a status report on where this topic sits at this time.
> 
> I came across this, earlier, from the government RFP solicitation site:
> http://www.eps.gov/spg/NASA/ARC/OPDC20220/NASA-SNOTE-020108-001/Synopsis.html
> 
> "A special briefing to introduce you to NASA's newest patent-pending data 
> mining technology is being held at NASA Ames Research Center. The briefing is 
> an opportunity for your firm to license PERILOG, and leverage its powerful 
> capabilities for your software solutions products. Product Profile: PERILOG 
> unearths data that is contextually relevant to the subject being 
> investigated. The software measures the degree of contextual association for 
> large numbers of terms pairs in text (or any other sequence) to produce 
> models that capture the structure of the text. PERILOG statistically compares 
> these models to measure their degree of similarity to a query model, develops 
> a ranking, and presents the search results to the user. Furthermore, the user 
> has access to powerful query tools that, for example, generate search options 
> automatically. The licensing event will be held at the NASA Ames Research 
> Center, Moffett Field, California, on Tuesday, January 29, 2002, from 10 a.m. 
> to noon and will include a light lunch. Please register on-line at 
> http://ettc.usc.edu/ames/perilog/homepage.html For additional information, 
> please contact Patrick Hung at 650-604-5063.Email your questions to Patrick 
> Hung at phung@mail.arc.nasa.gov"
> 
> Is there any relationship between "Data Mining", the business method, and 
> "Hypertext", the concept?

Only in that they are both methods of information retrieval.  Data mining
involves searching for connections after the fact, whereas hypertext
involves recording, preserving, manipulating and accessing connections
explicitly rather than trying to discern them from a body of data without
explicit connections.

> The reason I ask, is that I was thinking, today [really hurts when
> I do that], and Xanadu seems like the perfect workaround for XLink,
> a process that has never been realized to this date.

Ted was consulted by the XLink working group during the development
of that standard, so it is no accident that XLink does provide some
support for some of the Xanadu concepts.  Not being directly involved
in those working groups myself I can't speak to the reasons for the slow
deployment of XLink in actual released software.

> Further, my disappointment with the unbelievably crude efforts at
> representing global standards to the Public, has me looking for some
> approach to web communications that will not be hobbled by corporate
> standards such as the W3C.org folks are promoting.

While I do have some doubts as to the ultimate relevance of the W3C
standards and there have been some concerns over patents on processes
used in W3C standards, I believe that the members of the W3C and its
working groups are by and large sincerely well-intentioned and doing
plenty of good work.  However there is no requirement to propose a W3C
standard before launching a new idea on the Internet - that's one of
the great things about the net.  While Project Xanadu is happy to work
with standards groups wherever relevant and feasible, we are also doing
plenty of development outside standards groups.

===

To: tom poe <tompoe@renonevada.net>
From: Andrew Pam <xanni@glasswings.com.au>
Subject: Re: Greetings
Date: Wed, 9 Jan 2002 15:04:14 +1100

On Tue, Jan 08, 2002 at 06:28:22PM -0800, tom poe wrote:
> Hello:  I'm copying Andrew directly, as he represents another mail list.

Thanks, but that isn't necessary since I am also on the Udanax mailing
list.  I do not "represent another mail list".  Rather I am the system
administrator for the Xanadu and Udanax domains, websites and mailing
lists and the server on which they run, as well as having been involved
with the Xanadu project since the 1980s.

> Well, I went to the site, skimmed through the material, and the impression I 
> have, is that there is some work going on to reposition as a publishing 
> house, "if-you-will".

Certainly not.  Xanadu is intended to permit people to publish information
on a global network (generally the Internet at this point), and while
no doubt Project Xanadu itself will continue to be a publisher both in
print and online it has never been the intention to run a centralised
organisation.  The original idea in the 1960s and 1970s was to have
franchised Xanadu outlets rather like Cybercafes in conjunction with an
online service in the vein of Compuserve, but since the early 1990s the
focus has changed to developing and designing software and concepts.

> On a grander scale, an Internet3 [Internet2 has already been fleshed
> out by the government and big business folks, along with universities]
> seems like an appropriate term.  This Internet3 would enable all those
> who want to write, publish, and receive royalties on the web, to have
> a nice arrangement.  Sort of butts up against other would-be publishing
> houses like Acrobat, e-book types.  What's truly appealing, is the part
> about transclusion, and at that level looks real good to me, IMHO.

Now you're on the right track.  Xanadu services will no doubt be provided
as overlays on other underlying services and protocols.

> So, the troubling part is, there does not seem to be any consideration given 
> to my friend in Africa, who lives in a village, without any money, but wants 
> to access the world.  Can't do it.  Even when we get s/he a computer, s/he is 
> dead in the water.  Why?

Lack of access to the Internet?  You tell me.

> Nope.  Xanadu is just one more scam on those who wish to perpetuate 
> illiteracy at the expense of those less fortunate.

What on earth are you talking about.  Xanadu in no way excludes third
world nations or users.  Are you suggesting that we should devote our
time to specifically assisting those in poorer nations?  While it is
certainly appropriate to consider how our designs can be used by all of
humanity, we are not a humanitarian aid organisation and it is ridiculous
to suggest that we should take on their work.

> Well, let's fix that little glitch.  This stuff is open source?
> Does anyone know what the situation is with udanax?  Is it software
> that can be placed on a server and client that tracks the documents?

The Udanax code is open source, yes.  If you want to work on it and
deploy it in third world countries I'm sure we would all be delighted.

> Anyone point me to the manual?

http://www.udanax.com/
http://www.sunless-sea.net/XanaduInfoArch

Hope that helps,
		Andrew

===

To: tom poe <tompoe@renonevada.net>
From: Andrew Pam <xanni@glasswings.com.au>
Subject: Re: Greetings
Date: Thu, 10 Jan 2002 00:27:26 +1100

On Tue, Jan 08, 2002 at 09:29:05PM -0800, tom poe wrote:
> Nope, It's the MONEY!  You're adding to the cost of accessing information.  
> The problem of gaining access to the Internet is one thing, but then if the 
> user is paying royalties to information providers, then the cost goes up.  
> Big problem for an awful lot of Third world residents.

You appear to be making two (admittedly common) assumptions that I do
not believe are justified:

Firstly, many people focus immediately upon the Xanadu royalty facilities
when the vast majority of content seems likely to be made available
free of charge (zero royalty rate), especially initially where people
have a strong history and expectation of free content on the Internet.

The purpose of having a royalty system is because there is a significant
amount of content of a distinctly different type that is presently not
readily available online (or at least not legally):  Valuable content
created by people whose primary source of income is content creation
and who cannot afford to feed, clothe and house themselves if they give
their creative efforts away for free.  Most of the existing content on the
Internet is created by people who can afford to give it away at no cost
since they derive their income from other sources.

I am not suggesting that one type of content is inherently more valuable
than the other, only pointing out that the purpose of having a royalty
system is to enable both kinds of content to be made available where
presently this does not occur.  Thus people in third world countries may
gain access to more content than they do presently, since the online
royalties would hopefully be relatively low compared to current costs
of content on physical media (and also since the Xanadu system permits
paying for only the parts you actually want, rather than being forced
to pay for a larger aggregation).

Secondly, you assume that people with less money do not have valuable
content of their own to offer.  While the large corporations that have
evolved in our current society are benefited by a producer-consumer
structure, especially publishing companies who gain economies of scale by
promoting small numbers of high profit "bestsellers" rather than a larger
(and more diverse) number of products, it is not at all clear that the
same factors hold true on the Internet where peer-to-peer relationships
are far more effective than ever before.  Surely people in Africa have
stories of their own to tell that might be of financial value just as
much as in any other country.

> Andrew.  I am suggesting that you/we should devote our time to specifically 
> assisting those in poorer nations.  For example, how difficult would it be 
> for you to edit your home page with a short little statement to the effect 
> that Xanadu project -project encourages all publishers to participate in its 
> global responsibility to make as much information as possible to third world 
> nations through - - - whatever.  As I understand it, publishers and users are 
> identified on the system in some way.  At whatever level the gateway is 
> established, is probably a good point to structure affordable information for 
> the population within that segment.  Such an approach envisions Public 
> libraries use on the Internet.  Those in need, can be subjected to second 
> class status through their own population segment.  May be a little clunky, 
> but a real sales obstacle is taken care of by such banter.  

Again I think you are under a misconception.  The Xanadu system is
not intended primarily for conventional publishers at all - they will
probably be the last to accept a system that is so radically different
from their current model.  Project Xanadu encourages everyone to become
a publisher online, in poorer nations and neighbourhoods just as much as
anywhere else.  "Publishers" and "users" are roles that all individuals
using the system take on per transaction, and few users of the system
are likely to have nothing to publish - especially as the system is also
designed to be useful for distributed storage of private information.

I don't understand what you mean by a "gateway" at all.  It is certainly
not our place to advocate what price people may choose to put on the
fruits of their labour, nor to encourage discriminatory pricing!

> The only other thing that comes to mind, at this point, is the possibility of 
> coming at this from the other end.  If a Public Internet library is 
> established, and arranges for funding to pay all royalties, and in turn, acts 
> as the screening agent for those who would apply for assistance, then Xanadu 
> keeps right on truckin' and everyone's happy, and no need to change the 
> system as designed by you folks.  And, quite an impressive feat so, far, IMHO.

There is certainly nothing preventing an organisation from paying the
fees for access to content for others.  Indeed in Australia libraries
do pay royalties to authors in proportion to the number of times the
work is lent and are funded primarily by local ratepayers through their
municipal rates (taxes).  If you propose to set up public access Xanadu
terminals I would certainly applaud your initiative.

Regards,
	Andrew Pam
===

To: udanax@udanax.com
From: Billy Tanksley <btanksley@hifn.com>
Subject: RE: Greetings
Date: Wed, 9 Jan 2002 12:23:33 -0800 

From: Andrew Pam [mailto:xanni@glasswings.com.au]
>The purpose of having a royalty system is because there is a 
>significant
>amount of content of a distinctly different type that is presently not
>readily available online (or at least not legally):  Valuable content
>created by people whose primary source of income is content creation
>and who cannot afford to feed, clothe and house themselves if they give
>their creative efforts away for free.  Most of the existing 
>content on the
>Internet is created by people who can afford to give it away at no cost
>since they derive their income from other sources.

This is a little off-topic, but have you guys checked out the 'royalty'
system in Mojonation (http://www.mojonation.net)?  Essentially, they created
a system whereby you pay using an invented currency, called 'mojo'.  Mojo
can be produced by anyone, but it has value according to what it can be used
for; Mojonation itself produces one currency, which is of use to pay for
their services, while a bandwidth provider could produce another to provide
for its services.  Like real currency, exchange rates would form, some mojo
would be universally acceptable (and thus act as money) while others would
trade at a discount.  You can pay for content, storage, transport,
processing time, almost anything the network can offer.

>	Andrew Pam

===
To: udanax@udanax.com
From: Henry at ProZ <henry@proz.com>
Subject: RE: Greetings
Date: Wed, 09 Jan 2002 12:43:23 -0800

ProZ.com uses a point system called browniz, which 
translators can earn, by doing things for the community (like 
uploading glossaries), and can use, to access community 
services (like online glossaries).

Among other things, these new currencies will allow us, 
perhaps for the first time, to quantify the relationship between 
brownie points and mojo.

===

To: udanax@udanax.com, xanadu@xanadu.net
From: Andrew Pam <xanni@glasswings.com.au>
Subject: Re: Greetings
Date: Thu, 10 Jan 2002 22:13:54 +1100

This topic has been moved to the Xanadu mailing list, xanadu@xanadu.net.      
Please reply on that list rather than on the Udanax mailing list.               
Apologies to those who are on both lists and got two copies.

On 1/9/02 12:23:33 PM, Billy Tanksley <btanksley@hifn.com> wrote:
> This is a little off-topic, but have you guys checked out the 'royalty'
> system in Mojonation (http://www.mojonation.net)?  Essentially, they
> created a system whereby you pay using an invented currency, called
> 'mojo'.  Mojo can be produced by anyone, but it has value according
> to what it can be used for; Mojonation itself produces one currency,
> which is of use to pay for their services, while a bandwidth provider
> could produce another to provide for its services.  Like real currency,
> exchange rates would form, some mojo would be universally acceptable
> (and thus act as money) while others would trade at a discount.  You can
> pay for content, storage, transport, processing time, almost anything
> the network can offer.

On Wed, Jan 09, 2002 at 12:43:23PM -0800, Henry at ProZ wrote:
> ProZ.com uses a point system called browniz, which 
> translators can earn, by doing things for the community (like 
> uploading glossaries), and can use, to access community 
> services (like online glossaries).
> 
> Among other things, these new currencies will allow us, 
> perhaps for the first time, to quantify the relationship between 
> brownie points and mojo.

Hee!  I am indeed aware of MojoNation, but thank you for drawing my
attention to ProZ.com.  I recently discovered another very promising
distributed network with a credit system, GNet:

http://gecko.cs.purdue.edu/gnet/

Share and enjoy,
		Andrew
===

To: udanax@udanax.com
From: Andrew Pam <xanni@glasswings.com.au>
Subject: [sw@tiac.net: Sunless-Sea page on EnfiladeTheory]
Date: Sat, 12 Jan 2002 12:23:59 +1100

----- Forwarded message from sw@tiac.net -----

Date: Thu, 10 Jan 2002 20:07:56 -0800
From: sw@tiac.net
Subject: Sunless-Sea page on EnfiladeTheory

Ted, Mark, Roger, Andrew--

Sunnless-sea.net seemed to lack a basic tutorial on enfilades,
so I added one:

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

Mark, I made some bold surmises about Ents on this page:

    http://www.sunless-sea.net/wiki/Definitions/ent

Comment to me on either one or just edit the page there (click "revise"
near the top of the left margin), it's a Wiki.

Praise appreciated too :-)

  --Steve
P.S. Andrew sent out an ad for the sunless-sea.net site on Jan. 8;
look at the daily usage stats for January:

http://www.timecastle.net/stats/sunless-sea.net/usage_200201.html#DAYSTATS

===

To: udanax@udanax.com
From: Andrew Pam <xanni@glasswings.com.au>
Subject: Re: Sunless-Sea page on EnfiladeTheory
Date: Sat, 12 Jan 2002 12:26:55 +1100

--- Forwarded message ---

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

   Great Work!


   sw@tiac.net wrote:

     Ted, Mark, Roger, Andrew--

     Sunnless-sea.net seemed to lack a basic tutorial on enfilades,
     so I added one:

         [1]http://www.sunless-sea.net/wiki/EnfiladeTheory

     Mark, I made some bold surmises about Ents on this page:

         [2]http://www.sunless-sea.net/wiki/Definitions/ent

     Comment to me on either one or just edit the page there (click
     "revise" near the top of the left margin), it's a Wiki.  Delaunay
     triangulation Praise appreciated too :-)

       --Steve
     P.S. Andrew sent out an ad for the sunless-sea.net site on Jan. 8;
     look at the daily usage stats for January:

     [3]http://www.timecastle.net/stats/sunless-sea.net/usage_200201.htm
     l#DAYSTATS

     -- -- Your presence is required.

--
 Roger Gregory 75 Melba San Francisco ca 94132 415 664-6850 home
 roger@xanadu.net

[4]http://www.udanax.com
the software but not the name!
the name but not the software!
[5]http://www.xanadu.com

References

   1. http://www.sunless-sea.net/wiki/EnfiladeTheory
   2. http://www.sunless-sea.net/wiki/Definitions/ent
   3. http://www.timecastle.net/stats/sunless-sea.net/usage_200201.html#DAYSTATS
   4. http://www.udanax.com/
   5. http://www.xanadu.com/

===

To: udanax@udanax.com
From: Andrew Pam <xanni@glasswings.com.au>
Subject: [sw@tiac.net: Re: Sunless-Sea page on
Date: Sat, 12 Jan 2002 12:27:19 +1100

----- Forwarded message from sw@tiac.net -----

In-Reply-To: <3C3F10D7.6205CBFA@best.com>
Date: Fri, 11 Jan 2002 13:07:08 -0800
From: sw@tiac.net
Subject: Re: Sunless-Sea page on EnfiladeTheory

Jeff, if you're there,

Wouldn't it be better if we could carry out (or at least log) this
discussion on the site's message board?

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?  Trying to think of an explanation, I realized that this can
bootstrap off the notion of parallelizing: the way you would split a
computation to parallelize it would work to split it into a tree.
I.e. 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 the word-wrap and pagination enfilade in the mid-1980s.
The wids are lookup tables, and the widding operation is
function composition on the tables.

I wrote an in-memory enfilade that wids counts of instances of each ascii
character, & used it in in a compression algorithm, this year.


  --Steve
===

To: udanax@udanax.com
From: Andrew Pam <xanni@glasswings.com.au>
Subject: Re: Sunless-Sea page on EnfiladeTheory
Date: Sat, 12 Jan 2002 12:36:18 +1100

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

http://www.xanadu.com.au/mail/xanadu/msg00004.html

===

To: udanax@udanax.com
From: Andrew Pam <xanni@glasswings.com.au>
Subject: Re: Sunless-Sea page on EnfiladeTheory
Date: Sat, 12 Jan 2002 12:53:59 +1100

On Sat, Jan 12, 2002 at 12:36:18PM +1100, Andrew Pam wrote:
> >    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.
> 
> http://www.xanadu.com.au/mail/xanadu/msg00004.html

Pulling out my copy of that issue, the full details are:

"K-Tree Container Data Structures" by Rodney Bates, pp. 26-34 of
Dr. Dobbs September 1994 "Data Structures and File Formats" issue.

Rodney Bates is an engineer with Boeing aircraft.
A recent email address appears to be rod.bates@wichita.boeing.com.

See also:

http://www.sunless-sea.net/wiki/the%20fabled%20Ent
http://xanadu.com.au/archive/bibliography.html
http://www.google.com/search?q=cache:E2zEjRTwgC0C:armoire.cs.nwu.edu/Reading/Doctor%2520Dobbs%2520-%2520Release%252010/articles/1994/9409/9409b/9409b.htm

===

To: udanax@udanax.com
From: Andrew Pam <xanni@glasswings.com.au>
Subject: Sunless-sea covered in The Register!
Date: Sat, 12 Jan 2002 15:39:58 +1100

http://www.theregister.co.uk/content/4/23586.html

===

To: andrew.orlowski@theregister.co.uk
From: Andrew Pam <xanni@glasswings.com.au>
Subject: Error in Xanadu/Udanax article
Date: Sat, 12 Jan 2002 15:45:04 +1100

While your article "Xanadu project lifts open source kimono" is on the
whole excellent, it is incorrect to claim as you do in the very first
sentence that "yesterday the project's curators made the web site public."
The official Udanax website containing the source code was made public at
http://www.udanax.com/ in 1999 at the time of the open source release.
The http://www.sunless-sea.net/ website is a separate project, the
"Xanadu Cyberarchaeology Project", though of course many of the usual
suspects are involved.  :)

A correction would be appreciated.

===

To: udanax@udanax.com
From: John Dougan <jdougan@acm.org>
Subject: [Fwd: SEP94: K-Tree Container Data Structures]
Date: Fri, 11 Jan 2002 23:52:16 -0800

This is a multi-part message in MIME format.

--Boundary_(ID_jvndEZDHaY5K96N7hiJdFQ)
Content-type: text/plain; charset=us-ascii; format=flowed
Content-transfer-encoding: 7BIT

I love Google's cacheing...the original page is now password protected. 
Can anybody figure out how to tickle Google to get the illustration pages?

--john dougan



--Boundary_(ID_jvndEZDHaY5K96N7hiJdFQ)
Content-type: message/rfc822; name="SEP94: K-Tree Container Data Structures.eml"

Return-path: <jdougan@bigserver.com>
Received: from [204.174.46.76] (account jdougan HELO bigserver.com)
  by bigserver.com (CommuniGate Pro SMTP 3.4.8)  with ESMTP id 829276; Mon,
 07 Jan 2002 23:48:10 -0800
Date: Mon, 07 Jan 2002 23:48:10 -0800
From: John Dougan <jdougan@bigserver.com>
Subject: SEP94: K-Tree Container Data Structures
To: John Dougan <jdougan@acm.org>
Message-id: <3C3AA43A.3030509@bigserver.com>
MIME-version: 1.0
Content-type: multipart/mixed; boundary="Boundary_(ID_PnRt1TIRDcXe3yebQzX/CQ)"
X-Accept-Language: en-gb, en-us, fr-ca
User-Agent: Mozilla/5.0 (Windows; U; WinNT4.0; en-US; rv:0.9.7) Gecko/20011221

This is a multi-part message in MIME format.

--Boundary_(ID_PnRt1TIRDcXe3yebQzX/CQ)
Content-type: multipart/alternative;
 boundary="Boundary_(ID_YvrOrDbGqSgaTXRt8UDcYg)"


--Boundary_(ID_YvrOrDbGqSgaTXRt8UDcYg)
Content-type: text/plain; charset=us-ascii; format=flowed
Content-transfer-encoding: 7BIT


http://www.google.com/search?q=cache:E2zEjRTwgC0C:armoire.cs.nwu.edu/Reading/Doctor%20Dobbs%20-%20Release%2010/articles/1994/9409/9409b/9409b.htm+k-tree+dobbs&hl=en 
<http://www.google.com/search?q=cache:E2zEjRTwgC0C:armoire.cs.nwu.edu/Reading/Doctor%2520Dobbs%2520-%2520Release%252010/articles/1994/9409/9409b/9409b.htm+k-tree+dobbs&hl=en>

-- 
John Dougan
jdougan@bigserver.com



--Boundary_(ID_YvrOrDbGqSgaTXRt8UDcYg)
Content-type: text/html; charset=us-ascii
Content-transfer-encoding: 7BIT

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
  <title></title>
</head>
<body>
<br>
<a href="http://www.google.com/search?q=cache:E2zEjRTwgC0C:armoire.cs.nwu.edu/Reading/Doctor%2520Dobbs%2520-%2520Release%252010/articles/1994/9409/9409b/9409b.htm+k-tree+dobbs&amp;hl=en">
http://www.google.com/search?q=cache:E2zEjRTwgC0C:armoire.cs.nwu.edu/Reading/Doctor%20Dobbs%20-%20Release%2010/articles/1994/9409/9409b/9409b.htm+k-tree+dobbs&amp;hl=en</a><br>
<br>
<pre class="moz-signature" cols="$mailwrapcol">-- <br>John Dougan<br><a class="moz-txt-link-abbreviated" href="mailto:jdougan@bigserver.com">jdougan@bigserver.com</a></pre>
<br>
</body>
</html>

--Boundary_(ID_YvrOrDbGqSgaTXRt8UDcYg)--

--Boundary_(ID_PnRt1TIRDcXe3yebQzX/CQ)
Content-type: text/html;
 name=":E2zEjRTwgC0C:armoire.cs.nwu.edu/Reading/Doctor%20Dobbs%20-%20Release%2010/articles/1994/9409/9409b/9409b.htm+k-tree+do"
Content-transfer-encoding: 7BIT
Content-disposition: inline;
 filename=":E2zEjRTwgC0C:armoire.cs.nwu.edu/Reading/Doctor%20Dobbs%20-%20Release%2010/articles/1994/9409/9409b/9409b.htm+k-tre"
Content-Base: 
 "http://www.google.com/search?q=cache:E	2zEjRTwgC0C:armoire.cs.nwu.edu/Read
	ing/Doctor%2520Dobbs%2520-%2520Rele	ase%252010/articles/1994/9409/9409b
	/9409b.htm+k-tree+dobbs&hl=en"
Content-Location: 
 "http://www.google.com/search?q=cache:E	2zEjRTwgC0C:armoire.cs.nwu.edu/Read
	ing/Doctor%2520Dobbs%2520-%2520Rele	ase%252010/articles/1994/9409/9409b
	/9409b.htm+k-tree+dobbs&hl=en"

<BASE HREF="http://armoire.cs.nwu.edu/Reading/Doctor%20Dobbs%20-%20Release%2010/articles/1994/9409/9409b/9409b.htm"><table border=1 width=100%><tr><td><table border=1 bgcolor=#ffffff cellpadding=10 cellspacing=0 width=100% color=#ffffff><tr><td><font face=arial,sans-serif color=black size=-1>This is <b><font color=#0039b6>G</font> <font color=#c41200>o</font> <font color=#f3c518>o</font> <font color=#0039b6>g</font> <font color=#30a72f>l</font> <font color=#c41200>e</font></b>'s <a href="http://www.google.com/help/features.html#cached"><font color=blue>cache</font></a> of <A HREF="http://armoire.cs.nwu.edu/Reading/Doctor%20Dobbs%20-%20Release%2010/articles/1994/9409/9409b/9409b.htm"><font color=blue>http://armoire.cs.nwu.edu/Reading/Doctor%20Dobbs%20-%20Release%2010/articles/1994/9409/9409b/9409b.htm</font></a>.<br>
<b><font color=#0039b6>G</font> <font color=#c41200>o</font> <font color=#f3c518>o</font> <font color=#0039b6>g</font> <font color=#30a72f>l</font> <font color=#c41200>e</font></b>'s cache is the snapshot that we took of the page as we crawled the web.<br>
The page may have changed since that time.  Click here for the <A HREF="http://armoire.cs.nwu.edu/Reading/Doctor%20Dobbs%20-%20Release%2010/articles/1994/9409/9409b/9409b.htm"><font color=blue>current page</font></a> without highlighting.</font><br><br><center><font size=-2><i>Google is not affiliated with the authors of this page nor responsible for its content.</i></font></center></td></tr>
<tr><td>
<table border=0 cellpadding=0 cellspacing=0><tr><td><font face=arial,sans-serif color=black size=-1>These search terms have been highlighted:&nbsp;</font></td><td bgcolor=#ffff66><B><font face=arial,sans-serif color=black size=-1>k&nbsp;</font></B></td><td bgcolor=#A0FFFF><B><font face=arial,sans-serif color=black size=-1>tree&nbsp;</font></B></td></tr></table>
<font face=arial,sans-serif color=black size=-1>These terms only appear in links pointing to this page: <B>dobbs </B></font>
</td></tr></table></td></tr></table>
<hr>
<HTML>
<META NAME="year" CONTENT="1994">
<HEAD>
<TITLE>SEP94: K-Tree Container Data Structures</TITLE></HEAD>
<BODY BGCOLOR="#ffffff">
<h1><B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">Tree</B> Container Data Structures<a name="00c6_0046"></h1><P>
<h2><a name="00c6_0044"><a name="00c6_0000">Fast subscripting, slicing, and concatenation of sequences</h2><P>
<h3>Rodney Bates</h3><P>
<p><i><a name="00c6_0045"><a name="00c6_0000">Rod is an engineer with Boeing aircraft and can be contacted at bates@salsv3.boeing.com.</i></p><hr><P>
In dealing with the problem of browsing and debugging incomplete programs, I needed to efficiently handle <B style="color:black;background-color:#A0FFFF">tree</B> nodes with variable (possibly large) numbers of children. To address this problem, I developed a data structure called a &quot;<B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B>,&quot; which also has general applicability.<P>
<B style="color:black;background-color:#ffff66">K</B>-trees are container data structures that represent linear sequences of integers, pointers, and the like. There are countless ways of representing a sequence, but almost all are variations on arrays or linked lists.<P>
Arrays are very fast when you have a subscript, say, <I>I</I>, and want to find the <I>I</I>th element of the sequence. The time required by the address computation does not increase as the sequence gets longer. This is called a &quot;constant-time&quot; operation. On the other hand, if you want to concatenate two sequences or extract a subsequence (a slice), part of some array must be copied. The time this requires increases in direct proportion to the length of the sequences. This is a &quot;linear-time&quot; operation.<P>
The many variants of linked-list representations tend to be just the opposite. You can cut apart pieces of a linked list and splice them together in constant time. But finding the <I>I</I>th element requires traversing from one end of the list, which is linear.<P>
Now, suppose you need to do a mixture of constant-time operations and linear operations. As the problem gets bigger, linear operations will account for almost all the time the program takes to run, while the overall effect of constant-time operations is negligible. In an application where both kinds of operations are needed, performance is indicated by the most inefficient operation--linear, in this case.  <P>
With <B style="color:black;background-color:#ffff66">K</B>-trees, subscripting, slicing, and concatenation all take time proportional to the logarithm of the length of the sequence. This is not as good as constant time, but it's much better than linear time. Since no operation is worse than logarithmic time, the logarithmic performance dominates.<P>
<B style="color:black;background-color:#ffff66">K</B>-trees have one other important characteristic that I needed in my application. When you extract a slice, the original sequence from which it was taken is preserved. The same goes for concatenation and subscripted assignment. Most of the array and linked representations have some operation which destroys operands, unless you first make a copy, which is, of course, linear.<P>
To make this preservation of operands happen, <B style="color:black;background-color:#ffff66">K</B>-trees use heap objects that are immutable--once created, they never change. These objects can be shared among several sequences, and this is vital to making the operations logarithmic. On the downside, some kind of garbage collection is needed to reclaim objects no longer used in any sequence.<P>
<h3><a name="00c6_0047">The <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B> Data Structure<a name="00c6_0047"></h3><P>
A <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B> is a pointer to one of two kinds of nodes, both of which contain an integer field named <I>Height</I>. If <I>Height=1</I>, the node is a leaf node and contains a field named <I>LeafElems</I> (a small array of sequence elements). If <I>Height&gt;1</I>, the node is a nonleaf node and contains a field named <I>NonleafElems</I> (a small array of records). Each record contains two fields named <I>CumChildCt</I> and <I>ChildRef</I>. <I>CumChildCt</I> has the type of sequence subscripts. <I>ChildRef</I> is a <B style="color:black;background-color:#ffff66">K</B>-subtree pointer.<P>
Every node has a field named <I>ElemCt</I> which gives the number of elements. The elements of both leaf and nonleaf nodes have subscripts in the range 0..<I>ElemCt</I>--1. Each node is dynamically allocated when created, with exactly enough space to hold <I>ElemCt</I> elements.<P>
<a href="199400c8.htm">Figure 1</A> shows a graphical notation for both kinds of nodes. The fields and array subscripts are labeled, showing how to interpret the nodes in the examples that follow.<P>
There is a global maximum, N, for the number of array elements in any node of either kind. N must be at least 3. A leaf node with one element occurs only in the representation of a singleton sequence. Every other node always has at least two elements. <a href="199400c9.htm">Figure 2</A> shows some examples of small <B style="color:black;background-color:#ffff66">K</B>-trees and the sequences they represent. The elements of sequences are integers. <a href="199400ca.htm">Figures 2(b) and 2(c)</A> are two different <B style="color:black;background-color:#ffff66">K</B>-trees which represent the same sequence. In general, there are many <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B> representations for a given sequence. A given <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B> represents only one sequence, according to the following rules:<P>
<UL>
<li>A NIL pointer represents the empty sequence. A pointer to a leaf node represents just the elements of <I>LeafElems</I>. A pointer to a nonleaf node represents the concatenation of the sequences represented by the <I>ChildRef</I> fields.</li>
<li>The value of <I>CumChildCt</I> in the <I>J</I>th element of a nonleaf node is the sum of the lengths of the subsequences represented by the <I>ChildRef</I> fields of <I>NonleafElems[0..J]</I>. This means that <I>NonleafElems[ElemCt  --1].CumChildCt</I> is the length of the sequence represented by this node.</li>
<li>From a given node, all paths to leaves have the same length. This value is stored in the <I>Height</I> field. <B style="color:black;background-color:#ffff66">K</B>-trees are always full in the sense that, although <I>ElemCt</I> may vary, there are no NIL pointers in <I>ChildRef</I> fields.</li>
<li>No node contains any information derived from its parent or siblings. Since the nodes are immutable, any subtree can be shared among many parents, each of which belongs to a different <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B>.</li>
</UL>
<h3><a name="00c6_0048">Subscripted Fetching<a name="00c6_0048"></h3><P>
Subscripted fetching proceeds top-down, using an intermediate subscript I that is always relative to the current <B style="color:black;background-color:#ffff66">K</B>-subtree. If the <B style="color:black;background-color:#ffff66">K</B>-subtree is a leaf, the sequence subscript is the subscript to <I>LeafElems</I> and leads directly to the desired sequence element.<P>
If the <B style="color:black;background-color:#ffff66">K</B>-subtree is a nonleaf, fetch must determine to which of the node's subtrees it should descend by comparing <I>I</I> with the values of <I>CumChildCt</I> in the elements of <I>NonleafElems</I>. These values are, by definition, in ascending order, so this can be done using a classic binary search.<P>
Before fetch descends into the subtree, it must reduce the sequence subscript by <I>CumChildCt</I> of the subtree to the left of the one it is about to descend into.<P>
<h3><a name="00c6_0049">Subscripted Assignment<a name="00c6_0049"></h3><P>
Subscripted assignment begins like subscripted fetching, proceeding top-down through the <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B> to the desired leaf element. However, the located element cannot be altered in place, as this would violate the preservation-of-operands property.<P>
Instead, <I>store</I> allocates a copy of the old leaf node and alters the <I>I</I>th element of the copy. It then returns the pointer to the new node to the level above. Each nonleaf level does essentially the same thing, except it replaces only the <I>ChildRef</I> field of the selected element of its copied node with the pointer it receives from below.<P>
The result is a new <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B>, in which all nodes on the path from the root to the leaf node containing the <I>I</I>th sequence element have been replaced, while all nodes off this path are shared with the original <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B>.<P>
<a href="199400cb.htm">Figure 3</A> shows the result of assigning value 8 to element number 4 of the <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B> in <a href="199400cc.htm">Figure 2</A>(d). The shaded nodes have identical contents and are the same nodes as before the assignment. The other nodes are new. The two new nonleaf nodes look the same as before, but have different values in one of the <I>ChildRef</I> fields. To illustrate this, pointer values which have changed are shown as dashed arrows.<P>
<h3><a name="00c6_004a">Concatenation<a name="00c6_004a"></h3><P>
Concatenation is done by constructing a <I>seam</I> along the right edge of the left-operand <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B> and the left edge of the right-operand <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B>. The seam is constructed bottom-up, matching, and possibly joining, pairs of nodes of the same height from both sides of the seam.  <P>
The <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B> representation rules leave some choices as to how the seam is constructed. If the two operand <B style="color:black;background-color:#ffff66">K</B>-trees have the same height, <I>concatenate </I>could just create a new nonleaf node of two elements, with the operand <B style="color:black;background-color:#ffff66">K</B>-trees as its two children. This is simple, but building tends toward binary trees. It would be better to try to keep nodes more nearly full.<P>
Starting from the bottom in the algorithm I chose, <I>concatenate</I> moves higher as long as the total number of elements in the nodes on either side of the seam at a given level is greater than N. Once it reaches a level with N or fewer elements, it allocates a new node and repacks the elements.<P>
Once repacking has started, every level above has to have one or two new nodes allocated because some changes in child pointers will be needed to reflect the replacement of old nodes at the level below.<P>
If the total number of new elements along the seam is greater than N, two new nodes will be needed. In this case, I divide the elements equally between the new nodes, so as to keep node sizes equal.<P>
<a href="#00c6_004d">Figure 4</A> gives an example of <B style="color:black;background-color:#ffff66">K</B>-trees before and after concatenation, showing only the nodes along the seam. The <I>CumChildCt</I> fields are omitted in this example. The small numbers in circles represent nodes to either side of the seam without showing their contents. All these nodes are reused.<P>
At height one, the two leaf nodes collectively have seven elements, which can't be repacked into one node. They are reused intact in the result. At height two, there are six elements altogether, so they are repacked into one new nonleaf node.  <P>
At height three, there are initially eight elements. Two point to nodes that are not reused in the result and whose replacement consists of only one node. This leaves a total of seven new elements needed along the seam. These are distributed into the two new nodes, three elements in one node and four in the other.<P>
At height four, only the right-operand <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B> has a node. The root pointer of the left operand is treated as a fictitious, one-element node, which must be repacked with the elements from the right side of the seam. This requires a total of seven elements: Two point to replacements for old nodes, and the rest point to reused nodes to the right of the seam.<P>
Finally, a new node at height five is needed to collect the two nodes of height four. Thus the height of the result <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B> is one greater than the highest-operand <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B>.<P>
Implementing concatenation is somewhat more complex than the concept. A recursive procedure has to start at the top of the <B style="color:black;background-color:#ffff66">K</B>-trees, descend to the leaves, and then do its work on the way back up. The operand <B style="color:black;background-color:#ffff66">K</B>-trees could have different heights. The <I>Height</I> field allows the descent to synchronize itself so it is working on nodes of the same height on each side of the seam. Unequal heights also create some special cases for node construction during the return to the top.<P>
<h3><a name="00c6_004b">Slicing<a name="00c6_004b"></h3><P>
<B style="color:black;background-color:#ffff66">K</B>-trees are sliced bottom-up by constructing two cuts through the operand <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B> along the left and right edges of what will become the result <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B>. At each level, the node is divided between the elements belonging to the slice and those outside the slice. The <I>node slice</I> of the divided node on its &quot;sliceward&quot; side must be included in the result <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B>.  <P>
The node slice could have only one element. If this happens, it is repacked with the adjacent node in the sliceward direction. This will give a total of at least three and at most N+1 elements, which can always be packed into either one or two new nodes. As an optimization to keep nodes more nearly full, the node slice and the adjacent node are also repacked any time they will collectively fit into one new node.<P>
As with concatenation, the slice algorithm must start at the top of the operand <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B>, descend recursively, and do its reconstruction on the way back up. However, when slicing, the descending phase must determine, at each level, which child to descend to, using the starting and ending slice subscripts. This is done using the same binary-search technique used in subscripting.<P>
When computing a wide-enough slice at low-enough levels, the left and right cuts are separated by other <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B> nodes, which will be reused in the result <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B>. Whenever at least two nodes separate those containing the two cuts, each side of the slice can be constructed independently.<P>
At higher levels, the two cuts must be handled interdependently whenever they are spread over three or fewer nodes,  since a sliceward node adjacent to a cut is involved. In these cases, the new elements will fit in at most three new nodes. When only one element exists, no new node is constructed. Instead, the single pointer is passed up, eventually to become the result <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B>, which will be lower than the operand <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B>.<P>
<a href="#00c6_004e">Figure 5</A> gives an example of slice construction, showing only relevant nodes along the cuts. The notation is the same as in <a href="#00c6_004d">Figure 4</A>, except that wavy lines through nodes are used to show the location of the left and right cuts.<P>
At height one, the two cuts are independent. On the left, the node slice of the leftmost node shown in full contains one element whose value is 20. This is repacked with the three elements 19, 4, and 25 of the next rightward node. On the left, the entire node containing element values 16 and 10 is reused.<P>
At height two, three nodes are involved in the slice. At the left end, two elements have been replaced by one new element, returned from below. All other elements involved are reused. This gives a total of seven elements, which are repacked into two new nodes.<P>
At height three, only two nodes are involved. The two new pointers returned from the level below are packed into a single new node.<P>
Finally, at height four, only one node is involved. Two of its elements are replaced by one new node. Since one pointer does not require a node at this level, it becomes the entire result <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B>.  <P>
<h3><a name="00c6_004c">The Implementation<a name="00c6_004c"></h3><P>
The source-code implementation of <B style="color:black;background-color:#ffff66">K</B>-trees (along with programmer notes) is available electronically; see &quot;Availability&quot; on page 3. I implemented <B style="color:black;background-color:#ffff66">K</B>-trees in Modula-3 for a couple of reasons. First, it has sufficient richness in its type system to handle <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B> data structure without resorting to type-unsafe tactics. Secondly, it has built-in garbage collection. <P>
I tested the <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">Tree</B> program with many randomly generated cases. If you run the test program, be aware that the large number of trees and the brute-force verification make it a memory and CPU hog. You might want to reduce <I>SingletonCt</I>, <I>CatCt</I>, <I>CatOfSliceCt</I>, and <I>StoreCt</I>, for a more modest test run.<P>
<H4><a href="199400cd.htm">Figure 1</A>  Notation for <B style="color:black;background-color:#ffff66">K</B>-<B style="color:black;background-color:#A0FFFF">tree</B> nodes.<P>
<a href="199400ce.htm">Figure 2</A>  <B style="color:black;background-color:#ffff66">K</B>-trees and their sequences; (a) 13; (b) 7, 25, 19, 47, 5; (c) 7, 25, 19, 47, 5; (d) 16, 0, 15, 23, 6, 14, 11, 7, 3, 19, 29.<P>
<a href="199400cf.htm">Figure 3</A>  New <B style="color:black;background-color:#ffff66">K</B>-trees after assignment of value 8 to element number 4.<P></H4>
<h4><a name="00c6_004d"><B>Figure 4:</B>  <a href="199400d0.htm">(a)</A> Before concatenation; <a href="199400d1.htm">(b)</A> after concatenation; N=6.<a name="00c6_004d"></h4><P>
<h4><a name="00c6_004e"><B>Figure 5:</B>  <a href="199400d2.htm">(a)</A> Before slicing; <a href="199400d3.htm">(b)</A> after slicing.<a name="00c6_004e"></h4><P>
<P>
<HR><P>Copyright &copy; 1994, <I>Dr. Dobb's Journal</I></P></BODY></HTML>

--Boundary_(ID_PnRt1TIRDcXe3yebQzX/CQ)--

--Boundary_(ID_jvndEZDHaY5K96N7hiJdFQ)--
===


the rest of The Pile (a partial mailing list archive)

doom@kzsu.stanford.edu