Order-preserving hashtable for integer tuples

Question

There are integer tuples which index cells of a sparse multi-dimensional array (points inside n-parallelepiped), $n \le 32$.
The array itself is a BST with keys formed as $key = (...((a_0 * S_1 + a_1) * S_2 + a_3 ) * ... + a_{n-2}) * S_{n-1} + a_{n-1}$,
such keys preserve the order of tuples and can be compared in constant time,
but they occupy $log_2 \prod_{i=0}^{n-1}{S_i} $ bits per key (in my program there are already $512-2048$ bit keys).
Total number of keys can be estimated beforehand and the usual array density is $10^{-10} - 10^{-20}$ (fraction of array cells that are populated).
The tuples are not available beforehand but are added to the array from time to time, and they are never deleted.

I want to shrink size of the keys at the expense of comparison time.

I need a data structure (hashtable) that:

1. Maps a tuple into an integer as a perfect hash fuction in $O(n + \log N)$ time, where $N$ is the number of already processed tuples. Addition of a new tuple doesn't change any already existing mappings as they are in use elsewhere.
2. allows key comparison in $\lt O(\log N)$ time (ideally constant time)

EDIT

This question is not about a multidimensional array enhancement, it's about hashing large integer tuples while preserving their row-major order.

Answer 1

Could you use a different ordering, specifically Morton Ordering (Z-order curve)?

I could offer one of my own projects, the PH-tree index. It is an ordered map that uses multidimensional keys (e.g. a vector of integer). In your case, you would use the "coordinate" of your matrix as "key". This would save you from manually creating a key and inserting it into a (perfect) hashmap. Insertion, deletion and lookup are all in the order of $O(n*\log{N})$. Space complexity is roughly $O(nN)$.

Note that the Java implementation support up to 1000 dimensions (actually more, but I never tested more). The (more recent) C++ implementation supports up to 63 dimensions, but it hasn`t been optimized much for $n>6$ yet.

It all hinges obviously on whether Morton order (instead of row-major) would be an option for you problem.

You can simulate row-major ordering by performing a window query on any given row and it would return all entries in that row in the correct order. That means, to get all occupied cells in row-major order, you would need to perform one window query for each row...

EDIT

I forgot to mention: The original PH-tree concept uses prefix sharing to reduce memory consumption. In short: all keys in a "node" of the PH-tree are spatially close, meaning that they typically share a lot of their leading bits. The tree exploits this and stores the common prefix only once. The differing bits of the keys in the node are then compressed into a single bit stream.

Unfortunately, this "compression" is only available in Java version and it is not used by default. Please let me know if this is interesting to you, I can provide instructions on how to enable it.

Answer 2

The problem is a case of list-labeling problem.

It seems impossible to fullfill Addition of a new tuple doesn't change any already existing mappings as they are in use elsewhere requirement, as even unacceptably large $N$-bit mappings (labels of size $m = 2^{\Omega(N)}$ in list-labeling problem terminology) are still expected to be relabeled.

So I dropped Addition of a new tuple doesn't change any already existing mappings as they are in use elsewhere requirement.
The current draft idea is to use polynomial list-labeling over a BST or a skip list that contains the tuples to get the labels,
a mapping consists of 2 parts - a label itself and a version of the label,
if mappings are compared externally then first their versions are compared, if they are the same then labels are compared, otherwise mappings are updated in $O(log N)$ to the most actual version, that's the worst comparison time.
However overall efficiency depends on when and how often the external comparisons happen and if the economy of reduced mapping size outweights downside of need to store the older versions of labels.