# US 2016/0253405 A1 · Algorithm to apply a predicate to data sets

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

- Number: US 2016/0253405 A1
- Document ID: US20160253405A1
- Status: Published application
- Kind: A1
- Application number: 15/030,785
- Filed: 2014-10-21
- Published: 2016-09-01
- Earliest claimed: 2013-10-21
- Assignees: Brytlyt Limited
- Applicants: Brytlyt Limited
- Inventors: RICHARD HEYNS
- Web page: https://patentgrep.com/patent/US20160253405A1

## CPC

- G06F 16/285: {Clustering or classification}
- G06F 16/24544: {Join order optimisation}
- G06F 16/2457: with adaptation to user needs
- G06F 17/18: for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

The present invention relates to a method and apparatus for analysing a pair of data sets with respect to a predicate, the predicate having a predicate criterion, each data set comprising one or more elements sorted according to the predicate criterion. The invention comprises recursive partitioning of the data sets in a parallel manner across multiple computing cores until a base case is reached. The invention is particularly suited for carrying out join, filter and sort operations on large data sets within database management systems.

## Claims

### Claim at position 1

1-30. (canceled)

### Claim 31

A method of analysing a first digital data set and a second digital data set with respect to a predicate, the predicate including a predicate criterion, each of the first and second data sets comprising at least one digital element sorted according to the predicate criterion, wherein the method is adapted to operate on a processing device, the processing device comprising a plurality of computing cores, and the steps of the method comprise:
(a) partitioning each data set into a plurality of sub-groups, wherein each sub-group has an upper boundary element and a lower boundary element;
(b) evaluating the probability of the predicate being satisfied by at least one element of each subgroup of the first data set and at least one element of each sub-group of the second data set, via analysis of the boundary elements of the sub-groups, where each pair of sub-groups evaluated is referred to as a “sub-group pairing”;
(c) classifying a sub-group pairing as a “zero probability sub-group pairing” if there is a zero probability of the predicate being satisfied by the elements of the subgroup pairing;
(d) classifying a sub-group pairing as “non-zero probability sub-group pairing” if there is a non-zero probability of the predicate being satisfied by the elements of the sub-group pairing;
(e) for each non-zero probability sub-group pairing, recursively repeat steps (a) to
(d) until the partitioning step results in base case sub-groups for both data sets, wherein the recursions are distributed among the plurality of cores;
(f) performing a predicate evaluation of the elements within each base case subgroup pairing.

### Claim 32 (depends on 31)

A method as claimed in claim 31 comprising the additional step of generating an output digital data set, wherein the digital data set comprises the base case sub-group pairings where the predicate evaluation is true.

### Claim 33 (depends on 31)

A method as claimed in claim 31 in which steps (a) to (d) are carried out by a single core in a first instance.

### Claim 34 (depends on 33)

A method as claimed in claim 33 in which steps (a) to (d) are carried out by a single core in each recursion.

### Claim 35 (depends on 31)

A method as claimed in claim 31 in which the base case sub-group is defined in relation to the hardware on which the method will be carried out, the nature of the predicate; and
the nature of the data.

### Claim 36 (depends on 31)

A method as claimed in claim 31 comprising the initial step of storing the elements of at least one of the sorted digital data sets in consecutive memory address locations.

### Claim 37 (depends on 31)

A method as claimed in claim 31 in which the step of partitioning comprises identifying the memory location of the upper boundary element and the memory location of the lower boundary element of a sub-group and retrieving the elements stored therein.

### Claim 38 (depends on 31)

A method as claimed in claim 31 in which the processing device is a Graphics Processing Unit (GPU).

### Claim 39 (depends on 31)

A method as claimed in claim 31 implemented across a cluster of computing devices, each computing device comprising a plurality of computing cores.

### Claim 40

An apparatus for analysing digital data sets with respect to a predicate, the predicate including a predicate criterion, the apparatus comprising memory adapted to store a first digital data set and a second digital data set, each data set comprising one or more digital elements sorted according to the predicate criterion; and at least one processing device having a plurality of computing cores; the apparatus being adapted to:
(a) partition each data set into a plurality of sub-groups, each sub-group having an upper boundary element and a lower boundary element;
(b) for each sub-group of the first data set, evaluate the probability of the predicate being satisfied by at least one element of that sub-group and at least one element of each sub-group of the second data set by analysis of the boundary elements of the sub-groups, where each pair of sub-groups evaluated is referred to as a sub-group pairing;
(c) classify a sub-group pairing as a zero probability sub-group pairing if there is a zero probability of the predicate being satisfied by the elements of the subgroup pairing;
(d) classify a sub-group pairing as non-zero probability sub-group paring if there is a non-zero probability of the predicate being satisfied by the elements of the sub-group pairing;
(e) for each non-zero probability sub-group pairing, recursively repeat steps (a) to
(d) until the partitioning step results in base case sub-groups for both data sets, wherein the recursions are distributed among the plurality of cores;
(f) perform a predicate evaluation of the elements within each base case sub- group pairing.

### Claim 41 (depends on 40)

An apparatus as claimed in claim 40 further adapted to generate an output digital data set comprising the base case sub-group pairings where the predicate evaluation is true.

### Claim 42 (depends on 40)

An apparatus as claimed in claim 40 wherein the elements of at least one of the sorted digital data sets are stored in the memory in consecutive memory address locations.

### Claim 43 (depends on 40)

An apparatus as claimed in claim 40 in which the processing device is a Graphics Processing Unit (GPU).

### Claim 44 (depends on 40)

An apparatus as claimed in claim 40 in which the processing device comprises a Single Program Multiple Data (SPMD) parallel computing architecture.

### Claim 45 (depends on 31)

Computer code which, when executed by a processing device comprising a plurality of computing cores, causes the processing device to perform the method as set out in claim 31.
