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:

$$ b_0 b_1 \cdots b_{w-1} $$

The data structure maintains:

component	purpose
binary trie	represents prefixes of stored keys
prefix hash tables	map prefixes at each depth to trie nodes
linked leaves	store all keys in sorted order
jump pointers	help locate predecessor or successor

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:

decimal	bits
3	0011
9	1001
12	1100

Search for 9. Its full binary key is 1001.

depth	prefix
1	1
2	10
3	100
4	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.

operation	expected time
exact membership	$O(1)$
deepest prefix search	$O(\log w)$
predecessor or successor	$O(\log w)$

Space usage is:

$$ O(nw) $$

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
}