scientific article; zbMATH DE number 6381684

MaRDI QIDQ2934638zbMATH OpenFDO

Authors Mihai Patrascu, Mikkel Thorup

Publication date 18 December 2014

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Recommendations

• scientific article; zbMATH DE number 1380606
• Random searching
• Not all (possibly) “random” sequences are created equal
• Predecessors in random mappings
• Randomizing without randomness
• Prequential Randomness
• Random heuristic search
• Sequential search beats a two-parameter search

Cited in

(11)

• Lower bounds for predecessor searching in the cell probe model
• Time-space trade-offs for predecessor search
• Connectivity oracles for graphs subject to vertex failures
• Confluently Persistent Tries for Efficient Version Control
• On the complexity of the (approximate) nearest colored node problem
• Nearly Optimal Static Las Vegas Succinct Dictionary
• Non-adaptive data structure bounds for dynamic predecessor
• The complexity of the co-occurrence problem
• Predecessor on the Ultra-Wide Word RAM
• Random input helps searching predecessors
• Confluently persistent tries for efficient version control

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2934638)