Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2005-11-08
2005-11-08
Mizrahi, Diane D. (Department: 2165)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06963868
ABSTRACT:
A tree structure and method to organize routing information for processing messages within a network, each message being associated with a search key of “n” bits. The processing determines where to send the message next. The structure has a direct table (DT) of 2xentries for decoding the first “x” bits of the search key, and one or more pattern search control blocks (PSCB's), each having 2mentries for decoding subsequent groups of “m” bits. Each PSCB entry and DT entry includes a pointer to data associated with a specific route, if at this point a specific routing table entry is a potential match to the search key or a pointer to a subsequent PSCB if the end of a search trail is not identified. Each PSCB entry DT entry also indicates that the search has been resolved to the end of the search trail.
REFERENCES:
patent: 5173906 (1992-12-01), Dreibelbis et al.
patent: 5493689 (1996-02-01), Waclawsky et al.
patent: 5506846 (1996-04-01), Edem et al.
patent: 5717632 (1998-02-01), Richart et al.
patent: 5845234 (1998-12-01), Testa et al.
patent: 6052683 (2000-04-01), Irwin
patent: 6061712 (2000-05-01), Tzeng
patent: 6067574 (2000-05-01), Tzeng
patent: 6223172 (2001-04-01), Hunter et al.
patent: 6237061 (2001-05-01), Srinivasan et al.
patent: 6675163 (2004-01-01), Bass et al.
patent: 6848086 (2005-01-01), Teig et al.
patent: 2004/0215609 (2004-10-01), Takatsu et al.
Szpankowski, Wojciech, Patricia tries again revisited, Oct. 1990, ACM Press, vol. 37, Issue 4, pp. 691-711.
Paolo Ferragina et al., The string B-tree: a new data structure for string search in external memory and its applications, Mar. 1999 ACM Press, vol. 46, Issue 2, pp. 236-280.
Basso Claude
Calvignac Jean L.
Davis Gordon T.
Heddes Marco
Patel Piyush C.
Hogg William N.
Mizrahi Diane D.
LandOfFree
Multi-bit Patricia trees does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multi-bit Patricia trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-bit Patricia trees will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3486636