Improved Dominance Filtering for Unions and Minkowski Sums of Pareto Sets

An ND-tree is a typical rooted $c$-ary tree $T$, in which a distinct node $r=root(T)$, of degree at most $c$, is the root node, all nodes of degree $1$ (except possibly for the root) are its leaf nodes, and the remaining nodes of degree from $2$ up to $c+1$ are its internal nodes. The ND-trees are leaf-oriented, meaning that all data points are stored exclusively in leaf nodes. Each leaf node can store up to $m$ points. The parameters $c$ and $m$ must satisfy the condition $c\le m+1$ [14]. Each node $v$ stores a lower-bounding vector ${\mathrm{𝐥𝐛}}_{𝐯}$ and an upper-bounding vector ${\mathrm{𝐮𝐛}}_{𝐯}$ for all the data points stored in leaves of the subtree $T_v$ of $T$ rooted at $v$. Specifically, for each point $𝐩$ stored in $T_v$, it holds that $\forall i\in [d],{\mathrm{𝐥𝐛}}_{𝐯}[i]\le 𝐩[i]\le {\mathrm{𝐮𝐛}}_{𝐯}[i]$. An example of an ND-tree can be found in Figure 1.

The lower and upper-bounding vectors are typically used to determine, as early as possible, if a new data point $𝐩$ is dominated by any data point already in the tree. For instance, if , then $𝐩$ is not dominated by any data point stored in $T_v$, and we do not have to explicitly verify this with all of them (of course, it might still be the case that $𝐩$ dominates some of these data points). If then $𝐩$ dominates all the data points stored in $T_v$. Finally, if $𝐩>{\mathrm{𝐮𝐛}}_{𝐯}$, then all the data points stored in leaves of $T_v$ dominate $𝐩$. An ND-tree $T$ supports the following operations.

• $\mathrm{■}$

  NonDomPrune$(𝐩,T)$: This operation effectively utilizes the bounding vectors to perform two tasks, a dominance-check for a point $𝐩$ to decide whether it is dominated by any data point in $T$, and a pruning of $T$ to remove all its data points that are dominated by $𝐩$. If $𝐩$ is not dominated by any point in $T$, NonDomPrune returns True; otherwise, it returns False.

• $\mathrm{■}$

  Insert$(𝐩,v)$: This operation inserts a new point $𝐩$ into a leaf of $T_v$ as follows. If $v$ is a non-leaf node, then a child node $w$ of $v$ is selected with minimum distance from $𝐩$. The distance of $𝐩$ from any node $u$ is the Euclidean distance between $𝐩$ and $\frac{{\mathrm{𝐥𝐛}}_{𝐮}+{\mathrm{𝐮𝐛}}_{𝐮}}{2}$ (the center of the bounding box containing all data points stored $T_u$). Consequently, $𝐩$ is recursively requested to be inserted in $T_w$. For a leaf node $v$, if it stores less than $m$ data points, then $𝐩$ is simply appended to its list of stored points; otherwise, $v$ is converted into an internal node with $c$ children, and the pending $m+1$ data points are distributed evenly among them. Throughout the insertion process, the bounds of all affected nodes are updated accordingly.

• $\mathrm{■}$

  SPNDBuild$(P)$: This operation, introduced in [14], aims to handle situations in which repeated insertions into an ND-tree might eventually lead to an unbalanced tree structure. It takes as input a Pareto set $P$ (e.g., with all the data points stored in an unbalanced ND-tree) and builds from scratch a perfectly balanced ND-tree from it, as no pruning is ever required, in which the bounding areas defined by the upper and lower bounds also are non-overlapping.

The following dominance-filtering algorithms, proposed in [13], are all based on ND-trees and are, to our knowledge, the state-of-the-art techniques for $d\ge 3$ criteria.

• $\mathrm{■}$

  PlainND: This algorithm employs NonDomPrune and Insert to compute either the Pareto union or the Pareto sum of two Pareto sets $A$ and $B$. It begins with an empty ND-tree $T$, and processes sequentially the points in $F$ (either $A\cup B$, or $A\oplus B$). For each point $𝐩\in F$, it calls NonDomPrune($𝐩,T$). If False is returned, $𝐩$ is discarded. Otherwise, it executes Insert($𝐩,T$) to store $𝐩$ in $T$. After having processed all points in $F$, the points eventually stored in the leaves of $T$ constitute the Pareto frontier of $F$.

