Performance analysis of a main memory multi-directory hashing technique

DOI10.1016/0020-0190(93)90118-SMaRDI QIDQ1209985zbMATH OpenOpenAlexWikidataFDO

Authors Anastasia Analyti, Sakti Pramanik

Publication date 16 May 1993

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(93)90118-s

zbMATH Keywords

Extendible hashingmain memory databasesMulti-directory hashing

Mathematics Subject Classification ID

Database theory (68P15) Analysis of algorithms and problem complexity (68Q25)

Review text

Hashing permits fast access to both disk-based and main memory-based databases. The retrieval time in main memory databases consists of the time to follow the address pointers plus the time to compare the key values. We define optimal search in main memory databases as the search that requires at most one key comparison to locate a record. Extendible hashing becomes impractical when it is adapted to yield optimal search because of its large directory size. Multi-directory hashing techniques can provide significantly improved directory utilization over extendible hashing. The objective of the paper is to analyze the directory utilization of a main memory hashing technique, called Extendible Root Multi-Directory Hashing (ERMH), ERMH uses a tree-structured hash directory of height one. The size of the leaf subdirectories is fixed and the root subdirectory expands to allow for more records. ERMH requires at most one key comparison to locate a record and its expected directory size is \(O(m^{4/3})\), where \(m\) is the number of inserted records.

Recommendations

• Multi-directory hashing
• Optimality in external memory hashing
• scientific article; zbMATH DE number 1070502
• Collections of Functions for Perfect Hashing
• Indexed extendible hashing

Cites work

• Dynamic hashing
• On the performance evaluation of extendible hashing and trie searching

Cited in

(5)

• Indexed extendible hashing
• An asymptotic comment on a paper by Analyti and Pramanik
• scientific article; zbMATH DE number 1070502 (Why is no real title available?)
• scientific article; zbMATH DE number 1481756 (Why is no real title available?)
• Multi-directory hashing

This page was built for publication: Performance analysis of a main memory multi-directory hashing technique

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