Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2007-03-13
2007-03-13
Mizrahi, Diane (Department: 2165)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
10254378
ABSTRACT:
The present invention increases the efficiency of performing longest prefix matching operations by selecting a radix-encoded trie structure optimized with respect to memory cost. The structure is optimized by determining memory costs for retrie structures indexed on different numbers of high-order characters, and then selecting the structure corresponding to the lowest memory cost. The optimization improves performance in IP look-up operations as well as longest-prefix matching operations performed on general alphabets.
REFERENCES:
patent: 5651099 (1997-07-01), Konsella
patent: 5706507 (1998-01-01), Schloss
patent: 5835720 (1998-11-01), Nelson et al.
patent: 5856974 (1999-01-01), Gervais et al.
patent: 5937160 (1999-08-01), Davis et al.
patent: 6000020 (1999-12-01), Chin et al.
patent: 6006259 (1999-12-01), Adelman et al.
patent: 6009436 (1999-12-01), Motoyama et al.
patent: 6029203 (2000-02-01), Bhatia et al.
patent: 6038598 (2000-03-01), Danneels
patent: 6061712 (2000-05-01), Tzeng
patent: 6067545 (2000-05-01), Wolff
patent: 6078954 (2000-06-01), Lakey et al.
patent: 6119153 (2000-09-01), Dujari et al.
patent: 6131067 (2000-10-01), Girerd et al.
patent: 6134588 (2000-10-01), Guenthner et al.
patent: 6138142 (2000-10-01), Linsk
patent: 6182121 (2001-01-01), Wiaschin
patent: 6192417 (2001-02-01), Block et al.
patent: 6195622 (2001-02-01), Altschuler et al.
patent: 6243761 (2001-06-01), Mogul et al.
patent: 6253234 (2001-06-01), Hunt et al.
patent: 6266706 (2001-07-01), Brodnick et al.
patent: 6275496 (2001-08-01), Burns et al.
patent: 6295283 (2001-09-01), Falk
patent: 6304895 (2001-10-01), Schneider et al.
patent: 6330561 (2001-12-01), Cohen et al.
patent: 6343320 (2002-01-01), Fairchild et al.
patent: 6396842 (2002-05-01), Rochberger
patent: 6412008 (2002-06-01), Fields et al.
patent: 6418544 (2002-07-01), Nesbitt et al.
patent: 6425014 (2002-07-01), Aiken et al.
patent: 6470389 (2002-10-01), Chung et al.
patent: 6529508 (2003-03-01), Li et al.
patent: 6532217 (2003-03-01), Alkhatib et al.
patent: 6546424 (2003-04-01), Cucchiara
patent: 6549538 (2003-04-01), Beck et al.
patent: 6553420 (2003-04-01), Karger et al.
patent: 6560610 (2003-05-01), Eatherton et al.
patent: 6563517 (2003-05-01), Bhagwat et al.
patent: 6563823 (2003-05-01), Przygienda et al.
patent: 6570866 (2003-05-01), Murase et al.
patent: 6611873 (2003-08-01), Kanchara
patent: 6628652 (2003-09-01), Chrin et al.
patent: 6640240 (2003-10-01), Hoffman et al.
patent: 6643706 (2003-11-01), Marques et al.
patent: 6714975 (2004-03-01), Aggarwal et al.
patent: 6725261 (2004-04-01), Novaes et al.
patent: 6792575 (2004-09-01), Samaniego et al.
patent: 6876655 (2005-04-01), Afek et al.
patent: 6928485 (2005-08-01), Krishnamurthy et al.
patent: 6970924 (2005-11-01), Chu et al.
patent: 2001/0051927 (2001-12-01), London et al.
patent: 2002/0118682 (2002-08-01), Choe
patent: 2002/0129086 (2002-09-01), Garcia-Lune-Aceves
patent: 2002/0160790 (2002-10-01), Schwartz et al.
patent: 2002/0198961 (2002-12-01), Krishnamurthy et al.
patent: 2003/0012279 (2003-01-01), Chaddha
patent: 2003/0046343 (2003-03-01), Krishnamurthy et al.
patent: 2003/0126200 (2003-07-01), Wolff
patent: 2003/0177175 (2003-09-01), Worley et al.
patent: 2003/0236793 (2003-12-01), Karlsson
patent: 2004/0059830 (2004-03-01), Brown
patent: 2004/0085928 (2004-05-01), Chari et al.
patent: 2004/0088571 (2004-05-01), Jerrim et al.
patent: 2004/0090913 (2004-05-01), Scudder et al.
patent: 2004/0128618 (2004-07-01), Datta
patent: 2004/0153558 (2004-08-01), Gunduc, et al.
O. Buyukkokten, et al., “Efficient Web Browsing on Handheld Devices Using Page and Form Summarization,” ACM Transactions on Inform. Sys., vol. 20, Issue 1, pp. 82-115, 2002.
E. Kirda, “Web Engineering Device Independent Web Services,” Proc. of 23rd Int'l Conf. on Software Engineering, pp. 795-796, Toronto, 2001.
C. Anderson, et al., “Personalizing Web Sites for Mobile Users,” Int'l WWW Conf, Proc. of 16th Int'l conf. on World Wide Web, pp. 569-575, Hong-Kong, 2001.
R. Han, et al., WebSplitter: A Unified XML Framework for Multi-Device Collaborative Web Browsing, Proc. of 2000 ACM Conf. on Computer Supported Cooperative Work, pp. 221-230, Philadelphia, 2000.
U.S. Appl. No. 09/603,154, filed Jun. 23, 2000.
U.S. Appl. No. 09/705,325, filed Nov. 3, 2000.
U.S. Appl. No. 09/705,675, filed Nov. 3, 2000.
U.S. Appl. No. 10/213,587, filed Aug. 7, 2002.
U.S. Appl. No. 10/213,611, filed Aug. 7, 2002.
B. Kristnamurthy & C.E. Williams, Study of Piggyback Cache Validation for Proxy Caches in the WWW, Proc. of USENIX Symposium on Internet Tech. & Systems, Montery, CA Dec. 1997.
Cheung, Gene and McCanne, Steve “Optimal Routing Table Design for IP Address Lookups Under Memory Constraints”, Department of EECS, University of California, Berkeley, CA, 1999 IEEE, pp. 1437-1444.
Buchsbaum Adam Louis
Fowler Glenn Stephen
Krishnamurthy Balachander
Vo Kiem-Phong
Wang Jia
AT&T Corp.
Mizrahi Diane
LandOfFree
Fast prefix matching of bounded strings does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast prefix matching of bounded strings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast prefix matching of bounded strings will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3741385