Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2007-10-30
2007-10-30
Wong, Don (Department: 2163)
Data processing: database and file management or data structures
Database design
Data structure types
C370S392000
Reexamination Certificate
active
10731125
ABSTRACT:
Parallel binary searches on lengths using hash tables is described. The parallel search uses more than one search instance. The search instances probe in parallel mutually different contiguous ranges of a search area during each round of searches. After each round, a new search area is defined and one or more search instances are redeployed into the new search area. The search instance for a range of shorter lengths can be redirected to help those of the longer lengths. Due to the help from other search instances, some ranges can be made large without sacrificing the performance. The invention realizes faster address lookups even for longer address lengths.
REFERENCES:
patent: 6018524 (2000-01-01), Turner et al.
patent: 6516319 (2003-02-01), Benayoun et al.
patent: 6810037 (2004-10-01), Kalapathy et al.
patent: 6813620 (2004-11-01), Lin et al.
patent: 6947931 (2005-09-01), Bass et al.
patent: 6996559 (2006-02-01), Beshai
patent: 2004/0044868 (2004-03-01), Guerrero
Selim G. Akl, et al. Parallel Binary Search, IEEE Transactions on Parallel and Distributed Systems vol. 1, No. 2, Apr. 1990.
L.L. Miller, et al. A Parallel Binary Search Processor For Fast Data Retrieval, International Journal of Mini & Microcomputers 12 (1990) No. 1, Anaheim, CA, US., pp. 29-35.
Sarang Dharmapurika, et al., Longest Prefix Matching Using Bloom Filters, SIGCOMM '03, Aug. 25-29, 2003, Karlsruche, Germany, p. 201-212.
Waldvogel, et al., Scalable High Speed IP Routing Lookups, Computer Engineering and Networks Laboratory, 1997.
Miguel A. Ruiz-Sanchez, et al., Survey and Taxonomy of IP Address Lookup Algorithms, IEEE Network Mar./Apr. 2001, pp. 8-23.
Ok-Hyeong Cho, et al., Associative Random Access Machines and Data-Parallel Multiway Binary-Search Join, Future Generation Computer Systems 13 (1997/98) 451-467.
Jaehyung Park, et al., Parallelisation of trie-based longest prefix matching for fast IP address lookups, Electronics Letters, Dec. 5, 2002 vol. 38, No. 25.
Andrei Broder, et al., Using Multiple Hash Functions to Improve IP Lookups, IEEE INFOCOM 2001, pp. 1454-1463.
Alcatel Lucent
Kramer & Amado P.C.
Lie Angela M
Wong Don
LandOfFree
Parallel asymmetric binary search on lengths does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Parallel asymmetric binary search on lengths, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel asymmetric binary search on lengths will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3882313