Data processing: database and file management or data structures – Miscellaneous
Reexamination Certificate
2007-04-25
2010-11-02
Vy, Hung T (Department: 2163)
Data processing: database and file management or data structures
Miscellaneous
C370S389000
Reexamination Certificate
active
07827218
ABSTRACT:
An input lookup key is hashed and the hashed key divided into stride bits into a multi-level Trie structure. A compression function logically combines the stride bits to generate the compressed index bits into the stride tables. The bucket in the last stride table found by the hashed key may have several keys that collide at the same hash value. Discriminant bits are read from the key and select a stored key in the bucket table for verification of its result. Since the hashed key is a compression of the longer input key, more information is contained per bit of the hashed key than in the long key. The multi-stride lookup is performed first on the hashed key, allowing a faster convergence to the lookup result. The first stride can index a single hash table, with the remaining hash bits and discriminant bits used to select from among colliding keys.
REFERENCES:
patent: 5105353 (1992-04-01), Charles et al.
patent: 5276868 (1994-01-01), Poole
patent: 5640551 (1997-06-01), Chu et al.
patent: 5651099 (1997-07-01), Konsella
patent: 5781772 (1998-07-01), Wilkinson, III et al.
patent: 5813001 (1998-09-01), Bennett
patent: 6067574 (2000-05-01), Tzeng
patent: 6691131 (2004-02-01), Tikkanen et al.
patent: 6697363 (2004-02-01), Carr
patent: 6782382 (2004-08-01), Lunteren
patent: 6910043 (2005-06-01), Iivonen et al.
patent: 7007101 (2006-02-01), Schwaderer
patent: 7019674 (2006-03-01), Cadambi et al.
patent: 7325059 (2008-01-01), Barach et al.
patent: 7430560 (2008-09-01), Mittal
patent: 7444318 (2008-10-01), Sahni et al.
patent: 7474657 (2009-01-01), Sahni et al.
patent: 7702629 (2010-04-01), Cytron et al.
patent: 2004/0111440 (2004-06-01), Richardson et al.
patent: 2004/0117600 (2004-06-01), Bodas et al.
patent: 2004/0141509 (2004-07-01), Sahni et al.
patent: 2004/0167923 (2004-08-01), Carr
patent: 2004/0258061 (2004-12-01), Sahni et al.
patent: 2005/0187898 (2005-08-01), Chazelle et al.
Auvinen Stuart T.
gPatent LLC
Vy Hung T
X-Engines, Inc.
LandOfFree
Deterministic lookup using hashed key in a multi-stride... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Deterministic lookup using hashed key in a multi-stride..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deterministic lookup using hashed key in a multi-stride... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4247884