Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
2008-09-09
2008-09-09
Lane, Jack A. (Department: 2185)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C711S216000
Reexamination Certificate
active
11455339
ABSTRACT:
A computer implemented method, data processing system, and computer usable program code are provided for storing data items in a computer. A plurality of hash functions of data values in a data item are computed. A corresponding memory location is determined for one of the plurality of hash functions. The data item and a key portion and a payload portion of all data items are stored contiguously within the memory location.Also provided for are retrieving data items in a computer. A plurality of hash functions of data values in a probe key are computed. A corresponding memory location is determined for each of the plurality of hash functions. Data items in each memory location are examined to determine a match with the probe key. Responsive to a match, a payload of the matching stored data item is returned. All of the steps are performed free of conditional branch instructions.
REFERENCES:
patent: 4996663 (1991-02-01), Nemes
patent: 5287499 (1994-02-01), Nemes
patent: 5579501 (1996-11-01), Lipton et al.
patent: 6014733 (2000-01-01), Bennett
patent: 6097725 (2000-08-01), Glaise et al.
patent: 2007/0234005 (2007-10-01), Erlingsson et al.
Dietzfelbinger et al., “Balanced Allocation and Dictionaries with Tightly Packed Constant Size Bins”, Jul. 18, 2005, pp. 1-23, ICALP, LNCS 3580.
Erlingsson et al., “A Cool and Practical Alternative to Traditional Hash Tables”, Microsoft Research—Silicon Valley, Workshop on Distributed Data and Structures, 2006, pp. 1-6.
Fotakis et al., “Space Efficient Hash Tables With Worst Case Constant Access Time”, Theory Comput. Syst., 38 (2):229-248, 2005.
Pagh et al., “Cuckoo Hashing”, J. Algorithms, 51 (2): 122-144, 2004.
Panigrahy, “Efficient Hashing with Lookups in Two Memory Accesses”, Mar. 23, 2006, Cisco Systems, pp. 1-12.
International Business Machines - Corporation
Lammes Francis
Lane Jack A.
Yamonaco Lisa M.
Yee Duke W.
LandOfFree
Splash tables: an efficient hash scheme for processors does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Splash tables: an efficient hash scheme for processors, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Splash tables: an efficient hash scheme for processors will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3938034