Fast comparison with a tolerance

Question

I am trying to find a way to compare two real numbers (actually floating-point) with a tolerance, i.e. test $|r-s|\le\epsilon$. Without loss of generality, $\epsilon=1$.

I want to do this by replacing the numbers by a discrete key computed on them in such a way that when two keys differ, they map two significantly distant numbers.

$$K(r)\ne K(s)\implies |r-s|\ge 1.$$

The converse,

$$K(r)=K(s)\implies |r-s|<1.$$

may only partially hold, but should be false in a minority of the cases. ($K(r):=0$ is indeed a trivial solution to the first requirement, but is of no use because of the second.)

In my context (database search), the key being discrete and a single comparison for equality being sufficient are essential properties.

The first idea that come to mind is simple rounding, or equivalently, flooring, i.e.

$$K(r):=\lfloor r\rfloor.$$

Anyway this doesn't work as all values in range $[r,r+1)$ map to $K(r)$; the values $1$ unit away from these span $(r-1,r+2)$, which maps to one of $r-1,r,r+1$. So you would need a triple equality test

$$|r-s|<1\implies \lfloor r\rfloor=\lfloor s\rfloor-1\lor \lfloor r\rfloor=\lfloor s\rfloor\lor \lfloor r\rfloor=\lfloor s\rfloor+1.$$

If I am right, the reasoning can be extended to any function $K$: the numbers that map to $K(r)$ are in the set $K^{-1}(K(r))$; the numbers one unit away are in the Minkowski sum $K^{-1}(K(r)) + (0,1)$, which cannot be covered by a single $K^{-1}(K(s))$.

I can also accept a scheme where the key function is computed differently for $s$, but the single comparison principle must remain

$$K(r)\ne L(s)\implies |r-s|\ge 1.$$

Is this a known problem ? Is there a solution or a workaround ?

Update: the problem statement was reformulated in the original text.

Answer 1

If for all $|r - s| < 1$ it is the case that $K(r) = K(s)$ then $K$ is constant (exercise).

What you are asking is impossible.

One thing which is possible is to compare keys with three rather than two possible outcomes:

1. If $K(r)$ is close to $K(s)$ then $|r - s| < 1$.
2. If $K(r)$ is far from $K(s)$ then $|r - s| \geq 1$.
3. Otherwise, we don't know.

Of course, the aim is that the third case happens as rarely as possible. One simple way to achieve this is to choose a random $x$ and some small (non-random) $\epsilon > 0$, and to use $$ K(r) = \lfloor r/\epsilon + x \rfloor. $$ Under this definition, the only uncertainty is for $r,s$ at distance $(1-\epsilon,1+\epsilon)$. The random component mitigates even this uncertainty, albeit only by a little.

Answer 2

The second variant isn't much better: $\forall s,r: |r-s| < 1 \Rightarrow K(r) = L(s)$ implies that $\forall r: K(r) = L(r)$, as $r = s$ is only a special case. On the other hand, you are down to two comparisons:

$K(x) := \lfloor 0.5\cdot r + 0.5 \rfloor \\ L(s) := \lfloor 0.5\cdot s \rfloor \\ \forall r,s: |r-s|<1 \Rightarrow K(r) = L(s) \lor K(r) = L(s) + 1$

If you are trying to build an index by hashing these keys, two lookups or double the space might be good enough.

Answer 3

As others have said, what you want is impossible.

But you might want to look at locality-sensitive hashing. It achieves something vaguely similar: if two elements are similar, then with significant probability they will have the same hash.

It is possible to amplify the probability by hashing with multiple independent hash functions. With high probability, at least one of the hashes will have the property that the two elements have the same hash.

This may or may not be adequate for your application, but it's worth knowing about.