3

Where would you use splay-tree in production. I mean a REAL LIFE example.

I was thinking about implementing autocomplete using tries and splay trees. For a large dataset it's not a good idea to traverse through trie from node x to the leaves to return results, so the idea was of having a splay tree inside a node in trie, so when user entered 'sta' it will go to s-t-a, 'a' - node and then return the top 5 elements in the splay tree (by BFS/level traversing, which doesn't necessarily mutates/modifies the tree)

Of course after the autocomplete variant was picked, we should traverse up the trie and update all splay trees inside those nodes.

Since splay trees are sensitive in concurrent environments I was questioning its' usage in production

Your ideas?

2 Answers 2

4

Splay trees are not a good match for data which rarely or never changes, particularly in a threaded environment. The extra mutations during read operations defeat memory caches and can create unnecessary lock contention. In any case, for read-only data structures, you can do a one-time computation of an optimal tree. Even if that computation is slow, it will have no impact on the long-term execution time.

I'm not entirely persuaded by the claim that large tries are slow, and certainly not in the case of autocompleters. On even not-so-modern hardware, the cost of a trie traversal is trivial compared to the time it takes for the user to type a character, or even the time it takes for the underlying keyboard driver and input processor to deliver the keypress to your application.

If you really need to optimise a trie, there is good reason to believe that a hybrid data structure with a trie at the root combined with a linear (or binary) search once the alternatives can fit in a cache line. This maximizes the benefit of the trie's large fan-out while avoiding the poor caching behaviour and excessive storage overhead at the end of the lines.

Splay trees are most useful (if they are useful at all) on data structures which are modified frequently. The ckassic example is a "rope" data structure (a tree of string segments), which is one way to attempt to optimise a text editor by avoiding large string copies. Compared with a deterministic tree-balancing algorithm such as RB-trees, the splay tree algorithm has the benefit of simplicity, as well as only touching nodes which form part of the tree traversal.

However, the ready availability of self-balancing tree libraries (part of the standard libraries of many modern programming languages) combined with often-disappointing empirical results make the splay algorithm a niche product at best, although it is certainly a fascinating idea.

2
  • thanks for your answer! Of course the usage in this case for splay tree would be to show top 5 autocompletes for the given input string. For example for the given input 1 million suggestions can be printed out, but we want to show the most frequent ones. That's is why I was thinking of using trie together with a splay tree in this example, in order to fast retrieve the relevant recommendations
    – denis631
    Dec 6, 2017 at 23:04
  • 1
    @denis631, careful. Splay Trees are amortized O(log N) retrieval, but will see cases where individual retrievals take N time. This will at minimum mess with your long tail latencies. It will also mess with your intuitions. E.g. you said "by BFS/level traversing, which doesn't necessarily mutates/modifies the tree" but this leads me to believe you think the splay tree is mostly balanced. Splay trees can be wildly unbalanced, which means most classic recursive algorithms are a bad idea. I suggest using something like a Red-Black tree instead. Oct 6, 2022 at 10:34
2

I found a quite interesting usage of splay trees in Network load optimisations, it's called SplayNet. A Autonomous System (I think under Facebook) has implemented this maybe around 2015 and they have somehow managed with this to lower their internal communication load by around 40%(?). So there is a good usage for Splaytrees!

Few weeks ago i was also reading about Splaytrees being usefully depending on the spread in the sequence of Search. If there is none you could also use f.a. binary trees or some static trees. But in the moment there is one, Splaytrees perform (if you use unlimited time) better.

In my thesis I use splay trees as pre processed data collection for the actual searching. So the splay tree only stores the results of the most common search requests. In the next step the search starts from the splay tree given node ... I think this is useful for big datasets, specially if it's stored on different computers/storages, so your program has a better guess where to start. To say it the easy way - my splaytrees stores the FAQ of the given datastructure/dataset :)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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