Package org.apache.sysds.runtime.data
Class SparseBlockCOO
- java.lang.Object
- 
- org.apache.sysds.runtime.data.SparseBlock
- 
- org.apache.sysds.runtime.data.SparseBlockCOO
 
 
- 
- All Implemented Interfaces:
- Serializable
 
 public class SparseBlockCOO extends SparseBlock SparseBlock implementation that realizes a traditional 'coordinate matrix' representation, where the entire sparse block is stored as triples in three arrays: row indexes, column indexes, and values, where row indexes and colunm indexes are sorted in order to allow binary search. This format is very memory efficient for ultra-sparse matrices, allows fast incremental construction but has performance drawbacks for row-major access through our sparse block abstraction since there is no constant-time random access to individual rows. Similar to CSR, the nnz is limited to Integer.MAX_VALUE. In contrast to COO matrix formats with three arrays, we use 1+#dims arrays to represent the values and indexes of all dimensions.- See Also:
- Serialized Form
 
- 
- 
Nested Class Summary- 
Nested classes/interfaces inherited from class org.apache.sysds.runtime.data.SparseBlockSparseBlock.Type
 
- 
 - 
Constructor SummaryConstructors Constructor Description SparseBlockCOO(int rlen)SparseBlockCOO(int rlen, int capacity)SparseBlockCOO(SparseBlock sblock)Copy constructor sparse block abstraction.SparseBlockCOO(SparseRow[] rows, int nnz)Copy constructor old sparse row representation.
 - 
Method SummaryAll Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description booleanadd(int r, int c, double v)Add a value to a matrix cell (r,c).voidallocate(int r)Allocate the underlying data structure holding non-zero values of row r if necessary.voidallocate(int r, int nnz)Allocate the underlying data structure holding non-zero values of row r if necessary, w/ given size.voidallocate(int r, int ennz, int maxnnz)Allocate the underlying data structure holding non-zero values of row r w/ the specified estimated nnz and max nnz.voidappend(int r, int c, double v)Append a value to the end of the physical representation.booleancheckValidity(int rlen, int clen, long nnz, boolean strict)Validate the correctness of the internal data structures of the different sparse block implementations.voidcompact(int r)Re-allocate physical row if physical size exceeds logical size plus resize factor.voiddeleteIndexRange(int r, int cl, int cu)Deletes all non-zero values of the given column range [cl,cu) in row r.static longestimateSizeInMemory(long nrows, long ncols, double sparsity)Get the estimated in-memory size of the sparse block in COO with the given dimensions w/o accounting for overallocation.SparseRowget(int r)Get values of row r in the format of a sparse row.doubleget(int r, int c)Get value of matrix cell (r,c).Iterator<IJV>getIterator()Get a non-zero iterator over the entire sparse block.Iterator<IJV>getIterator(int ru)Get a non-zero iterator over the partial sparse block [0,ru).Iterator<IJV>getIterator(int rl, int ru)Get a non-zero iterator over the subblock [rl, ru).int[]indexes()Get raw access to underlying array of column indices For use in GPU codeint[]indexes(int r)Get the sorted array of column indexes of all non-zero entries in row r.booleanisAllocated(int r)Indicates if the underlying data structure for a given row is already allocated.booleanisContiguous()Indicates if the underlying data structures returned by values and indexes are contiguous arrays, which can be exploited for more efficient operations.booleanisEmpty(int r)Get information if row r is empty, i.e., does not contain non-zero values.booleanisThreadSafe()Indicates if the underlying implementation allows thread-safe row updates if concurrent threads update disjoint rows.intnumRows()Get the number of rows in the sparse block.intpos(int r)Get the starting position of row r in the indexes/values arrays returned by indexes(r) and values(r).intposFIndexGT(int r, int c)Get position of first column index greater than column c in row r.intposFIndexGTE(int r, int c)Get position of first column index greater than or equal column c in row r.intposFIndexLTE(int r, int c)Get position of first column index lower than or equal column c in row r.voidreset()Clears the sparse block by deleting non-zero values.voidreset(int ennz, int maxnnz)Clears the sparse block by deleting non-zero values.voidreset(int r, int ennz, int maxnnz)Clears row r of the sparse block by deleting non-zero values.int[]rowIndexes()Get raw access to underlying array of row indices For use in GPU codebooleanset(int r, int c, double v)Set the value of a matrix cell (r,c).voidset(int r, SparseRow row, boolean deep)Set the values of row r to the given sparse row.voidsetIndexRange(int r, int cl, int cu, double[] v, int[] vix, int vpos, int vlen)Sets a sparse array of non-zeros values and indexes into the column range [cl,cu) in row r.voidsetIndexRange(int r, int cl, int cu, double[] v, int vix, int vlen)Sets a dense array of non-zeros values into the column range [cl,cu) in row r.longsize()Get the number of non-zero values in the sparse block.intsize(int r)Get the number of non-zero values in row r.longsize(int rl, int ru)Get the number of non-zeros values in the row range of [rl, ru).longsize(int rl, int ru, int cl, int cu)Get the number of non-zeros values in the row and column range of [rl/cl, ru/cu);voidsort()Sort all non-zero value/index pairs of the sparse block by row and column index.voidsort(int r)Sort all non-zero value/index pairs of row r column index.StringtoString()double[]values()Get raw access to underlying array of values For use in GPU codedouble[]values(int r)Get the array of all non-zero entries in row r, sorted by their column indexes.- 
Methods inherited from class org.apache.sysds.runtime.data.SparseBlockisAligned, isAligned
 
