Adapting ADtrees for High Arity Features

Robert Van Dam, Irene Langkilde-Geary, Dan VenturaAAAI 2008

Abstract

All-Dimensions trees (ADtrees) are efficient for caching data statistics but suffer from performance degradation when handling high-arity features. This paper introduces Complete Vary Nodes and Clump Nodes to mitigate exponential query times and memory bloat, enabling ADtrees to scale to complex domains like natural language processing.

Introduction

The All-Dimensions tree (ADtree) is a specialized data structure designed for rapid "counting" queries in large datasets. A core optimization in the original ADtree design is the removal of the Most Common Value (MCV) node for any feature. Since the total count is known at the parent level, the MCV count can be derived by subtracting the counts of all other sibling nodes.

While effective for low-arity features, this "MCV trick" fails when features have thousands of possible values (e.g., vocabulary in text data). In such cases, querying the MCV requires expanding and summing thousands of sibling nodes. In dynamic or "lazy" trees, this leads to a catastrophic expansion of unnecessary nodes, exhausting memory and increasing query latency.

Proposed Methods

To address the challenges of high-arity features, two primary modifications are proposed:

1. Complete Vary Nodes and RatioMCVs

The system introduces an Arity Threshold. If a feature's number of possible values exceeds this threshold (e.g., 50), the MCV node is retained rather than deleted. These are termed "Complete Vary Nodes," ensuring $O(1)$ lookup time for all values. Additionally, a RatioMCV threshold is used: if one value is overwhelmingly dominant (e.g., >99% of occurrences), it may still be deleted to save space, provided the query cost remains manageable.

2. Clump Nodes

In dynamic trees, expanding every sibling to calculate a missing MCV is inefficient. Clump Nodes solve this by grouping all un-queried siblings into a single aggregate node. This node stores the sum of all "other" values, allowing the MCV to be calculated via a single subtraction without fully populating the tree.

Clump nodes aggregate multiple low-frequency values into a single node to avoid expanding the entire tree for high-arity features.

Experimental Evaluation

The methods were evaluated using the Wall Street Journal (WSJ) corpus from the Penn Treebank. This dataset is characterized by high-arity features such as "Original Word" (42,136 values) and "Word Stem" (35,698 values). The researchers generated 16 feature sets, incorporating linguistic context that expanded the potential event space to $10^{31}$ combinations.

Key Results and Insights

Empirical results demonstrate that the "space-saving" benefit of removing MCVs is negligible in high-arity settings—often less than 0.01%—while the computational cost is immense.

The relationship between arity threshold and tree size across various feature sets, highlighting the optimal threshold range.

Key findings include:

  • Optimal Thresholds: An arity threshold between 20 and 50 provides the best balance between memory usage and query speed.
  • Memory Efficiency: In dynamic settings, these modifications reduced tree sizes by 80-90% by preventing unnecessary node expansions.
  • Scalability: The proposed methods allowed complex linguistic models to be built in hours, whereas baseline ADtrees often crashed due to memory exhaustion.
  • Local Context Sensitivity: The arity of a feature is not static; it decreases as one moves deeper into the tree (e.g., filtering by Part-of-Speech). The proposed methods adapt to this local context dynamically.

Conclusion

By adapting ADtrees with Complete Vary Nodes and Clump Nodes, the researchers have made this powerful data structure viable for high-arity datasets. Future work will focus on further optimizing memory management during the tree construction and garbage collection phases to handle even larger state spaces.

Summary updated

BibTeX
@inproceedings{dam2008adapting,
  author = {Robert Van Dam and Irene Langkilde-Geary and Dan Ventura},
  title = {{Adapting ADtrees for High Arity Features}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure