Algorithm for efficient weighted sampling from a collection that can efficiently be updated

Question

I'm writing a Monte Carlo simulation in which I have to maintain a large collection of items. This collection contains a great many duplicates, and it will most likely be best to store some or all of these in the form of a number that records the number of duplicates, rather than storing each one individually. (The items are essentially strings, so they have a non-negligible memory cost.)

On each iteration I remove a random item from the collection, and possibly add one or two new items. Each item has a weight, and when sampling from the container it's important that the probability of drawing a given item is equal to its weight multiplied by the number of items of that type.

The items that get added on each iteration may or may not be duplicates of ones that are already in the container. The items will probably be roughly Pareto distributed, with a few items having loads of duplicates and many having none, but it's hard to tell in advance.

This seems like a fairly common thing to want to do, and it also seems not entirely trivial to do it efficiently. The obvious way is to store the items in some kind of hash table, pairing each with an integer representing its frequency. The problem is that then it's not very efficient to sample from the container, since you'd have to iterate over the items in an essentially random order.

On the other hand, if they were stored in something like a balanced binary tree then sampling would be very efficient. However, since the container's contents are changing on every update, this would involve rebalancing the tree all the time, which (at least if done in a naïve way) would be very inefficient.

It seems to me that I need a data structure has a trade-off between speed of sampling and speed of updating. Perhaps some kind of partially-sorted heap-like thing that can be re-sorted with a low average cost when only a few items have changed. But I don't know of such a structure.

If there is a standard algorithm / data structure for this purpose then what's it called? If there is there a readily available implementation in Python and/or C++ then that would be a huge bonus.

_{(Note that user thus spake a.k. gave an elegant answer to the question in the non-weighted case, but I've realised that for my application, the weights are really necessary.)}

Answer 1

You can do this with any balanced binary search tree data structure by additionally maintaining the total weight below each node. To randomly sample, compute a uniform random number between $0$ and the weight of the root node, and traverse down through the tree until you find the leaf whose range contains the random number.

Unfortunately, while maintaining the total weight below a given node is straightforward, it does mean you'll likely have to implement your own balanced binary tree structure. Copying and modifying an existing data structure might be fastest in terms of programmer time; you could even use libstdc++'s red black tree implementation.

Answer 2

Assuming C++, if you're willing to store duplicate items, a time efficient approach for the unweighted case is to store them unsorted in a std::vector or std::deque, v.
You can then efficiently add new items by inserting them at the end of v.
To draw a sample, simply pick a random index i into v and use

sample = v[i];
v[i] = v.back();
v.pop_back();

For the additional storage cost you'll get (amortized in the case of std::vector) constant time iterations.

Answer 3

The "standard" data structures for this in C++ are the multiset

http://www.cplusplus.com/reference/set/multiset/

based on a balanced binary tree and the unordered_multiset

http://www.cplusplus.com/reference/unordered_set/unordered_multiset/

based on a hash table.

I would try those first and see if their performance is adequate for your requirements.

Answer 4

You say that you expect to have a lot of items only once, and a few many times.

While in general a self-balancing search tree like the one Geoffrey suggested would be fastest, there is an easier to implement alternative.

Simply keep the $k$ items that only occur once in a vector, like thus spake a.k. suggested, and the other $m$ unique items in an unordered map. You then keep track of the total number of items in each structure, and when you have to sample the map, you accept the $O(m)$ time. However as you expect $k >> m$, this is likely not a problem.

Answer 5

Suppose you have I unique items, each one with multiplicity m_i. You can create a hash table that maps i -> (item, m_i). When you want to sample, construct a partition of [0,1] (i.e. a sorted array of numbers from 0 to 1) where each interval corresponds to an item, and its width is proportional to the multiplicity E.g. if you have 1 cat, 1 dog, 2 frogs, and 3 rats, the array will be [0, 1/7, 2/7, 4/7, 1]. Then, draw from the uniform distribution, and use binary search to find the interval it falls in; this is the sampled item.