- 
 
- 
- 
- 
Constructor Detail- 
SparseBlockCOOpublic SparseBlockCOO(int rlen) 
 - 
SparseBlockCOOpublic SparseBlockCOO(int rlen, int capacity)
 - 
SparseBlockCOOpublic SparseBlockCOO(SparseBlock sblock) Copy constructor sparse block abstraction.- Parameters:
- sblock- sparse block to copy
 
 - 
SparseBlockCOOpublic SparseBlockCOO(SparseRow[] rows, int nnz) Copy constructor old sparse row representation.- Parameters:
- rows- array of sparse rows
- nnz- number of non-zeros
 
 
- 
 - 
Method Detail- 
estimateSizeInMemorypublic static long estimateSizeInMemory(long nrows, long ncols, double sparsity)Get the estimated in-memory size of the sparse block in COO with the given dimensions w/o accounting for overallocation.- Parameters:
- nrows- number of rows
- ncols- number of columns
- sparsity- sparsity ratio
- Returns:
- memory estimate
 
 - 
allocatepublic void allocate(int r) Description copied from class:SparseBlockAllocate the underlying data structure holding non-zero values of row r if necessary.- Specified by:
- allocatein class- SparseBlock
- Parameters:
- r- row index
 
 - 
allocatepublic void allocate(int r, int nnz)Description copied from class:SparseBlockAllocate the underlying data structure holding non-zero values of row r if necessary, w/ given size.- Specified by:
- allocatein class- SparseBlock
- Parameters:
- r- row index
- nnz- number of non-zeros
 
 - 
allocatepublic void allocate(int r, int ennz, int maxnnz)Description copied from class:SparseBlockAllocate the underlying data structure holding non-zero values of row r w/ the specified estimated nnz and max nnz.- Specified by:
- allocatein class- SparseBlock
- Parameters:
- r- row index
- ennz- estimated non-zeros
- maxnnz- max non-zeros
 
 - 
compactpublic void compact(int r) Description copied from class:SparseBlockRe-allocate physical row if physical size exceeds logical size plus resize factor.- Specified by:
- compactin class- SparseBlock
- Parameters:
- r- row index
 
 - 
numRowspublic int numRows() Description copied from class:SparseBlockGet the number of rows in the sparse block.- Specified by:
- numRowsin class- SparseBlock
- Returns:
- number of rows
 
 - 
isThreadSafepublic boolean isThreadSafe() Description copied from class:SparseBlockIndicates if the underlying implementation allows thread-safe row updates if concurrent threads update disjoint rows.- Specified by:
- isThreadSafein class- SparseBlock
- Returns:
- true if thread-safe row updates
 
 - 
