Updating a perfect hash data structure, such as a multi-dimensional perfect hash data structure, used for high-speed string matching
US8775393B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Mar 1, 2012 |
| Grant date | Jul 8, 2014 |
| Priority date | — |
| Expiry date | Mar 1, 2032 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L63/0245
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A representation of a new rule, defined as a set of a new transition(s), is inserted into a perfect hash table which includes previously placed transitions to generate an updated perfect hash table. This may be done by, for each new transition: (a) hashing the new transition; and (b) if there is no conflict, inserting the hashed new transition into the table. If, however, the hashed new transition conflicts with any of the previously placed transitions, either (A) any transitions of the state associated with the conflicting transition are removed from the table, the hashed new transition is placed into the table, and the removed transitions are re-placed into the table, or (B) any previously placed transitions of the state associated with the new transition are removed, and the transitions of the state associated with the new transition are re-placed into the table.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.