3
$\begingroup$

I'm aware that typical techniques to store matrices in sparse form are compressed formats or maps where the key is the pair of indices and value the value of the entry in a matrix.

I was wondering if vEB trees could be used to such purpose as well. At the end of the day the dynamic set to be stored would be the pairs $(i,j)$ in lexicographic order. If $MN$ is the size of the matrix a vEB tree would allow the access to a specific entry in time $O(log(log(MN))$ which isn't bad, though the space requirement doesn't change, but maybe with some improvements something interesting could come out.

Is there some research in this direction? I quickly looked up on google doesn't seem anything specific comes out.

Thank you

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Yes you are right; but actually I think what you need is a hash table, which supports insert, delete and find in O(1) (although it requires some randomization).

Of course, you can replace a hash table by a VEB tree, when the elements are integers. However, if you want to optimize the space usage, you still need hashing when constructing the VEB tree. Luckily, there's some data structure called Y-fast trie that supports operations similar to VEB tree, but only needs linear space, and is deterministic.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Is it the hash table the common used DS for sparse matrices? $\endgroup$
    – user8469759
    Commented Sep 14, 2018 at 9:17
  • $\begingroup$ I don't know; I think in practice compressed row/column storage is commonly used, but it does not support (really) fast lookup. If you want to support insert/delete and find simultaneously, at least hash table is the best choice in theory, neglecting the large constants. $\endgroup$
    – hqztrue
    Commented Sep 14, 2018 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.