Optimizing Simple Tabular Reduction with a Bitwise Representation

1 Introduction

Constraint propagation is used for solving constraint satisfaction problems. The most well studied and successfully used constraint propagation technique is generalized arc consistency (GAC). Table constraints define constraint relations extensionally, i.e. the allowed combination of values, namely the most general form of a finite domain constraint. State-of-the-art GAC algorithms for table constraint include simple tabular reduction (STR) [Ullmann, 2007] algorithms: STR2 [Lecoutre, 2011], STR3 [Lecoutre et al., 2012]; and Multi-valued Decision Diagram (MDD) algorithms: MDDc [Cheng and Yap, 2010], MDD4 [Perez and R´egin, 2014]. Usually, GAC is invoked at each node in the backtrack search tree, giving rise to maintaining GAC.

Constraint and variable domain representation is the basis of a GAC algorithm. Several algorithms based on bit variable domains have been proposed for binary constraints. AC3bit [Lecoutre and Vion, 2008], considered an efficient arc consistency (AC) algorithm optimizes AC3 [Mackworth, 1977] algorithm by using a bit variable domain to represent the binary constraint. MaxRPCbit [Guo et al., 2011] uses a bit variable domain to reduce the cost of searching for a PC-witness.

⇤This work was supported by the MOE AcRF (R-252-000505-112, R-252-000-592-112), the NSFC (61272208, 61373052), and the Jilin Province Science and Technology Development Plan (20140101200JC).

In [Ullmann, 2010], domain reduction algorithms based on bit variable domain are given, such as AC, forward checking and focus domain reduction. A recent GAC algorithm using bit vectors for table constraints is implemented in the OR-Tools solver (see [Demeulenaere, 2015]). It maintains the validity of tuples with bit vectors and seeks support for variable domain values with bit operations. Our focus is exploiting bit-vectors in GAC for non-binary table constraints while gaining the benefits of simple tabular reduction.

When the size of a table constraint is large, constraint representations which reduce space can also substantially speed up the GAC algorithm. Various representations have been proposed to compress table constraints. For example, a compressed table [Katsirelos and Walsh, 2007] represents a set of tuples as c-tuples, a short-support [Jefferson and Nightingale, 2013] represents a set of tuples by omitting some variables which are implied, and a sliced table [Gharbi et al., 2014] represents a set of tuples as a sub-table associated with patterns. These representations have been used in the following GAC algorithms. STR2-C and STR3-C [Xia and Yap, 2013] extends STR2 and STR3 for c-tables; shortSTR2 [Jefferson and Nightingale, 2013] extends STR2 with short support; and STR-slice [Gharbi et al., 2014] enforces GAC on sliced tables. For problem instances with high compression, these algorithms can be faster than STR2.

In this paper, we introduce a new table constraint representation, called bit table. A bit table encodes the supports in the form of a dual table [Lecoutre et al., 2015] with bit vectors. We propose a new GAC algorithm to maintain GAC during search, STRbit, using the bit table representation. STRbit like STR3 focuses on maintaining GAC during search (unlike STR2 which is a standalone GAC algorithm). The advantage of the bit table is that it allows operations which deal with maintaining support in the GAC algorithm to be performed in parallel using O(1) machine instructions. STRbit can also be faster than STR3 as the bit table can be (much) smaller than the dual table. We also extend the bit table to handle compressed tables on c-tuples with the STRbit-C algorithm. Experimental evaluation using well known benchmarks show STRbit to be faster than the state-of-the-art STR2, STR3 and MDDc algorithms on most problem instances. In a similar way, STRbit-C is also faster than the corresponding c-table algorithms, STR2-C and STR3-C.

(b) Dual table

(b) Bit table

Figure 2: A table partition and its corresponding bit table.

2 Background

A constraint satisfaction problem (CSP) is a pair (@↪ ⇣) where @ is a set of n variables and ⇣ is a set of e constraints. Each variable X 2 @ has a domain D(X) defining possible values for X. The maximum domain size of all variables is denoted by d. A literal (X↪ a) represents a variable value pair. During search dom(X) denotes the current domain of X. If a 2 dom(X), we say that (X↪ a) is valid, otherwise (X↪ a) is invalid. Each constraint C 2 ⇣ involves a constraint scope scp(C) and a relation rel(C), where scp(C) is a subset of @ and rel(C) is a set of tuples satisfying constraint C. A tuple ⌧ 2 rel(C) is composed of a set of literals of the variable in scp(C). The number of literals in rel(C) is denoted by L. A solution to a CSP is a set of valid literals for all variables such that all constraint are satisfied.

