Amazon.com, Inc.
System for dividing a tree data structure to improve traversal operations

Abstract:

Described are techniques for efficiently traversing a tree data structure to determine responses to queries by first dividing the tree data structure into linear chains of nodes. Linear chains may be formed by beginning at an initial node, including the child node of the initial node that has the largest number of descendant nodes, and proceeding to include child nodes associated with the largest number of descendant nodes until a node lacking child nodes is reached. Additional chains may then be formed by beginning at an initial node not included in previous linear chains and repeating the process. Responsive to a received query, traversal of each linear chain encountered along a query path may be performed more efficiently than other traversal algorithms that traverse a tree data structure until an end node is reached.