3
$\begingroup$

Problem formulation

I have implemented an interesting probability distribution data structure: having $n$ elements $a_1, a_2, \dots, a_n$ in the data structure with respective positive weights $w_1, w_2, \dots, w_n > 0$, upon request each $a_i$ may be returned with probability $$\frac{w_i}{\sum_{j = 1}^n w_j}.$$

A Java implementation of my data structure can be obtained here, yet I will specify the algorithm here textually:

There are two types of nodes, relay nodes and leaf nodes. The actual elements with their actual weights are stored in leaf nodes. What comes to relay nodes, we allow only those that have both children (the tree is binary). However, each relay node know how many leaves is there in the subtree starting from that very relay node; also each relay node knows the sum of weights of all its leaves.

Whenever adding a new element, we start traversing the tree from its root, and until we reach a leaf node, we choose that relay node, whose node count is smallest; this way it maintains a logarithmic height.

What comes to the removal of an element, the data structure maintains a hashtable mapping each element to its leaf node. So, first we get the leaf node, remove it, after which, we replace the parent relay node with the sibling leaf.

Whenever sampling an element, we start from root, and choose an appropriate relay node until we reach the appropriate leaf node, whose element we return.

All three basic operations seem to run in worst-case $\mathcal{O}(\log n)$, and my benchmarking supports the observation.

A simple visualization:

Question

Is this data structure already discovered? If yes, could you tell me the name of the paper that discusses it?

$\endgroup$
  • 1
    $\begingroup$ These types of data structures where you store additional info on nodes are generally called 'Augmented Data Structures'.They don't have a solid form , but I can say that storing the number of child nodes and their values are being used in many cases. $\endgroup$ – atayenel Jun 16 '16 at 7:35
  • $\begingroup$ I have seen this factor in the Rational Bézier Curves. This augmented tree reminds me of rank tree / interval tree mixed with scapegoat tree. I know Java, but haven't read your source, I cannot imagine from pure description how it will react for ordered list. $\endgroup$ – Evil Jun 17 '16 at 17:38
  • $\begingroup$ @EvilJS I had to relax the order criterion: the actual internal order will not match, say, insertion order. $\endgroup$ – coderodde Jun 17 '16 at 17:40
  • 1
    $\begingroup$ Sampling from finite sets/distributions is a well-studied problem; I recommend you check out Knuth's TAOCP. IIRC, he has an algorithm that samples faster than logarithmic time. $\endgroup$ – Raphael Jun 17 '16 at 17:48
  • $\begingroup$ @Raphael Do you have any recollection of how efficient are adding/removing elements to/from the distribution? $\endgroup$ – coderodde Jun 17 '16 at 17:54
6
+100
$\begingroup$

This is a straightforward use of augmented data structures. I wouldn't expect it to be publishable on its own; it's more of an undergraduate exercise. So, I would expect that it's probably been thought of many times before by many people independently, but not necessarily written down in any particular research paper.

The idea of storing in the node of a tree the number of leaves under it is a completely standard idea in augmented data structures. So too is the idea of storing each node the sum of the values in the leaves under it. If you read some algorithms and data structures textbooks that describe augmented data structures, I'm sure you'll find examples of both of those motifs.

$\endgroup$
0
$\begingroup$

I might be misunderstanding this, but what functionality does the data structure provide? What is its goal? It seems like you have given a way to build a data structure, but I am unsure what functionality it provides other than perhaps the ability to answer questions about its own structure?

For something that looks similar, but is more static (no insertions or deletions, just a given number of elements with frequency counts or weights), a very well-known problem is to try to minimize the weighted sum of node depths in the tree. These are known as Huffman Trees, used to generate Huffman Codes for compressing data. The tree can be computed in $\Theta(n \lg n)$ time, or $\Theta(n)$ time if you have the weights in sorted order.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.