[HN Gopher] What Cannot be Skipped About the Skiplist
       ___________________________________________________________________
        
       What Cannot be Skipped About the Skiplist
        
       Author : todsacerdoti
       Score  : 74 points
       Date   : 2024-03-09 13:03 UTC (9 hours ago)
        
 (HTM) web link (arxiv.org)
 (TXT) w3m dump (arxiv.org)
        
       | JadeNB wrote:
       | The full subtitle is "A Survey of Skiplists and Their
       | Applications in Big Data Systems."
        
       | kragen wrote:
       | the title makes this review sound a lot less comprehensive than
       | it really is. it covers basically every variant of pugh's skip
       | list ever published, so you can in fact skip most of them
       | 
       | but this is the paper you want if you need to look up what
       | variants exist of, say, the interval skip list, and how they
       | compare. as it happens, that's exactly what i needed today
       | 
       | gold
        
       | ComputerGuru wrote:
       | I thought arXiv papers were all (experimentally) available as
       | HTML for accessibility reasons now, but I can't find the html
       | link here.
       | 
       | Ref: https://blog.arxiv.org/2023/12/21/accessibility-update-
       | arxiv...
        
         | mananaysiempre wrote:
         | From your link:
         | 
         | > [...] arXiv is now generating an HTML formatted version of
         | all papers _submitted in TeX /LaTeX_ [...]
         | 
         | This paper has been submitted as a PDF blob rather than
         | buildable TeX source, it seems. (Otherwise there'd also be a
         | "TeX Source" link on the left.)
        
       | anfelor wrote:
       | Another interesting data structure related to skiplists but not
       | mentioned here are zip trees: https://arxiv.org/abs/1806.06726
       | 
       | The are a tree-based version of skiplists and thus more suited to
       | functional programming / immutable datastructures.
        
         | rtheunissen wrote:
         | Zip trees are novel but their performance (and therefore also
         | skip lists, since they are isomorphic) lacks behind other
         | linked structures like Treaps and especially LBSTs. [1] I
         | personally find skip lists to be overhyped binary search trees
         | in disguise.
         | 
         | [1] https://rtheunissen.github.io/bst
        
           | bonzini wrote:
           | Absolutely trees in disguise, in fact there are deterministic
           | versions of skip lists that are equivalent to B-trees. An 1-2
           | skip list (where each pointer to next can skip from 1 to 2
           | pointers on the level below) is isomorphic to a 2-3 tree.
        
       | fancy_pantser wrote:
       | Section 2.3, "Analysis of p" is incomplete. The ideal value is
       | 1/e. In most practical applications, you want to start with
       | setting it to 1/e, which is a good speed/memory tradeoff. I tried
       | for years to get Redis and some widely-used libraries to update
       | their default values for everyone's benefit, as this one of my
       | favorite data structures.
       | 
       | Ref:
       | http://www.sciencedirect.com/science/article/pii/03043975940...
        
       ___________________________________________________________________
       (page generated 2024-03-09 23:00 UTC)