Coded data generation or conversion – Digital code to digital code converters – Coding by table look-up techniques
Reexamination Certificate
2006-03-28
2006-03-28
Jeanglaude, Jean Bruner (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
Coding by table look-up techniques
C341S050000, C341S051000
Reexamination Certificate
active
07019674
ABSTRACT:
A content-based information retrieval architecture is herein disclosed that can achieve correct and predictable high speed lookups while taking advantage of inexpensive conventional memory components. A content-based information retrieval architecture is herein disclosed that can achieve high speed lookups with a constant query time while taking advantage of inexpensive conventional memory components. In accordance with an embodiment of the invention, the architecture comprise a hashing module, a first table of encoded values, a second table of lookup values, and a third table of associated input values. The input value is hashed a number of times to generate a plurality of hashed values, the hashed values corresponding to locations of encoded values in the first table. The encoded values obtained from an input value encode an output value such that the output value cannot be recovered from any single encoded value.
REFERENCES:
patent: 5371499 (1994-12-01), Graybill et al.
patent: 6087967 (2000-07-01), Budnik et al.
patent: 6160891 (2000-12-01), Al-Salqan
patent: 6236341 (2001-05-01), Dorward et al.
patent: 6611213 (2003-08-01), Bentley et al.
patent: 6624762 (2003-09-01), End, III
patent: 2002/0143755 (2002-10-01), Wynblatt et al.
patent: 2003/0198224 (2003-10-01), Lee et al.
patent: 2005/0187898 (2005-08-01), Chazelle et al.
Cormen, T.H. et al., “Introduction to Algorithms” Second Edition—Chapter 11, Copyright 2001 by The Massachusetts Institute of Technology, month unknown.
Pagh, R. et al., “Cuckoo Hashing”, Journal of Algorithms, 51, 2004, month unknown.
Bloom, B.H., “Space/Time Trade-Offs in Hash Coding in Allowable Errors”, Communications of the ACM, vol. 13, No. 7, Jul. 1970.
Brodnik, A. et al., “Membership in Constant Time and Almost-Minimum Space”, SIAM J. Comput., vol. 28, No. 5, 1999 Society for Industrial and Applied Mathematics, no month.
Buhrman, H. et al., “Are Bitvectors Optimal?”, Proc. 32nd STOC, 2000, month unknown.
Capalbo, M. et al., “Randomness Conductors and Constant-Degree Lossless Expanders”, Proc. 34nd STOC, 2002, month unknown.
Cohen, S. et al., “Spectral Bloom Filters”, SIGMOD Jun. 9-12, 2003.
Fan, L., et al., “Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol”, IEEE/ACM Transaction Networking, vol. 8, No. 3, Jun. 2000.
Fredman, M.L. et al., “Storing a Sparse Table with O(1) Worse Case Access”, Journal of the Association for Computing Machinery, vol. 31, No. 3, Jul. 1984.
Kleitman, D.J. et al., “Families of k-Independent Sets”, Discrete Mathematics 6, 1973, month unknown.
Luby, M., “LT Codes”, Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002, month unknown.
Mitzenmacher, M., “Compressed Bloom Filters”, IEEE/ACM Transactions on Networking, vol. 10, No. 5, Oct. 2002.
Razborov, A.A., “Applications of Matrix Methods to the Theory of Lower Bounds in Computational Complexity”, Combinatorica 10(1), 1990, month unknown.
Rhea, S.C. et al., “Probabilistic Location and Routing”, IEEE Infocome 2002, month unknown.
Sipser, M. et al., “Expander Codes”, IEEE Transactions on Information Theory, vol. 42, No. 6, Nov. 1996.
Kobayashi, M. et al., “A Longest Prefix Match Search Engine for Multi-Gigabit IP Processing”, IEEE, 2000, month unknown.
Waldvogel, M. et al., “Scalable High Speed IP Routing Lookups”, SIGCOMM, 1997, month unknown.
Taylor, D.E. et al., “Scalable IP Lookup for Programmable Routers”, IEEE 2002, month unknown.
Dharmapurikar, S. et al., “Longest Prefix Matching Using Bloom Filters”, SIGCOMM 2003, month unknown.
Mansour, M. et al., “FPGA-Based Internet Protocol Version 6 Router”, no date.
Lampson, B. et al., “IP Lookups Using Multiway and Multicolumn Search”, IEEE/ACM Transactions on Networking, vol. 7, No. 3, Jun. 1999.
Prakash, A. et al., “A Middle Ground Between CAMs and DAGs for High-Speed Packet Classification”, Proceedings of the 10th Symposium on High Performance Interconnects Hot Interconnects 2002, no month.
Liu, H., “Reducing Routing Table Size Using Ternary-Cam”, Hot Interconnects 9, 2001, month unknown.
Broder, A. et al., “A Survey: Network Applications of Bloom Filters”, Proceedings of the 40th Annual Allerton Conference, Oct. 2002.
Ashar Pranav
Cadambi Srihari
Chakradhar Srimat T.
Kilian Joseph
Jeanglaude Jean Bruner
Lee Benjamin S.
NEC Laboratories America, Inc.
LandOfFree
Content-based information retrieval architecture does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Content-based information retrieval architecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Content-based information retrieval architecture will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3578221