The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
May. 09, 2006
Filed:
Jan. 28, 2003
Deepali Joshi, Pune, IN;
Ajit Shelat, Pune, IN;
Amit Phansalkar, Maharashtra, IN;
Sundar Iyer, Palo Alto, CA (US);
Ramana Kompella, Mountain View, CA (US);
George Varghese, San Diego, CA (US);
Deepali Joshi, Pune, IN;
Ajit Shelat, Pune, IN;
Amit Phansalkar, Maharashtra, IN;
Sundar Iyer, Palo Alto, CA (US);
Ramana Kompella, Mountain View, CA (US);
George Varghese, San Diego, CA (US);
PMC-Sierra, Inc., Santa Clara, CA (US);
Abstract
A combined hash table/bucket trie technique facilitates fast, deterministic, memory-efficient exact match look-ups on extremely large tables. A limited number of hash keys which collide on the same location can be stored in the hash table. If further keys collide on the same location, a bucket trie is formed, the colliding keys are stored in the trie, and trie traversal information is stored in the hash table. Regardless of the number of buckets in the trie, an input key need only be compared with the keys in one bucket to detect a stored key identical to the input key or conclude that no stored key is identical to the input key.