Low-contention data structures

DOI10.1016/J.JPDC.2011.10.018MaRDI QIDQ433458zbMATH OpenOpenAlexFDO

Authors James Aspnes, David Eisenstat, Yitong Yin

Publication date 13 July 2012

Published in Journal of Parallel and Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jpdc.2011.10.018

zbMATH Keywords

data structurememory contentioncell-probe model

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parallel algorithms in computer science (68W10)

Recommendations

• A distribution-sensitive dictionary with low space overhead
• Contention-sensitive data structures and algorithms
• Low redundancy in static dictionaries with constant query time
• De Dictionariis Dynamicis Pauco Spatio Utentibus
• Contention-Sensitive Data Structures and Algorithms

Cites work

• scientific article; zbMATH DE number 177800 (Why is no real title available?)
• A complexity theory of efficient parallel algorithms
• An optimal parallel dictionary
• Contention in shared memory algorithms
• Cuckoo hashing
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Parallelism in random access machines
• Probability Inequalities for Sums of Bounded Random Variables
• Should Tables Be Sorted?
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Universal classes of hash functions

Cited in

(1)

• The hyperring: a low-congestion deterministic data structure for distributed environments

This page was built for publication: Low-contention data structures

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