• $\mathrm{■}$

  PlainSPND: This algorithm is similar to PlainND, but it periodically takes the Pareto set $P$ of data items in the current ND-tree, it then destroys the tree, and consequently calls SPNDBuild$(P)$ to create a new, balanced ND-tree. This periodic tree reconstruction can significantly improve the efficiency of intermediate calls to the NonDomPrune and Insert operations, due to limitations in the imbalance of the evolving ND-tree, while the tree reconstruction cost is amortized among consecutive insertion and pruning operations.

• $\mathrm{■}$

  PruneSPND: This algorithm is custom-tailored for computing the Pareto union of two Pareto sets $A$ and $B$. It exploits the fact that points in $A$ may only be dominated by points in $B$, and vice versa. Therefore, for the larger of the two sets (say, $A$) it calls SPNDBuild$(A)$ to build a balanced ND-tree $T$. Subsequently, for each point $𝐩$ in the smaller set (say, $B$), it calls NonDomPrune$(𝐩,T)$ to check if $𝐩$ is dominated and to remove from $T$ all points dominated by $𝐩$. If $𝐩$ is dominated, it is removed from $B$. After having processed all points in $B$, $T$ contains all points of $A$ which are not dominated by any point in $B$, and (eventually) $B$ has only retained those points which are not dominated by any point in $A$. Their union constitutes the Pareto union.

An ND⁺-tree $T$ is a leaf-oriented binary tree, with each leaf node storing up to $m$ data points. As in k-d trees [1], every node $v$ is associated with a level-dependent dimension $v.dim=1+(v.level\mathrm{𝐦𝐨𝐝}d)$, a subset $S_v$ of data points (to be stored in the leaves of $T_v$) and the median value $v.q$ among the coordinates of all the points of $S_v$ in dimension $v.dim$. Each node $v$ also maintains a lower-bounding vector ${\mathrm{𝐥𝐛}}_{𝐯}$ (i.e., the coordinate-wise minimum) of all points in $S_v$, similarly to ND-trees [10]. However, we avoid storing also the upper-bounding vectors, since our experimental evaluation showed that maintaining them is not beneficial for the operations on ND⁺-trees. Moreover, if $v$ is internal node, then $S_v$ is partitioned in two distinct subsets, one per child of $v$: the left child gets all points in $S_v$ with and the right child gets all the remaining points of $S_v$. An example of an ND⁺-tree is shown in Figure 2.

For each ND⁺-tree $T$, the following elementary operations are supported:

• $\mathrm{■}$

  BuildND⁺($P$, $\mathrm{\ell }$, $d$) constructs an ND⁺-(sub)tree at level $\mathrm{\ell }$ (an entire tree, when $\mathrm{\ell }=0$) containing all the data points of a Pareto set $P$.

• $\mathrm{■}$

  ComputeBoundsND⁺($r$) computes the lower-bounding vectors for all nodes of $T_r$.

• $\mathrm{■}$

  WidenBoundsND${}_{}{}^{+}(v,𝐩)$ updates the lower-bounding vector of node $v$, if necessary, due to a (previous) addition of a new point $𝐩$ in $T_v$.

• $\mathrm{■}$

  InsertND${}_{}{}^{+}(v,\mathrm{\ell },𝐩)$ inserts a new point $𝐩$ into the subtree $T_v$ rooted at the level-$\mathrm{\ell }$ node $v$.

• $\mathrm{■}$

  DominatedND${}_{}{}^{+}(v,\mathrm{\ell },𝐩)$ decides whether a new point $𝐩$ is dominated by any other point in the subtree $T_v$ rooted at the level-$\mathrm{\ell }$ node $v$.

In the remaining part of this section we provide some theoretical guarantees on the complexities of these elementary operations, when each leaf of the tree stores at most $m$ $d$-dimensional points, for arbitrary constants $m,d\in O(1)$.

