Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2006-08-29
2006-08-29
Gaffin, Jeffrey (Department: 2165)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
07099881
ABSTRACT:
Sparsely distributed prefixes within a bitmapped multi-bit trie are compressed by one or more of: replacing a single entry table string terminating with a single prefix end node with a parent table entry explicitly encoding a prefix portion; replacing a table with only two end nodes or only an end node and an internal node with a single parent table entry explicitly encoding prefix portions; replacing two end nodes with a single compressed child entry at a table location normally occupied by an internal node and explicitly encoding prefix portions; and replacing a plurality of end nodes with a prefix-only entry located at the table end explicitly encoding portions of a plurality of prefixes. The compressed child entry and the prefix-only entry, if present, are read by default each time the table is searched. Run length encoding allows variable length prefix portions to be encoded.
REFERENCES:
patent: 5781772 (1998-07-01), Wilkinson et al.
patent: 6014659 (2000-01-01), Wilkinson et al.
patent: 6067574 (2000-05-01), Tzeng
patent: 6385649 (2002-05-01), Draves et al.
patent: 6430527 (2002-08-01), Waters et al.
patent: 6522632 (2003-02-01), Waters et al.
patent: 6581106 (2003-06-01), Crescenzi et al.
patent: 6697363 (2004-02-01), Carr
patent: 6928430 (2005-08-01), Chien et al.
patent: 2003/0174717 (2003-09-01), Zabarski et al.
Degemark et al.:Small forwarding tables for fast routing lookups. ACM computer Communication Review 27, 4 (Oct. 1997), pp. 3-14.
Lampson et al.: IP Lookups Using Multiway and Multicolumn Search. IEE/ACM Transaction on Networking (TON), vol. 7, Issue 3, Jun. 199, p. 324-334.
Nilson et al.: IP-Address Looup Using LC Tries. IEEE Journal, vol. 17, Issue 6, Jun. 1999, pp. 1083-1092.
Huang Lun Bin
Rajgopal Suresh
Richardson Nicholas Julian
Jorgenson Lisa K.
Munck William A.
STMicroelectronics Inc.
Veillard Jacques
LandOfFree
Method for increasing average storage capacity in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for increasing average storage capacity in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for increasing average storage capacity in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3707465