Persistent partitioning of the data

Question

I am looking for the approach or algorithm that can help with the following requirements:

• Partition the elements into a defined number of X partitions. Number of partitions might be redefined manually over time if needed.
• Each partition should not have more than Y elements
• Elements have a "category Id" and "element Id". Ideally all elements with the same category Id should be within the same partition. They should overflow to as few partitions as possible only if a given category has more than Y elements. Number of categories is orders of magnitude larger than number of partitions.
• If the element from the set has been previously assigned to a given partition it should continue being assigned to the same partition
• Account for change in the data. Existing elements might be removed and new elements within each of the categories can be added.

So far my naive approach is to:

• sort the categories descending by their number of elements
• keep a variable with a count-of-elements for a given partition
• assign the rows from the first category to the first partition and increase the count-of-elements
• if count-of-elements > Y: assign overflowing elements to the next partition, but only if the number of elements in a category is bigger than Y. Otherwise assign all elements from a given category to the next partition
• continue till all elements are assigned to partitions

In order to persist the assignments store in the database all pairs: (element Id, partition Id)

On the consecutive re-assignments:

• remove from the database any elements that were deleted
• assign existing elements to the partitions based on (element Id, partition Id)
• for any new elements follow the above algorithm

My main worry is that after few such runs we will end up with categories spread all across the partitions as the initial partitions will get all filled in. Perhaps adding a buffer (of 20% or so) to Y might help. Also if one of the categories will see a sudden increase in a number of elements the partitions will need rebalancing.

Are there any existing algorithms that might help here?

Answer 1

This is NP hard (knapsack) on NP hard (finding optimal way to split too large categories) on currently unknown because of future data changes. Obviously the best that you can do is a heuristic.

Sort the categories by descending size. Using a heap/priority queue for the partitions, put each category into the least full available partition. If the category won't fit, then split it as evenly as you can into the smallest number of possible partitions. My guess (experiment!) is that trying to leave partitions at the same fill is best.

On reassignment, delete the deleted elements first. Then group new elements by category. Sort the categories by how many preferred locations they have ascending, and then by descending size. Now move the categories with 0 preferred locations to the end.

For each category, if possible split its new elements across the preferred partitions, leaving them equally full. If this is not possible, put them into the emptiest possible partition. If that is not possible, then split them to put them across the fewest possible partitions.

It is, of course, possible to come up with data sets that eventually turn this into a mess. But it makes a pretty good good faith effort to try to come out well.