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 with word size $w$, determine whether a target key x exists.

Return true if present, otherwise false.

Structure

A Y fast trie consists of two layers:

Keys are partitioned into buckets of expected size $O(w)$.

Each bucket is represented by a key stored in the X fast trie.

Algorithm

First find the predecessor or successor representative in the X fast trie. That identifies the bucket that may contain the key. Then perform a BST search inside that bucket.

y_fast_trie_member(T, x):
    r = x_fast_predecessor(T.representatives, x)

    if r == null:
        return false

    bucket = T.bucket[r]

    return bst_search(bucket, x)

Example

Assume word size $w = 4$ and keys:

Representatives stored in the X fast trie:

Search for 10:

Correctness

Each key belongs to exactly one bucket, and the representatives partition the key space.

The X fast trie identifies the representative whose bucket contains all keys in the relevant range. The BST inside that bucket maintains sorted order, so standard BST search correctly determines whether the key is present.

If the algorithm returns true, the key exists in its bucket. If it returns false, the key is not in the bucket, and no other bucket can contain it.

Complexity

Let $w$ be the word size.

Space usage:

This improves over X fast tries, which require $O(nw)$ space.

When to Use

Y fast tries are useful when:

• keys are integers from a bounded universe
• predecessor and successor queries are required
• memory usage must remain linear
• faster than comparison based trees is desired

They provide a practical balance between speed and space for integer search problems.

Implementation

class YFastTrie:
    def __init__(self, xfast, buckets):
        self.xfast = xfast        # X fast trie over representatives
        self.buckets = buckets    # map representative -> sorted list or BST

def bst_search(bucket, x):
    lo, hi = 0, len(bucket) - 1

    while lo <= hi:
        mid = (lo + hi) // 2
        if bucket[mid] == x:
            return True
        elif bucket[mid] < x:
            lo = mid + 1
        else:
            hi = mid - 1

    return False

def y_fast_trie_member(T, x):
    r = T.xfast.predecessor(x)

    if r is None:
        return False

    bucket = T.buckets[r]
    return bst_search(bucket, x)

type YFastTrie struct {
	XFast   *XFastTrie
	Buckets map[uint64][]uint64
}

func BSTSearch(bucket []uint64, x uint64) bool {
	lo, hi := 0, len(bucket)-1

	for lo <= hi {
		mid := lo + (hi-lo)/2

		if bucket[mid] == x {
			return true
		} else if bucket[mid] < x {
			lo = mid + 1
		} else {
			hi = mid - 1
		}
	}

	return false
}

func YFastTrieMember(T *YFastTrie, x uint64) bool {
	r, ok := T.XFastPredecessor(x)
	if !ok {
		return false
	}

	bucket := T.Buckets[r]
	return BSTSearch(bucket, x)
}