An analysis on the performance of hash table-based dictionary implementations with different data usage models
Pages 78 - 90
Abstract
The efficiency of in-memory computing applications depends on the choice of mechanism to store and retrieve strings. The tree and trie are the abstract data types ADTs that offer better efficiency for ordered dictionary. Hash table is one among the several other ADTs that provides efficient implementation for unordered dictionary. The performance of a data structure will depend on hardware capabilities of computing devices such as RAM size, cache memory size and even the speed of the physical storage media. Hence, an application which will be running on real or virtualised hardware environment certainly will have restricted access to memory and hashing is heavily used for such applications for speedy process. In this work, an analysis on the performance of six hash table based dictionary ADT implementations with different data usage models is carried out. The six different popular hash table based dictionary ADT implementations are Khash, Uthash, GoogleDenseHash, TommyHashtable, TommyHashdyn and TommyHashlin, tested under different hardware and software configurations.
References
[1]
Askitis, N. (2007) Efficient Data Structures for Cache Architectures, School of Computer Science and Information Technology, RMIT University, Melbourne, Australia.
[2]
Askitis, N. (2009) 'Fast and compact hash tables for integer keys', Proceedings of the Thirty-Second Australasian Conference on Computer Science, ACSC 2009, Vol. 91, pp.113-122.
[3]
Askitis, N. and Zobel, J. (2008) 'B-tries for disk-based string management', Int. J. Very Large Datab., Vol. 18, No. 1, pp.157-179.
[4]
Askitis, N. and Zobel, J. (2011) 'Redesigning the string hash table, burst trie and BST to exploit cache', ACM Journal of Experimental Algorithmics, January, Vol. 15, No. 1, Article 1.7, pp.1-61.
[5]
Bell, J. and Gupta, G. (1993) 'An evaluation of self adjusting Binary search tree techniques', Software-Practice and Experience, April, Vol. 23, No. 4, pp.369-382.
[6]
Betts, A., Liu, L., Li, Z. and Antonopoulos, N. (2014) 'A critical comparative evaluation on DHT-based peer-to-peer search algorithms', Int. J. Embedded Systems, Vol. 6, Nos. 2/3, pp. 250-256
[7]
Casey, J. and Zhou, W. (2009) 'Reducing the bandwidth requirements of P2P keyword indexing', Int. J. High Performance Computing and Networking, Vol. 6, No. 2, pp.119-129.
[8]
Chilimbi, T.M. (1999) Cache-conscious data structures - design and implementation, PhD thesis, Computer Sciences Department, University of Wisconsin-Madison.
[9]
Mazzoleni, A. (2011) Tommy Benchmark and TommyDS 1.8, A High Performance C Library of Hash Tables and Tries [online] https://github.com/amadvance/tommyds (accessed 05/12/2013).
[10]
Pugh, W. (1990) 'Skip lists: a probabilistic alternative to balanced trees', Comm. of ACM, Vol. 33, No. 6, pp.668-676.
[11]
Rao, J. and Ross, K.A. (2000) 'Making B+-trees cache conscious in main memory', in Proceedings of the International Conference on the Management of Data, ACM, New York, pp.475-486.
[12]
Rubin, S., Bernstein, D. and Rodeh, M. (1999) 'Virtual cache line: a new technique to improve cache exploitation for recursive data structures', in Proceedings of the International Conference on Compiler Construction, Springer, Berlin, pp.259-273.
[13]
Thenmozhi, M. and Srimathi, H. (2015) 'An analysis on the performance of the tree and trie based dictionary implementations with different data usage models', Indian Journal of Science and Technology, February, Vol. 8, No. 4, pp.364-375.
[14]
Williams, H.E., Zobel, J. and Heinz, S. (2001) 'Self-adjusting trees in practice for large text collections', Software Practice and Experience, Vol. 31, No. 10, pp.925-939.
[15]
Yang, T-M., Feng, D., Chou, W-K. and Liu, J-N. (2015) 'A study on disk index design for large scale de-duplication storage systems', Int. J. Computational Science and Engineering, Vol. 10, Nos. 1-2, pp.171-180.
[16]
Zobel, J., Heinz, S. and Williams, H.E. (2001) 'In-memory hash tables for accumulating text vocabularies', Information Processing, December, Vol. 80, No. 6, pp.271-277.
Recommendations
High Performance Single-Chip FPGA Rijndael Algorithm Implementations
CHES '01: Proceedings of the Third International Workshop on Cryptographic Hardware and Embedded SystemsThis paper describes high performance single-chip FPGA implementations of the new Advanced Encryption Standard (AES) algorithm, Rijndael. The designs are implemented on the Virtex-E FPGA family of devices. FPGAs have proven to be very effective in ...
High-Throughput Online Hash Table on FPGA
IPDPSW '15: Proceedings of the 2015 IEEE International Parallel and Distributed Processing Symposium WorkshopHash tables are widely used in many network applications such as packet classification, traffic classification, and heavy hitter detection, etc. In this paper, we present a pipelined architecture for high throughput online hash table on FPGA. The ...
Clock Power Analysis of Low Power Clock Gated Arithmetic Logic Unit on Different FPGA
CICN '14: Proceedings of the 2014 International Conference on Computational Intelligence and Communication NetworksThis paper, deals with Latch Free Clock Gating technique for reduction of clock power and total power consumption in Low Power Arithmetic and Logic Unit and we have analysed power reduction on different FPGA devices. Without latch free clock gating ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Inderscience Publishers
Geneva 15, Switzerland
Publication History
Published: 01 January 2017
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 20 Dec 2024