GXCS index limitation

[rok]

If I understand correctly GXCS indexes all value locations in single int64 space. This works fine in low dimensional space, but causes overflows quickly as we go to higher dimensional space. See the issue below:

import numpy as np
import sparse

coords_1 = np.array([(1,) * 63]).T
coords_2 = np.array([(1,) * 64]).T
coords_1[-1] = [0]
coords_2[-1] = [0]

# This works
sparse_tensor_1 = sparse.COO(data=[1], coords=coords_1).asformat('gxcs')

# This fails
sparse_tensor_2 = sparse.COO(data=[1], coords=coords_2).asformat('gxcs')

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-1-7b99e8ced0f4> in <module>
      8 
      9 sparse_tensor_1 = sparse.COO(data=[1], coords=coords_1).asformat('gxcs')
---> 10 sparse_tensor_2 = sparse.COO(data=[1], coords=coords_2).asformat('gxcs')

~/.virtualenvs/d3m/lib/python3.6/site-packages/sparse/_coo/core.py in asformat(self, format, compressed_axes)
   2179         from .._compressed import GXCS
   2180         if format == 'gxcs' or format is GXCS:
-> 2181             return GXCS.from_coo(self, compressed_axes=compressed_axes)
   2182         elif compressed_axes is not None:
   2183             raise ValueError(

~/.virtualenvs/d3m/lib/python3.6/site-packages/sparse/_compressed/compressed.py in from_coo(cls, x, compressed_axes)
    130     def from_coo(cls, x, compressed_axes=None):
    131         arg, shape, compressed_shape, compressed_axes, axis_order, reordered_shape, axisptr, fill_value = _from_coo(
--> 132             x, compressed_axes)
    133         return cls(
    134             arg,

~/.virtualenvs/d3m/lib/python3.6/site-packages/sparse/_compressed/compressed.py in _from_coo(x, compressed_axes)
     52     shape = x.shape
     53 
---> 54     x = x.transpose(axis_order)
     55     linear = linear_loc(x.coords, new_shape)
     56     order = np.argsort(linear)

~/.virtualenvs/d3m/lib/python3.6/site-packages/sparse/_coo/core.py in transpose(self, axes)
   1421                      has_duplicates=False,
   1422                      cache=self._cache is not None,
-> 1423                      fill_value=self.fill_value)
   1424 
   1425         if self._cache is not None:

~/.virtualenvs/d3m/lib/python3.6/site-packages/sparse/_coo/core.py in __init__(self, coords, data, shape, has_duplicates, sorted, prune, cache, fill_value)
    254 
    255         if not sorted:
--> 256             self._sort_indices()
    257 
    258         if has_duplicates:

~/.virtualenvs/d3m/lib/python3.6/site-packages/sparse/_coo/core.py in _sort_indices(self)
   1922         array([3, 4, 1], dtype=uint8)
   1923         """
-> 1924         linear = self.linear_loc()
   1925 
   1926         if (np.diff(linear) >= 0).all():  # already sorted

~/.virtualenvs/d3m/lib/python3.6/site-packages/sparse/_coo/core.py in linear_loc(self)
   1658         """
   1659         from .common import linear_loc
-> 1660         return linear_loc(self.coords, self.shape)
   1661 
   1662     def reshape(self, shape, order='C'):

~/.virtualenvs/d3m/lib/python3.6/site-packages/sparse/_coo/common.py in linear_loc(coords, shape)
     52     strides = int(1)
     53     for i, d in enumerate(shape[::-1]):
---> 54         np.multiply(coords[-(i + 1), :], strides, out=tmp)
     55         np.add(tmp, out, out=out)
     56         strides *= d

TypeError: Cannot cast ufunc multiply output from dtype('float64') to dtype('int64') with casting rule 'same_kind'

[hameerabbasi]

That's an inherent limitation: One you will run into COO often as well:

>>> coords = np.array([(1,) * 64]).T
>>> coords[-1] = [1]
>>> sp.COO(data=[1], coords=coords).sum()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/Users/hameerabbasi/Quansight/sparse/sparse/_coo/core.py", line 272, in __init__
    self._sort_indices()
  File "/Users/hameerabbasi/Quansight/sparse/sparse/_coo/core.py", line 1981, in _sort_indices
    linear = self.linear_loc()
  File "/Users/hameerabbasi/Quansight/sparse/sparse/_coo/core.py", line 1711, in linear_loc
    return linear_loc(self.coords, self.shape)
  File "/Users/hameerabbasi/Quansight/sparse/sparse/_coo/common.py", line 61, in linear_loc
    np.multiply(coords[-(i + 1), :], strides, out=tmp)
numpy.core._exceptions.UFuncTypeError: Cannot cast ufunc 'multiply' output from dtype('float64') to dtype('int64') with casting rule 'same_kind'

This is because internally, often, we need to convert between linearized and multi-axis coordinates.

[hameerabbasi]

As a side note, NumPy only supports 32-dimensions, IIRC.

[rok]

That's an inherent limitation ..

The reason I'm asking is I'm implementing CSF in arrow and find this a bit limiting, but I don't know many use cases. Did you come across any cases where this was an issue?

[hameerabbasi]

Not me personally.

[rok]

Ok, let's close this. I would love to hear of any high dimensional cases if they come up.
Thanks @hameerabbasi! :)