"Last Come => More Relevant" data structures

Question

As I think of data structures I studied and dealt with, they are all optimized to retrieve/put a random element, to perform optimally based on unspoken assumption that each element has equal odds of being asked for (e.g. Red-Black trees).

By the nature of my program, I need to maintain an online dictionary of items that typically serves items that were added last.

That is, the later an item has been added, the higher the likelihood of it being retrieved back in the nearest future.

Speaking more formally, let's define a set $S$ of pair $(k_i, d_i)$, where $k_i \in K $ and $K$ has a comparison operator $\leq$ defined, $d_i \in D$. Let $p(k)$ be the probability of our need to retrieve pair $(k, d)$.

What is an efficient way to store $S$ with regard to function $p$ ?

Answer 1

I think of three possible options:

1. As mentioned before in the comments, one of my all-time favorite data structure, splay-trees. They are easy to implement and probably (assuming the Dynamic Optimality conjecture is true) roughly as good as any other dynamic search tree data structure. We already know that splay trees are as good as any static search tree. Note that there are other types of dynamic binary search trees (tango trees, zipper trees, ...), which will also perform well compared to the best dynamic search tree.

2. Use one or more optimal binary search tree (via dynamic programming). Since you insert/delete elements you need to rebuild the search tree form time to time. Say after a threshold value of elements that change you build the new optimal tree from scratch. This might be applicable, if you have time between the request. The rebuilding can be also be done in the background. Since building a optimal search tree is $O(n^2)$, this is not a good idea for large data sets.

3. Use Hashing. It might not treat the later inserted elements different, but in practice it might be as good as the other ideas.

You might think of keeping the last inserted elements in a separate data-structure (like a hash-map ) which you query first. Of course, from time to time you need to rebuilt.

Answer 2

You can use caching.

Just remember the last element inserted. O(1) when last element is queried. You can also keep list of latest k elements inserted.

And use any good data structure that the language you are using provides. O(log n) for balanced tree based data structure.

Answer 3

Have a look at treaps. A treap is a binary search tree with respect to keys and a heap with respect to a second element parameter ("priority"). That is, if you insert new elements with a higher priority than all already present keys (e.g. by using an increasing counter) those element inserted most recently stay at the top of the tree, thus enabling fast access.

If your access patterns are more dynamic than that, self-adjusting data structures such as splay trees or self-organising lists may be better. Note that you can easily make treaps self-adjusting by changing priorities accordingly when elements are accessed.