# US 2019/0171641 A1 · Single-pass distributed sampling from block-partitioned matrices

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

- Number: US 2019/0171641 A1
- Document ID: US20190171641A1
- Status: Published application
- Kind: A1
- Application number: 16/271,485
- Filed: 2019-02-08
- Published: 2019-06-06
- Earliest claimed: 2015-11-20
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Douglas R. Burdick; Alexandre V. Evfimievski; Berthold Reinwald; Sebastian Schelter
- Web page: https://patentgrep.com/patent/US20190171641A1

## CPC

- G06F 16/2465: {Query processing support for facilitating data mining operations in structured databases}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A computer-implemented method is provided that includes identifying an input dataset formatted as an input matrix, the input matrix including a plurality of rows and a plurality of columns. The computer-implemented method also includes dividing the input matrix into a plurality of input matrix blocks. Further, the computer-implemented method includes distributing the input matrix blocks to a plurality of different machines across a distributed filesystem, and sampling, by at least two of the different machines in parallel, at least two of the input matrix blocks. Finally, the computer-implemented method includes generating at least one sample matrix based on the sampling of the at least two of the input matrix blocks.

## Claims

### Claim 1

A computer-implemented method, comprising:
identifying an input dataset formatted as an input matrix that includes a plurality of rows and a plurality of columns;
dividing the input matrix into a plurality of input matrix blocks;
distributing the input matrix blocks to a plurality of different machines across a distributed filesystem;
sampling, by at least two of the different machines in parallel, at least two of the input matrix blocks; and
generating at least one sample matrix based on the sampling of the at least two of the input matrix blocks.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, wherein sampling the at least two of the input matrix blocks includes, by each of the at least two of the different machines in parallel:
for each of the input matrix blocks stored at the machine:
reading the input matrix block by iterating over partitions of the input matrix block,
for each of the partitions of the input matrix block, determining occurrences of the partition in the at least one sample matrix,
for each occurrence of one of the partitions in the at least one sample matrix, emitting a record.

### Claim 3 (depends on 2)

The computer-implemented method of claim 2, wherein the partitions comprise one of rows and columns.

### Claim 4 (depends on 3)

The computer-implemented method of claim 3, wherein each of the records includes a sample matrix identifier that identifies a particular sample matrix of the at least one sample matrix, a vertical block index, a position, and a partial observation.

### Claim 5 (depends on 4)

The computer-implemented method of claim 4, wherein generating the at least one sample matrix includes:
grouping the emitted records;
sorting each of the groups of the emitted records; and
re-blocking each of the sorted groups of the emitted records.

### Claim 6 (depends on 5)

The computer-implemented method of claim 5, wherein grouping the emitted records comprises grouping the emitted records based on the sample matrix identifiers and the vertical block indices of the emitted records.

### Claim 7 (depends on 6)

The computer-implemented method of claim 6, wherein sorting each of the groups of the emitted records comprises sorting each of the groups of the emitted records based on the positions of the emitted records in the group.

### Claim 8 (depends on 7)

The computer-implemented method of claim 7, wherein the at least one sample matrix is generated based on the re-blocking of the sorted groups of the emitted records.

### Claim 9

A computer program product for performing single-pass distributed sampling from block-partitioned matrices, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to:
identify, by the processor, an input dataset formatted as an input matrix that includes a plurality of rows and a plurality of columns;
divide, by the processor, the input matrix into a plurality of input matrix blocks;
distribute, by the processor, the input matrix blocks to a plurality of different machines across a distributed filesystem, wherein at least two of the different machines sample, in parallel, at least two of the input matrix blocks; and
generate, by the processor, at least one sample matrix based on the sampling of the at least two of the input matrix blocks.

### Claim 10 (depends on 9)

The computer program product of claim 9, wherein sampling the at least two of the input matrix blocks includes, by each of the at least two of the different machines in parallel:
for each of the input matrix blocks stored at the machine:
reading the input matrix block by iterating over partitions of the input matrix block,
for each of the partitions of the input matrix block, determining occurrences of the partition in the at least one sample matrix,
for each occurrence of one of the partitions in the at least one sample matrix, emitting a record.

### Claim 11 (depends on 10)

The computer program product of claim 10, wherein the partitions comprise one of rows and columns.

### Claim 12 (depends on 11)

The computer program product of claim 11, wherein each of the records includes a sample matrix identifier that identifies a particular sample matrix of the at least one sample matrix, a vertical block index, a position, and a partial observation.

### Claim 13 (depends on 12)

The computer program product of claim 12, wherein generating the at least one sample matrix includes:
grouping the emitted records;
sorting each of the groups of the emitted records; and
re-blocking each of the sorted groups of the emitted records.

### Claim 14 (depends on 13)

The computer program product of claim 13, wherein grouping the emitted records comprises grouping the emitted records based on the sample matrix identifiers and the vertical block indices of the emitted records.

### Claim 15 (depends on 14)

The computer program product of claim 14, wherein sorting each of the groups of the emitted records comprises sorting each of the groups of the emitted records based on the positions of the emitted records in the group.

### Claim 16 (depends on 15)

The computer program product of claim 15, wherein the at least one sample matrix is generated based on the re-blocking of the sorted groups of the emitted records.

### Claim 17

A system, comprising:
one or more processors and logic integrated with the processors, executable by the processors, or integrated with and executable by the processors, the logic being configured to:
identify an input dataset formatted as an input matrix that includes a plurality of rows and a plurality of columns;
divide the input matrix into a plurality of input matrix blocks;
distribute the input matrix blocks to a plurality of different machines across a distributed filesystem;
sample, by at least two of the different machines in parallel, at least two of the input matrix blocks; and
generate at least one sample matrix based on the sampling of the at least two of the input matrix blocks.

### Claim 18 (depends on 17)

The system of claim 17, wherein sampling the at least two of the input matrix blocks includes, by each of the at least two of the different machines in parallel:
for each of the input matrix blocks stored at the machine:
reading the input matrix block by iterating over partitions of the input matrix block,
for each of the partitions of the input matrix block, determining occurrences of the partition in the at least one sample matrix,
for each occurrence of one of the partitions in the at least one sample matrix, emitting a record.

### Claim 19 (depends on 18)

The system of claim 18, wherein the partitions comprise one of rows and columns.

### Claim 20 (depends on 19)

The system of claim 19, wherein each of the records includes a sample matrix identifier that identifies a particular sample matrix of the at least one sample matrix, a vertical block index, a position, and a partial observation.
