http://dl.acm.org/citation.cfm?id=139478
http://www.cs.ucsb.edu/~ravenben/research/CS252/252Paper.pdf
I have an old implementation (in C) of paged, deterministic skip lists here:
It sounds like they mean that, if you have all the data you want for your skiplist and all you need going forward is a read-only data structure for doing lookups, then you can put your data in order in a regular list and then build up the towers of skip links in deterministic fashion to get an optimally balanced distribution.
Doesn't seem like much of a trick, though. If you can do that, then you can just stick it all in an array and bsearch to find things.
I initially thought it might be referring to deterministic skip lists (Munro, Papadakis, Sedgewick, http://www.ic.unicamp.br/~celio/peer2peer/skip-net-graph/det...), but the "linking on traversal" part stumps me. Maybe it's referring to the top-down approach in section 3 of the paper.
Says one comment. Can anyone explain that?