Cuckoo tree with duplicate key support
US11048757B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Aug 2, 2019 |
| Grant date | Jun 29, 2021 |
| Priority date | — |
| Expiry date | Jan 29, 2040 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/9017
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
An aspect of implementing a Cuckoo tree includes providing a Cuckoo filter table for performing lookups in a Cuckoo tree. The table tracks fingerprints of keys and tablets in which the keys reside. An aspect also includes providing a stash configured to manage duplicate keys in the tree. The stash includes: a key hash table that stores full keys corresponding bucket index references that point to a reverse time ordered list of values corresponding to the full keys; and a value store having buckets with slots for storing the list. An aspect further includes setting a duplicate threshold value in the tree that provides a limit on a number of fingerprints that can exist in a bucket. During a store operation on a key, upon determining the number of existing entries with same fingerprint in target bucket would exceed the threshold, another bucket is selected for the key.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.