Data structure using a tree bitmap and method for rapid classification of data in a database
US6728732B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Feb 18, 2003 |
| Grant date | Apr 27, 2004 |
| Priority date | — |
| Expiry date | Feb 18, 2023 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99948
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
In random access memory, a data structure of trie elements of compact and fixed size is provided in order to store elements of a hierarchical prefix-type data structure such that the data structure can be searched quickly. A trie element according to the invention contains the data in one stride of the search through the prefix-type data structure. According to the invention, the trie element may contain 1) a description of the tree structure associated with the trie element, 2) a description of the links to the next level trie element, and 3) a pointer to the storage location of the next level trie element. The prefix structure has a first level trie element, and at least one second level trie element. The trie element includes a first code of the first level trie element describing the prefixes contained in the first level trie element, a second code specifying paths between the first level trie element and all children of the first level trie element (such children are second level trie elements), and a pointer for linking the first level trie element with one of the second level trie elements. Each of the first and second trie elements and the pointer are of a fixed, predefined…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.