For a Pareto set $P$ with its points having distinct values per dimension, BuildND⁺ constructs a balanced ND⁺-tree in quasilinear time (cf. Theorem 1). However, objective spaces $F$ emerging from real-world scenarios (and their Pareto subsets) rarely adhere to such a strong property. Instead, it is common for large subsets of objective vectors to possess identical values in certain dimensions, e.g., for tolls in road networks. When a subset of $S_v$ constitutes a large plateau around $v.q$ (i.e., those data points have the same value $v.q$ in $v.dim$) for some internal node $v$, the resulting partition of $S_v$ may be (possibly heavily) uneven. If this pattern occurs frequently at intermediate nodes, then the resulting ND⁺-tree will be heavily unbalanced, leading to quadratic construction time and also linear (instead of logarithmic) time for insertion of new points. This may happen even if initially a balanced tree is constructed, due to subsequent insertions of points that constitute a plateau in $F$.

To tackle these worst-case performances of the ND⁺-trees, we introduce in this section an alternative data structure, the QND⁺-trees (Quartile ND⁺-trees). In a nutshell, the QND⁺-trees are almost identical to the ND⁺-trees, the only difference being that they perform a more careful bipartition of the data set $S_v$ associated with an internal node $v$. Specifically, if there is a large plateau (more than one fourth) in dimension $v.dim$ around the splitting value $v.q$, then this plateau is entirely assigned to $v$’s right child, with the remaining points being assigned (irrespectively of their values in dimension $v.dim$) to its left child. Moreover, when checking for dominance-checks in the subtree rooted at $v$’s right child, it is no longer necessary to consider $v.dim$, achieving dimensionality reduction. If no such plateau is discovered in $S_v$, then the split is done as in an ND⁺-tree.

We consider the following partitioning strategies: Median Partitioning (MP), also used in ND⁺-trees, assigns points of $S_v$ with values in $v.dim$ less than $v.q$ to $v$’s left child, and the remaining points of $S_v$ to $v$’s right child; Quartile Partitioning (QP) assigns points of $S_v$ with value $v.q$ in dimension $v.dim$ to $v$’s right child, and all other points to $v$’s left child. The following elementary operations are supported for QND⁺-trees:

• $\mathrm{■}$

  BuildQND${}_{}{}^{+}(P,\mathrm{\ell },d)$ constructs a QND⁺-tree with the points of Pareto set $P$, in an analogous manner with BuildND${}_{}{}^{+}(P,\mathrm{\ell },d)$. The only difference is that, before splitting the point set $S_v$ associated to an internal node $v$, it first computes the quartiles of $S_v$ in dimension $v.dim$ and then applies QP when $Q_1=Q_2$ (this implies that the size of the plateau is at least $|S_v|/4$), and MP otherwise. After completing the tree construction, it calls ComputeBoundsND⁺ to compute all the lower bounding vectors.

• $\mathrm{■}$

  InsertQND${}_{}{}^{+}(v,\mathrm{\ell },𝐩)$ inserts a new point $𝐩$ in $T_v$, similarly to the corresponding operation on ND⁺-trees. It first updates ${\mathrm{𝐥𝐛}}_{𝐯}$ using WidenBoundsND⁺ and then recursively calls itself for the appropriate child of $v$ (if this is an internal node), depending on the existence (or not) of a plateau in $v.dim$, or else (for a leaf node) it either stores $𝐩$ in $v$’s data list, otherwise (when there is no free space in $v$’s list) it changes $v$ into an internal node and redistributes evenly all the pending data points among its two children, executing also ComputeBoundsND⁺ to update their lower bounding vectors.

• $\mathrm{■}$

  DominatedQND⁺($v$,$\mathrm{\ell }$,$𝐩$,$D$), an adaptation of DominatedND⁺ on QND⁺-trees, checks whether a new point $𝐩$ is dominated by any other point in $T_v$, taking also into account if there are any dimensions to ignore (due to existence of plateaus) during its recursive calls.

TND⁺-trees (Ternary ND⁺-trees) are designed to exploit both tree balance and dimensionality reduction due to the existence of plateaus. Contrary to the other trees, TND⁺-trees are not strictly binary. In particular, whenever a large plateau is discovered within $S_v$ in dimension $v.dim$ of an internal node $v$, three children are created: The left child is associated with points $𝐩\in S_v$ with , the right child with points $𝐩\in S_v$ with $𝐩[v.dim]>v.q$, and the middle child with all the points which constitute the plateau (i.e., $𝐩[v.dim]=v.q$). Again, for the middle child we also exploit the resulting dimensionality reduction. We will refer to this plateau-based partitioning strategy as a TriPartitioning (TP). If no plateau is detected, then the standard Median Partitioning (MP) strategy is applied. The following elementary operations are supported for TND⁺-trees:

• $\mathrm{■}$

  BuildTND${}_{}{}^{+}(P,\mathrm{\ell },d)$ constructs a TND⁺-tree for the points of a Pareto set in a fashion analogous to that of BuildQND⁺, applying (TP) whenever $Q_1=Q_2$ or $Q_2=Q_3$ for the quartiles of $S_v$ in dimension $v.dim$, ensuring that at least 25% of $S_v$ are assigned to the middle child where we also benefit from dimensionality reduction. After completing the tree construction, ComputeBoundsTND⁺ is executed, a slightly modified version of ComputeBoundsND⁺ that also takes into consideration the middle child, to compute the lower-bounding vectors of each node in the tree.

• $\mathrm{■}$

  InsertTND${}_{}{}^{+}(v,\mathrm{\ell },𝐩)$ inserts $𝐩$ to the TND⁺-(sub)tree $T_v$, resembling InsertQND⁺. It first updates $v$’s lower-bounding vector using WidenBoundsND⁺. If $v$ is an internal node, then a recursive call of the method is executed to insert $𝐩$ to the appropriate child of $v$, taking also into account whether $v$ possesses a middle child. If $v$ is a leaf node that stores less than $m$ points, then it simply stores $𝐩$ at $v$’s list of points, otherwise $v$ is converted into an internal node and the $m+1$ now pending points (including $𝐩$) are redistributed among its (either two or three, depending on the presence of a plateau) children, using BuildTND⁺. Upon completion, ComputeBoundsTND⁺ is executed to compute the lower bounds of the newly created children.

• $\mathrm{■}$

  DominatedTND${}_{}{}^{+}(v,\mathrm{\ell },𝐩,D)$ determines whether $𝐩$ is dominated by any other point in the TND⁺-(sub)tree $T_v$.

To illustrate the differences between the three data structures, and to demonstrate how QND⁺- and TND⁺-trees produce more balanced structures than ND⁺-trees in the presence of plateaus, consider building ND⁺-, QND⁺-, and TND⁺-trees from the point set $S=\{(1,10,2),(2,9,6),(2,8,7),(2,12,0),(2,7,8),(2,11,1),(4,7,4),(5,7,3),(6,7,2),(7,6,1),(8,6,0)\}$. Assume that each leaf node can store up to $m=4$ points.

• $\mathrm{■}$

  ND⁺-tree: Median Partitioning (MP) is first applied in the first dimension, yielding the median value 2. This assigns $(1,10,2)$ to the left subtree and all remaining points to the right, giving $L=\{(1,10,2)\}$ and $R=\{(7,6,1),(8,6,0),(2,7,8),(4,7,4),(5,7,3),(6,7,2),(2,8,7),(2,9,6),(2,11,1),(2,12,0)\}$. MP is then applied to $R$ in the second dimension, with median 7, producing $RL=\{(7,6,1),(8,6,0)\}$ and $RR=\{(2,12,0),(2,11,1),(6,7,2),(5,7,3),(4,7,4),(2,9,6),(2,8,7),(2,7,8)\}$. Since $RR$ exceeds the leaf size $m$, it is split once more using MP in the third dimension, where the median is 4, giving $RRL=\{(2,12,0),(2,11,1),(6,7,2),(5,7,3)\}$ and $RRR=\{(4,7,4),(2,9,6),(2,8,7),(2,7,8)\}$. All resulting subtrees contain at most $m$ points, completing the tree (see Figure 3).

• $\mathrm{■}$

  QND⁺-tree: Since $Q_1=Q_2=2$ in the first dimension, Quartile Partitioning (QP) is used, yielding $L=\{(7,6,1),(8,6,0),(4,7,4),(5,7,3),(6,7,2),(1,10,2)\}$ and $R=\{(2,7,8),(2,8,7),(2,9,6),(2,11,1),(2,12,0)\}$. In $L$, $Q_1=6\ne 7=Q_2$ in the second dimension, so MP is applied, splitting it into $LL=\{(7,6,1),(8,6,0)\}$ and $LR=\{(4,7,4),(5,7,3),(6,7,2),(1,10,2)\}$, both of which satisfy the leaf size constraint. In $R$, $Q_1=8\ne 9=Q_2$ in the second dimension, so MP is again applied, giving $RL=\{(2,8,7),(2,7,8)\}$ and $RR=\{(2,9,6),(2,11,1),(2,12,0)\}$, each also within the allowed limit. The tree is thus complete (see Figure 4).

