Indexation by transposition of matrix of large dimension
AssigneeFrance Telecom
InventorEdmond Lassalle
Life of this patent
Estimating the term…
Abstract
A data processing system comprises a first memory and a second memory including a sparse direct matrix comprising full boxes storing a data item and a column index and addressable consecutively. A module dimensions a transposed matrix, by reading row by row column indices of the direct matrix so as to reserve boxes of the transposed matrix in the second memory. A module identifies in the first memory a submatrix of reserved boxes of the transposed matrix and occupying a memory space smaller than the first memory. A module fills in the boxes of the submatrix according to the column indices read from the boxes of the direct matrix, and transfers the submatrix into the second memory to fill-in the transposed matrix.
Claims7
A method of indexation in a data processing system that comprises a first memory and a second memory including a sparse direct matrix that only has full boxes and arises from a matrix of full and empty boxes, said boxes of said direct matrix each storing an associated data item and an associated column index, said method including the steps of:
- dimensioning row by row a matrix which is the transpose of said direct matrix, by reading row by row column indices of said direct matrix so as to reserve as many boxes for each row of said transposed matrix in said second memory as a number of occurrences of a respective column index in said direct matrix;
- identifying in said first memory a submatrix of reserved boxes forming together with other consecutive submatrices said transposed matrix, each submatrix occupying a memory space smaller than the size of said first memory;
- filling in the boxes of said submatrix in said first memory with data associated with column indices read from said boxes of said direct matrix in said second memory and that are identical to row indices of said transposed matrix that relate to rows included in said submatrix;
- transferring the filled-in submatrix from said first memory to said second memory so as to fill in said transposed matrix;
- and
- iteratively repeating the preceding three steps for each of the submatrices of said transposed matrix.
A data processing system for the implementation of a method of indexation, said data processing system including:
- a first memory and a second memory including a sparse direct matrix that only has full boxes and arises from a matrix of full and empty boxes, said boxes of said direct matrix storing an associated data item and an associated column index;
- a processor arrangement for:
- (a) dimensioning row by row a matrix which is the transpose of the direct matrix, by reading row by row column indices of said direct matrix so as to reserve as many boxes for each row of said transposed matrix in the second memory as a number of occurrences of a respective column index in said direct matrix;
- (b) identifying in said first memory a submatrix of reserved boxes forming together with other consecutive submatrices said transposed matrix, each submatrix occupying a memory space smaller than the size of said first memory;
- and
- (c) filling in the boxes of said submatrix in said first memory with data associated with column indices read from said boxes of said direct matrix in said second memory and that are identical to row indices of the transposed matrix that relate to rows included in said submatrix so as to transfer the filled-in submatrix from said first memory to said second memory.
A storage element storing a computer program adapted to be executed on a data processing system that comprises a first memory and a second memory including a sparse direct matrix that only has full boxes and arises from a matrix of full and empty boxes, said boxes of said direct matrix each storing an associated data item and an associated column index, said computer program comprising instructions suitable for the implementation of the method of indexation by matrix transposition which, when the program is loaded and executed on said data processing system, carry out the steps of:
- dimensioning row by row a matrix which is the transpose of said direct matrix, by reading row by row column indices of said direct matrix so as to reserve as many boxes for each row of said transposed matrix in said second memory as a number of occurrences of a respective column index in said direct matrix;
- identifying in said first memory a submatrix of reserved boxes forming together with other consecutive submatrices said transposed matrix, each submatrix occupying a memory space smaller than the size of said first memory;
- filling in the boxes of said submatrix in said first memory with data associated with column indices read from said boxes of said direct matrix in said second memory and that are identical to row indices of said transposed matrix that relate to rows included in said submatrix;
- transferring the filled-in submatrix from said first memory to said second memory so as to fill in said transposed matrix;
- and
- iteratively repeating the preceding three steps for each of the submatrices of said transposed matrix.
Dependencies are inferred from the claim text.