# Order-preserving hashtable for integer tuples

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.

• I am not entirely sure what do you want to do. Questions: 1) What is your ordering based on? Is it insertion order, some kind of ordering by locality, or do you just want ordering to be stable? 2) What are $S$ and $a$? I assume they are somehow related to the x,y coordinates in your array? 3) I assume $10^{−10} − 10^{−20}$ refers to the fraction of your array that is populated, not the number of keys? 4) Is the hash function that constructs the key set in stone, or can you change it? Nov 9, 2022 at 9:08
• Also, how many dimension can/does your array have? Nov 9, 2022 at 10:41
• @TilmannZ 1) the usual row-major order 2) $S_i$ is the $i$-th dimension size 3) You are correct, it's the array density 4) the data structure I require should implement the function, nothing here is set in stone 5) let's say there is a hard cap of 32 dimensions, so there are from 1 to 32 dimensions Nov 9, 2022 at 11:25

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 hasnt 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.

• Tha question is not about multidimensional array data structure, its about shrinking of the key size while preserving their order. The keys themselves are used outside the array and this cause memory bloat. The Morton ordering keys require $n * log_2 (max(S_i))$ bits each, which is even worse than the naive linearizing that is in use now. Nov 9, 2022 at 15:59
• That was a misunderstanding then. In my defense, the question is called "Order-preserving hashtable for integer tuples" which is exactly what the PH-tree can provide. This is also why I asked whether the key generation is set in stone (apparently it is required, because the keys are used outside). As an aside, the Morton order keys are actually not stored in the PH-tree, they are just partially created when needed. But I did apparently wrongly assume that you use the same number of bits for each dimension. Nov 9, 2022 at 18:20

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.