isContiguouspublic boolean isContiguous() Description copied from class:SparseBlockIndicates if the underlying data structures returned by values and indexes are contiguous arrays, which can be exploited for more efficient operations.- Specified by:
- isContiguousin class- SparseBlock
- Returns:
- true if underlying data structures are contiguous arrays
 
 - 
isAllocatedpublic boolean isAllocated(int r) Description copied from class:SparseBlockIndicates if the underlying data structure for a given row is already allocated.- Specified by:
- isAllocatedin class- SparseBlock
- Parameters:
- r- row index
- Returns:
- true if already allocated
 
 - 
checkValiditypublic boolean checkValidity(int rlen, int clen, long nnz, boolean strict)Description copied from class:SparseBlockValidate the correctness of the internal data structures of the different sparse block implementations.- Specified by:
- checkValidityin class- SparseBlock
- Parameters:
- rlen- number of rows
- clen- number of columns
- nnz- number of non zeros
- strict- enforce optional properties
- Returns:
- true if the sparse block is valid wrt the corresponding format such as COO, CSR, MCSR.
 
 - 
resetpublic void reset() Description copied from class:SparseBlockClears the sparse block by deleting non-zero values. After this call all size() calls are guaranteed to return 0.- Specified by:
- resetin class- SparseBlock
 
 - 
resetpublic void reset(int ennz, int maxnnz)Description copied from class:SparseBlockClears the sparse block by deleting non-zero values. After this call all size() calls are guaranteed to return 0.- Specified by:
- resetin class- SparseBlock
- Parameters:
- ennz- estimated non-zeros
- maxnnz- max non-zeros
 
 - 
resetpublic void reset(int r, int ennz, int maxnnz)Description copied from class:SparseBlockClears row r of the sparse block by deleting non-zero values. After this call size(r) is guaranteed to return 0.- Specified by:
- resetin class- SparseBlock
- Parameters:
- r- row index
- ennz- estimated non-zeros
- maxnnz- max non-zeros
 
 - 
sizepublic long size() Description copied from class:SparseBlockGet the number of non-zero values in the sparse block.- Specified by:
- sizein class- SparseBlock
- Returns:
- number of non-zero values in sparse block
 
 - 
sizepublic int size(int r) Description copied from class:SparseBlockGet the number of non-zero values in row r.- Specified by:
- sizein class- SparseBlock
- Parameters:
- r- row index starting at 0
- Returns:
- number of non-zero values in row r
 
 - 
sizepublic long size(int rl, int ru)Description copied from class:SparseBlockGet the number of non-zeros values in the row range of [rl, ru).- Specified by:
- sizein class- SparseBlock
- Parameters:
- rl- row lower index
- ru- row upper index
- Returns:
- number of non-zero values in the row range
 
 - 
sizepublic long size(int rl, int ru, int cl, int cu)Description copied from class:SparseBlockGet the number of non-zeros values in the row and column range of [rl/cl, ru/cu);- Specified by:
- sizein class- SparseBlock
- Parameters:
- rl- row lower index
- ru- row upper index
- cl- column lower index
- cu- column upper index
- Returns:
- number of non-zero values in the row and column range
 
 - 
isEmptypublic boolean isEmpty(int r) Description copied from class:SparseBlockGet information if row r is empty, i.e., does not contain non-zero values. Equivalent to size(r)==0. Users should do this check if it is unknown if the underlying row data structure is allocated.- Specified by:
- isEmptyin class- SparseBlock
- Parameters:
- r- row index starting at 0
- Returns:
- true if row does not contain non-zero values
 
 - 
indexespublic int[] indexes(int r) Description copied from class:SparseBlockGet the sorted array of column indexes of all non-zero entries in row r. Note that - for flexibility of the implementing format - the returned array may be larger, where the range for row r is given by [pos(r),pos(r)+size(r)).- Specified by:
- indexesin class- SparseBlock
- Parameters:
- r- row index starting at 0
- Returns:
- sorted array of column indexes
 
 - 