A tuple ⌧ 2 rel(C) is a support of literal (X↪ a) iff (X↪ a) 2 ⌧. A tuple ⌧ 2 rel(C) is valid iff (X↪ a) is valid for any literal (X↪ a) 2 ⌧. A literal (X↪ a) is generalized arc consistent (GAC) on a constraint C involving X iff there exists a valid support ⌧ of (X↪ a) on C. A variable X is GAC on a constraint C involving X iff dom(X) 6= ; and (X↪ a) is GAC on C for each value a 2 dom(X). A constraint C is GAC iff X is GAC on C for each X 2 scp(C). A CSP is GAC iff each of its constraints is GAC.

A positive (negative) table constraint C is a constraint whose relation rel(C) is represented in a table of allowed (disallowed) tuples. A table can be transformed into an equivalent dual table by mapping the index of tuples to their supported literals. Figure 1(a) gives a (standard) table with 24 literals and its corresponding dual table in Figure 1(b).

3 Bit representation in STRbit

We first introduce a bit representation for table constraints. The idea of our bit representation is to encode the supports of each literal in a constraint's dual table with bit vectors. We assume a natural word size w where the underlying processor

Function GACInit(C : Constraint)

• 1 remove invalid tuples from rel(C) and build a bit table for constraint C; for each sub-table ✓ of rel(C) do 2 VAL(C↪ ✓) := -1; // all bits are value 1 for each X 2 scp(C) and a 2 dom(X) do 3 LAST(C↪X↪ a) := BIT SUP(C↪X↪ a)▷size -1; for each X 2 scp(C) do 4 DEL(C↪X) := ; ;

provides O(1) time bit vector operations. We partition a table into a set of sub-tables such that the number of tuples in a subtable equals w (w.l.o.g., we assume the total number of tuples in the table is divisible by w). Then for each literal (X↪ a) and sub-table ✓, a bit vector mask records the supports of (X↪ a) in ✓. The ith bit in mask indicates whether the ith tuple in sub-table ✓ is a support (value 1) or not (value 0).

Definition 1. A sub-table ✓ is a table support of (X↪ a) iff at least one tuple in ✓ is a support of (X↪ a). This is equivalent to that at least one bit of the corresponding bit vector mask is value 1.

For each literal in the dual table, we replace its index of support tuples by a set of value pairs whose first value ✓ gives the index of the table support and the second value is the corresponding bit vector mask. We call such value pairs as bit supports of literals, and the dual table with bit supports as a bit table. For convenience, we say "a tuple in ✓" to mean that the tuple is included in the sub-table with index ✓.

Example 1. Figure 2(a) shows a partition of the table given in Figure 1(a) that the table is partitioned into 2 sub-tables ✓1 and ✓2 and each sub-table contains 4 original tuples. Then we use a bit-vector mask to encode every sub-table. Figure 2(b) gives the corresponding bit table. (Y↪ a) has two bit supports. The first bit support (✓1↪ 1000) indicates the 1st tuple in sub-table ✓1 is a support of (Y↪ a). The second bit support indicates the 1st and 3rd tuples in sub-table ✓2 are supports.

The number of bit supports in bit table is O(L), but always  L. Thus, the bit table can be seen as a way of compressing the dual table (see L◁Lbit in Section 5).

3.1 Maintaining GAC on bit table during search

We give a GAC algorithm STRbit for the table constraint represented in a bit table. Our algorithm adapts the simple tabular reduction (STR) algorithm which shrinks tables dynamically during search. STRbit maintains GAC during search by updating the validity of tuples and seeking supports for each value in the variable's current domains. Validity of tuples is also represented by bit vectors VAL, where bit value 1 indicates the corresponding tuple is valid and value 0 indicates

Function deleteInvalidTuple(C : Constraint)

