Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site down.FUN
Path: utzoo!watmath!clyde!burl!ulysses!allegra!princeton!down!honey
From: honey@down.FUN (Peter Honeyman)
Newsgroups: net.news.b
Subject: new algorithm for expire
Message-ID: <554@down.FUN>
Date: Sat, 3-Aug-85 16:37:01 EDT
Article-I.D.: down.554
Posted: Sat Aug  3 16:37:01 1985
Date-Received: Sun, 4-Aug-85 09:35:51 EDT
Organization: CS Dept., Princeton University
Lines: 30

recently, someone suggested a new way to expire.  the gist of it was to
expire "conversations" not articles.  (it is mandatory to reference larry
peterson's work whenever mentioning conversations in the context of
electronic communication, but i forget when he presented his dragonmail
usenix paper, sometime in the last year.  sorry, larry, i tried.)

in a nutshell, expire only those articles that haven't been reference*-ed
for N days.  (reference* is the transitive and symmetric closure of the
relation induced by the References: header.)

this fairly shouts "union-find!  union-find!" (which can be distracting
late at night, and might even wake the baby).  since applications of
union-find don't crop up every day, it's important not to let this one
get away.

i plan to assign this to the next junior that walks up to me and says
"don't hurt me professor honey; do you have any ideas for independent
study projects?"  "no problem, grasshopper, write me a program."  just
think, path compression in netnews code.

can anyone tell me why references should contain anything other than the
last article referenced?  larry would be disappointed with any practice
other than shipping the transitive reduction of the references relation.
since netnews conversations are tree-like, this is just the article being
up-followed.

i don't recall ever having seen an article that merited a non-standard
Expires: header.  anyone else?

	peter