valuespublic double[] values(int r) Description copied from class:SparseBlockGet the array of all non-zero entries in row r, sorted by their column indexes. Note that - for flexibility of the implementing format - the returned array may be larger, where the range for row r is given by [pos(r),pos(r)+size(r)).- Specified by:
- valuesin class- SparseBlock
- Parameters:
- r- row index starting at 0
- Returns:
- array of all non-zero entries in row r sorted by column indexes
 
 - 
pospublic int pos(int r) Description copied from class:SparseBlockGet the starting position of row r in the indexes/values arrays returned by indexes(r) and values(r).- Specified by:
- posin class- SparseBlock
- Parameters:
- r- row index starting at 0
- Returns:
- starting position of row r
 
 - 
setpublic boolean set(int r, int c, double v)Description copied from class:SparseBlockSet the value of a matrix cell (r,c). This might update an existing non-zero value, insert a new non-zero value, or delete a non-zero value.- Specified by:
- setin class- SparseBlock
- Parameters:
- r- row index starting at 0
- c- column index starting at 0
- v- zero or non-zero value
- Returns:
- true, if number of non-zeros changed
 
 - 
setpublic void set(int r, SparseRow row, boolean deep)Description copied from class:SparseBlockSet the values of row r to the given sparse row. This might update existing non-zero values, insert a new row, or delete a row. NOTE: This method exists for incremental runtime integration and might be deleted in the future.- Specified by:
- setin class- SparseBlock
- Parameters:
- r- row index starting at 0
- row- sparse row
- deep- indicator to create deep copy of sparse row
 
 - 
addpublic boolean add(int r, int c, double v)Description copied from class:SparseBlockAdd a value to a matrix cell (r,c). This might update an existing non-zero value, or insert a new non-zero value.- Specified by:
- addin class- SparseBlock
- Parameters:
- r- row index starting at 0
- c- column index starting at 0
- v- zero or non-zero value
- Returns:
- true, if number of non-zeros changed
 
 - 
appendpublic void append(int r, int c, double v)Description copied from class:SparseBlockAppend a value to the end of the physical representation. This should only be used for operations with sequential write pattern or if followed by a sort() operation. Note that this operation does not perform any matrix cell updates.- Specified by:
- appendin class- SparseBlock
- Parameters:
- r- row index starting at 0
- c- column index starting at 0
- v- zero or non-zero value
 
 - 
setIndexRangepublic void setIndexRange(int r, int cl, int cu, double[] v, int vix, int vlen)Description copied from class:SparseBlockSets a dense array of non-zeros values into the column range [cl,cu) in row r. The passed value array may be larger and the relevant range is given by [vix,vix+len).- Specified by:
- setIndexRangein class- SparseBlock
- Parameters:
- r- row index starting at 0
- cl- lower column index starting at 0
- cu- upper column index starting at 0
- v- value array
- vix- start index in value array
- vlen- number of relevant values
 
 - 
setIndexRangepublic void setIndexRange(int r, int cl, int cu, double[] v, int[] vix, int vpos, int vlen)Description copied from class:SparseBlockSets a sparse array of non-zeros values and indexes into the column range [cl,cu) in row r. The passed value array may be larger.- Specified by:
- setIndexRangein class- SparseBlock
- Parameters:
- r- row index starting at 0
- cl- lower column index starting at 0
- cu- upper column index starting at 0
- v- value array
- vix- column index array
- vpos- start index in value and index arrays
- vlen- number of relevant values
 
 - 
deleteIndexRangepublic void deleteIndexRange(int r, int cl, int cu)Description copied from class:SparseBlockDeletes all non-zero values of the given column range [cl,cu) in row r.- Specified by:
- deleteIndexRangein class- SparseBlock
- Parameters:
- r- row index starting at 0
- cl- lower column index starting at 0
- cu- upper column index starting at 0
 
 - 
sortpublic void sort() Description copied from class:SparseBlockSort all non-zero value/index pairs of the sparse block by row and column index.- Specified by:
- sortin class- SparseBlock
 
 - 
