18
$\begingroup$

I need to store sets of elements of type a. Type a is partially ordered, so comparing $a_1$ and $a_2$ can return smaller, greater, equal or incomparable.

One problem with hashtables is that two equal elements can be represented differently, and I do not have access to a hashing function consistent with equality.

Comparing two elements can be a lengthy process so it would be interesting to minimize comparisons. If needed, it is possible to memoize calls to the comparison operator. I realize now that I will only need to store antichains (or let's assume so). More precisely, the operations I will need to perform are as follows:

  • Remove an element from the antichain;
  • Try to add an element. If the element is smaller than a member, do not add it, otherwise, add it and remove every element smaller than it.

I can also bound every element by two integers, so that if I know that $i_1 < a < i_2$ and $i_3 < b < i_4$, then knowing $i_2 < i_3$ instantly gives me $a < b$. Of course, $i_2 \not< i_3$ does not mean $a \not < b$... Finding integer bounds is a relatively cheap operation in comparison to a full blown element comparison.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ I think we need to know more to inteligently answer your question. Are you storing the elements and the partial order is easily computed? Or are you also storing the partial order in some sort of a lookup table? How do you intend to use the partial order? Are you hoping to use it the same way that linear order is used to store sets (for example in search trees)? $\endgroup$
    – Andrej Bauer
    Commented Oct 7, 2011 at 4:49
  • $\begingroup$ Now that I realized I will only have antichains, I'm not sure there is anything better than the naïve solution of storing the results in a list. If so, sorry for the trouble! $\endgroup$
    – Abdallah
    Commented Oct 7, 2011 at 6:37
  • $\begingroup$ If you think your question is now moot, maybe you should flag it for deletion/closing ? $\endgroup$
    – Suresh Venkat
    Commented Oct 7, 2011 at 15:13
  • 1
    $\begingroup$ Any two elements in the set will be incomparable, but this doesn't mean that the naive representation is the best you can do. For example, consider finite multisets ordered by inclusion (= integers ordered with divisibility): there is a lot of potential for optimisation, depending on your data representation (using cardinality, using the support set, …). These optimisations will strongly depend on the nature of the order relation. Then there's the separate issue of deciding whether it's worth keeping information about now-deleted elements: are you going to compare them often to new additions? $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Oct 7, 2011 at 22:10
  • $\begingroup$ Ok, thank you. So I added some information (the integer bounding possibility) that could lead to optimizations. $\endgroup$
    – Abdallah
    Commented Oct 7, 2011 at 22:44

2 Answers 2

Reset to default
10
$\begingroup$

The paper "Sorting and Selection in PoSets" by Daskalakis, Karp, Mossel, Risensefield, Verbin, 2008 which describes a dynamic representation of PoSets based on antichains.

You might also be interested in the paper "Succinct Posets" by Munro, Nicholson, 2012 recently released on Arxiv and in the bibliography therein. Their data-structure is static but I assume that the next step is to have a dynamical data-structure.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Sorting and Selection in Posets is great to get an idea what is needed for a data structure, but the algorithms are assuming $\mathcal{O}(1)$ tagging of elements in the poset (e.g. exactly the problem we want to solve in the first place!) to compute the relation between two elements in $\mathcal{O}(1)$ after building up the data structure in $\mathcal{O}(qn)$ queries. So, the paper assumes queries of the relation between two elements to be expensive and mapping elements of posets to be trivial, whereas map data structures typically assume the converse of the former to solve the latter. $\endgroup$
    – Sebastian Graf
    Commented Nov 15, 2017 at 11:24
  • $\begingroup$ Having maps represented as a (minimal) decomposition of chains is good insight. Preserving that invariant through deletes is what is tricky, though. $\endgroup$
    – Sebastian Graf
    Commented Nov 15, 2017 at 11:27
5
$\begingroup$

Have you looked at Heeringa et al's "Searching in Dynamic Tree-Like Partial Orders"? They give a dynamic data structure for the predecessor problem on posets. It is designed for a RAM, but you can represent arrays as balanced binary trees and incur only a $O(\lg n)$ multiplicative overhead while making the structure purely functional.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Note this only cover 'tree-like' partial orders, e.g. meet-semilattices, where all elements less than or equal to some element e form a chain. $\endgroup$
    – Sebastian Graf
    Commented Aug 10, 2017 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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