4
$\begingroup$

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$ ?

$\endgroup$
5
  • 1
    $\begingroup$ What's wrong with double linked list ? $\endgroup$ Jul 11 '13 at 19:28
  • 5
    $\begingroup$ Splay trees? quote: "A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again" $\endgroup$ Jul 11 '13 at 21:13
  • 1
    $\begingroup$ I second splay trees (and optimal binary search trees). Is your setting dynamic or static (it's static if the set of elements doesn't change -- I'm guessing dynamic)? $\endgroup$
    – Juho
    Jul 11 '13 at 22:12
  • $\begingroup$ What operations does your data-structure need to support? $\endgroup$
    – Aryabhata
    Jul 12 '13 at 0:59
  • $\begingroup$ The set is dynamic. Operations are: look-up and insertion/deletion with look-up making 95% of request, among which most refer to the latest inserted... $\endgroup$ Jul 12 '13 at 6:37
5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ optimal bst is in $O(n^3)$? $\endgroup$ Jul 12 '13 at 8:21
  • 1
    $\begingroup$ @HendrikJan: Opt. BST can be computed in quadratic time. The speed-up is due to Knuth. "6.2.2: Binary Tree Searching". The Art of Computer Programming. 3: "Sorting and Searching" (3rd ed.). Addison-Wesley. pp. 426–458. ISBN 0-201-89685-0. $\endgroup$
    – A.Schulz
    Jul 12 '13 at 11:24
  • $\begingroup$ Thanks!! Indeed, standard Dynamic programming is $n^3$, but I forgot about the monotonicity property that limits the search for the optimal root in each level: "if you add an item at the right, the optimal root cannot move left". $\endgroup$ Jul 12 '13 at 11:41
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.