minutes/2022-09-07-strawman.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "a943b110-2ee1-47d1-93d6-f040f8f63041",
   "metadata": {},
   "source": [
    "- **Author:** [Erik Welch](https://github.com/eriknw)\n",
    "- **Date:** 2022-09-07\n",
    "- **Purpose:** Strawman proposal to help discuss [PR #3](https://github.com/GraphBLAS/binsparse-specification/pull/3)\n",
    "and its [proposal](https://github.com/GraphBLAS/binsparse-specification/blob/main/design_docs/01_rankN_arrays.md)\n",
    "- https://github.com/GraphBLAS/binsparse-specification"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "506a97f3",
   "metadata": {},
   "source": [
    "# High level perspective\n",
    "\n",
    "Let's call our binary sparse storage format `binsparse` in this document.\n",
    "\n",
    "For high level design, let's assume we will use existing data storage formats that can store **metadata** and **arrays** including the shape and data type of arrays:\n",
    "```mermaid\n",
    "flowchart TB\n",
    "    high[binsparse: high level metadata]-->mid[containers for metadata and arrays]-->low[(files)]\n",
    "```\n",
    "Example data storage formats:\n",
    "```mermaid\n",
    "flowchart TB\n",
    "    binsparse-->NetCDF4\n",
    "    binsparse-->HDF5\n",
    "    binsparse-->Zarr\n",
    "    binsparse-->n5\n",
    "    binsparse-->ASDF\n",
    "    binsparse<-->anndata\n",
    "```\n",
    "These containers are higher level than e.g. ZIP, LMDB, and Tar files, and handle data types, multidimensional arrays, endianness, compression, etc.\n",
    "\n",
    "Our current design goal, then, is to determine the high level metadata and arrays for sparse arrays.\n",
    "\n",
    "We should also consider using `binsparse` as an _embedded_ spec to be used as components in other storage formats.\n",
    "```mermaid\n",
    "flowchart LR\n",
    "  subgraph Container\n",
    "  a[embedded binsparse 'foo']\n",
    "  b[embedded binsparse 'bar']\n",
    "  c[dense array 'baz']\n",
    "  d[other stuff]\n",
    "  end\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ef2e9ec-3752-444e-bf3f-bcd99aea4cb5",
   "metadata": {},
   "source": [
    "# Version 1.0\n",
    "- Very limited scope\n",
    "  - Simple and opinionated with no options\n",
    "  - Easy to explain and understand\n",
    "  - Smooth transition to version 2.0\n",
    "  - Cover most of MatrixMarket format\n",
    "- Sparse formats: COO, CSR, CSC, DCSR, DCSC, sparse vector (VEC)\n",
    "- Indices must be lexicographically sorted by dim0, dim1\n",
    "- No duplicate indices allowed\n",
    "  - Applies to COO\n",
    "  - Applies to row indices in DCSR\n",
    "- May support dense and bitmap formats\n",
    "- May allow attributes such as `is_symmetric`, `ndiag`, etc.\n",
    "\n",
    "Assume all metadata contains format type and version, such as:\n",
    "```json\n",
    "{\n",
    "  \"spec_version\": \"https://purl.org/binsparse/spec/core/1.0\"\n",
    "}\n",
    "```\n",
    "\n",
    "<table style=\"text-align:left; border:1px solid #ccc;\">\n",
    "    <tr></tr>\n",
    "    <tr><th> CSR </th><th> CSC </th><th> DCSR </th><th> DCSC </th><th> COO </th><th> VEC </th></tr>\n",
    "<tr><td>\n",
    "\n",
    "```json\n",
    "{\n",
    "  \"format\": \"CSR\",\n",
    "  \"shape\": [m, n]\n",
    "}\n",
    "```\n",
    "\n",
    "</td>\n",
    "<td>\n",
    "\n",
    "```json\n",
    "{\n",
    "  \"format\": \"CSC\",\n",
    "  \"shape\": [m, n]\n",
    "}\n",
    "```\n",
    "\n",
    "</td>\n",
    "<td>\n",
    "\n",
    "```json\n",
    "{\n",
    "  \"format\": \"DCSR\",\n",
    "  \"shape\": [m, n]\n",
    "}\n",
    "```\n",
    "\n",
    "</td>\n",
    "<td>\n",
    "\n",
    "```json\n",
    "{\n",
    "  \"format\": \"DCSC\",\n",
    "  \"shape\": [m, n]\n",
    "}\n",
    "```\n",
    "\n",
    "</td>\n",
    "<td>\n",
    "\n",
    "```json\n",
    "{\n",
    "  \"format\": \"COO\",\n",
    "  \"shape\": [m, n]\n",
    "}\n",
    "```\n",
    "\n",
    "</td>\n",
    "<td>\n",
    "\n",
    "```json\n",
    "{\n",
    "  \"format\": \"COO\",\n",
    "  \"shape\": [n]\n",
    "}\n",
    "```\n",
    "\n",
    "</td>\n",
    "</tr>\n",
    "    <tr></tr>\n",
    "<tr>\n",
    "<td>\n",
    "\n",
    "```\n",
    "Data:\n",
    " - pointers_0\n",
    " - indices_1\n",
    " - values\n",
    "\n",
    "```\n",
    "\n",
    "</td>\n",
    "<td>\n",
    "\n",
    "```\n",
    "Data:\n",
    " - pointers_0\n",
    " - indices_1\n",
    " - values\n",
    "\n",
    "```\n",
    "\n",
    "</td>\n",
    "<td>\n",
    "\n",
    "```\n",
    "Data:\n",
    " - indices_0\n",
    " - pointers_0\n",
    " - indices_1\n",
    " - values\n",
    "```\n",
    "\n",
    "</td>\n",
    "<td>\n",
    "\n",
    "```\n",
    "Data:\n",
    " - indices_0\n",
    " - pointers_0\n",
    " - indices_1\n",
    " - values\n",
    "```\n",
    "\n",
    "</td>\n",
    "<td>\n",
    "\n",
    "```\n",
    "Data:\n",
    " - indices_0\n",
    " - indices_1\n",
    " - values\n",
    "\n",
    "```\n",
    "\n",
    "</td>\n",
    "<td>\n",
    "\n",
    "```\n",
    "Data:\n",
    " - indices_0\n",
    " - values\n",
    "\n",
    "\n",
    "```\n",
    "\n",
    "</td>\n",
    "</tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2c41d74a-3b8c-479e-bf47-4a45e424f82b",
   "metadata": {},
   "source": [
    "### Questions\n",
    "Inluding some reactions from the September 7 meeting:\n",
    "\n",
    "- Should we save datatypes or defer to the storage container?\n",
    "  - e.g., `{\"data_types\": {\"indices_0\": \"uint64\", \"values\": \"float64\"}`\n",
    "    - *Jim says yes*\n",
    "    - *Keep v1 simple*\n",
    "    - *Researching data types is an action item*\n",
    "  - If so, should we indicate endianness such as `\"<i4\"`?\n",
    "    - *Jim and Ben say no*\n",
    "- Should we add `\"COOR\"` and `\"COOC\"` (or `\"COO-R\"` and `\"COO-C\"`) formats that are sorted by row then column and column then row?\n",
    "  - *Jim, yes for COOR, COOC*\n",
    "- Should `\"COO\"` format be \"special\" and allowed to be unsorted and/or have duplicates?\n",
    "  - *Ben: COO defaults to COOR*\n",
    "- Should we always include `dim_types` (see below)?\n",
    "  - *Nah*\n",
    "- Should we add a field for arbitrary user metadata such as comments?\n",
    "  - *Yes, a field such as `\"attrs\"` that can save key-value pairs*\n",
    "  - *Would be nice to store SuiteSparse collection w/o losing any info*\n",
    "  - *Erik: follow Zarr's example and don't allow arbitrary key-value pairs--have a specified place for user metadata*\n",
    "- Should bitmap and full formats be in v1?\n",
    "  - *Jim, Ben, Erik: gut reactions--no*\n",
    "  - *Isaac would like to consider memory-friendliness*\n",
    "\n",
    "```\n",
    "Easy datatypes\n",
    "    int8 int16 int32 int64\n",
    "    uint8 uint16 uint32 uint64\n",
    "    float32 float64\n",
    "\n",
    "Harder datatypes\n",
    "    bool\n",
    "    complex64\n",
    "    int128\n",
    "    uint128\n",
    "    float16\n",
    "    fixed-width UDTs (void or composed?)\n",
    "    strings or variable-length\n",
    "    datetimes\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe9eb46a-29d1-47fb-bf65-37fb52a28223",
   "metadata": {},
   "source": [
    "#### Ideas for handling data types and values\n",
    "Single values array:\n",
    "```json\n",
    "{\n",
    "  \"format\": \"CSR\",\n",
    "  \"shape\": [m, n],\n",
    "  \"data_types\": {\"pointers_0\": \"int32\", \"indices_1\": \"uint64\", \"values\": \"float64\"},\n",
    "}\n",
    "```\n",
    "Iso-value:\n",
    "```json\n",
    "{\n",
    "  \"format\": \"CSR\",\n",
    "  \"shape\": [m, n],\n",
    "  \"data_types\": {\"pointers_0\": \"int32\", \"indices_1\": \"uint64\", \"values\": \"float64\"},\n",
    "  \"isovalue\": 1.0\n",
    "\n",
    "  \"data_types\": {\"pointers_0\": \"int32\", \"indices_1\": \"uint64\", \"values\": {\"iso[float64\"]: 1.0}},\n",
    "}\n",
    "```\n",
    "No value, structure-only:\n",
    "```json\n",
    "{\n",
    "  \"format\": \"CSR\",\n",
    "  \"shape\": [m, n],\n",
    "  \"data_types\": {\"pointers_0\": \"int32\", \"indices_1\": \"uint64\", \"values\": null}\n",
    "\n",
    "  \"is_structure_only\": true\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ba9e7544-15f6-4be7-b12b-9cc77af0b4ad",
   "metadata": {},
   "source": [
    "# Version 2.0\n",
    "- Version 2.x is an extension of and can read version 1.x\n",
    "- Support multidimensional sparse arrays\n",
    "- Support duplicated indices\n",
    "  - common for COO\n",
    "- Support unordered indices\n",
    "  - common for COO\n",
    "  - \"jumbled\" columns in SuiteSparse:GraphBLAS CSR and DCSR\n",
    "- Support multiple value arrays, no value arrays, and iso-valued arrays\n",
    "- Support per-dimension, per-values, and global attributes\n",
    "- Allow extensions\n",
    "\n",
    "<table style=\"text-align:left; border:1px solid #ccc;\">\n",
    "    <tr></tr>\n",
    "    <tr><th> CSR </th><th> CSC </th></tr>\n",
    "<tr>\n",
    "<td>\n",
    "\n",
    "```json\n",
    "{\n",
    "  \"format\": \"CSR\",\n",
    "  \"shape\": [m, n],\n",
    "\n",
    "  \"dim_types\": [\"compressed\", \"sparse\"],\n",
    "  \"dim_order\": [0, 1],\n",
    "\n",
    "  \"dim_properties\": {\"1\": {\"is_ordered\": true}},\n",
    "  \"properties\": {\"has_duplicates\": false},\n",
    "\n",
    "  \"dim_sizes\": [m, n],\n",
    "  \"dim_taco\": [\"dense\", \"compressed\"]\n",
    "}\n",
    "```\n",
    "\n",
    "</td>\n",
    "<td>\n",
    "\n",
    "```json\n",
    "{\n",
    "  \"format\": \"CSC\",\n",
    "  \"shape\": [m, n],\n",
    "\n",
    "  \"dim_types\": [\"compressed\", \"sparse\"],\n",
    "  \"dim_order\": [1, 0],\n",
    "\n",
    "  \"dim_properties\": {\"1\": {\"is_ordered\": true}},\n",
    "  \"properties\": {\"has_duplicates\": false},\n",
    "\n",
    "  \"dim_sizes\": [n, m],\n",
    "  \"dim_taco\": [\"dense\", \"compressed\"]\n",
    "}\n",
    "```\n",
    "\n",
    "</td>\n",
    "</tr>\n",
    "    <tr><th> DCSR </th><th> DCSC </th></tr>\n",
    "<tr>\n",
    "<td>\n",
    "\n",
    "```json\n",
    "{\n",
    "  \"format\": \"DCSR\",\n",
    "  \"shape\": [m, n],\n",
    "\n",
    "  \"dim_types\": [\"doubly_compressed\", \"sparse\"],\n",
    "  \"dim_order\": [0, 1],\n",
    "\n",
    "  \"dim_properties\": {\n",
    "    \"0\": {\"is_ordered\": true, \"is_unique\": true},\n",
    "    \"1\": {\"is_ordered\": true}\n",
    "  },\n",
    "  \"properties\": {\"has_duplicates\": false},\n",
    "\n",
    "  \"dim_sizes\": [m, n],\n",
    "  \"dim_taco\": [\"compressed\", \"compressed\"]\n",
    "}\n",
    "```\n",
    "\n",
    "</td>\n",
    "<td>\n",
    "\n",
    "```json\n",
    "{\n",
    "  \"format\": \"DCSC\",\n",
    "  \"shape\": [m, n],\n",
    "\n",
    "  \"dim_types\": [\"doubly_compressed\", \"sparse\"],\n",
    "  \"dim_order\": [1, 0],\n",
    "\n",
    "  \"dim_properties\": {\n",
    "    \"0\": {\"is_ordered\": true, \"is_unique\": true},\n",
    "    \"1\": {\"is_ordered\": true}\n",
    "  },\n",
    "  \"properties\": {\"has_duplicates\": false},\n",
    "\n",
    "  \"dim_sizes\": [n, m],\n",
    "  \"dim_taco\": [\"compressed\", \"compressed\"]\n",
    "}\n",
    "```\n",
    "\n",
    "</td>\n",
    "</tr>\n",
    "    <tr><th> COO </th><th> Vector </th></tr>\n",
    "<tr>\n",
    "<td>\n",
    "\n",
    "```json\n",
    "{\n",
    "  \"format\": \"COO\",\n",
    "  \"shape\": [m, n],\n",
    "\n",
    "  \"dim_types\": [\"sparse\", \"sparse\"],\n",
    "  \"dim_order\": [0, 1],\n",
    "\n",
    "  \"dim_properties\": {\n",
    "    \"0\": {\"is_ordered\": true},\n",
    "    \"1\": {\"is_ordered\": true}\n",
    "  },\n",
    "  \"properties\": {\"has_duplicates\": false},\n",
    "\n",
    "  \"dim_sizes\": [m, n],\n",
    "  \"dim_taco\": [\"compressed-nonunique\", \"singleton\"]\n",
    "}\n",
    "```\n",
    "\n",
    "</td>\n",
    "<td>\n",
    "\n",
    "```json\n",
    "{\n",
    "  \"format\": \"COO\",\n",
    "  \"shape\": [n],\n",
    "\n",
    "  \"dim_types\": [\"sparse\"],\n",
    "  \"dim_order\": [0],\n",
    "\n",
    "  \"dim_properties\": {\n",
    "    \"0\": {\"is_ordered\": true}\n",
    "  },\n",
    "  \"properties\": {\"has_duplicates\": false},\n",
    "\n",
    "  \"dim_sizes\": [n],\n",
    "  \"dim_taco\": [\"compressed\"]\n",
    "}\n",
    "\n",
    "```\n",
    "\n",
    "</td>\n",
    "</tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4258ac88-a5fe-4552-80a4-cb286564ebe3",
   "metadata": {},
   "source": [
    "### `dim_types`\n",
    "  - Each dimension is one of `\"sparse\"`, `\"compressed\"`, or `\"doubly_compressed\"` as described here:\n",
    "    - https://github.com/GraphBLAS/binsparse-specification/blob/main/design_docs/01_rankN_arrays.md\n",
    "  - Design choices\n",
    "    - required, even in version 1.0\n",
    "    - required _except_ for formats in version 1.0\n",
    "    - not required if it can be inferred from the format name\n",
    "      - Example: `\"format\": \"SCSR\"` --> `\"dim_types\": [\"sparse\", \"compressed\", \"sparse\"]`\n",
    "    - make `format` optional if `dim_types` is given?\n",
    "\n",
    "### `dim_order`\n",
    "  - Logically reorders dimensions\n",
    "      - Like `dimOrdering` in [MLIR sparse tensor](https://mlir.llvm.org/docs/Dialects/SparseTensorOps/)\n",
    "      - `shape = [dim_sizes[i] for i in dim_order]`\n",
    "      - `dim_sizes = [shape[i] for i in argsort(dim_order)]`\n",
    "  - Optional; defaults to `[0, 1, ..., N-1]`\n",
    "  - _(choice)_ May infer from last character in `format` if `dim_types` can also be inferred:\n",
    "    - `\"R\"` results in `[0, 1, ..., N-1]`\n",
    "    - `\"C\"` results in `[N-1, ..., 1, 0]`\n",
    "    - otherwise `dim_order` is required (or choose a character like `\"X\"` to mean this)\n",
    "  - _(choice)_ Make required like `dim_types`?\n",
    "\n",
    "### `dim_properties`\n",
    "  - Optional; dictionary of properties for specified dimensions\n",
    "  - Default properties:\n",
    "    - `\"compressed\"`: `{}`\n",
    "    - `\"sparse\"`: `{\"is_ordered\": true}`\n",
    "    - `\"doubly_compressed\"`: `{\"is_ordered\": true, \"is_unique\": true}`\n",
    "  - `is_ordered` property\n",
    "    - Are the indices in `indices_i` in order for `\"sparse\"` or `\"doubly_compressed\"` dimensions?\n",
    "    - Indicates whether `indices_0` is sorted\n",
    "    - Indicates whether `indices_i` with the same previous indices (i.e., between `pointers_{i-1}` boundaries) is sorted\n",
    "    - TACO (paper) _may_ call this `ordered`\n",
    "    - SuiteSparse:GraphBLAS uses `jumbled`\n",
    "  - `is_unique` property\n",
    "    - Indicates whether `indices_i` has no duplicates for `\"doubly_compressed\"` dimensions\n",
    "    - TACO (paper) _may_ call this `unique`\n",
    "    - If `false`, then this conceptually splits a single index tree into multiple trees\n",
    "\n",
    "### `properties`\n",
    "  - Overall properties of the entire sparse index structure\n",
    "  - Optional; defaults to `{\"has_duplicates\": false}`\n",
    "  - `has_duplicates` property\n",
    "    - Indicates whether the sparse array has values with the same indices\n",
    "  - May add `is_symmetric`, `ndiag`, `fill_value`, etc\n",
    "\n",
    "### `dim_sizes`\n",
    "  - Optional; allowed for clarity\n",
    "  - Determined from `dim_order` and `shape`\n",
    "      - `shape = [dim_sizes[i] for i in dim_order]`\n",
    "      - `dim_sizes = [shape[i] for i in argsort(dim_order)]`\n",
    "\n",
    "### `dim_taco`\n",
    "  - Dimension names for TACO and MLIR sparse\n",
    "  - Optional; allowed for clarity\n",
    "  - Determined by `dim_types` (when possible)\n",
    "  - Each dimension is one of `\"compressed\"`, `\"dense\"`, `\"singleton\"`, or `\"compressed-nonunique\"`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "62b793d3-8ca7-4a01-9c6f-17081115106c",
   "metadata": {},
   "source": [
    "## Value arrays\n",
    "\n",
    "Still being explored; don't yet have a complete strawman proposal.\n",
    "\n",
    "Some ideas:\n",
    "<table style=\"text-align:left; border:1px solid #ccc;\">\n",
    "    <tr></tr>\n",
    "    <tr><th> Full v1 </th><th> Bitmap v1</th></tr>\n",
    "<tr>\n",
    "<td>\n",
    "\n",
    "```json\n",
    "{\n",
    "  \"format\": \"Full\",\n",
    "  \"shape\": [m, n],\n",
    "}\n",
    "```\n",
    "\n",
    "</td>\n",
    "<td>\n",
    "\n",
    "```json\n",
    "{\n",
    "  \"format\": \"Bitmap\",\n",
    "  \"shape\": [m, n],\n",
    "}\n",
    "```\n",
    "\n",
    "</td>\n",
    "</tr>\n",
    "    <tr></tr>\n",
    "<tr>\n",
    "<td>\n",
    "\n",
    "```\n",
    "Data:\n",
    " - values\n",
    "\n",
    "```\n",
    "\n",
    "</td>\n",
    "<td>\n",
    "\n",
    "```\n",
    "Data:\n",
    " - values\n",
    " - bitmap\n",
    "```\n",
    "\n",
    "</td>\n",
    "</tr>\n",
    "    <tr><th> Full v2 </th><th> Bitmap v2</th></tr>\n",
    "<tr>\n",
    "<td>\n",
    "\n",
    "```json\n",
    "{\n",
    "  \"format\": \"Full\",\n",
    "  \"shape\": [m, n],\n",
    "\n",
    "  \"dim_types\": [\"full\", \"full\"],\n",
    "  \"dim_order\": [0, 1],\n",
    "\n",
    "  \"dim_properties\": {},\n",
    "  \"properties\": {\"has_duplicates\": false},\n",
    "\n",
    "  \"dim_sizes\": [m, n],\n",
    "  \"dim_taco\": [\"dense\", \"dense\"]\n",
    "}\n",
    "\n",
    "\n",
    "```\n",
    "\n",
    "</td>\n",
    "<td>\n",
    "\n",
    "```json\n",
    "{\n",
    "  \"format\": \"Bitmap\",\n",
    "  \"shape\": [m, n],\n",
    "\n",
    "  \"dim_types\": [\"full\", \"full\"],\n",
    "  \"dim_order\": [0, 1],\n",
    "\n",
    "  \"dim_properties\": {},\n",
    "  \"properties\": {\"has_duplicates\": false},\n",
    "\n",
    "  \"dim_sizes\": [m, n],\n",
    "  \"dim_taco\": [\"dense\", \"dense\"],\n",
    "\n",
    "  \"value_bitmaps\": {\"values\": \"bitmap\"}\n",
    "}\n",
    "```\n",
    "\n",
    "</td>\n",
    "</tr>\n",
    "    <tr></tr>\n",
    "<tr>\n",
    "<td>\n",
    "\n",
    "```\n",
    "Data:\n",
    " - values\n",
    "\n",
    "```\n",
    "\n",
    "</td>\n",
    "<td>\n",
    "\n",
    "```\n",
    "Data:\n",
    " - values\n",
    " - bitmap\n",
    "```\n",
    "\n",
    "</td>\n",
    "</tr>\n",
    "    <tr><th> CSR (bitmap) </th><th> DCSC (iso) </th></tr>\n",
    "<tr>\n",
    "<td>\n",
    "\n",
    "```json\n",
    "{\n",
    "  \"format\": \"CSR\",\n",
    "  \"shape\": [m, n],\n",
    "\n",
    "  \"dim_types\": [\"compressed\", \"sparse\"],\n",
    "  \"dim_order\": [0, 1],\n",
    "\n",
    "  \"dim_properties\": {\"1\": {\"is_ordered\": true}},\n",
    "  \"properties\": {\"has_duplicates\": false},\n",
    "\n",
    "  \"dim_sizes\": [m, n],\n",
    "  \"dim_taco\": [\"dense\", \"compressed\"],\n",
    "\n",
    "  \"value_bitmaps\": {\"values\": \"bitmap\"}\n",
    "}\n",
    "\n",
    "\n",
    "\n",
    "```\n",
    "\n",
    "</td>\n",
    "<td>\n",
    "\n",
    "```json\n",
    "{\n",
    "  \"format\": \"DCSC\",\n",
    "  \"shape\": [m, n],\n",
    "\n",
    "  \"dim_types\": [\"doubly_compressed\", \"sparse\"],\n",
    "  \"dim_order\": [1, 0],\n",
    "\n",
    "  \"dim_properties\": {\n",
    "    \"0\": {\"is_ordered\": true, \"is_unique\": true},\n",
    "    \"1\": {\"is_ordered\": true}\n",
    "  },\n",
    "  \"properties\": {\"has_duplicates\": false},\n",
    "\n",
    "  \"dim_sizes\": [n, m],\n",
    "  \"dim_taco\": [\"compressed\", \"compressed\"],\n",
    "\n",
    "  \"value_isovalues\": {\"values\": 0}  // needs data_type!\n",
    "}\n",
    "```\n",
    "\n",
    "</td>\n",
    "</tr>\n",
    "    <tr></tr>\n",
    "<tr>\n",
    "<td>\n",
    "\n",
    "```\n",
    "Data:\n",
    " - pointers_0\n",
    " - indices_1\n",
    " - values\n",
    " - bitmap\n",
    "```\n",
    "\n",
    "</td>\n",
    "<td>\n",
    "\n",
    "```\n",
    "Data:\n",
    " - indices_0\n",
    " - pointers_0\n",
    " - indices_1\n",
    "\n",
    "```\n",
    "\n",
    "</td>\n",
    "</tr>\n",
    "    <tr><th> CSC (many value arrays) </th><th> DCSC (structure-only) </th></tr>\n",
    "<tr>\n",
    "<td>\n",
    "\n",
    "```json\n",
    "{\n",
    "  \"format\": \"CSC\",\n",
    "  \"shape\": [m, n],\n",
    "\n",
    "  \"dim_types\": [\"compressed\", \"sparse\"],\n",
    "  \"dim_order\": [1, 0],\n",
    "\n",
    "  \"dim_properties\": {\"1\": {\"is_ordered\": true}},\n",
    "  \"properties\": {\"has_duplicates\": false},\n",
    "\n",
    "  \"dim_sizes\": [n, m],\n",
    "  \"dim_taco\": [\"dense\", \"compressed\"],\n",
    "\n",
    "  \"value_names\": [\"foo\", \"bar\"],\n",
    "}\n",
    "\n",
    "\n",
    "\n",
    "```\n",
    "\n",
    "</td>\n",
    "<td>\n",
    "\n",
    "```json\n",
    "{\n",
    "  \"format\": \"DCSR\",\n",
    "  \"shape\": [m, n],\n",
    "\n",
    "  \"dim_types\": [\"doubly_compressed\", \"sparse\"],\n",
    "  \"dim_order\": [0, 1],\n",
    "\n",
    "  \"dim_properties\": {\n",
    "    \"0\": {\"is_ordered\": true, \"is_unique\": true},\n",
    "    \"1\": {\"is_ordered\": true}\n",
    "  },\n",
    "  \"properties\": {\"has_duplicates\": false},\n",
    "\n",
    "  \"dim_sizes\": [m, n],\n",
    "  \"dim_taco\": [\"compressed\", \"compressed\"],\n",
    "\n",
    "  \"value_names\": [],\n",
    "}\n",
    "```\n",
    "\n",
    "</td>\n",
    "</tr>\n",
    "    <tr></tr>\n",
    "<tr>\n",
    "<td>\n",
    "\n",
    "```\n",
    "Data:\n",
    " - pointers_0\n",
    " - indices_1\n",
    " - foo\n",
    " - bar\n",
    "```\n",
    "</td>\n",
    "<td>\n",
    "\n",
    "```\n",
    "Data:\n",
    " - indices_0\n",
    " - pointers_0\n",
    " - indices_1\n",
    "\n",
    "```\n",
    "\n",
    "</td>\n",
    "</tr>\n",
    "    <tr><th> semi-COO </th><th> CSR (array values) </th></tr>\n",
    "<tr>\n",
    "<td>\n",
    "\n",
    "```json\n",
    "{\n",
    "  \"format\": \"SFR\",\n",
    "  \"shape\": [m, n],\n",
    "\n",
    "  \"dim_types\": [\"sparse\", \"full\"],\n",
    "  \"dim_order\": [0, 1],\n",
    "\n",
    "  \"dim_properties\": {\"0\": {\"is_ordered\": true}},\n",
    "  \"properties\": {\"has_duplicates\": false},\n",
    "\n",
    "  \"dim_sizes\": [m, n],\n",
    "  \"dim_taco\": [\"compressed-nonunique\", \"dense\"]\n",
    "}\n",
    "\n",
    "\n",
    "\n",
    "```\n",
    "\n",
    "</td>\n",
    "<td>\n",
    "\n",
    "```json\n",
    "{\n",
    "  \"format\": \"CSFR\",\n",
    "  \"shape\": [m, n, o],\n",
    "\n",
    "  \"dim_types\": [\"compressed\", \"sparse\", \"full\"],\n",
    "  \"dim_order\": [0, 1, 2],\n",
    "\n",
    "  \"dim_properties\": {\n",
    "    \"0\": {\"is_ordered\": true},\n",
    "    \"1\": {\"is_ordered\": true}\n",
    "  },\n",
    "  \"properties\": {\"has_duplicates\": false},\n",
    "\n",
    "  \"dim_sizes\": [m, n, o],\n",
    "  \"dim_taco\": [\"dense\", \"compressed\", \"dense\"],\n",
    "}\n",
    "```\n",
    "\n",
    "</td>\n",
    "</tr>\n",
    "    <tr></tr>\n",
    "<tr>\n",
    "<td>\n",
    "\n",
    "```C\n",
    "Data:\n",
    " - indices_0\n",
    " - values  // shape = [len(indices_0), n]\n",
    "\n",
    "```\n",
    "\n",
    "</td>\n",
    "<td>\n",
    "\n",
    "```C\n",
    "Data:\n",
    " - pointers_0\n",
    " - indices_1\n",
    " - values  // shape = [len(indices_1), o]\n",
    "```\n",
    "\n",
    "</td>\n",
    "</tr>\n",
    "    <tr><th> CSR (multigraph) </th><th> CSR (variable-size datatype) </th></tr>\n",
    "<tr>\n",
    "<td>\n",
    "\n",
    "```json\n",
    "{\n",
    "  \"format\": \"CSR\",\n",
    "  \"shape\": [m, n],\n",
    "\n",
    "  \"dim_types\": [\"compressed\", \"doubly_compressed\"],\n",
    "  \"dim_order\": [0, 1],\n",
    "\n",
    "  \"dim_properties\":\n",
    "    {\"1\": {\"is_ordered\": true, \"is_unique\": true}\n",
    "  },\n",
    "  \"properties\": {\"has_duplicates\": true},\n",
    "\n",
    "  \"dim_sizes\": [m, n],\n",
    "  \"dim_taco\": null,\n",
    "}\n",
    "\n",
    "```\n",
    "\n",
    "</td>\n",
    "<td>\n",
    "\n",
    "```json\n",
    "{\n",
    "  \"format\": \"CSR\",\n",
    "  \"shape\": [m, n],\n",
    "\n",
    "  \"dim_types\": [\"compressed\", \"sparse\"],\n",
    "  \"dim_order\": [0, 1],\n",
    "\n",
    "  \"dim_properties\": {\"1\": {\"is_ordered\": true}},\n",
    "  \"properties\": {\"has_duplicates\": false},\n",
    "\n",
    "  \"dim_sizes\": [m, n],\n",
    "  \"dim_taco\": [\"dense\", \"compressed\"],\n",
    "\n",
    "  \"value_pointers\": {\"values\": \"valptr\"}\n",
    "}\n",
    "\n",
    "```\n",
    "\n",
    "</td>\n",
    "</tr>\n",
    "    <tr></tr>\n",
    "<tr>\n",
    "<td>\n",
    "\n",
    "```\n",
    "Data:\n",
    " - pointers_0\n",
    " - indices_1\n",
    " - pointers_1\n",
    " - values\n",
    "```\n",
    "\n",
    "</td>\n",
    "<td>\n",
    "\n",
    "```\n",
    "Data:\n",
    " - pointers_0\n",
    " - indices_1\n",
    " - values\n",
    " - valptr\n",
    "```\n",
    "\n",
    "</td>\n",
    "</tr>\n",
    "</table>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}