Two-way chaining for non-uniform distributions

DOI10.1080/00207160802132871MaRDI QIDQ5852152zbMATH OpenOpenAlexFDO

Authors Ebrahim Malalla

Publication date 26 January 2010

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/00207160802132871

zbMATH Keywords

non-uniform distributionsworst-case search timetwo-way chainingmultiple choice allocation processwitness tree

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Analysis of algorithms (68W40) Searching and sorting (68P10)

Recommendations

• Two-Way Chaining with Reassignment
• The expected length of the longest probe sequence for bucket searching when the distribution is not uniform
• Efficient hashing with lookups in two memory accesses
• Hashing with Linear Probing under Nonuniform Probabilities
• The analysis of double hashing

Cites work

• scientific article; zbMATH DE number 3954145 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3548141 (Why is no real title available?)
• scientific article; zbMATH DE number 3586221 (Why is no real title available?)
• scientific article; zbMATH DE number 1301967 (Why is no real title available?)
• scientific article; zbMATH DE number 1936537 (Why is no real title available?)
• scientific article; zbMATH DE number 1559577 (Why is no real title available?)
• An algorithmic and complexity analysis of interpolation search
• Balanced Allocations
• Balanced Allocations: The Heavily Loaded Case
• Balanced allocation and dictionaries with tightly packed constant size bins
• Dynamic Perfect Hashing: Upper and Lower Bounds
• Efficient PRAM simulation on a distributed memory machine
• Expected Length of the Longest Probe Sequence in Hash Code Searching
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• How asymmetry helps load balancing
• Multidimensional balanced allocations
• Neighborhood preserving hashing and approximate queries
• Probability and random processes.
• Randomized allocation processes
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Studying Balanced Allocations with Differential Equations
• The expected length of the longest probe sequence for bucket searching when the distribution is not uniform
• Two-Way Chaining with Reassignment
• Using the Power of Two Choices to Improve Bloom Filters

Cited in

(2)

• Efficient hashing with lookups in two memory accesses
• Two-Way Chaining with Reassignment

This page was built for publication: Two-way chaining for non-uniform distributions

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