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.
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.
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