Method and apparatus for performing a binary search on an...

Details Method and apparatus for performing a binary search on an... Method and apparatus for performing a binary search on an...

2006-07-04

2006-07-04

Robinson, Greta (Department: 2168)

Data processing: database and file management or data structures

Database design

Data structure types

C709S238000

Reexamination Certificate

active

07072885

ABSTRACT:
A method and apparatus for searching an electronically stored table of information including a plurality of table entries and facilitating high speed searching of a table to provide a longest matching entry. The table searching method uses at least one memory unit having a table of information including a plurality of data entries. The table of information has a plurality of search keys associated with the plurality of data entries and the plurality of search keys form a tree structure based on a prefix length for each of the search keys. The plurality of search keys are expanded such that each of the plurality of search keys has two lowest level search keys associated therewith that cover a lowest level of the tree structure. A binary search of the lowest level search keys is performed based on a search value to determine a longest prefix match. A data entry of the plurality of data entries is output based on said longest prefix match. The method is also applicable to routing data in an internet router where the routing of data packets depends on address information stored in the table of information.

REFERENCES:
patent: 5278789 (1994-01-01), Inoue et al.
patent: 5390173 (1995-02-01), Spinney et al.
patent: 5414704 (1995-05-01), Spinney
patent: 5423015 (1995-06-01), Chung
patent: 5459717 (1995-10-01), Mullan et al.
patent: 5473607 (1995-12-01), Hausman et al.
patent: 5499295 (1996-03-01), Cooper
patent: 5524254 (1996-06-01), Morgan et al.
patent: 5555398 (1996-09-01), Raman
patent: 5568477 (1996-10-01), Galand et al.
patent: 5579301 (1996-11-01), Ganson et al.
patent: 5644784 (1997-07-01), Peek
patent: 5652579 (1997-07-01), Yamada et al.
patent: 5696899 (1997-12-01), Kalwitz
patent: 5742613 (1998-04-01), MacDonald
patent: 5748631 (1998-05-01), Bergantino et al.
patent: 5781549 (1998-07-01), Dai
patent: 5787084 (1998-07-01), Hoang et al.
patent: 5787430 (1998-07-01), Doeringer et al.
patent: 5790539 (1998-08-01), Chao et al.
patent: 5802052 (1998-09-01), Venkataraman
patent: 5802287 (1998-09-01), Rostoker et al.
patent: 5825772 (1998-10-01), Dobbins et al.
patent: 5828653 (1998-10-01), Goss
patent: 5831980 (1998-11-01), Varma et al.
patent: 5842038 (1998-11-01), Williams et al.
patent: 5845081 (1998-12-01), Rangarajan et al.
patent: 5887187 (1999-03-01), Rostoker et al.
patent: 5892922 (1999-04-01), Lorenz
patent: 5898687 (1999-04-01), Harriman et al.
patent: 5909686 (1999-06-01), Muller et al.
patent: 5918074 (1999-06-01), Wright et al.
patent: 5940596 (1999-08-01), Rajan et al.
patent: 5950205 (1999-09-01), Aviani, Jr.
patent: 5987507 (1999-11-01), Creedon et al.
patent: 6011795 (2000-01-01), Varghese et al.
patent: 6018524 (2000-01-01), Turner et al.
patent: 6041053 (2000-03-01), Douceur et al.
patent: 6052683 (2000-04-01), Irwin
patent: 6061351 (2000-05-01), Erimli et al.
patent: 6067574 (2000-05-01), Tzeng
patent: 6119196 (2000-09-01), Muller et al.
patent: 6175902 (2001-01-01), Runaldue et al.
patent: 6185185 (2001-02-01), Bass et al.
patent: 6192051 (2001-02-01), Lipman et al.
patent: 6223172 (2001-04-01), Hunter et al.
patent: 6430527 (2002-08-01), Waters et al.
patent: 6516319 (2003-02-01), Benayoun et al.
patent: 6553002 (2003-04-01), Bremer et al.
patent: 6581106 (2003-06-01), Crescenzi et al.
patent: 6594268 (2003-07-01), Aukia et al.
patent: 6631419 (2003-10-01), Greene
patent: 6658482 (2003-12-01), Chen et al.
patent: 6662184 (2003-12-01), Friedberg
patent: 6826561 (2004-11-01), Cao et al.
Oberhauser et al., Fast Data Structures for Shortest Path Routing: A Comparative Evaluation, Communications 1995. ICC 95 Seattle, Gateway to Globalization, 1995 IEEE International on, vol. 3, Jun. 18-22, 1995, pp.: 1597-1601.

Affiliated with

Also associated with

Rating

Method and apparatus for performing a binary search on an... 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 and apparatus for performing a binary search on an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing a binary search on an... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3609375