Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2006-12-05
2006-12-05
Gaffin, Jeffrey (Department: 2165)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
07146371
ABSTRACT:
A data structure and corresponding search methods are disclosed for improving the performance of table lookups. A data structure for the table is employed using a single hash table with hash table entries pointing to tree fragments that are contiguous in main memory and can be efficiently loaded into a local data store or cache. Decision nodes are stored in a contiguous block of memory in a relative position based on the position of the decision node in the tree structure, including blank positions. Leaf nodes are stored in a contiguous block of memory based on the position of the leaf node in the tree structure, concatenating leaf nodes to eliminate blank positions. Leaf nodes of the tree fragments contain indicia of a data record, or indicia of another tree fragment. The data structure and corresponding search algorithm are employed for searches based on a longest prefix match in an internet routing table.
REFERENCES:
patent: 4468728 (1984-08-01), Wang
patent: 4599691 (1986-07-01), Sakaki et al.
patent: 5202986 (1993-04-01), Nickel
patent: 5371885 (1994-12-01), Letwin
patent: 5390307 (1995-02-01), Yoshida
patent: 5465352 (1995-11-01), Nakazawa et al.
patent: 5546390 (1996-08-01), Stone
patent: 5587930 (1996-12-01), Hori et al.
patent: 5664184 (1997-09-01), Ferguson et al.
patent: 5710916 (1998-01-01), Barbará et al.
patent: 5752243 (1998-05-01), Reiter et al.
patent: 5829004 (1998-10-01), Au
patent: 5892513 (1999-04-01), Fay
patent: 6067574 (2000-05-01), Tzeng
patent: 6233656 (2001-05-01), Jones et al.
patent: 6246347 (2001-06-01), Bakhmutsky
patent: 6292795 (2001-09-01), Peters et al.
patent: 6396842 (2002-05-01), Rochberger
patent: 6675163 (2004-01-01), Bass et al.
patent: 6687815 (2004-02-01), Dwyer et al.
patent: 1316696 (2001-10-01), None
patent: 10091797 (1998-04-01), None
patent: 2001099921 (2001-04-01), None
Marcel Waldvogel et al.:“Scalable High Speed IP Routing Lookups”, 1997, ACM, pp. 25-36.
Sklower, K.; Abstract; “A Tree-Based Packet Routing Table for Berkeley Unix”; Computer System Research Group, EECS Dept., Computer Science Division, University of Calif., Berkeley, CA 94720.
Natarajan, K.S. et al.; “Predictive Method of Controlling Artificial Intelligence Search by Exploration and Ordering”;IBM Technical Disclosure Bulletin; Dec. 1989; vol. 32, No. 7; IBM Corp.
Hofstee Peter
Necker Marc C.
Carr LLP
Gaffin Jeffrey
Gerhardt Diana R.
Veillard Jacques
LandOfFree
Performance and memory bandwidth utilization for tree... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Performance and memory bandwidth utilization for tree..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Performance and memory bandwidth utilization for tree... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3664499