System for indexing collections of structured objects that provides strong multiversioning semantics
US9400816B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Dec 30, 2013 |
| Grant date | Jul 26, 2016 |
| Priority date | — |
| Expiry date | Oct 12, 2034 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/2474
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A multiversioned position-space indexing system is disclosed. The system includes data structures for maintaining a multiversioned position space including a multi-versioned filter merge list which represents many versions of a changing position space in a very compact form and a position shift map which describes how to translate stored positions in many different log-structured merge tree layers into logical positions at a particular timestamp. Each log-structured merge tree layer can be divided into two sublayers: a final sublayer and a correction sublayer. The final sublayer contains index entries added after the layer's start timestamp and remain live as of the layer's final timestamp as well as deletion makers for index entries that were inserted before the layer's start timestamp, but deleted before the layer's final timestamp. The correction layer contains index entries that were both created and deleted between the start and end timestamps of the layer.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.