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.

Problem

Given an X fast trie storing integer keys with word size $w$, decide whether a target key x is present.

Return true if x exists, otherwise false.

Structure

An X fast trie stores keys as fixed width binary strings.

For word size $w$, each key has bits:

The data structure maintains:

For exact membership, the deepest prefix of length $w$ is the full key.

Algorithm

Check whether the full key appears in the hash table for depth $w$.

For predecessor or successor search, the structure first finds the longest existing prefix using binary search over depths. Exact membership is simpler because the full length prefix is enough.

x_fast_trie_member(T, x):
    prefix = bits(x, T.word_size)

    if prefix in T.level[T.word_size]:
        return true

    return false

For the more general search path:

x_fast_trie_deepest_prefix(T, x):
    lo = 0
    hi = T.word_size

    while lo < hi:
        mid = (lo + hi + 1) // 2
        p = prefix(x, mid)

        if p in T.level[mid]:
            lo = mid
        else:
            hi = mid - 1

    return lo

Example

Use word size $w = 4$.

Stored keys:

Search for 9. Its full binary key is 1001.

Since prefix 1001 exists at depth 4, the key is present.

Correctness

Every stored key appears as a leaf in the binary trie. The hash table at depth $w$ contains exactly the full length prefixes of stored keys.

If the lookup finds the full bit string for x, then a leaf for x exists, so the key is present. If the full bit string is absent, no stored key has exactly the same $w$ bits, so x is absent.

The deepest prefix routine is correct because prefixes are monotone by depth. If a prefix of length $d$ exists for x, then every shorter prefix also exists. Therefore binary search over prefix length finds the maximum existing depth.

Complexity

Let $w$ be the number of bits in the universe.

Space usage is:

because every stored key may contribute one prefix per level.

When to Use

X fast tries are useful for bounded integer keys when fast predecessor, successor, and membership operations are needed.

They are appropriate when:

• keys are fixed width integers
• expected hash table performance is acceptable
• memory overhead of storing many prefixes is acceptable
• ordered operations are needed faster than comparison tree bounds

For lower memory usage, a Y fast trie is often preferred.

Implementation

class XFastTrie:
    def __init__(self, word_size):
        self.word_size = word_size
        self.level = [set() for _ in range(word_size + 1)]

    def bits(self, x, length):
        shift = self.word_size - length
        return x >> shift if length > 0 else 0

    def insert_key_prefixes(self, x):
        for depth in range(self.word_size + 1):
            self.level[depth].add(self.bits(x, depth))

    def member(self, x):
        return self.bits(x, self.word_size) in self.level[self.word_size]

    def deepest_prefix(self, x):
        lo = 0
        hi = self.word_size

        while lo < hi:
            mid = (lo + hi + 1) // 2
            p = self.bits(x, mid)

            if p in self.level[mid]:
                lo = mid
            else:
                hi = mid - 1

        return lo

type XFastTrie struct {
	WordSize int
	Level    []map[uint64]bool
}

func NewXFastTrie(wordSize int) *XFastTrie {
	level := make([]map[uint64]bool, wordSize+1)

	for i := range level {
		level[i] = make(map[uint64]bool)
	}

	return &XFastTrie{
		WordSize: wordSize,
		Level:    level,
	}
}

func (t *XFastTrie) Prefix(x uint64, length int) uint64 {
	if length == 0 {
		return 0
	}

	shift := t.WordSize - length
	return x >> shift
}

func (t *XFastTrie) InsertKeyPrefixes(x uint64) {
	for depth := 0; depth <= t.WordSize; depth++ {
		t.Level[depth][t.Prefix(x, depth)] = true
	}
}

func (t *XFastTrie) Member(x uint64) bool {
	p := t.Prefix(x, t.WordSize)
	return t.Level[t.WordSize][p]
}

func (t *XFastTrie) DeepestPrefix(x uint64) int {
	lo, hi := 0, t.WordSize

	for lo < hi {
		mid := lo + (hi-lo+1)/2
		p := t.Prefix(x, mid)

		if t.Level[mid][p] {
			lo = mid
		} else {
			hi = mid - 1
		}
	}

	return lo
}