Is there an efficient storage format for general, non-symmetric sparse matrices for which one can find all non-zero entries in a given row or column in $O(d)$ time? ($d$ is the max number of non-zero entries in any row or column.)
If I store an $m \times n$ sparse matrix $A$ in the compressed row or ellpack formats, I can find all non-zero entries in a given row in $O(d)$ time, but finding all non-zero entries in a given column takes $O(m)$. Of course, I could store $A$ in compressed column format, in which case the column accesses would take $O(d)$ but the row accesses would take $O(n)$.
A blunt approach would be to store both formats, compressed row and column, for the same matrix, which of course entails double the memory. Can one do much better?
Best I can come up with: For square matrices, one can store it as a structurally symmetric matrix. If you want to find all entries in column j, you instead find all entries in row j and then remove the redundant ones.