Fast, deterministic exact match look-ups in large tables
US7043494B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Jan 28, 2003 |
| Grant date | May 9, 2006 |
| Priority date | — |
| Expiry date | Mar 1, 2024 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99945
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.