• $\mathrm{■}$

  TND⁺-tree: $Q_1=Q_2=2$ in the first dimension, so TriPartitioning (TP) is applied, producing $L=\{(1,10,2)\}$, $M=\{(2,7,8),(2,8,7),(2,9,6),(2,11,1),(2,12,0)\}$, and $R=\{(7,6,1),(8,6,0),(4,7,4),(5,7,3),(6,7,2)\}$. $L$ needs no further processing. In $M$, no plateau is present in the second dimension, so MP is used with median 9, resulting in $ML=\{(2,7,8),(2,8,7)\}$ and $MR=\{(2,9,6),(2,11,1),(2,12,0)\}$. In $R$, a plateau is found: $Q_2=7=Q_3$, so TP is applied again, yielding $RL=\{(7,6,1),(8,6,0)\}$ and $RM=\{(4,7,4),(5,7,3),(6,7,2)\}$. All resulting subtrees respect the leaf size constraint, completing the tree (see Figure 5).

As noted in [13], the main computational burden in PlainND, PlainSPND and PruneSPND is the execution of NonDomPrune operations (cf. Section 3). The most demanding task is the removal of all dominated points from the tree, as new points are inserted to it. The main idea behind the reduced PlainND algorithm (PlainNDred in short) is to avoid this costly pruning task of the evolving tree, by ensuring that any point that is inserted to the tree is actually a member of the required Pareto frontier of $F$. To achieve this, PlainNDred first lexicographically sorts $F$, in quasilinear time. Then, to efficiently manage dominance-checks, it processes the data points in that order and uses one of the new indexing structures (ND⁺-trees in PlainNDred, QND⁺-trees in PlainQNDred, and TND⁺-trees in PlainTNDred) to store only the non-dominated ones of $F$ so far. In particular, for each point $𝐩$ in the lexicographic order, the algorithm must only check if it is dominated by any point in the tree, since $𝐩$ cannot dominate any of the preceding points in that order, as shown next.

If $𝐩$ is not dominated by any point already in the tree, the algorithm inserts it. Moreover, dominance-checks can safely ignore dimension $1$, since $𝐩[1]\ge 𝐪[1]$ for any point preceding $𝐩$ in the lexicographic order. Therefore, PlainNDred needs only to check the remaining $d-1$ dimensions. As a result, the algorithm builds a tree considering only the last $d-1$ dimensions of the points in $F$. We denote as ${𝐩}_{\mathrm{𝐫𝐞𝐝}}$ the projection of $𝐩$ on the last $d-1$ dimensions. The following statement demonstrates time complexity of PlainNDred.

The consecutive insertions into the tree by PlainNDred are likely to gradually unbalance it, thereby diminishing the efficiency of subsequent dominance-checks and insertions. To address this challenge, one option would be to periodically rebuild the tree, as is done by PlainSPND in [13]. However, building the entire tree from scratch is not a trivial task. To avoid that, we could leverage once more the lexicographic order of the point set $F=({𝐩}_{\mathrm{𝟏}},\mathrm{\dots },{𝐩}_{𝐧})$ to compute first an initial subset $P$ of the Pareto frontier, which is then used to construct a balanced ND⁺-tree that will be large enough so that the subsequent insertions of the remaining non-dominated points, again examined in lexicographic order, will not be able to unbalance it severely. This is exactly the main idea of the presorted ND algorithm (PreND in short).

