Sorting Cuckoo - Enhancing Lookup Performance of Cuckoo Hashing Using Insertion Sort - 


Vol. 42,  No. 3, pp. 566-576, Mar.  2017


PDF
  Abstract

Key-value stores proved its superiority by being applied to various NoSQL databases such as Redis, Memcached. Lookup performance is important because key-value store applications performs more lookup than insert operations in most environments. However, in traditional applications, lookup may be slow because hash tables are constructed out of linked-list. Therefore, cuckoo hashing has been getting attention from the academia for constant lookup time, and bucketized cuckoo hashing (BCH) has been proposed since it can achieve high load factor. In this paper, we introduce Sorting Cuckoo which inserts data using insertion sort in BCH structure. Sorting Cuckoo determines the existence of a key with a relatively small memory access because data are sorted in each buckets. In particular, the higher memory load factor, the better lookup performance than BCH’s. Experimental results show that Sorting Cuckoo has smaller memory access than BCH’s as many as about 19 million (25%) in 10 million negative lookup operations (key is not in the table), about 4 million times (10%) in 10 million positive lookup operations (where it is) with load factor 95%.

  Statistics
Cumulative Counts from November, 2022
Multiple requests among the same browser session are counted as one view. If you mouse over a chart, the values of data points will be shown.


  Cite this article

[IEEE Style]

D. Min, R. Jang, D. Nyang, K. Lee, "Sorting Cuckoo - Enhancing Lookup Performance of Cuckoo Hashing Using Insertion Sort -," The Journal of Korean Institute of Communications and Information Sciences, vol. 42, no. 3, pp. 566-576, 2017. DOI: .

[ACM Style]

Dae-hong Min, Rhong-ho Jang, Dae-hun Nyang, and Kyung-hee Lee. 2017. Sorting Cuckoo - Enhancing Lookup Performance of Cuckoo Hashing Using Insertion Sort -. The Journal of Korean Institute of Communications and Information Sciences, 42, 3, (2017), 566-576. DOI: .

[KICS Style]

Dae-hong Min, Rhong-ho Jang, Dae-hun Nyang, Kyung-hee Lee, "Sorting Cuckoo - Enhancing Lookup Performance of Cuckoo Hashing Using Insertion Sort -," The Journal of Korean Institute of Communications and Information Sciences, vol. 42, no. 3, pp. 566-576, 3. 2017.

Search
(IN TITLE, AUTHOR, ABSTRACT,KEYWORDS)

Advanced Search ▼

POPULAR KEYWORDS
(TOP 10 KEYWORDS)

Recent Publications
(LAST 3 YEARS)






pISSN : 1226 - 4717
eISSN : 2287 - 3880