Designing small comparable objects

Question

Intro

Consider you have a list of key/value pairs:

(0,a) (1,b) (2,c)

You have a function, that inserts a new value between two current pairs, and you need to give it a key that keeps the order:

(0,a) (0.5,z) (1,b) (2,c)

Here the new key was chosen as the average between the average of keys of the bounding pairs.

The problem is, that you list may have milions of inserts. If these inserts are all put close to each other, you may end up with keys such to 2^(-1000000), which are not easily storagable in any standard nor special number class.

The problem

How can you design a system for generating keys that:

• Gives the correct result (larger/smaller than) when compared to all the rest of the keys.
• Takes up only O(logn) memory (where n is the number of items in the list).

My tries

• First I tried different number classes. Like fractions and even polynomium, but I could always find examples where the key size would grow linear with the number of inserts.
• Then I thought about saving pointers to a number of other keys, and saving the lower/greater than relationship, but that would always require at least O(sqrt) memory and time for comparison.

Extra info: Ideally the algorithm shouldn't break when pairs are deleted from the list.

Answer 1

Perhaps you can use the Farey Sequence? Each key will be a number in reduced form a/b.

If you insert between a/b and a1/b1, the key value you give the new one is (a+a1)/(b+b1).

So you store the ordered pair (a,b) in reduced form (i.e. find the gcd and divide out: Euclid's GCD algorithm).

Initally you start out with 0 and 1. Since the the n^th farey sequence has a/b where both a <= n and b <= n, your O(log n) space requirement will likely also hold.

If a/b > c/d (where a,b,c,d are non-negative integers) then we have that a/b > (a+b)/(c+d) > c/d, so it seems like this should work, even with arbitrary deletions.

Related: Stern-Brocot Tree.

Hope it helps.

Answer 2

I agree with snowlord. A tree would be ideal in this case. A red-black tree would prevent things from getting unbalanced. If you really need keys, though, I'm pretty sure you can't do better than using the average of the keys on either side of the value you need to insert. That will increase your key length by 1 bit each time. What I recommend is renormalizing the keys periodically. Every x inserts, or whenever you detect keys being generated too close together, renumber everything from 1 to n.

Edit: You don't need to compare keys if you're inserting by position instead of key. The compare function for the red-black tree would just use the order in the conceptual list, which lines up with in-order in the tree. If you're inserting in position 4 in the list, insert a node at position 4 in the tree (using in-ordering). If you're inserting after a certain node (such as "a"), it's the same. You might have to use your own implementation if whatever language/library you're using requires a key.

Answer 3

I don't think you can avoid getting size O(n) keys without reassigning the key during operation.

As a practical solution I would build an inverted search tree, with pointers from the children to the parents, where each pointer is marked whether it is coming from a left or right child. To compare two elements you need to find the closest common ancestor, where the path to the elements diverges.

Reassigning keys is then rebalancing of the tree, you can do that by some rotation that doesn't change the order.