# US 2024/0256513 A1 · Compact Probabilistic Data Structure For Storing Streamed Log Lines

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2024/0256513 A1
- Document ID: US20240256513A1
- Status: Published application
- Kind: A1
- Application number: 18/119,331
- Filed: 2023-03-09
- Published: 2024-08-01
- Earliest claimed: 2023-01-09
- Assignees: Dynatrace LLC
- Applicants: Dynatrace LLC
- Inventors: Julian REICHINGER
- Web page: https://patentgrep.com/patent/US20240256513A1

## CPC

- G06F 16/137: {Hash-based (content-based indexing of textual data G06F16/31)}
- G06F 16/2282: {Tablespace storage structures; Management thereof}
- G06F 16/2228: {Indexing structures}
- G06F 16/2453: Query optimisation
- G06F 16/24573: {using data annotations, e.g. user-defined metadata}
- G06F 11/3006: {where the computing system is distributed, e.g. networked systems, clusters, multiprocessor systems (multiprogramming arrangements G06F9/46; allocation of resources G06F9/50)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A computer-implemented method is presented for storing log data generated in a distributed computing environment. The method includes: receiving a data element from a log line, where the data element is associated with a given computing source at which the log line was produced; applying a hash function to the data element to generate a hash value; updating a listing of computing entities with the given computing source, where entries in the listing of computing entities can identify more than one computing source and each entry in the listing of computing entities specifies a unique set of computing sources; and storing the hash value, along with an address, in a probabilistic data structure, where the address maps the hash value to an entry in the listing of computing entities.

## Claims

### Claim 1

A computer-implemented method for storing log data generated in a distributed computing environment, comprising:
receiving a data element from a log line, where the data element is associated with a given computing source at which the log line was produced;
applying a hash function to the data element to generate a hash value;
updating a listing of computing entities with the given computing source, where entries in the listing of computing entities can identify more than one computing source and each entry in the listing of computing entities specifies a unique set of computing sources; and
storing the hash value, along with an address, in a token map table of a probabilistic data structure, where the address maps the hash value to an entry in the listing of computing entities.

### Claim 2 (depends on 1)

The method of claim 1 wherein each entry in the listing of computing entities further includes a counter, a list of computing entities and a hash value for the list of computing entities, where the counter indicates the number of entries in the probabilistic data structure mapped to a given entry in the listing of computing entities.

### Claim 3 (depends on 2)

The method of claim 2 wherein updating the listing of computing entities with the given computing source further comprises
determining whether the hash value is stored in the probabilistic data structure;
retrieving an entry in the listing of computing entities corresponding to the hash value, where the entry is retrieved in response to a determination that the hash value is stored in the probabilistic data structure;
from the retrieved entry, determining whether the given computing source is in the list of computing entries;
incrementing the counter by one in the retrieved entry in response to a determination that the given computing source is contained in the list of computing entities; and
creating a new entry in the listing of computing entities and setting the counter in the new entry to one in response to a determination that the given computing source is absent from the list of computing entities.

### Claim 4 (depends on 3)

The method of claim 3 wherein creating a new entry in the listing of computing entities includes generating a hash value for the list of computing entities using a commutative hash function.

### Claim 5 (depends on 3)

The method of claim 3 wherein updating the listing of computing entities with the given computing source further comprises adding an entry into the probabilistic data structure for the hash value, where the entry is added in response to a determination that the hash value is absent from the probabilistic data structure.

### Claim 6 (depends on 2)

The method of claim 2 further comprises creating a lookup table having an index, where each entry in the lookup table includes a hash value for the list of computing entities and each entry corresponds to an entry in the listing of computing entities.

### Claim 7 (depends on 6)

The method of claim 6 wherein each entry in the lookup table includes an address, where the address maps the hash value of the entry to an entry in the listing of computing entities.

### Claim 8 (depends on 1)

The method of claim 1 further comprises receiving a data stream, where the data stream includes the log line, and tokenizing the log line to create a plurality of data elements.

### Claim 9 (depends on 1)

The method of claim 1 further comprises encoding the addresses in the token map table and encoding the entries in the listing of computing entities.

### Claim 10 (depends on 1)

The method of claim 1 wherein the hash function is further defined as Minimal Perfect Hash function.

### Claim 11 (depends on 1)

The method of claim 1 wherein the hash function is further defined as a Compressed Static function and the hash function is applied to the data element and the corresponding address.

### Claim 12 (depends on 9)

The method of claim 9 wherein the addresses in the token map table are encoded using entropy encoding.

### Claim 13 (depends on 12)

The method of claim 12 further comprises sorting entries in the token map table by address and according to value of a counter in the listing of computing entities, wherein each entry in the listing of computing entities further includes a counter and the counter indicates the number of entries in the token map table mapped to a given entry in the listing of computing entities.

### Claim 14 (depends on 9)

The method of claim 9 wherein the entries in the listing of computing entities are encoded using a Binary Interpolative Coding method.

### Claim 15 (depends on 9)

The method of claim 9 wherein the probabilistic data structure is stored in a file format having three sequential sections, where a first section of the file format contains a version number and information describing encoding steps applied to the data stored in the probabilistic data structure, a second section of the file format contains header information, and a third section of the file format contains the data stored in the probabilistic data structure.

### Claim 16

A non-transitory computer-readable medium having computer-executable instructions that, upon execution of the instructions by a processor of a computer, cause the computer to perform:
receiving a data element from a log line, where the data element is associated with a given computing source at which the log line was produced;
applying a hash function to the data element to generate a hash value;
updating a listing of computing entities with the given computing source, where entries in the listing of computing entities can identify more than one computing source and each entry in the listing of computing entities specifies a unique set of computing sources; and
storing the hash value, along with an address, in a probabilistic data structure, where the address maps the hash value to an entry in the listing of computing entities.

### Claim 17 (depends on 16)

The non-transitory computer-readable medium of claim 16 wherein each entry in the listing of computing entities further includes a counter, a list of computing entities and a hash value for the list of computing entities, where the counter indicates the number of entries in the probabilistic data structure mapped to a given entry in the listing of computing entities.

### Claim 18 (depends on 17)

The non-transitory computer-readable medium of claim 17 wherein updating the listing of computing entities with the given computing source further comprises
determining whether the hash value is stored in the probabilistic data structure;
retrieving an entry in the listing of computing entities corresponding to the hash value, where the entry is retrieved in response to a determination that the hash value is stored in the probabilistic data structure;
from the retrieved entry, determining whether the given computing source is in the list of computing entries;
incrementing the counter by one in the retrieved entry in response to a determination that the given computing source is contained in the list of computing entities; and
creating a new entry in the listing of computing entities and setting the counter in the new entry to one in response to a determination that the given computing source is absent from the list of computing entities.

### Claim 19 (depends on 18)

The non-transitory computer-readable medium of claim 18 wherein creating a new entry in the listing of computing entities includes generating a hash value for the list of computing entities using a commutative hash function.

### Claim 20 (depends on 18)

The non-transitory computer-readable medium of claim 18 wherein updating the listing of computing entities with the given computing source further comprises adding an entry into the probabilistic data structure for the hash value, where the entry is added in response to a determination that the hash value is absent from the probabilistic data structure.

### Claim 21 (depends on 17)

The non-transitory computer-readable medium of claim 17 wherein the computer-executable instructions further perform creating a lookup table having an index, where each entry in the lookup table includes a hash value for the list of computing entities and each entry corresponds to an entry in the listing of computing entities.

### Claim 22 (depends on 21)

The non-transitory computer-readable medium of claim 21 wherein each entry in the lookup table includes an address, where the address maps the hash value of the entry to an entry in the listing of computing entities.

### Claim 23 (depends on 16)

The non-transitory computer-readable medium of claim 16 wherein the computer-executable instructions further perform receive a data stream, where the data stream includes the log line, and tokenize the log line to create a plurality of data elements.