for each X 2 scp(C) do for a 2 DEL(C↪X) do for i := 0 to LAST(C↪ X↪ a) do 1 ✓ := BIT SUP(C↪ X↪ a)[i]▷ts; u := BIT SUP(C↪ X↪ a)[i]▷mask & VAL(C↪ ✓); if u 6= 0 then save((C↪ ✓)↪ VAL(C↪ ✓)↪ restoreV ); 2 VAL(C↪ ✓) := (≻u) & VAL(C↪ ✓); DEL(C↪X) := ;;

Function searchSupport(C : Constraint)

for each X 2 scp(C) and a 2 dom(C↪ X) do now := LAST(C↪ X↪ a); ✓ := BIT SUP(C↪ X↪ a)[now]▷ts; 1 while BIT SUP(C↪X↪ a)[now]▷mask & VAL(C↪ ✓) = 0 do now := now - 1; if now = -1 then remove(C↪ X↪ a); if dom(X) = ; then return false; break; ✓ := BIT SUP(C↪ X↪ a)[now]▷ts; 2 if now 6= LAST(C↪X↪ a) then save((C↪ X↪ a)↪ LAST(C↪ X↪ a)↪ restoreL); LAST(C↪X↪ a) := now; return true;

invalid. For example, we can use two 4-bit vectors to represent the validity of tuples in the two sub-tables in Figure 2(a). If we assume only tuple 1 in ✓1 and tuple 7 in ✓2 are valid and all the other tuples are invalid, then the values of the vectors are (1000) and (0010). Before giving the details of STRbit, we first introduce its data structures.

• ÷ BIT SUP(C↪X↪ a) is an array of bit supports of literal (X↪ a) in the bit table of constraint C. In fact, BIT SUP(C↪X↪ a)[i] is the ith bit-support of (X↪ a). BIT SUP(C↪X↪ a)[i]▷ts is the index of table support and BIT SUP(C↪ X↪ a)[i]▷mask is the corresponding bit vector mask. BIT SUP(C↪X↪ a)▷size is the number of bit-supports of (X↪ a) and used for initialization.
• ÷ VAL(C↪ ✓) is a bit vector recording the validity of tuples in ✓.
• ÷ LAST(C↪X↪ a) records the last position i such that the table support BIT SUP(C↪X↪ a)[i]▷ts includes at least one valid tuple, and BIT SUP(C↪X↪ a)[j]▷ts doesn't include valid tuples for each j > i.
• ÷ DEL(C↪X) is a set of literals that have been deleted from dom(X), but GAC has not been maintained on C.
• ÷ restoreV and restoreL are two stacks recording the validity of tuples and the last position of bit supports to restore information when backtracking happens.

remove literal (X↪ a) from dom(X); add X to the propagation queue; for each C1 2 ⇣ and C1 6= C and X 2 scp(C1) do add a to DEL(C1↪ X);

Function remove(C↪ X↪ a) Function save(key↪ newdata↪ store)

if (key↪ olddata) ◁2 top(store) for any olddata then add newdata to top(store)

Like STR3, STRbit is only used to maintain GAC during search, as such, a separate GAC algorithm needs to be invoked before search to make the input instance GAC. Then we call the function GACinit to remove invalid tuples and initialize the data structures of STRbit before search starts. In GACinit, we set VAL(C↪ ✓) to be a bit vector of ones (line 2) and set the separator LAST(C↪X↪ a) pointing to the last bit support (line 3). We then initialize DEL(C↪X) to the empty set since all constraints are GAC at the start.

During search, the STRbit algorithm is invoked for each constraint C when a value is removed from the domain of a variable involved in C. Algorithm 1 gives both parts of STRbit. Firstly, deleteInvalidTuple(C) deletes all invalid tuples and updates bit vector VAL. For each removed literal (X↪ a) in DEL, deleteInvalidTuple(C) set its bit supports to be invalid (between line 1 and 2). Then the second part searchSupport(C) seeks supports for each (X↪ a) such that a 2 dom(X). We seek supports from the position recorded by LAST(C,X,a) and use now to point to the bit support being checked. ✓ indicates the index of sub-table so that we can fetch the validity of tuples in VAL(C↪ ✓). We apply bit operations to check whether the current bit support includes a valid tuple (line 1). If all values are 0, there is no valid tuple in the current bit support and now shifted to the left by one. If now = -1, then there no valid bit tuple supports (X↪ a) and (X↪ a) can be deleted. The function save is used to record the old data in a stack before updating the data structures. The data structure restoreL records the old data of LAST(C↪ X↪ a), and restoreV records old data of VAL(C↪ ✓). Upon backtracking, the algorithm just needs to reset the value of LAST(C↪X↪ a) and VAL(C↪ ✓) by popping the old data from restoreL and restoreV . In addition, since the constraint network is always consistent before accessing the next layer in the search tree, we just need to set DEL(C↪X) as empty when backtracking.

