Abstract
We present the first parallel compact hash table algorithm. It delivers high performance and scalability due to its dynamic region-based locking scheme with only a fraction of the memory requirements of a regular hash table.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Amble, O., Knuth, D.E.: Ordered Hash Tables. The Computer Journal 17(2), 135–142 (1974)
Bryant, R.E.: Graph-Based Algorithms for Boolean Function Manipulation. IEEE Transactions on Computers 35, 677–691 (1986)
Cleary, J.G.: Compact Hash Tables Using Bidirectional Linear Probing. IEEE Transactions on Computers C-33(9), 828–834 (1984)
Click, C.: A Lock-Free Hash Table. Talk at JavaOne (2007), http://www.azulsystems.com/events/javaone_2007/2007_LockFreeHash.pdf
Geldenhuys, J., Valmari, A.: A Nearly Memory-Optimal Data Structure for Sets and Mappings. In: Ball, T., Rajamani, S.K. (eds.) SPIN 2003. LNCS, vol. 2648, pp. 136–150. Springer, Heidelberg (2003)
Herlihy, M., Shavit, N.: The Art of Multiprocessor Programming. M. Kaufmann (2008)
Laarman, A.W., van de Pol, J.C., Weber, M.: Boosting Multi-Core Reachability Performance with Shared Hash Tables. In: Sharygina, N., Bloem, R. (eds.) FMCAD 2010, pp. 247–255. IEEE Computer Society (2010)
Laarman, A., van de Pol, J., Weber, M.: Parallel Recursive State Compression for Free. In: Groce, A., Musuvathi, M. (eds.) SPIN Workshops 2011. LNCS, vol. 6823, pp. 38–56. Springer, Heidelberg (2011)
van der Vegt, S.: A Concurrent Bidirectional Linear Probing Algorithm. In: Heijnen, C., Koppelman, H. (eds.) 15th Twente Student Conference on Information Technology, Enschede, The Netherlands, Enschede. TSConIT, vol. 15, pp. 269–276. Twente University Press (2011), http://referaat.cs.utwente.nl/TSConIT/download.php?id=981
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
van der Vegt, S., Laarman, A. (2012). A Parallel Compact Hash Table. In: Kotásek, Z., Bouda, J., Černá, I., Sekanina, L., Vojnar, T., Antoš, D. (eds) Mathematical and Engineering Methods in Computer Science. MEMICS 2011. Lecture Notes in Computer Science, vol 7119. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25929-6_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-25929-6_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-25928-9
Online ISBN: 978-3-642-25929-6
eBook Packages: Computer ScienceComputer Science (R0)