tag

#integer-set

3 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

X Fast Trie Search

X Fast Trie Search X fast trie search looks up an integer key from a fixed word universe by combining a binary trie with hash tables over prefixes. A normal binary trie follows one bit at a time. An X fast trie accelerates this process by storing every prefix length in a hash table. This allows the search to find the deepest existing prefix by binary search over prefix length....
algorithms searching x-fast-trie integer-set
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Van Emde Boas Search

Van Emde Boas Search Van Emde Boas search looks up an integer key in a recursive data structure over a fixed universe of keys. A van Emde Boas tree stores integers from the universe $$ {0, 1, \ldots, u - 1} $$ where $u$ is usually a power of two. The structure supports membership, successor, predecessor, insertion, and deletion in logarithmic time with respect to the bit width of the...
algorithms searching van-emde-boas-tree integer-set
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Y Fast Trie Search

Y Fast Trie Search Y fast trie search improves the space cost of X fast tries by storing only a subset of keys in the prefix structure and grouping the rest into balanced binary search trees. Instead of storing all prefixes, it samples representatives and maintains buckets of nearby keys. Search combines a fast prefix lookup with a local tree search. Problem Given a Y fast trie storing integer keys...
algorithms searching y-fast-trie integer-set