Abstract
An algorithm for storage and retrieval in a small dynamic cache is presented. This algorithm is based on C.C. Chang’s ordered minimal perfect hashing scheme. Our algorithm has the property that it divides the set of objects that could occupy the cache into an arbitrary number of equivalence classes. The only restriction on which objects can occupy the cache are that no two objects in the same equivalence class can be in the cache at the same time. Retrieval from the cache is performed in constant time. Update of the cache is performed in logarithmic time.
Recommended Citation
Sager, Thomas J., "A Dynamic Caching Algorithm based on C. C. Chang's Ordered Minimal Perfect Hashing Scheme" (1987). Computer Science Technical Reports. 11.
https://scholarsmine.mst.edu/comsci_techreports/11
Department(s)
Computer Science
Report Number
CSc-87-2
Document Type
Technical Report
Document Version
Final Version
File Type
text
Language(s)
English
Rights
© 1987 University of Missouri--Rolla, All rights reserved.
Publication Date
1987
