Scalable retrieval of data entries using an array index or a secondary key
US7505960B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Nov 15, 2005 |
| Grant date | Mar 17, 2009 |
| Priority date | — |
| Expiry date | May 5, 2026 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99932
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Example embodiments improve the lookup times and modification costs of indexing on a dynamically sorted list by using a combination of data structures to determine index values for secondary keys and vice versa. More specifically, exemplary embodiments provide a combination of a binary tree (e.g., a balanced binary tree) with a lookup table (e.g., linear dynamic hash table) to provide scalable retrieval of entries by either an array index or a secondary key. For example, given a key, a hash thereof returns a node placement within a balanced binary tree. This positioning can then be used at runtime to determine an index value for a data record, resulting in a near real-time lookup cost. Also note that modifications, such as reordering, insertions, and deletions, become a function of the nodes depth in the binary tree, rather than a linear function of number of records within the data array.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.