# US 2016/0259826 A1 · Parallelized Hybrid Sparse Matrix Representations for Performing Personalized Content Ranking

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

- Number: US 2016/0259826 A1
- Document ID: US20160259826A1
- Status: Published application
- Kind: A1
- Application number: 14/635,007
- Filed: 2015-03-02
- Published: 2016-09-08
- Earliest claimed: 2015-03-02
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Emrah Acar; Rajesh R. Bordawekar; Michele M. Franceschini; Luis A. Lastras-Montano; Haifeng Qian; Livio B. Soares
- Web page: https://patentgrep.com/patent/US20160259826A1

## CPC

- G06F 16/9536: Search customisation based on social or collaborative filtering
- G06F 16/9535: Search customisation based on user profiles and personalisation
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Mechanisms are provided for performing a matrix operation. A processor is configured to perform hybrid compressed representation matrix operations on an input matrix that comprises zero value and non-zero value entries. A first compressed representation data structure corresponding to the input matrix, and a second compressed representation data structure are obtained, each utilizing a different format for representing the non-zero value entries of the input matrix. A matrix operation is iteratively executed on the input matrix using the first compressed representation data structure and the second compressed representation data structure. The first compressed representation data structure is utilized for a first subset of iterations of the matrix operation and the second compressed representation data structure is utilized for a second subset of iterations of the matrix operation different from the first subset of iterations.

## Claims

### Claim 1

A method, in a data processing system comprising a processor and a memory, for performing a matrix operation, the method comprising:
configuring the processor of the data processing system to perform hybrid compressed representation matrix operations on an input matrix;
receiving, by the processor, the input matrix, wherein the input matrix comprises zero value and non-zero value entries;
obtaining, by the processor, a first compressed representation data structure corresponding to the input matrix, wherein the first compressed representation data structure represents the non-zero value entries of the input matrix in a first compressed format;
obtaining, by the processor, a second compressed representation data structure corresponding to the input matrix, wherein the second compressed representation data structure represents the non-zero value entries of the input matrix in a second compressed format different from the first compressed format; and
iteratively executing, by the processor, a matrix operation on the input matrix using the first compressed representation data structure and the second compressed representation data structure, wherein the first compressed representation data structure is utilized for a first subset of iterations of the matrix operation and the second compressed representation data structure is utilized for a second subset of iterations of the matrix operation different from the first subset of iterations.

### Claim 2 (depends on 1)

The method of claim 1, wherein the first compressed representation data structure is a Compact Sparse Column (CSC) compressed representation data structure and the second compressed representation data structure is a Compact Sparse Row (CSR) compressed representation data structure.

### Claim 3 (depends on 2)

The method of claim 2, wherein the first subset of iterations in which the CSC compressed representation data structure is utilized comprises the first two iterations of the matrix operation.

### Claim 4 (depends on 3)

The method of claim 3, wherein the second subset of iterations in which the CSR compressed representation data structure is utilized comprises all iterations subsequent to the second iteration of the matrix operation.

### Claim 5 (depends on 1)

The method of claim 1, wherein iteratively executing the matrix operation on the input matrix using the first compressed representation data structure and the second compressed representation data structure, further comprises:
determining a sparsity of an input vector for a current iteration;
determining if the sparsity of the input vector has a predetermined relationship to a threshold sparsity value; and
selecting either the first compressed representation data structure or the second compressed representation data structure based on results of determining if the sparsity of the input vector has the predetermined relationship to the threshold sparsity value.

### Claim 6 (depends on 5)

The method of claim 5, wherein the predetermined relationship comprises the sparsity of the input vector indicating the input vector has a sparsity less than a threshold sparsity value, and wherein in response to determining that the predetermined relationship does not exist, selecting the first compressed representation data structure, and in response to determining that the predetermined relationship does exist, selecting the second compressed representation data structure.

### Claim 7 (depends on 1)

The method of claim 1, wherein entries in the input matrix comprise indicators of relationships between concepts found in a corpus of information, and wherein the input vector comprises elements for which related concepts are to be identified by the matrix operation.

### Claim 8 (depends on 1)

The method of claim 1, wherein iteratively executing the matrix operation on the input matrix using the first compressed representation data structure and the second compressed representation data structure, further comprises utilizing a plurality of worker threads to execute portions of the second subset of iterations in parallel.

### Claim 9 (depends on 8)

The method of claim 8, wherein each worker thread in the plurality of worker threads executes a partial matrix vector multiplication operation of an allocated row of the input matrix based on the input vector, and wherein results of each of the partial matrix vector multiplication operations are combined to generate a final result of the matrix operation.

