Electrical computers and digital processing systems: memory – Address formation – Address mapping
Patent
1994-06-30
1998-11-24
Chan, Eddie P.
Electrical computers and digital processing systems: memory
Address formation
Address mapping
711 1, 711201, 370392, 370396, 370397, G06F 1206
Patent
active
058422242
ABSTRACT:
To provide for fast access times with very large key fields, an associative memory utilizes a location addressable memory and look up tables to generate from a key an address in memory storing an associated record. The look up tables, stored in a memory, are constructed with the aid of arithmetic data compression methods to create a near perfect hashing of the keys. For encoding into the look up table, keys are divided into a string of symbols. Each symbol is assigned an index value, such that a modulo sum of index values for symbols of a particular key is a unique value that is used as an address to the memory storing the record associated with that key.
REFERENCES:
patent: 3979733 (1976-09-01), Fraser
patent: 3987251 (1976-10-01), Texier et al.
patent: 3988544 (1976-10-01), Texier et al.
patent: 4168401 (1979-09-01), Molrone et al.
patent: 4494230 (1985-01-01), Turner
patent: 4547877 (1985-10-01), Lehman et al.
patent: 4603416 (1986-07-01), Servel et al.
patent: 4661951 (1987-04-01), Segarra
patent: 4742511 (1988-05-01), Johnson
patent: 4865432 (1989-09-01), Andros et al.
patent: 4875208 (1989-10-01), Furuhashi et al.
patent: 4887265 (1989-12-01), Felix
patent: 4922503 (1990-05-01), Leone
patent: 4953162 (1990-08-01), Lyons et al.
patent: 5164943 (1992-11-01), Waggoner
Cerone, et al., "Minimal and Almost Minimal Perfect Hash Function Search with Applications to Natural Language Lexicon Design," vol. 9, No. 1, p. 215, 1983.
Wilnai, Dan et al., "Speed Lan-Address Filtering With CAMS", Electronic Design, Apr. 26, 1990, pp. 75-90.
"LAN Interperability Study of Protocols Needed for Distributed Command and Control" by W.L. Eldon, A.L. Miller, S.L. Morgan, and B.A. Romanzo Rome Air Development Center DTIC AD-A154-003 (Mar. 1985).
"C3I Information Systems Internetwork Study" by T.C. Bartee, O.P. Buneman, J.M. McQuillan, and S.T. Walker Institute for Defense Analysis (Apr. 1984).
"Internetwork Naming, Addressing, and Routing" by J.F. Shoch IEEE Proceedings of COMPCON (1978).
"Addressing Problems in Multi-network Systems" C.A. Sunshine IEEE Proc. INFOCOM (1982).
"Multi-cast Routing in Internetworks and Extended LANs" by S.E. Deering ACM SIGCOMM (1988).
"The Landmark Hierarchy for Routing in very large Systems" by Paul F. Tsuchiya ACM SIGCOMM '88 Symposium on Communications Architectures & Protocols Stanford, California (Aug. 1988).
"A trade-Off between Space and Efficiency for Routing Tables" by David Peleg and Eli Upfal Journal of the ACM (Jul. 1989).
"Dynamic Hashing Schemes" by R.J. Enbody and H.C. Du in ACM Computing Surveys vol. 20 No. 2 (Jun. 1988).
"Hashing for Dynamic and Static Internal Tables" by T.G. Lewis and C.R. cook in IEEE Computer Magazine (Oct. 1988).
"Should Tables be Sorted" by Abdrew Chi-Chih Yao Journal of the ACM (Jul. 1981).
"Storing a Table with O(1) Worst Case Access Time" by M.L. Fredman, J. Komolos, and E. Szemeredi Journal of the ACM (Jul. 1984).
"Hashing in Practice, Analysis of Hashing and Universal Hashing" by M.V. Ramakrishna Proceedings of ACM SIGMOD (Jun. 1988).
"Linear Hashing with Overflow-Handling" by Linear Probing by P.A. Larson in ACM Transactions on Database Systems (Mar. 1985).
"Analysis of Dynamic Hashing with Deferred Splitting" by E. Veklerov in ACM Transactions on Database Systems (Mar. 1985).
"Partial-Match Retrieval Using Hashing and Descriptors" by K. Ramamohanarao, J.W. Lloyd, and J.A. Thom in ACM Transactions on Database Systems (Dec. 1983).
"New File Organization Based on Dynamic Hashing" by Michael Scholl in ACM Transactions on Database Systems (Mar. 1981).
"Analysis of Uniform Hashing" by Per-Ake Larson Journal of the ACM (Oct. 1983).
"Bounded Index Exponential Hashing" by David B. Lomet ACM Transactions on Database Systems (Mar. 1983).
"Reciprocal Hashing: A Method for Generating Minimal Perfect Hashing Functions" G. Jaeschke Communications of the ACM (Dec. 1981).
"Dynamic Hash Table" by Per-Ake Larson Communications of the ACM (Apr. 1988).
"Data Compression" by D.A. Lelewer and D.S. Hirschberg, ACM Computing Surveys (Sep. 1987).
"Arithmetic Coding for Data Compressioin" by I.H. Whitten, R.H. Neal, and J.G. Cleary, Communications of the ACM Jun. 1987.
"A Working-Set Coprocessor" by Milan Milenkovic, SMU Technical Report (Mar. 1989).
"An Adaptive Dependency Source Model for Data Compression" by David M. Ambrahamson, Communications of the ACM (Jan. 1989).
"A Multiplication-Free Multi-alphabet Arithmetic Code" by J. Rissanen and K. M. Mohiuddin IEEE Transactions on Communications (Feb. 1989).
Cercone, et al., "Minimal and Almost Minimal Perfect Hash Function Search with Applications to Natural Language Lexicon Design," Marks with Applications, vol. 9, No. 1, p. 215, 1983.
Pearson, "Fast Hashing of Variable Length Text Strings," Communications of the ACm, vol. 33, No. 6, p. 677, Jun., 1990.
Larson, et al., "File Organization: Implementation of a Method Guaranteeing Retrieval in One Access," Communications of the ACM, vol. 27, No. 7, p. 670 Jul., 1984.
Chan Eddie P.
Hubbard Marc A.
Nguyen T. V.
LandOfFree
Method and apparatus for source filtering data packets between n 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 source filtering data packets between n, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for source filtering data packets between n will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1715331