7
$\begingroup$

I am looking for a data structure to store a set such that given two instances of size $O(n)$ which are known to have non-empty intersection, the minimum element of the intersection can be found in $O(\log n)$ time. Is this possible to achieve, either for worst-case or amortized complexity? Other requirements for the data structure: $O(\log n)$ deletion, $O(n \log n)$ initialization.

Here is an example application of such a data structure, to clarify the requirements. The input consists of n subsets of $\{1, ..., n\}$ all containing the number n. The output is an n by n matrix whose $i, j$ entry is the minimal element in the intersection of sets i and j. With a basic approach one can solve this problem in $O(n^3)$ time. With a data structure satisfying the conditions above, one could solve it in $O(n^2 \log n)$ time.

Improve this question
$\endgroup$
8
  • $\begingroup$ The situation I am most interested in is when the sets have sparse lower tail with density steadily increasing. For instance there is an obvious O(d log n) algorithm for sets with density bounded below by 1/d, where you use min heaps and start from the minimum of one set, then ping pong back and forth always grabbing the next largest element in the heap until you stabilize. $\endgroup$ – pre-kidney Aug 14 '18 at 1:35
  • $\begingroup$ What does it mean for a set to have a sparse lower tail, or for its density to be steadily increasing? $\endgroup$ – D.W.♦ Aug 14 '18 at 20:13
  • $\begingroup$ For example, think of a random set where element i is included with probability 1/(n-i) for i <n and n is included with probability 1. $\endgroup$ – pre-kidney Aug 14 '18 at 20:19
  • $\begingroup$ If you're able to edit the question to specify a particular prob. distribution, that might make this easier to solve. For instance, if each set is randomly chosen (where element i is included with probability p, regardless of i), then I think there's a natural algorithm whose expected running time is something like $O(n^2 \log n)$: first enumerate all pairs of sets $S_i,S_j$ that both contain 1; then all pairs that contain 1 (but haven't already been found); and so on. There's a simple stopping condition, and if the sets are random, you won't need to continue very far before stopping. $\endgroup$ – D.W.♦ Aug 14 '18 at 20:20
  • $\begingroup$ As another example, for the specific distribution in your comment, there's a straightforward $O(n^2 \log n)$ time algorithm, as the expected size of each set is $O(\log n)$. $\endgroup$ – D.W.♦ Aug 14 '18 at 20:26
2
+50
$\begingroup$

You can't. There is no such data structure. Assuming you have a separate instance per set, and each instance is initialized separately (using only information about the set it represents and not any information about any of the other sets), these running times are not achievable.

In particular, when you have two sets, finding the minimum common element takes $\Omega(n)$ time. Indeed, testing disjointness requires $\Omega(n)$ time, as explained here. Now, imagine starting with two sets $S_1,S_2$ over the universe $\{1,2,\dots,n-1\}$. Let $T_1=S_1 \cup \{n\}$ and $T_2 = S_2 \cup \{n\}$. Now $T_1,T_2$ are guaranteed to have a common element. So, if you had a good data structure for your problem, store $T_1$ in one instance of the data structure and $T_2$ in another. Then, if we had a way to find the minimum element of $T_1 \cap T_2$ in $o(n)$ time, this would give us a way to test disjointness of $S_1,S_2$ in $o(n)$ time (just test whether the minimum element is smaller than $n$) -- but we already know the latter is not possible. It follows that the former is not possible, either, i.e., any data structure for your problem must take $\Omega(n)$ time to find the minimum common element of two sets.

This doesn't mean that your application can't be solved efficiently. There still could be a way to solve your application in $O(n^2 \log n)$ time; this result doesn't rule that out.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ I would greatly appreciate if you could make your answer a little bit more self-contained, as it cites your answer on another post which in turn cites a result you have not given reference to. $\endgroup$ – pre-kidney Aug 16 '18 at 6:43
  • $\begingroup$ Let me point out exactly which step I believe needs further elaboration. The key step in your argument is the claim that, for sets stored in whichever way but unable to access each other's memory, solving the disjointness decision problem takes Omega(n) time. You claim that any faster algorithm would contradict basic communication complexity results. However, this model of the communication channel appears to be more general than the basic communication models I have found in the literature, for which the Omega(n) bound is known. This is why I ask for a specific citation. $\endgroup$ – pre-kidney Aug 16 '18 at 19:09
  • $\begingroup$ @pre-kidney, I don't understand what way it seems more general. Anyway, it seems your objection is primarily to my other answer, so let's take any discussion there, please. I've edited my answer there to articulate the reduction in detail. If you have a specific concern about the model of computation, please comment there explaining specifically what difference in model of computation you see. I don't see one, but that doesn't mean you're wrong -- I'm not an expert on this subject, and I could always be mistaken. $\endgroup$ – D.W.♦ Aug 16 '18 at 19:20
  • $\begingroup$ Fair points and thanks for the update. Will take a look. $\endgroup$ – pre-kidney Aug 16 '18 at 19:46
-1
$\begingroup$

Here is an idea to solve the problem, given 2 sets:

You can hold "sets" by a red black tree. In addition, for every node in the tree we associate one bit to determine if its subtree contains an element in both sets. For sake of presentation, it is called the insertion bit. I assume the red black tree sorts the elements from left to right.

When inserting an element to the tree, the algorithm checks if the element exists in the tree (i.e., in the other the set). If not- we insert the element as usual. If not, by traveling from the root to the leaf containing the element, the algorithm turns on the insertion bit of the corresponding nodes. In the worst case it takes $O(\log n)$.

When deleting an element, the algorithm checks if the element exists in the tree, and if the insertion bit is turned on. If the element does not exists in the tree- we return an error. If the element exists, and the insertion bit is off, then we delete the element as in the Red Black tree algorithm. Otherwise, by traveling from the root to the leaf containing the element, the algorithm turns off the insertion bit of the corresponding nodes. Deletion takes $O(\log n)$.

Finally, the algorithm for finding minimal element shared by both sets begins with the root. If the insertion bit of the root is turn off- then the sets are disjointed, the the algorithm returns an error. Otherwise, the algorithm travels recursively to the left child if its insertion bit is turned on, and otherwise it travels to the right child. The algorithm stops at the element with the minimal value. The algorithm runs at $O(\log n)$.

I am trying to think how to generalized the for a larger number of sets...

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ This doesn't meet the stated criteria since it assumes the two instances are known to each other during initialization - if you had many instances and needed to find pair wise minimal intersections, this would not meet timing since you would have to rebuild the data structure for each pair of sets. $\endgroup$ – pre-kidney Aug 14 '18 at 17:06
  • $\begingroup$ If the instances are not know to each other- then you can merge them in $O(n)$ time using en.wikipedia.org/wiki/… $\endgroup$ – user3563894 Aug 14 '18 at 18:21
  • $\begingroup$ What is the input of the problem? When initializing the sets you can insert\delete the elements into a common tree, and then using successive operations of delete and insert won't effect the complexity of a query, which takes $O(\log n)$ $\endgroup$ – user3563894 Aug 14 '18 at 18:25
  • $\begingroup$ That's the point, the sets can't be coupled. Let me update my question with an example application of such a data structure, to clarify. $\endgroup$ – pre-kidney Aug 14 '18 at 20:04
  • $\begingroup$ By the way, I did not down vote you - I think your answer is useful for the discussion and extra clarification it generated, even if it does not truly answer my question. $\endgroup$ – pre-kidney Aug 14 '18 at 20:16
-1
$\begingroup$

Initialize:
1) create a red-black tree containing all elements of list #1 - O(n log n) for the entire list.
2) iterate through all elements of list #2, and check if it exists in the red-black tree - O(n log n) for the entire list
3) if it exists in the red-black tree, insert that element from list #2 into your favorite min heap - O(n log n) for the entire list

To then search find the min intersecting element just look at the top of the heap, so that's O(1).

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ This approach suffers from the same issues as user3563894's answer, see comments there. $\endgroup$ – pre-kidney Aug 16 '18 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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