Efficient improvement of Brain-Tharp's algorithm
Апстракт
In this paper we present possible improvement of the best known perfect hashing algorithm. A comparison of the proposed algorithm with other known important perfect hashing algorithms in addition to Brain-Tharp's algorithm is also given. The Brain-Tharp's algorithm is the best known in the special class of algorithms that can be used to form ordered minimal perfect hash functions for very large word lists in terms of function building efficiency, pattern collision avoidance and retrieval function complexity. However, building a perfect hash function by the Brain-Tharp's algorithm is still extremely slow. In this paper we analysed important features of Brain-Tharp's algorithm and proposed three solutions to improve the total processing time of the packing phase. The proposed techniques are validated empirically. The improvement factor is close to 2 on the example of the standard UNIX dictionary.
Кључне речи:
physical design / perfect hashing / file structures / algorithmsИзвор:
Yugoslav Journal of Operations Research, 1999, 9, 2, 235-256Издавач:
- Univerzitet u Beogradu - Fakultet organizacionih nauka, Beograd, i dr.
Институција/група
Fakultet organizacionih naukaTY - JOUR AU - Simić, Dejan AU - Starčević, Dušan PY - 1999 UR - https://rfos.fon.bg.ac.rs/handle/123456789/187 AB - In this paper we present possible improvement of the best known perfect hashing algorithm. A comparison of the proposed algorithm with other known important perfect hashing algorithms in addition to Brain-Tharp's algorithm is also given. The Brain-Tharp's algorithm is the best known in the special class of algorithms that can be used to form ordered minimal perfect hash functions for very large word lists in terms of function building efficiency, pattern collision avoidance and retrieval function complexity. However, building a perfect hash function by the Brain-Tharp's algorithm is still extremely slow. In this paper we analysed important features of Brain-Tharp's algorithm and proposed three solutions to improve the total processing time of the packing phase. The proposed techniques are validated empirically. The improvement factor is close to 2 on the example of the standard UNIX dictionary. PB - Univerzitet u Beogradu - Fakultet organizacionih nauka, Beograd, i dr. T2 - Yugoslav Journal of Operations Research T1 - Efficient improvement of Brain-Tharp's algorithm EP - 256 IS - 2 SP - 235 VL - 9 UR - conv_2953 ER -
@article{ author = "Simić, Dejan and Starčević, Dušan", year = "1999", abstract = "In this paper we present possible improvement of the best known perfect hashing algorithm. A comparison of the proposed algorithm with other known important perfect hashing algorithms in addition to Brain-Tharp's algorithm is also given. The Brain-Tharp's algorithm is the best known in the special class of algorithms that can be used to form ordered minimal perfect hash functions for very large word lists in terms of function building efficiency, pattern collision avoidance and retrieval function complexity. However, building a perfect hash function by the Brain-Tharp's algorithm is still extremely slow. In this paper we analysed important features of Brain-Tharp's algorithm and proposed three solutions to improve the total processing time of the packing phase. The proposed techniques are validated empirically. The improvement factor is close to 2 on the example of the standard UNIX dictionary.", publisher = "Univerzitet u Beogradu - Fakultet organizacionih nauka, Beograd, i dr.", journal = "Yugoslav Journal of Operations Research", title = "Efficient improvement of Brain-Tharp's algorithm", pages = "256-235", number = "2", volume = "9", url = "conv_2953" }
Simić, D.,& Starčević, D.. (1999). Efficient improvement of Brain-Tharp's algorithm. in Yugoslav Journal of Operations Research Univerzitet u Beogradu - Fakultet organizacionih nauka, Beograd, i dr.., 9(2), 235-256. conv_2953
Simić D, Starčević D. Efficient improvement of Brain-Tharp's algorithm. in Yugoslav Journal of Operations Research. 1999;9(2):235-256. conv_2953 .
Simić, Dejan, Starčević, Dušan, "Efficient improvement of Brain-Tharp's algorithm" in Yugoslav Journal of Operations Research, 9, no. 2 (1999):235-256, conv_2953 .