3.2 Complexity analysis

STRbit is designed to maintain GAC during search, thus, we analyse the "time complexity along a path" in the search tree. The time cost of STRbit is bounded by the number of bit supports included in the bit table. For one constraint C, Lbit denotes the number of bit supports included in the bit table.

Theorem 1. The accumulated time cost of r arity constraint C in STRbit along a single path of length m in the search tree is O(Lbit + r2d2 + m).

(c) Bit c-table

Proof. The primary time cost of STRbit includes two parts. One is the function deleteInvalidTuple(C): the time cost of this part is O(Lbit), since every bit support is only processed once; Another part is the function searchSupport(C): the time cost of this part is O(Lbit+r2d2 ). At line 2, when LAST is decreased, each bit support in BIT SUP will be checked only once, so the time cost is O(Lbit). Otherwise when LAST is not changed, an invocation's cost is O(rd), and the number of calls STRbit on C is at most rd times along a single path in search tree, so the time cost is O(r2d2 ). Correspondingly, the total time cost is O(Lbit + r2d2 +m) along a single path in search tree, as all other statements have fixed cost O(1) at each node.

STR3 has a path-optimality property but STRbit is not (Theorem 1) so in the worst case a bit support in a bit table may be processed multiple times in a search tree path. From a practical efficiency perspective, the importance of path-optimality is unclear, e.g. STR2 is not path-optimal but is faster than STR3 on many benchmarks [Lecoutre et al., 2012]. In practice, the actual cost in STRbit depends on the size of Lbit which can be much smaller than L (used in STR3) by a factor of w (due to bit vectors). Our experiments (Figure 4(a)) show STRbit to be up to 25X faster than STR3. The speedup ratio is not always close to the ratio L◁Lbit because in STR algorithms L varies dynamically due to the tabular reduction, thus, the worst case time complexity may be a rather crude bound.

4 Bit-C representation in STRbit-C

We now combine Cartesian product compression with its bit representation giving a new dual table representation, called bit c-table. For an r-arity constraint C(x1↪ ▷ ▷ ▷ ↪ xr), the Cartesian product representation of a set of tuples (¶a1↪1↪ ▷ ▷ ▷ ↪ a1↪k1♦↪ ▷ ▷ ▷ ↪ ¶ar↪1↪ ▷ ▷ ▷ ↪ ar↪kr♦) is called a c-tuple [Katsirelos and Walsh, 2007]. This c-tuple admits any set of assignments that assigns one of a1↪1↪ ▷ ▷ ▷ ↪ a1↪k1 to x1, one of a2↪1↪ ▷ ▷ ▷ ↪ a2↪k2 to x2, etc. A c-tuple ⌧c is a c-support of literal (X↪ a) iff there is a valid tuple in ⌧c supports (X↪ a). We can compress a standard table into a c-table with c-tuples. The standard table in Figure 1(a) represented in c-table form is shown in Figure 3(a). As before, we partition a c-table into a set of sub-c-tables by the word size, where a sub-c-table is a subset of c-table.

Similar to table support, a sub-c-table ⌘ is a table c-support of (X↪ a) iff at least one c-tuple in ⌘ supports (X↪ a). Then

Function deleteInvalidCTuple(C : Constraint)

for each literal (X↪ a), we use a set of pair (⌘↪mask) to represent a bit c-support of (X↪ a), where ⌘ is an index of table c-support and mask is a bit vector. In mask, the ith bit indicates whether the corresponding ith c-tuple in ⌘ is a c-support of (X↪ a) (value 1) or not (value 0). For convenience, we say "a c-tuple in ⌘" to mean that the c-tuple is included in the sub-c-table with index ⌘.

Example 2. Figure 3(b) gives a partition of the c-table relc(C) in Figure 3(a). The partition has only one sub-ctable ⌘1 with all 4 tuples in relc(C). Thus each domain value has at most one bit c-support, e.g. (Y↪ c) has one bit c-support (⌘1↪ 0110) in Figure 3(c). The value (⌘1↪ 0110) means that the second and third c-tuple in ⌘1 are (Y↪ c)'s c-supports.