sortpublic void sort(int r) Description copied from class:SparseBlockSort all non-zero value/index pairs of row r column index.- Specified by:
- sortin class- SparseBlock
- Parameters:
- r- row index starting at 0
 
 - 
getpublic double get(int r, int c)Description copied from class:SparseBlockGet value of matrix cell (r,c). In case of non existing values this call returns 0.- Specified by:
- getin class- SparseBlock
- Parameters:
- r- row index starting at 0
- c- column index starting at 0
- Returns:
- value of cell at position (r,c)
 
 - 
getpublic SparseRow get(int r) Description copied from class:SparseBlockGet values of row r in the format of a sparse row. NOTE: This method exists for incremental runtime integration and might be deleted in the future.- Specified by:
- getin class- SparseBlock
- Parameters:
- r- row index starting at 0
- Returns:
- values of row r as a sparse row
 
 - 
posFIndexLTEpublic int posFIndexLTE(int r, int c)Description copied from class:SparseBlockGet position of first column index lower than or equal column c in row r. The position is relative to the indexes/values arrays returned by indexes(r) and values(r). If no such value exists, this call returns -1.- Specified by:
- posFIndexLTEin class- SparseBlock
- Parameters:
- r- row index starting at 0
- c- column index starting at 0
- Returns:
- position of the first column index lower than or equal to column c in row r
 
 - 
posFIndexGTEpublic int posFIndexGTE(int r, int c)Description copied from class:SparseBlockGet position of first column index greater than or equal column c in row r. The position is relative to the indexes/values arrays returned by indexes(r) and values(r). If no such value exists, this call returns -1. Note if CSR the pos(r) is subtracted from the result.- Specified by:
- posFIndexGTEin class- SparseBlock
- Parameters:
- r- row index starting at 0
- c- column index starting at 0
- Returns:
- position of the first column index greater than or equal to column c in row r
 
 - 
posFIndexGTpublic int posFIndexGT(int r, int c)Description copied from class:SparseBlockGet position of first column index greater than column c in row r. The position is relative to the indexes/values arrays returned by indexes(r) and values(r). If no such value exists, this call returns -1.- Specified by:
- posFIndexGTin class- SparseBlock
- Parameters:
- r- row index starting at 0
- c- column index starting at 0
- Returns:
- position of the first column index greater than column c in row r
 
 - 
getIteratorpublic Iterator<IJV> getIterator() Description copied from class:SparseBlockGet a non-zero iterator over the entire sparse block. Note that the returned IJV object is reused across next calls and should be directly consumed or deep copied.- Overrides:
- getIteratorin class- SparseBlock
- Returns:
- IJV iterator
 
 - 
getIteratorpublic Iterator<IJV> getIterator(int ru) Description copied from class:SparseBlockGet a non-zero iterator over the partial sparse block [0,ru). Note that the returned IJV object is reused across next calls and should be directly consumed or deep copied.- Overrides:
- getIteratorin class- SparseBlock
- Parameters:
- ru- exclusive upper row index starting at 0
- Returns:
- IJV iterator
 
 - 
getIteratorpublic Iterator<IJV> getIterator(int rl, int ru) Description copied from class:SparseBlockGet a non-zero iterator over the subblock [rl, ru). Note that the returned IJV object is reused across next calls and should be directly consumed or deep copied.- Overrides:
- getIteratorin class- SparseBlock
- Parameters:
- rl- inclusive lower row index starting at 0
- ru- exclusive upper row index starting at 0
- Returns:
- IJV iterator
 
 - 
toStringpublic String toString() - Specified by:
- toStringin class- SparseBlock
 
 - 
rowIndexespublic int[] rowIndexes() Get raw access to underlying array of row indices For use in GPU code- Returns:
- array of row indices
 
 - 
indexespublic int[] indexes() Get raw access to underlying array of column indices For use in GPU code- Returns:
- array of column indices
 
 - 
valuespublic double[] values() Get raw access to underlying array of values For use in GPU code- Returns:
- array of values
 
 
- 
 
-