Cache replacement based on traversal tracking
US11720501B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Aug 5, 2022 |
| Grant date | Aug 8, 2023 |
| Priority date | — |
| Expiry date | Aug 5, 2042 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F2212/684
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Techniques are disclosed relating to controlling cache replacement. In some embodiments, a computing system performs multiple searches of a data structure, where one or more of the searches traverse multiple links between elements of the data structure. The system may cache, in a traversal cache, traversal information that is usable by searches to skip one or more links traversed by one or more prior searches. The system may store tracking information that indicates a location in the traversal cache at which prior traversal information for a first search is stored. The system may select, based on the tracking information, an entry in the traversal cache for new traversal information generated by the first search. The selection may override a default replacement policy for the traversal cache, e.g., to select the location in the traversal cache to replace the prior traversal information with the new traversal information.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.