To compute this subset of the Pareto frontier, we deploy the ParetoSubset algorithm. It starts with the initialization of a vector $𝐲$ of length $d$, corresponding to the number of dimensions, with each dimension assigned the value $\mathrm{\infty }$, and then makes a single pass over the data points, in lexicographic order, using $𝐲$ to keep track of the smallest values seen in each dimension, up to the current point ${𝐩}_{𝐢}$. For the next point in order, ${𝐩}_{𝐢+\mathrm{𝟏}}$, if there exists a dimension $j\in [d]$ such that , then ${𝐩}_{𝐢+\mathrm{𝟏}}$ is not dominated by any preceding point. Moreover, due to the lexicographic order, ${𝐩}_{𝐢+\mathrm{𝟏}}$ cannot be dominated by any subsequent point ${𝐩}_{𝐤}:k\ge i+2$ (cf. Lemma 7). Therefore, ${𝐩}_{𝐢+\mathrm{𝟏}}$ is certainly a non-dominated point in $F$ and is appended to $P$, and $𝐲$ is updated to always keep the smallest value seen so far, per dimension. Otherwise, when $𝐲\le {𝐩}_{𝐢+\mathrm{𝟏}}$, ${𝐩}_{𝐢+\mathrm{𝟏}}$ is appended to another subset $Q$, for further examination, during the second processing phase. Note that, since all points are processed in lexicographic order, $Q$ remains lexicographically sorted. Observe also that, for $d=2$, ParetoSubset already computes the entire Pareto frontier of $F$.

The PreND algorithm initially calls ParetoSubset to get the sets $P$ and $Q$. It then calls BuildND⁺ to construct an initial ND⁺-tree with the points of $P$. Subsequently, for each point $𝐪\in Q$, it calls DominatedND⁺ to determine if $𝐪$ is dominated by any point of the tree. If it is dominated, then it is discarded. Otherwise, it is appended to $P$ and inserted to the ND⁺-tree by calling InsertND⁺. After having processed all points in $Q$, $P$ is the required Pareto frontier of $F$. Note that PreND can be used for constructing the Pareto union or the Pareto sum of two Pareto sets, but also for identifying the Pareto frontier of a single set.

Especially for the union of two Pareto sets $A,B$, recall that points of one set may be dominated only by points of the other set. Thus, applying some sort of symmetric dominance-filtering could be extremely efficient. This is exactly what the symmetric ND algorithm (SymND in short) does. It constructs first an ND⁺-tree using the points of $A$ and then executes DominatedND⁺ for each point in $B$, to remove from $B$ all those points which are dominated by a point in $A$. Then, it constructs another ND⁺-tree, using only the remaining points in $B$, and executes DominatedND⁺ for each point in $A$, to remove those points which are dominated by a point in $B$. In the end, both surviving subsets of $A$ and $B$ contain only non-dominated points, and their union constitutes the Pareto union of $A$ and $B$.

To evaluate the performance of our algorithms, we used both real-world and synthetic data sets. Note that real-world data sets with three or more objectives ($d\ge 3$) are very rare. Since our main goal is to test scalability with dimensionality, we have also used two families of synthetic data sets with up to $d=10$ objectives: the randomly constructed data sets of [13], and some new, carefully generated synthetic data sets that resemble some crucial features of real-world instances for MOCO problems. Below, we provide a brief overview of all these data sets; more details can be found in the full version of the paper. The RW sets are based on the New York City road network [5], and are equipped with two cost metrics: travel time and distance. We extend them to higher dimensions according to well established augmentation techniques: for $d=3$, we adopted [17] and introduced a third objective which is related to hazardous material transportation [7]. For $d=5$, we adopted [8] and added a fourth objective which is a random integer from $1$ to $100$, and a fifth objective which is a random integer from $1$ up to the number of graph edges. The URS sets were synthetically generated according to the procedure described in [13] (sampling points uniformly in $d$-dimensional space and then projecting them into the unit sphere to ensure that these are Pareto sets). Apart from these “baseline” RW and URS data sets, we also considered a few extensions towards incorporating some typical features of real-world instances. The RWP and URSP sets try to model realistic instances with repeated or flat objective values (e.g., tolls for road networks), by introducing plateaus in some objectives of the RW and URS sets, respectively. The RWC and URSC sets simulate interdependencies between objectives (also encountered quite often in real-world instances), by introducing correlations between some objectives. Finally, the URSPC set combines both correlation and plateau features in a single Pareto set. The size of data sets given as input to all algorithms varies from 10K to 1M points, while the number of objectives (dimensions) $d$ varies from 3 to 10 (3, 5 for RW, 5 for RWP and RWC, 4, 6, 8, 10 for URS, URSP, URSC and 5, 6, 8, 10 for URSPC).

We provide here an overview of our experimental results. All details can be found in the full version of the paper.