Algorithm for selection the most frequent object during factorization

user_1560850 0
Viewed 77

I have N objects, and M sets of those objects. Sets are non-empty, different, and may intersect. Typically M and N are of the same order of magnitude, usually M > N.

Historically my sets were encoded as-is, each just contained a table (array) of its objects, but I'd like to create a more optimized encoding. Typically some objects present in most of the sets, and I want to utilize this.

My idea is to represent sets as stacks (i.e. single-directional linked lists), whereas their bottom parts can be shared across different sets. It can also be defined as a tree, whereas each node/leaf has a pointer to its parent, but not children. Such a data structure will allow to use the most common subsets of objects as roots, which all the appropriate sets may "inherit".

The most efficient encoding is computed by the following algorithm. I'll write it as a recursive pseudo-code.

BuildAllChains()
{
    BuildSubChains(allSets, NULL);
}

BuildSubChains(sets, pParent)
{
    if (sets is empty)
        return;

    trgObj = the most frequent object from sets;

    pNode = new Node;
    pNode->Object = trgObj;
    pNode->pParent = pParent;

    newSets = empty;
    for (each set in sets that contains the trgObj)
    {
        remove trgObj from set;
        remove set from sets;

        if (set is empty)
            set->pHead = pNode;
        else
            newSets.Insert(set);            
    }

    BuildSubChains(sets, pParent);
    BuildSubChains(newSets, pNode);
}

Note: the pseudo-code is written in a recursive manner, but technically naive recursion should not be used, because at each point the splitting is not balanced, and in a degenerate case (which is likely, since the source data isn't random) the recursion depth would be O(N). Practically I use a combination of loop + recursion, whereas recursion always invoked on a smaller part.

So, the idea is to select each time the most common object, create a "subset" which inherits its parent subset, and all the sets that include it, as well as all the predecessors selected so far - should be based on this subset.

Now, I'm trying to figure-out an effective way to select the most frequent object from the sets. Initially my idea was to compute the histogram of all the objects, and sort it once. Then, during the recursion, whenever we remove an object and select only sets that contain/don't contain it - deduce the sorted histogram of the remaining sets. But then I realized that this is not trivial, because we remove many sets, each containing many objects.

Of course we can select each time the most frequent object directly, i.e. O(N*M). But it also looks inferior, in a degenerate case, where an object exists in either almost all or almost none sets we may need to repeat this O(N) times. OTOH for those specific cases in-place adjustment of the sorted histogram may be preferred way to go.

So far I couldn't come up with a good enough solution. Any ideas would be appreciated. Thanks in advance.

Update:

@Ivan: first thanks a lot for the answer and the detailed analysis. I do store the list of elements within the histogram rather than the count only. Actually I use pretty sophisticated data structures (not related to STL) with intrusive containers, corss-linked pointers and etc. I planned this from the beginning, because than it seemed to me that the histogram adjustment after removing elements would be trivial.

I think the main point of your suggestion, which I didn't figure-out myself, is that at each step the histograms should only contain elements that are still present in the family, i.e. they must not contain zeroes. I thought that in cases where the splitting is very uneven creating a new histogram for the smaller part is too expensive. But restricting it to only existing elements is a really good idea.

So we remove sets of the smaller family, adjust the "big" histogram and build the "small" one. Now, I need some clarifications about how to keep the big histogram sorted.

One idea, which I thought about first, was immediate fix of the histogram after every single element removal. I.e. for every set we remove, for every object in the set, remove it from the histogram, and if the sort is broken - swap the histogram element with its neighbor until the sort is restored.

This seems good if we remove small number of objects, we don't need to traverse the whole histogram, we do a "micro-bubble" sort. However when removing large number of objects it seems better to just remove all the objects and then re-sort the array via quick-sort.

So, do you have a better idea regarding this?

Update2:

I think about the following: The histogram should be a data structure which is a binary search tree (auto-balanced of course), whereas each element of the tree contains the appropriate object ID and the list of the sets it belongs to (so far). The comparison criteria is the size of this list.

Each set should contain the list of objects it contains now, whereas the "object" has the direct pointer to the element histogram. In addition each set should contain the number of objects matched so far, set to 0 at the beginning.

Technically we need a cross-linked list node, i.e. a structure that exists in 2 linked lists simultaneously: in the list of a histogram element, and in the list of the set. This node also should contain pointers to both the histogram item and the set. I call it a "cross-link".

Picking the most frequent object is just finding the maximum in the tree. Adjusting such a histogram is O(M log(N)), whereas M is the number of elements that are currently affected, which is smaller than N if only a little number is affected.

And I'll also use your idea to build the smaller histogram and adjust the bigger.

Sounds right?

graph algorithm
1 Answers

I denote the total size of sets with T. The solution I present works in time O(T log T log N).

For the clarity I denote with set the initial sets and with family the set of these sets.

Indeed, let's store a histogram. In BuildSubChains function we maintain a histogram of all elements which are presented in the sets at the moment, sorted by frequency. It may be something like std::set of pairs (frequency, value), maybe with cross-references so you could find an element by value. Now taking the most frequent element is straightforward: it is the first element in the histogram. However, maintaining it is trickier.

You split your family of sets into two subfamilies, one containing the most frequent element, one not. Let there total sizes be T' and T''. Take the family with the smallest total size and remove all elements from its sets from the histogram, making the new histogram on the run. Now you have a histogram for both families, and it is built in time O(min(T', T'') log n), where log n comes from operations with std::set.

At the first glance it seems that it works in quadratic time. However, it is faster. Take a look at any single element. Every time we explicitly remove this element from the histogram the size of its family at least halves, so each element will directly participate in no more than log T removals. So there will be O(T log T) operations with histograms in total.

There might be a better solution if I knew the total size of sets. However, no solution can be faster than O(T), and this is only logarithmically slower.

There may be one more improvement: if you store in the histogram not only elements and frequencies, but also the sets that contain the element (simply another std::set for each element) you'll be able to efficiently select all sets that contain the most frequent element.

user_21599390
Related