On the public citation graph

Average search and update costs in skip lists

0 signed · 33 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/3-540-52846-6_86openalex-snapshot
Analysis of the expected search cost in skip lists
inferredcites →https://doi.org/10.1007/bf01840390openalex-snapshot
Analysis of the standard deletion algorithms in exact fit domain binary search trees
inferredcites →https://doi.org/10.1016/b978-0-444-88071-0.50014-xopenalex-snapshot
Average-Case Analysis of Algorithms and Data Structures
inferredcites →https://doi.org/10.1093/comjnl/32.1.68openalex-snapshot
Explaining the Behaviour of Binary Search Trees Under Prolonged Updates: A Model and Simulations
inferredcites →https://doi.org/10.1109/sfcs.1989.63531openalex-snapshot
Randomized search trees
inferredcites →https://doi.org/10.1145/78973.78977openalex-snapshot
Skip lists: a probabilistic alternative to balanced trees
inferredcites →https://doi.org/10.1214/aoap/1177005651openalex-snapshot
A Limit Theory for Random Skip Lists

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/10719839_45openalex-snapshot
Run Statistics for Geometrically Distributed Random Variables
inferred← citeshttps://doi.org/10.1007/3-540-60313-1_170openalex-snapshot
The binomial transform and its application to the analysis of skip lists
inferred← citeshttps://doi.org/10.1007/978-3-031-38906-1_31openalex-snapshot
Zip-Zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent
inferred← citeshttps://doi.org/10.1007/978-3-0348-7915-6_35openalex-snapshot
The Number of Descents in Samples of Geometric Random Variables
inferred← citeshttps://doi.org/10.1007/978-3-540-72845-0_8openalex-snapshot
On the Cost of Persistence and Authentication in Skip Lists
inferred← citeshttps://doi.org/10.1007/bf01178735openalex-snapshot
The path length of random skip lists
inferred← citeshttps://doi.org/10.1007/s00026-001-8010-zopenalex-snapshot
Combinatorics of Geometrically Distributed Random Variables: Inversions and a Parameter of Knuth
inferred← citeshttps://doi.org/10.1016/0012-365x(95)00141-iopenalex-snapshot
Combinatorics of geometrically distributed random variables: Left-to-right maxima
inferred← citeshttps://doi.org/10.1016/0304-3975(94)00296-uopenalex-snapshot
Analysis of an optimized search algorithm for skip lists
inferred← citeshttps://doi.org/10.1016/j.disc.2005.02.008openalex-snapshot
Gap-free compositions and gap-free samples of geometric random variables
inferred← citeshttps://doi.org/10.1016/j.ejc.2006.06.007openalex-snapshot
The number of distinct values in a geometrically distributed sample
inferred← citeshttps://doi.org/10.1016/j.tcs.2005.10.041openalex-snapshot
The binomial transform and the analysis of skip lists
inferred← citeshttps://doi.org/10.1016/s0304-3975(02)00641-2openalex-snapshot
Combinatorics of geometrically distributed random variables: run statistics
inferred← citeshttps://doi.org/10.1051/ita/1997310302511openalex-snapshot
Skip trees, an alternative data structure to skip lists in a concurrent approach
inferred← citeshttps://doi.org/10.1089/cmb.2013.0032openalex-snapshot
Efficient Identification of Equivalences in Dynamic Graphs and Pedigree Structures
inferred← citeshttps://doi.org/10.1142/s0218126618502183openalex-snapshot
Pyramid Search: Skip Ring Data Structure-Based New Searching Algorithm
inferred← citeshttps://doi.org/10.1145/299649.299679openalex-snapshot
Using randomization in the teaching of data structures and algorithms
inferred← citeshttps://doi.org/10.1145/3747536openalex-snapshot
Pushing the Information-Theoretic Limits of Random Access Lists: Traversing Cons Lists in (1 + 1/𝜎 ) ⌊lg 𝑛⌋ + 𝜎 + 9 Steps
inferred← citeshttps://doi.org/10.1145/384266.299679openalex-snapshot
Using randomization in the teaching of data structures and algorithms
inferred← citeshttps://doi.org/10.14569/ijacsa.2016.070220openalex-snapshot
Skip List Data Structure Based New Searching Algorithm and Its Applications: Priority Search
inferred← citeshttps://doi.org/10.15215/aupress/9781927356388.01openalex-snapshot
Open Data Structures: An Introduction
inferred← citeshttps://doi.org/10.15215/aupress/9781927356395.01openalex-snapshot
Open Data Structures: An Introduction
inferred← citeshttps://doi.org/10.21203/rs.3.rs-2705092/v1openalex-snapshot
Skip (Insertion) Sort, Skip List Based New and Very Efficient Sorting Algorithm
inferred← citeshttps://doi.org/10.46298/dmtcs.3476openalex-snapshot
Analysis of a new skip list variant
inferred← citeshttps://doi.org/10.46298/dmtcs.363openalex-snapshot
The first descent in samples of geometric random variables and permutations
inferred← citeshttps://doi.org/10.6688/jise.2011.27.3.14openalex-snapshot
Alternating Runs of Geometrically Distributed Random Variables
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.