4.1 Maintaining GAC on bit c-table during search

We now give the STRbit-C GAC algorithm which works on bit c-tables. As with STRbit (Algorithm 1), STRbit-C is also composed of two functions: deleteInvalidCTuple(C) to delete invalid c-tuples and searchSupport(C) to seek supports for literals. A c-tuple is valid iff at least one ordinary tuple of the c-tuple is valid; otherwise it is invalid. Function searchSupport(C) is the same as STRbit but deleteInvalidCTuple(C) is different due to differences in how invalid c-tuples are deleted.

The data structures of STRbit-C is similar to STRbit. VAL(C↪ ⌘) represents the validity of c-tuples in ⌘, and a subc-table ⌘ is valid iff VAL(C↪ ⌘) 6= 0. BIT SUP(C↪X↪ a) represents a set of bit c-supports of literal (X↪ a) (array). Then we use three additional data structures:

• ÷ CDENSE[C] is a set of index of valid sub-c-tables for constraint C, CDENSE▷size is the size of CDENSE[C].
• ÷ restoreC is a stack recording old data of CDENSE[C] to restore information when backtrack happens.

• ÷ BUFF is a set of bit vectors for computing the validity of c-tuples.

If a c-tuple ⌧c in sub-c-table ⌘ is valid, then for each variable X in scp(C), there must be a valid literal (X↪ a) and a bit c-support (⌘↪mask) 2 BIT SUP(C↪X↪ a) such that the corresponding bit in VAL(C↪ ⌘) & mask for ⌧c ((VAL(C↪ ⌘) & mask)[⌧c]) is value 1. This means that the set of valid c-tuples for constraint C equals

where (⌘↪mask)=¶⌧c 2 ⌘ ♣(VAL(C↪ ⌘) &mask)[⌧c] = 1♦. At line 1, if DEL(C↪X) = ;, no literal has been deleted after the last invocation of deleteInvalidCTable(C), so variable X can be skipped. Otherwise, for each value a 2 dom(X) and bit c-support BIT SUP(C↪X↪ a)[i] such that i 2 [0, LAST(C, X, a)], BIT SUP(C↪X↪ a)[i]▷mask is recorded in BUFF at line 2 and line 3 (bitwise OR). Then for each ⌘ 2 CDENSE[C], VAL(C↪ ⌘) is updated by the bitwise AND operation of VAL(C↪ ⌘) and BUFF[⌘] between lines 4 and 5. In addition, ⌘ will be deleted from CDENSE[C] if VAL(C↪ ⌘) equals 0 (line 6).

4.2 Complexity analysis

Similar to STRbit, the time cost of STRbit-C along a path in search tree depends on the number of bit c-supports in bit ctable. We use Lbitc to represent the number of bit c-supports in a c-table.

Theorem 2. The accumulated time cost of r-arity constraint C in STRbit-C along a single path of length m in the search tree is O(dLbitc + r2d2 + m).

The proof is similar to Theorem 1 and omitted here.

5 Experiments

We evaluate STR2, STR3, STR2-C, STR3-C, MDDc, STRbit and STRbit-C in the Abscon [Merchez et al., 2001] solver. Our implementation uses 64-bit numbers (long Java type) so w = 64 and partitions the table in lexico order. In addition, we extract the c-table from the MDD. Experiments are run on a 3.40 GHz Intel core i7 processing on Linux, and all algorithms use the dom◁ddeg variable ordering heuristic and lexico value ordering heuristic. Timeout is 600 seconds. We consider classical series instances 1 , the series 2 introduced in STR2-C, and the PH-k-j series used in STR3 (896 instances).

Table 1 gives the mean runtime (in seconds) of 7 algorithms on different benchmarks. The column # gives the number of instances in each series. L (Lc) is the mean number of literals in the standard tables (c-tables), and Lbit (Lbitc) is the mean number of bit supports (bit c-supports) in the bit tables (bit c-tables). The columns L◁Lbit, Lc◁Lbitc, L◁Lc and L◁Lbitc represent the corresponding compression ratio. The column avgP (from the STR3 evaluation [Lecoutre et al., 2012]) is the mean ratio of "the number of tuples in the current standard table during search" to "the number of tuples in the initial standard table" during search. In addition, we divide the benchmarks into 4 groups: R for random benchmarks; S for structured; M for the instances with a small average table size (L < 50); and MC for small c-table sizes (Lc < 200).

