anirudh2290 commented on a change in pull request #7921: Add three sparse tutorials URL: https://github.com/apache/incubator-mxnet/pull/7921#discussion_r141502528
########## File path: docs/tutorials/sparse/csr.md ########## @@ -0,0 +1,349 @@ + +# CSRNDArray - NDArray in Compressed Sparse Row Storage Format + +Many real world datasets deal with high dimensional sparse feature vectors. Take for instance a recommendation system where the number of categories and users is on the order of millions. The purchase data for each category by user would show that most users only make a few purchases, leading to a dataset with high sparsity (i.e. most of the elements are zeros). + +Storing and manipulating such large sparse matrices in the default dense structure results in wasted memory and processing on the zeros. To take advantage of the sparse structure of the matrix, the `CSRNDArray` in MXNet stores the matrix in [compressed sparse row (CSR)](https://en.wikipedia.org/wiki/Sparse_matrix#Compressed_sparse_row_.28CSR.2C_CRS_or_Yale_format.29) format and uses specialized algorithms in operators. +**The format is designed for 2D matrices with a large number of columns, +and each row is sparse (i.e. with only a few nonzeros).** + +## Advantages of Compressed Sparse Row NDArray (CSRNDArray) +For matrices of high sparsity (e.g. ~1% non-zeros = ~1% density), there are two primary advantages of `CSRNDArray` over the existing `NDArray`: + +- memory consumption is reduced significantly +- certain operations are much faster (e.g. matrix-vector multiplication) + +You may be familiar with the CSR storage format in [SciPy](https://www.scipy.org/) and will note the similarities in MXNet's implementation. However there are some additional competitive features in `CSRNDArray` inherited from `NDArray`, such as non-blocking asynchronous evaluation and automatic parallelization that are not available in SciPy's flavor of CSR. You can find further explainations for evaluation and parallization strategy in MXNet in the [NDArray tutorial](https://mxnet.incubator.apache.org/tutorials/basic/ndarray.html#lazy-evaluation-and-automatic-parallelization). + +The introduction of `CSRNDArray` also brings a new attribute, `stype` as a holder for storage type info, to `NDArray`. You can query **ndarray.stype** now in addition to the oft-queried attributes such as **ndarray.shape**, **ndarray.dtype**, and **ndarray.context**. For a typical dense NDArray, the value of `stype` is **"default"**. For a `CSRNDArray`, the value of stype is **"csr"**. + +## Prerequisites + +To complete this tutorial, you will need: + +- MXNet. See the instructions for your operating system in [Setup and Installation](https://mxnet.io/get_started/install.html) +- [Jupyter](http://jupyter.org/) + ``` + pip install jupyter + ``` +- Basic knowledge of NDArray in MXNet. See the detailed tutorial for NDArray in [NDArray - Imperative tensor operations on CPU/GPU](https://mxnet.incubator.apache.org/tutorials/basic/ndarray.html). +- SciPy - A section of this tutorial uses SciPy package in Python. If you don't have SciPy, the example in that section will be ignored. +- GPUs - A section of this tutorial uses GPUs. If you don't have GPUs on your machine, simply set the variable `gpu_device` (set in the GPUs section of this tutorial) to `mx.cpu()`. + +## Compressed Sparse Row Matrix + +A CSRNDArray represents a 2D matrix as three separate 1D arrays: **data**, **indptr** and **indices**, where the column indices for row `i` are stored in `indices[indptr[i]:indptr[i+1]]` in ascending order, and their corresponding values are stored in `data[indptr[i]:indptr[i+1]]`. + +- **data**: CSR format data array of the matrix +- **indices**: CSR format index array of the matrix +- **indptr**: CSR format index pointer array of the matrix + +### Example Matrix Compression + +For example, given the matrix: +``` +[[7, 0, 8, 0] + [0, 0, 0, 0] + [0, 9, 0, 0]] +``` + +We can compress this matrix using CSR, and to do so we need to calculate `data`, `indices`, and `indptr`. + +The `data` array holds all the non-zero entries of the matrix in row-major order. Put another way, you create a data array that has all of the zeros removed from the matrix, row by row, storing the numbers in that order. Your result: + + data = [7, 8, 9] + +The `indices` array stores the column index for each non-zero element in `data`. As you cycle through the data array, starting with 7, you can see it is in column 0. Then looking at 8, you can see it is in column 2. Lastly 9 is in column 1. Your result: Review comment: Does it make sense to mention here that column indices for a specific row will be looked at in sorted order? ---------------------------------------------------------------- This is an automated message from the Apache Git Service. To respond to the message, please log on GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: [email protected] With regards, Apache Git Services
