Introduction to Sum Tree

What is a Sum Tree?

A Sum Tree is a type of binary tree, which means each parent can have up to two children. Its key feature is that each parent’s value is the sum of its children’s values.

The Problem: Sampling Data by Priority

Imagine you have a list of data and want to pick an item at random. The easiest way is to generate a random number between zero and the length of the list, then use that as the index.

data_list = np.array(np.random.rand(100))   # Data generation

index = np.random.randint(0, len(data_list))
data = data_list[index]
print(data)

With this method, every item in the list has the same chance of being chosen.

But what if some items should have a higher chance of being picked because they are more important? How can you sample randomly while still giving priority to certain items?

A Naive Approach: Sort, Then Sample from a Gaussian

One idea is to sort the data list by priority, from highest to lowest. Instead of picking indices at random, you could use a random number generator that is more likely to pick numbers near zero and less likely to pick numbers farther away. A Gaussian (normal) distribution centered at zero does this, and you can adjust how spread out it is using sigma.

The problem is that sigma needs to fit the size of the list. If the list changes, you have to adjust sigma each time. Also, if the generator gives a number bigger than the list, it won’t work. So this method doesn’t hold up well.

A Better Approach: Cumulative Sums

Here’s a method that works better. First, generate a random number between zero and the total of all the priority values in the list. For example, if the total is 1012.4 and the random number is 430.58, you add up the priority values from left to right until the total goes past 430.58.

In this case, the first 24 elements add up to 427.7, and the first 25 add up to 442.8. Since 430.58 is between those two, you would pick the 25th element.

Let’s look at a smaller example to make this clearer.

In this example, the total priority value is 68. If you generate a random number, a result between 0-17 picks the first element, 18-30 picks the second, and so on. The first element covers the largest range, so it has the highest chance of being chosen.

You might also notice that sorting the list is not required. As long as you always sum the priority values in the same order, the higher-priority items still get a bigger share of the number range and are more likely to be picked.

This method works, but it has a downside: finding the right item takes $\mathcal{O}(n)$ time because you have to add up the values one by one. For large datasets, this is very slow. A Sum Tree solves this problem by letting you find items in $\mathcal{O}(\log{n})$ time.

Building a Sum Tree

A Sum Tree stores a set number of data points, which you decide at the start. For example, if you want to store 8 values and their priorities, you need a tree with 15 nodes: 8 leaves for the priorities and 7 parent nodes above them.

Here’s how the earlier data list looks when stored in a Sum Tree. Each parent’s value is the sum of its two children, which is what makes it a Sum Tree.

Retrieving Data from a Sum Tree

Here’s the pseudocode for retrieval:

def retrieve(n, s):
  if n is leaf_node: return n

  if n.left.val >= s: return retrieve(n.left, s)
  else: return retrieve(n.right, s - n.left.val)

You give the function the root node and a random number between zero and the total priority. The function then moves down the tree and returns the leaf node with the matching priority. After that, you can find the related data in your list.

For example, if the random number is 24, the algorithm moves through the tree and finds this node:

That’s the whole idea: you use a simple walk through the tree instead of scanning the list from start to finish.

What’s Next

I might cover how to implement a Sum Tree in Python in a future post. Stay tuned!