Dec. 14, 2018
Standard approach and a heuristic alternative
Standard approach -- use graph and distance product
We note that transitive reduction is reduceable to transitive closure and vice versa both in additional time in $O(n ^ 2)$. Then, we know that if we can solve transitive closure in $O(n ^ 2 \cdot \textrm{polylog}(n))$ time, then we can also solve lax Boolean matrix multiplication (MM) in similar time by reducing it to transitive closure (or transitive reduction), according to Fischer/Meyer 1971. Lax Boolean MM is where input values are in $\{0, 1\}$ and we have semi-ring of $(\textrm{OR}, \textrm{AND})$. We can solve lax Boolean MM by reducing to standard (plus, times) MM. This means that significantly-subcubic-time approach is currently unlikely for transitive reduction. We can reduce node-based DAG transitive reduction to rectangle-containment-based DAG transitive reduction via topological ordering and shapes that have size inversely related to distance from source. For rectangle application, we should of course not have cycles, which happen when the rectangles are identical, in which case we should remove duplicates. A more direct algorithm is for computing reduction assuming sparse graph, which takes $O(n ^ 3)$ time. These times are also ignoring that to come up with initial DAG we ought to perform $n ^ 2$ containment tests, each of which takes time in $O(d) = O(2) = O(1)$.
Heuristic alternative -- use R-tree
Alternatively, assuming we have dimension $d$ moderately low and fixed and not bound tightly by $O(n)$, we can arrive at times that appear to be subcubic in $n$. We have two options -- both use an R-tree variant with bulk-loading e.g. via sort-tile-recursive (STR) approach via Leutenegger 1997 and that is balanced and that is dynamic via bkd-tree-like occasional rebuilding (see Procopiuc 2003) to support inserts and deletes in $O(\log^2(n))$ time. See Guttman 1984 for details on standard R-tree. The main idea is that we find close descendants for each of $n$ provided rectangles via a total of $n$ close-descendant queries. We consider both options to involve heuristics because we may have many intermediate hunches for close-descendant that do not ultimately survive, even though subqueries have good guaranteed time for option one.
If we have pair-wise rectangles that do not frequently involve enclosure/containment and overlap is highly correlated with enclosure/containment, then it is conceivable that we can get better performance using R-tree via either of the two options for our approach. We note that a rectangle enclosure query asks for given a query rectangle rectangles that contain it and a rectangle containment query asks for given a query rectangle rectangles that fit in it. Close-descendant query roughly works via a heuristic approach. We find primitive rectangles contained by query rectangle and use auxiliary queries to see if returned rectangles have parents that are contained by original query rectangle. The candidate close descendants we store in a "conflict" secondary R-tree for purpose of speeding up checks in form of enclosure subquery with early-stopping that determine whether a candidate parent encloses (and disqualifies) a candidate close descendant; we maintain this conflict tree via inserts and deletes. We note that when we encounter rectangles of same shape, we may choose to keep one of them arbitrarily. We use a best-first priority queue to guide bounding box consideration order; we prefer contained bounding boxes and we tie-break by preferring larger bounding box area (because it is harder to be a middle-man for a larger contained box).
Option #1 -- use look-ahead
The first option is to use look-ahead for subqueries such as rectangle enclosure and rectangle containment in conjunction with corner transformation. Close-descendant query would then not directly use look-ahead; its subqueries do. Then, we have a coefficient of $d$ for look-ahead-using queries for edge checks. We won't go into much detail about look-ahead except that it requires roughly disjoint bounding boxes for siblings (though shared edge is allowed) and that it is related to knowing that one child out of two subtrees definitely has a match (which is made more straightforward to notice assuming we also use corner transformation) via $d$ edge checks at each node. It should be noted that without look-ahead enclosure and containment already take at least $d$ time for each node for an R-tree. We modify enclosure subquery to use early-stopping, which leads time for such a query to be $O(\log(n))$ instead of $O(\log^2(n))$. Time for each close-descendant query is in $O(k \cdot \log^2(n))$, where $k$ is number of hunch close-descendants s.t. $k$ is in $O(n)$. This means for $n$ close-descendant queries overall we take time in $O(k \cdot n \cdot \log^2(n))$ = $O(n ^ 2 \cdot \log^2(n))$. Since this is less than cubic in $n$ (though we omit a factor of $d$ assuming it is moderately low and fixed), this approach may be used to get better performance in practice. We have left out detail that for look-ahead-using enclosure/containment subqueries we may take non-constant time even if there are zero matches.
Option #2 -- do not use look-ahead
The second option is to not use look-ahead and all we can say (without further simplifying assumptions) is that for each close-descendant query we have worst case of $n$ hunches, each of which would then take $O(\log(n))$ time to find (because we don't go down a branch more than once). We note that we assume that we do not use corner transformation. As a result, we have an exceedingly loose and pessimistic time bound of $O(n \cdot \log(n))$ for attempt to disqualify a hunch close descendant via enclosure subquery with early-stopping. Time for a close-descendant query then is bounded by $O(k' \cdot n \cdot \log(n))$, where $k'$ is worst-case number of hunches (i.e. $n$). Time for $n$ close-descendant queries then is bounded by $O(k' \cdot n ^ 2 \cdot \log(n))$ = $O(n ^ 3 \cdot \log(n))$. This figure is more than cubic in $n$ (again noting that we omit a factor of $d$ as it is moderately low and fixed), but the times for the approach are considerably pessimistic and we believe there is still a chance that it can perform well in practice w.r.t. brute-force. We show that this is plausible by now making a few assumptions, which we discuss below. While the first option does not take advantage of possibility that number of hunches can be significantly lower than $n$ either, it has lower theoretical bounds because they take advantage of possibility that enclosure subquery with early-stopping for disqualifying a hunch close descendant can be guaranteed to be fast.
Option #2 -- three assumptions
Assumption "zero-overlap" says that (i) bounding boxes do not overlap with query rectangle unless we enclose query rectangle for enclosure query or we are contained by query rectangle for containment query; and (ii) bounding boxes for siblings s.t. neither sibling is contained in the other do not overlap except at a boundary. We note that part one of that assumption can only mostly be true e.g. because a real rectangle collection has a largest rectangle that cannot be enclosed and a smallest rectangle that cannot contain. We introduce $b$, which describes average false-positive-to-actual-positive ratio for believing that a child for a node is associated with a guaranteed match during disqualify attempt subquery s.t. $b$ is in $[0, 1]$. Time for second option close-descendant query is broken into two parts. The first part describes getting the hunches. The second part describes attempts to disqualify each hunch. The third part is to handle updates to conflict tree. Assume number of hunches is $k''$. The time for the first part is $O(k'' \cdot \log(n))$. The time for the second part is $O(k'' \cdot (b + 1)^{\log(n)} \cdot \log(n))$. The time for the third part is $O(k'' \cdot \log^2(n))$. The total time is loosely (assuming $b$ is one) in $O(k'' \cdot n \cdot \log^2(n))$. The time for $n$ close-descendant queries is $O(k'' \cdot n ^ 2 \cdot \log^2(n))$ = $O(n ^ 3 \cdot \log^2(n))$ if $k''$ is in $O(n)$. This does not appear to be better than brute-force. If we make "zero-overlap" assumption, $b$ is zero, which gives $n$ close-descendant query time of $O(k'' \cdot n \cdot \log^2(n))$ = $O(n ^ 2 \cdot \log^2(n))$ if $k''$ is in $O(n)$. The factor of $\log^2(n)$ (instead of $\log(n)$) comes from insert/delete for conflict tree of hunch close descendants. This assumption can be true for rectangles for a hierarchy that is highly coherent -- i.e. one with many realized enclosure/containment relationships and good separation between rectangles that are not related via enclosure/containment.
We have two other assumptions -- "uniform sparsity" and "no pruning", each of which have secondary purposes that are related to our application of quantitative association rule mining. They allow us to tune to reduce work drastically given that the second option for close-descendant query can be very time-costly. Specifically, say average number of partitions for a quantitative attribute (treating categorical attribute as possibly multiple two-partition quantitative attributes) is $p$; then, number of solid regions considered for each quantitative attribute is $p ^ 2$ -- all of which survive if we have "no pruning" assumption. As we reduce $p$, the space of all possible multi-dimensional rectangles shrinks and via "uniform sparsity" assumption for fixed $n$ we have more collisions (i.e. possibly more enclosure/contain relationships) but number of rectangles (that are made of combinations of solid regions for different attributes) shrinks faster -- this means that w.r.t. close-descendant query the amount of time required we can drastically shrink by reducing average number of partitions $p$ slightly.
Miscellaneous shared details
The only reason we believe one might wish to not use option one is slightly more implementation difficulty. We don't often see a proposed algorithm that performs reporting and that has for each match a coefficient for time that is not one. Still, the coefficient that we have of $\log(n)$ or $\log^2(n)$ is fine; $\log^q(n)$ for low $q$ is often acceptable wherever we see $O(1)$, as opposed to when we have e.g. $n$ where we see $O(1)$. In general, an R-tree is better than multi-layer segment tree for rectangle enclosure/containment/intersection queries or point domination query if $d$ is less than $\log^{max(d - 1, 1)}(n)$ for $d \geq 1$ given that for an R-tree we do not clone stored rectangles. Option one and option two with assumptions imply that we appear to be better than brute-force given that it is appropriate to omit $d$.
References
- Pratyaksh - Transitive reduction of DAG - Answer (2014)
https://cs.stackexchange.com/q/29133
- Wikipedia - Transitive reduction - Computing the reduction in sparse graphs
https://en.wikipedia.org/wiki/Transitive_reduction
- Fischer, Meyer - Boolean matrix multiplication and transitive closure (1971)
- Leutenegger et al. - STR: A simple and efficient algorithm for R-tree packing (1997)
- Procopiuc et al. - Bkd-tree: A dynamic scalable kd-tree (2003)
- Guttman - R-trees: A dynamic index structure for spatial searching (1984)
