[william-newman]

Skip lists seem to be a powerful way of thinking about the problem, anyway. Note that they lead nicely to the very nifty multidimensional generalization, skip quadtrees, www.ics.uci.edu/~goodrich/pubs/skip.pdf .

And, FWIW, they also lead to my algorithms for hash-consing digraphs, which I put up as rough preprints and and prototype code at http://www.wryttyndyffyryntly.com/preprint/. Those algorithms are unreviewed, and I made a bad mistake in an early version, so who knows? (I sent email about them to other people who had cited the Mauborgne papers that I cited, and got no response. I don't know whether it's worth trying to bang them into shape for submission to a journal, and whether or not it's worth it in principle, in practice last year I was too tired of working on them to consider it very objectively.)