X-Y Fast Trie in real world applications

8
votes

I am trying to understand the X and Y Fast Trie data structures and it's not clear why that structures are not used in large database since their asymptotic complexity is less than Log(N). In cases where we have a database of Terabytes, is not better use a Y Fast Trie than for example a B-tree?

3
databasedata-structurestime-complexity
Which database implementation are you talking about? It would seem that if the states were high enough, as they might be in a flagship product, the vendor could simply try one, then try the other and use the best! – FastAl
I meant to say 'if the stakes were high enough' ... but S.O. won't let me edit it... – FastAl
I am looking for a data structure to handle potentially terabytes of data, and for example I found that BTree and derived are used to index data blocks or implement a filesystem. So my doubt is why not use something that is asymptotically better. I didn't find studies about the performace of Y Fast Trie in real context. I understood that Y Fast Trie could not be efficient when I have to store only few elements, or am I wrong? Thank you – 4nf3rt

3 Answers

10
votes

There are a few reasons that X-fast or Y-fast tries might not be useful in practice. Here are a few:

  1. X-fast tries internally require several linked structures, including a bitwise trie and a doubly-linked list of elements. These don't perform well in database environments where elements are stored on disks and following a pointer can require a disk seek. (For similar reasons, databases often use B-trees over binary search trees). Additionally, they require the use of balanced binary search trees augmented with information to perform a split or join, which adds in extra space and introduces even more pointers to follow.

  2. X-fast tries internally require the use of hash tables with worst-case O(1) lookups. Hash tables with these requirements usually require a variety of hash functions to be applied to look up an element and (generally speaking) don't have the best locality compared to, say, a linear-probing hash table, so lookups are a bit slower.

  3. Because of the hash tables in X-fast tries and the use of splitting and joining of BSTs in Y-fast tries, these two data structures are only amortized efficient rather than worst-case efficient. In some cases, this is unacceptable - it would be bad if, periodically, a database query ends up taking 100x or 1000x normal time even if on average everything works out quite well.

  4. The use of hash tables in X-fast tries and Y-fast tries means that there is an element of randomness involved in the runtimes of the data structures. On expectation they're efficient, but it's possible that due to bad luck, the runtimes of the data structures might be quite high. Specifically, the cost of doing a rehash in an internal hash table or doing a split or join on a tree can be quite high. In a database implementation, reliability is important, so this randomness might hurt.

  5. Due to all the reasons outlined above, the constant factors buried in the runtimes of X-fast and Y-fast tries are quite large. In the long run, they should end up being faster than other data structures, but "the long run" might require inputs that are vastly larger than the sorts of data sets that could feasibly fit into a database.

Hope this helps!

9
votes

While templatetypedef seems to have given a detailed answer, most points in that answer are simply not true. Let me refute it one by one:

  1. X-fast tries internally require several linked structures...don't perform well in database environments...

X-fast tries are essentially binary search trees defined on metric space. There are techniques to organize a binary trees into reasonable pages. The double linked structure seems bad, but the pointer will not be invoked until a successor was found. That's only 1 disk seek.

  1. X-fast tries internally require the use of perfect hash tables...

That's not true. You can use whatever hashing techniques. To guarantee the constant time look up, you can use cuckoo hashing instead of perfect hashing.

  1. Because of the hash tables in X-fast tries...only amortized efficient rather than worst-case efficient...

That's not true either. If you use perfect-hashing or cuckoo hashing, constant look-up time will be guaranteed. The insert/delete time will be amortized, but that's not too bad for a search intensive system (e.g. Lucene). Most modern search engines are built on the idea of sacrificing write time to boost search.

  1. The use of hash tables in X-fast tries and Y-fast tries means that there is an element of randomness involved in the runtimes of the data structures...

That's depend on the goal of the system. The above statement is true only if you want to support reliable and efficient write. But for the majority of the search-oriented applications, your priority is to boost the search speed.

  1. Due to all the reasons outlined above, the constant factors buried in the runtimes of X-fast and Y-fast tries are quite large...

It is true that the constant factor is not trivial - but I would be surprised to see anything more than 4, and consider the loglogM time (e.g., 6 for a 64 bit universe), that's nothing.

So what's the real reason why there are so few industrial applications of Y-fast tries? The database industry is a large, lucrative business that tends to be slow in adopting new techniques. The R-tree did not see much adoption until the late 1990s. The object-oriented concepts were consistently rejected by the industry, despite its theoretical maturity. They DB people also kept rejecting anything other than B-trees until open source search engines such as Lucene beats RDBMS in almost all fronts of search-related business. Just last month a senior Oracle guy told me a trie/hash table based system can never be real time - until I show him how to do it with in-memory caching/merging.

-1
votes

A bit late but I think the other answers are wrong. The reason no one uses x/y-fast tries is that there's a better, faster alternative.

BSTs can achieve the same querys of y/x-fast tries but with much smaller constants and worst case of O(logn). Most of the times for realy big data structures you can not afford an O(nlogu) or O(n + logu) worst case (like in the x/y-fast tries) because n can be huge.

Also the BST almost certainly is going to be faster no matter how big n is because the log is very small (even if n is the number of atoms in the observable universe the log is about 250-260).

So the constants matter the most, not the complexity. And even if the BST would be slower it's going to be only a little bit slower and only if n is really huge.

Also @jzl106 said that the constants are no more than 4 but that's completely bullshit. If the constants are measeared as they should be as the number of processor clock ticks devided by loglogM you would get much much bigger constants.

So BSTs are probably going to be faster, they have small worst case time and are much easier to implement. So there isn't any practical reason to use x/y-fast-tries (at least not for there regular queries of insert, delete, find, predecessor and successor)