Fast, deterministic exact match look-ups in large tables

Details Fast, deterministic exact match look-ups in large tables Fast, deterministic exact match look-ups in large tables

2006-05-09

2006-05-09

Alam, Shahid Al (Department: 2162)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

07043494

ABSTRACT:
A combined hash table/bucket trie technique facilitates fast, deterministic, memory-efficient exact match look-ups on extremely large tables. A limited number of hash keys which collide on the same location can be stored in the hash table. If further keys collide on the same location, a bucket trie is formed, the colliding keys are stored in the trie, and trie traversal information is stored in the hash table. Regardless of the number of buckets in the trie, an input key need only be compared with the keys in one bucket to detect a stored key identical to the input key or conclude that no stored key is identical to the input key.

REFERENCES:
patent: 4866634 (1989-09-01), Reboh et al.
patent: 5089952 (1992-02-01), Bozman
patent: 5404488 (1995-04-01), Kerrigan et al.
patent: 6034958 (2000-03-01), Wicklund
patent: 6097725 (2000-08-01), Glaise et al.
patent: 6226710 (2001-05-01), Melchior
patent: 6597661 (2003-07-01), Bonn
patent: 6598051 (2003-07-01), Wiener et al.
patent: 6690667 (2004-02-01), Warren
patent: 6701317 (2004-03-01), Wiener et al.
patent: 6754662 (2004-06-01), Li
patent: 6789156 (2004-09-01), Waldspurger
Mishra, Priti et al., “Join Processing in Relational Databases”, ACM Computing Surveys, vol. 24, No. 1, Mar. 1992.
M V Ramakrishna, E. Fu, E. Bahcekapili “Efficient Hardware Hashing Functions for High Performance Computers”, IEEE Transaction on Computers, Dec. 1997 vol. 46 No. 12, pp. 1378-1381.
J. Carter and M. Wegman, “Universal Classes of Hash Functions,” Journal of Computer and System Sciences, vol. 18, No. 2, pp. 143-154, 1979.
Mukesh Singhal et al “A Novel Cache Architecture to support Layer four Packet Classification at Memory Access Speeds”, IEEE Infocom 2000, pp. 1445-1454.
TC59LM814/06CFT-50, Toshiba 200MHz FCRAM datasheet, Nov. 30, 2001.
D. E. Knuth, The Art of Computer Programming, vol. 3, Sorting and Searching, §6.3 “Digital Searching” Addison Wesley, 1973, pp. 481-491.

Affiliated with

Also associated with

Rating

Fast, deterministic exact match look-ups in large tables does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Fast, deterministic exact match look-ups in large tables, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast, deterministic exact match look-ups in large tables will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3604542