Low-contention data structures

DOI10.1016/J.JPDC.2011.10.018zbMATH Open1242.68079OpenAlexW2064418086MaRDI QIDQ433458FDOQ433458

David Eisenstat, James Aspnes, 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

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

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)

Cites Work

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

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)