1 http://www.cril.univ-artois.fr/%7Elecoutre/benchmarks.html

2 http://www.comp.nus.edu.sg/%7Exiawei/STRC-benchmarks/

For benchmarks in groups R, S and MC, STRbit is faster than STR3 and the compression ratio L◁Lbit is large. For example, in the MDD0.7 and MDD0.9 series, L◁Lbit > 20 so STRbit can be 10X faster than STR3. STRbit is also faster than STR2 on most series except the ones with low avgP . We highlight the effect of the avgP factor which measures the average reduced table size (by tabular reduction) during search. For example, on the tsp-20, tsp-25, rand-8 and dag-rand series, avgP < 0▷004 so STRbit is a little slower than STR2 but still faster than STR3 (for dag-rand it is 16X faster). While for the rand-10-60 series, avgP > 0▷2, so STRbit can be faster than STR2 by an order of magnitude. Similarly, on most series in the R and S group, STRbit-C is faster than STR2-C and STR3-C and MDDc. The instances in the M group have small average table sizes, so fixed costs (data structure initialization, restoration, etc.) during search can dominate. The MDDc algorithm, which maintains only one sparse set during search, is fast on these instances, while STRbit is close to STR2 and STR3. In addition, on the series in the MC group, the compression of c-table makes the size small (< 200), hence the time cost of STRbit-C is close to STR2-C, STR3-C and MDDc on these series.

In Figure 4, we present scatter plots comparing the speedup of STRbit and STRbit-C with various factors. Every dot in these graphs corresponds to an instance. For Figures 4(a), 4(b), 4(c), 4(d), 4(e) and 4(f), we avoid some "noise" by removing the instances solved within 0.5 second (the slowest algorithm) and the series in M. We also omit the series in MC for Figures 4(b) and 4(f), because the size of the c-table is very small. Figures 4(a), 4(b), 4(c) and 4(d) depict the impact of compression ratio on the performance of STRbit and STRbit-C. As we can see, when the compression ratios L◁Lbit, Lc◁Lbitc and L◁Lbitc increase, STRbit (STRbit-C) can be up to 25X (80X) faster than STR3, while STRbit-C can be up to 27X faster than STR3-C. In addition, STRbit-C is faster than STRbit on most instances when Lbit◁Lbitc ≥ 3.

On many instances, the STRbit (STRbit-C) compression ratios are larger than the speed up, we believe it is due to the initialization times and other costs during search. Furthermore, the ratio is only an estimate as the true compression ratio varies dynamically due to tabular reduction. Figures 4(e) and 4(f) show the effect of avgP. When avgP is small (< 0▷004), STRbit (STRbit-C) may be a little slower than STR2 (STR2-C), but when avgP is larger, STRbit (STRbitC) can be up to 70X (40X) faster than STR2 (STR2-C). Figure 4(g) and 4(h) compare STRbit and STRbit-C with MDDc using all series in Table 1. These two graphs show that our algorithms are faster than MDDc on most instances.

6 Conclusion

In this paper, we introduce new table representations, bit table and bit c-table. Then we propose two algorithms to maintain GAC during search on bit table and bit c-table. Experiments show that our algorithms outperform the state-of-the-art GAC algorithms STR2, STR3 and MDDc and for compressed tables also STR2-C and STR3-C. Previous work has shown a dichotomy for STR algorithms: (i) in tables where the tabular reduction is strong, small avgP, STR2 is very effective; (ii) but when the tables reduce less, larger avgP, then STR3 performs better. Our STRbit algorithms significantly narrow this gap and the benchmarks show that STRbit is more efficient than STR2 and STR3 in most cases even when the reduction rate is small. This suggests that STRbit algorithms can replace the combination of STR2 and STR3.

Recently, the algorithmic framework of STR has been extended in other directions. For example, the factor encoding [Likitvivatanavong et al., 2014; 2015] adapts better to STRbased algorithms than MDD-based algorithms. The GIC4 algorithm [Bessiere et al., 2013] enforcing global consistency for configuration problem also uses STR-based algorithms. There is potential for our algorithms along these directions.