### Claim 10 (depends on 1)

The method of claim 1, wherein the data processing system implements a question and answer (QA) system, and wherein the input vector represents features of a natural language question input to the QA system and the input matrix represents a graph of concepts and relationships between concepts present in one or more electronic documents of a corpus of electronic documents.

### Claim 11

A computer program product comprising a computer readable storage medium having a computer readable program stored therein, wherein the computer readable program, when executed on a computing device, causes the computing device to:
receive an input matrix, wherein the input matrix comprises zero value and non-zero value entries;
obtain a first compressed representation data structure corresponding to the input matrix, wherein the first compressed representation data structure represents the non-zero value entries of the input matrix in a first compressed format;
obtain a second compressed representation data structure corresponding to the input matrix, wherein the second compressed representation data structure represents the non-zero value entries of the input matrix in a second compressed format different from the first compressed format; and
iteratively execute a matrix operation on the input matrix using the first compressed representation data structure and the second compressed representation data structure, wherein the first compressed representation data structure is utilized for a first subset of iterations of the matrix operation and the second compressed representation data structure is utilized for a second subset of iterations of the matrix operation different from the first subset of iterations.

### Claim 12 (depends on 11)

The computer program product of claim 11, wherein the first compressed representation data structure is a Compact Sparse Column (CSC) compressed representation data structure and the second compressed representation data structure is a Compact Sparse Row (CSR) compressed representation data structure.

### Claim 13 (depends on 12)

The computer program product of claim 12, wherein the first subset of iterations in which the CSC compressed representation data structure is utilized comprises the first two iterations of the matrix operation.

### Claim 14 (depends on 13)

The computer program product of claim 13, wherein the second subset of iterations in which the CSR compressed representation data structure is utilized comprises all iterations subsequent to the second iteration of the matrix operation.

### Claim 15 (depends on 11)

The computer program product of claim 11, wherein the computer readable program causes the computing device to iteratively execute the matrix operation on the input matrix using the first compressed representation data structure and the second compressed representation data structure at least by:
determining a sparsity of an input vector for a current iteration;
determining if the sparsity of the input vector has a predetermined relationship to a threshold sparsity value; and
selecting either the first compressed representation data structure or the second compressed representation data structure based on results of determining if the sparsity of the input vector has the predetermined relationship to the threshold sparsity value.

### Claim 16 (depends on 15)

The computer program product of claim 15, wherein the predetermined relationship comprises the sparsity of the input vector indicating the input vector has a sparsity less than a threshold sparsity value, and wherein in response to determining that the predetermined relationship does not exist, the first compressed representation data structure is selected, and in response to determining that the predetermined relationship does exist, the second compressed representation data structure is selected.

### Claim 17 (depends on 11)

The computer program product of claim 11, wherein entries in the input matrix comprise indicators of relationships between concepts found in a corpus of information, and wherein the input vector comprises elements for which related concepts are to be identified by the matrix operation.

### Claim 18 (depends on 11)

The computer program product of claim 11, wherein the computer readable program causes the computing device to iteratively execute the matrix operation on the input matrix using the first compressed representation data structure and the second compressed representation data structure, at least by utilizing a plurality of worker threads to execute portions of the second subset of iterations in parallel.

### Claim 19 (depends on 11)

The computer program product of claim 11, wherein the computing device implements a question and answer (QA) system, and wherein the input vector represents features of a natural language question input to the QA system and the input matrix represents a graph of concepts and relationships between concepts present in one or more electronic documents of a corpus of electronic documents.

### Claim 20

An apparatus comprising:
a processor; and
a memory coupled to the processor, wherein the memory comprises instructions which, when executed by the processor, configure the processor to perform cluster-based matrix reordering of an input matrix and to:
receive an input matrix, wherein the input matrix comprises zero value and non-zero value entries;
obtain a first compressed representation data structure corresponding to the input matrix, wherein the first compressed representation data structure represents the non-zero value entries of the input matrix in a first compressed format;
obtain a second compressed representation data structure corresponding to the input matrix, wherein the second compressed representation data structure represents the non-zero value entries of the input matrix in a second compressed format different from the first compressed format; and
iteratively execute a matrix operation on the input matrix using the first compressed representation data structure and the second compressed representation data structure, wherein the first compressed representation data structure is utilized for a first subset of iterations of the matrix operation and the second compressed representation data structure is utilized for a second subset of iterations of the matrix operation different from the first subset of iterations.
