Canonical representation of finite maps on non-overlapping finite rational intervals

Question

I would like to have a canonical representation of a map from rational intervals (f, t] with f, t ∈ ℚ to some irrelevant value type. These intervals are non-overlapping and there exist only finitely many such keys in the map. I would like to be able to implement the following functions on this representation:

1. Lookup by rationals (not by ranges, as it is unclear what exactly that would mean)
2. Insertion by ranges. This will partial overwrite existing intervals (which are split in the process)
3. Compare two maps for equality by comparing their representation.
4. Create an empty map.

Particularly interesting are cases such as inserting two adjacent intervals with the same value V. I think for the map to be canonical, this case would have to be indistinguishable from inserting the joined interval with value V.

As always with (me and) canonical representations, I have failed to come up with any good leads on google (scholar). Is anyone aware of a result for this particular problem? I would be very thankful for any pointers to papers or implementations.

Answer 1

It's possible to build a data structure that in practice has $O(\lg n)$ lookup, $O(\lg n)$ insertion, and $O(1)$ equality-tests. I'll describe how below. (If you care about theoretical worst-case complexity, there are some caveats, but those caveats can probably be ignored for practical implementation.)

You can handle the lookup, insertion, and creation operations using a balanced binary search tree on the endpoints of the intervals. If you have $n$ intervals, you'll have at most $2n$ endpoints, so you have a balanced tree on $O(n)$ leaves. Lookup and insertion can be done in $O(\lg n)$ time, using an appropriate balanced tree data structure, which is efficient.

Ensuring it has a canonical representation is difficult; I don't know how to do that, while ensuring efficiency. The standard data structures don't have a canonical representation: there are many possibilities for the structure of the tree, for any given contents, and they use these degrees of freedom to help make the operations efficient.

But we can still support the "equality-test" operation efficient, without needing a canonical representation. We'll construct a custom hash function, which produces a hash value $H(f)$ based on the contents of the map $f$ (regardless of the underlying structure of the tree or how the map is stored). Then we can do efficient equality tests: given two maps, we compare their hashes. If their hashes are different, we know they are different maps. If their hashes are the same, we can compare them exhaustively; with a reasonable hash function, the chances of two different maps yielding the same hash will have negligible probability. If you use a cryptographic-strength hash, that possibility is so exponentially rare that you can use a simpler procedure: if the hashes match, then the maps match, and there's no need to check any further. This yields a procedure that is $O(1)$ time to compare equality in practice.

So how do we build the hash function $H$? We'll use an associative hash function. Let $(G,+)$ be an abelian group, and a conventional hash function $h:\{0,1\}^* \to G$. Suppose the map $f$ maps the interval $[\ell_i,u_i]$ to the value $v_i$ for $i=1,2,\dots,n$. Then we'll define the hash of $f$ to be

$$H(f) = \sum_{i=1}^n h(\ell_i,u_i,v_i).$$

Notice that the hash value depends only on the map itself, and not on the structure of the tree used to store the map.

We'll update the hash of the map each time that we update the data structure. This is easy to do, thanks to the structure of $f$ and the fact that $+$ is commutative (since $G$ is abelian). If the map $f'$ is defined by removing an interval $[\ell,u] \mapsto v$ from the map $f$, then their hashes are related by

$$H(f') = H(f) - h(\ell,u,v),$$

which can be computed in $O(1)$ time. Similarly for adding an interval that doesn't overlap any other intervals. Adding an interval that overlaps an existing interval (triggering a split) can be done by deleting the existing intervals and adding in the new intervals. Each of these operations takes $O(1)$ time.

(Alternatively, you can choose a non-abelian group $G$ and then augment the binary tree: in each node, you store the hash of the map that corresponds to the subtree rooted at that node. In this way you can update the hash values for all nodes each time you update the tree.)

It remains to instantiate the hash $H$ by choosing an appropriate group $G$ and an appropriate hash $h$. I suggest that you use a cryptographic hash function for $h$, such as SHA256; that way you can treat collisions as effectively impossible in practice. You can find analysis of how to choose the group $G$ in the cryptographic literature: see https://crypto.stackexchange.com/q/11420/351, https://crypto.stackexchange.com/a/17936/351, and https://crypto.stackexchange.com/q/8615/351.

Answer 2

Here is another solution. You can use the SeqHash data structure in the following paper:

VerSum: Verifiable Computations Over Large Public Logs. Jelle van den Hooff, M. Frans Kaashoek, and Nickolai Zeldovich. CCS 2014.

The SeqHash data structure is a tree-based data structure that lets you store a sequence of numbers. You can do each of the following operations in at most $O((\log n)^2)$ time: create an empty sequence; find the $i$th number in the sequence; concatenate two sequences; compare two sequences for equality; extract a prefix or suffix or any consecutive range of the sequence.

We can use this to implement what you want.

1. First, to store a set of ranges, we extract the endpoints of the ranges, put them in sorted order, and store that sequence in SeqHash. Thus if the ranges are $[x_1,x_2], [x_3,x_4], \dots$, we store the sequence $x_1,x_2,x_3,x_4,\dots$ in SeqHash.

2. Second, we augment the data structure to store the mapping: if the range $[x_i,x_{i+1}]$ maps to the value $v$, we store the value $v$ with the left endpoint $x_i$ of the range in the SeqHash data structure. Thus, each leaf in the SeqHash data structure stores not only the number $x_i$ but also the value $v$ its corresponding range maps to (or null, if $x_i$ is not the left endpoint of a range).

3. Third, insertion is supported as follows: to insert a range, we find where the spot where it will go using binary search, then extract the prefix before the spot and the suffix after the spot, then concatenate the prefix, the new range, and the suffix. Thus we implement insertion using concatenation.

This then yields a solution to your problem.