Concurrent extensible cuckoo hashing

Details Concurrent extensible cuckoo hashing Concurrent extensible cuckoo hashing

2007-03-12

2010-02-02

Ali, Mohammad (Department: 2158)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C711S216000

Reexamination Certificate

active

07657500

ABSTRACT:
Concurrent cuckoo hashing is performed on a hash table that includes a number of locations; each may hold a value. A plurality of processes may concurrently execute on the table; each process includes a sequence of operations, which are divided into a number of phases. Each phase corresponds to one operation in the sequence. An overflow buffer is provided for each location in the table. Each overflow buffer may hold a value displaced from its corresponding location in the table. A plurality of sequences of operations is concurrently executed. Each phase in a sequence executes by acquiring one or two locks on two locations in the table; a lock acts on a location and its overflow buffer. An operation of a phase is then executed. If, on conclusion of the phase execution, any overflow buffer holds a value, the execution is repeated until all overflow buffers are empty.

REFERENCES:
patent: 5796939 (1998-08-01), Berc et al.
patent: 6304949 (2001-10-01), Houlsdworth
patent: 6442553 (2002-08-01), Take
patent: 6578131 (2003-06-01), Larson et al.
patent: 6757794 (2004-06-01), Cabrera et al.
patent: 6772155 (2004-08-01), Stegelmann
patent: 6952692 (2005-10-01), Bhattiprolu et al.
patent: 2004/0059734 (2004-03-01), Smith et al.
patent: 2008/0021908 (2008-01-01), Trask et al.
patent: 2008/0115042 (2008-05-01), Akkary et al.
patent: 2008/0115142 (2008-05-01), Scheuer
patent: 2008/0263044 (2008-10-01), Cantrill
Rasmus Pagh and Flemming Friche Rodler, Cuckoo Hashing, Dec. 8, 2003, pp. 1-27.

Affiliated with

Also associated with

Rating

Concurrent extensible cuckoo hashing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Concurrent extensible cuckoo hashing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Concurrent extensible cuckoo hashing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4195120