Invention Grant
- Patent Title: Data structure based on event compaction and read-offsets
-
Application No.: US17644426Application Date: 2021-12-15
-
Publication No.: US11803566B2Publication Date: 2023-10-31
- Inventor: Robert Fink , James Baker , Mark Elliot
- Applicant: Palantir Technologies Inc.
- Applicant Address: US CO Denver
- Assignee: Palantir Technologies Inc.
- Current Assignee: Palantir Technologies Inc.
- Current Assignee Address: US CO Denver
- Agency: Knobbe, Martens, Olson & Bear, LLP
- Priority: EP 216132 2020.12.21
- Main IPC: G06F16/25
- IPC: G06F16/25 ; G06F16/23 ; G06F16/2457

Abstract:
Disclosed herein is a data structure which includes a sequence of events, each event associated with a sequence number indicating a temporal position of an event within the sequence of events; one or more read-offsets, each read-offset associated with a consumer, wherein each read-offset indicates a sequence number up to which a consumer has read events within the sequence of events; and at least one snapshot which represents events with sequence numbers smaller than the smallest read-offset in a compacted form. Disclosed herein is also a computer-implemented method of maintaining the data structure. Disclosed herein is a computer-implemented method, wherein the method is performed on a sequence of events accessible by a plurality of consumers, each event associated with a sequence number indicating a temporal position of an event within the sequence of events, each consumer associated with a read-offset indicating the sequence number up to which the consumer has read events within the sequence of events, the method includes determining a smallest read-offset of all read-offsets; compacting events with sequence numbers smaller than the smallest read-offset into a snapshot; and replacing the events with sequence numbers smaller than the smallest read-offset with the snapshot. Disclosed herein are corresponding computer-readable media and computing systems.
Public/Granted literature
- US20220197921A1 DATA STRUCTURE BASED ON EVENT COMPACTION AND READ-OFFSETS Public/Granted day:2022-06-23
Information query