Mark Gritter (markgritter) wrote,
Mark Gritter

Partially-ordered tuple data sets

I've run into the following data structure problem on several occasions.

Given a partially-ordered set S and some subset B of S, identify whether 'x' is <= (or dually >=) some member of B. Usually this comes up when S is a tuple with pairwise ordering.

For example, S could be 3-tuples (a,b,c) with ordering defined as (a,b,c) <= (d,e,f) iff a<=d && b<=e && c<=f. B then defines a region of 3-space.

Or S could be polynomial terms like w^3 x^2 y^5 z^7. <= is then "divides" and >= is "is a multiple of". (The first time I can remember puzzling about this, I was working in some ring that wasn't an integral domain--- so some nontrivial products were zero. Quickly calculating if a product was divisible by one of the "known" zeros would have helped speed up the computation a bit.)

Or S could be Chinese Poker hands, and <= means "is dominated by". If we have a set of candidate arrangements B, knowing whether a possible arrangement x is dominated is quite useful. (Knowing that x dominates someting already in B is helpful too.)

So... we can obviously implement this data structure in O(N) time and space, just by keeping a list of B's and doing N comparisons. And since partially-ordered sets are commutative, we can avoid adding any element which is already >= an existing one (but that doesn't help the worst case.) But the dumb version has O(1) insertion so it's not all bad. :) If there's no structure to the ordering this is the best you can do.

With the polynomial example, what I ended up doing was using a total ordering based on "weight" (the sum of the exponents.) Then you can limit the search to objects in B with just greater or lesser "weight". You can apply this whenever you can find the appropriate order homomorphism to a total ordering.

A different order homomorphism is to use lexical ordering (if appropriate). To find if (5,6,7) is less than some element of B, we can start our search with (5,6,7) itself but this means we may have to search a lot of irrelevant entries like (6,1,10000) (6,2,20000), (6,3,30000), (7,1,9999) (7,2,19999) etc. A related idea is keep a sorted list for each element of the tuple and store each bound once in each list (D times), then look up the appropriate portion of each list based on x and do an intersection (of the D lists). Or you might do the same but only for one of the elements. These order homomorphism heuristics have the potential to give O(log N) search times instead, but the worst case is obviously still O(N).

One cute idea is to build a complete KxKxK array of all tuples, and then just 'color in' the appropriate tuples when an element is added to B. Lookups are O(1) but insertion is a major pain.

There might be a geometric algorithm which can be used in these cases, but I'm not familiar with that literature. I'd really like to have something in my toolbox that I know is a "good idea".
Tags: code, geek
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.