Existence of Efficient Set Difference Algorithm

Question

As a foreword, I'm not asking what the algorithm is, just whether one can possibly exist (though, if it does already exist and someone knows what it is, that'd be great).

Basically, given two sets $S$ and $T$, I want to compute the two set differences $I = T \setminus S$ and $R = S \setminus T$. The goal is that if $S$ represents a "before" set, and $T$ an "after" set, I want to know what elements were inserted into (represented by $I$) and removed from (represented by $R$) the original set $S$ to get to $T$.

A naïve approach would be to compare every element of $S$ with every element of $T$, a worst-case runtime of $O(n * m)$, where $n = |S|$ and $m = |T|$.

An improvement would be to treat $S$ as a list and sort it, then do a binary search in the sorted list for every element in $T$. This would be worst-case (I believe) $O(n \log n + m \log n)$.

However, I think I can get it down to $O(n + m)$, and here's my thought process:

If $S$ is a list of $s_i$ and $T$ a list of $t_i$, we can define a "modification" bit for each element in each list.

If we define $$c_i = \begin{cases} 1, & s_i \in R \\ 0, & \text{else} \end{cases}$$ and $$d_i = \begin{cases} 1, & t_i \in I \\ 0, & \text{else} \end{cases}$$

and we define a "concatenation" sequence of the two: $$x_i = \begin{cases} c_i, & 0 \leq i < n \\ d_{i-n}, & n \leq i < n+m \end{cases}$$

we can define a "modification" number: $$X = \sum_{i=0}^{n+m-1} 2^i x_i$$

We can then compute $R$ and $I$ by breaking down the "modification" number $X$ into $c_i$ and $d_i$, giving $$I = \{ t_i | d_i = 1 \}$$ and $$R = \{ s_i | c_i = 1 \}$$.

Now, since $c_i$ and $d_i$ rely on $R$ and $I$, we can redefine them based on how $R$ and $I$ are defined: $$(s_i \in R) \iff (s_i \in S \land s_i \notin T)$$ $$(t_i \in I) \iff (t_i \in T \land t_i \notin S)$$ So $c_i$ and $d_i$ are now: $$c_i = \begin{cases} 1, & s_i \in S \land s_i \notin T \\ 0, & \text{else} \end{cases}$$ $$d_i = \begin{cases} 1, & t_i \in T \land t_i \notin S \\ 0, & \text{else} \end{cases}$$

Therefore, the modification number $X$ only depends on the original sets/lists $S$ and $T$. Furthermore, since $X$ is composed of $n + m$ bits, any set difference algorithm should be able to compute these bits in $\Omega(n + m)$ time. It could then compute $S$ and $T$ as described above, which would take $O(n)$ and $O(m)$ time, respectively.

My primary concern is the assumption that computing $n + m$ bits should only take $\Omega(n + m)$ time - my reasoning for that is based on the proof of the lower bound of the general sorting algorithm, and how sorting a list is similar to computing $\log_2 n!$ bits, which (from Sterling's Approximation) is $O(n \log n)$.

Again, I'm mostly interested in the validity of my reasoning, and whether or not this means a linear-time algorithm exists for computing set-differences.

---

An example application that I'm currently interested in (and what originally inspired this) is when a SCSI host rescans its bus for changes in device topology. Typically, it has a list of custom device objects that represent the corresponding device's current state. Upon rescan, the host gets a list of devices currently on the bus, but only by a small identifier (such as it's bus location or LUN).

The problem, then, is how to efficiently map this new device list to the existing device object list, so that unchanged devices are mapped to their corresponding objects, and any device objects whose corresponding devices have been removed can be cleaned up, and any new devices can have objects allocated for them.

If I let $S$ be the list of current devices (by their ID, with some other simple mapping from the ID to the object data), and $T$ be the results of the rescan, then I can efficiently compute $I$ and $R$, and allocate new objects for devices in $I$ and clean up objects for devices in $R$ in linear ($O(n + m)$) time.

Answer 1

You can compute $S\setminus T$ and $T\setminus S$ from $S$ and $T$ in $O(n+m)$ time using a hash table. Put all of list $S$ into a hashtable, and then iterate through list $T$ and look it up in the hashtable. Then do the same, with $T$ in the hashtable and iterating through $S$.

Fine print for complexity purists: this is expected running time, making suitable assumptions about the hash function. However, the probability that the running time takes longer than $c \cdot (n+m)$ can be made exponentially small in $c$ with a suitable choice of hash function. For practical purposes, you typically don't need to worry about this.

You can also do it in $O(n \lg n + m \lg m)$ time, using a suitable sorting algorithm plus a standard merge algorithm. In some special circumstances, sorting might be even faster (look up counting sort and radix sort).

Which of these is faster in practice will depend upon the platform you run it on. You probably will need to implement and try both, to see which will be faster. You can't trust the asymptotic complexity in this situation, as caching effects and other implementation considerations have the potential to be more important than the asymptotics.

Answer 2

The nature of the answer depends on what you are attempting to optimize (e.g. computation, communication, interactivity) and the computational model (e.g. deterministic, probabilistic,distributed/centralized).

In the case where the two sets are on remote devices, this problem is known as the set reconciliation problem, or more generally the data reconciliation/synchronization problem.

In your application, it appears that you are just interested in computational complexity on a local host. In this case, as Karolis suggested, you can use a linear-time search algorithm (counting sort or radix sort) to get your desired complexity.