LES³: Learning-based Exact Set Similarity Search

Assume for now, that $\mathcal{D}$ is already partitioned into $n$ non-overlapping groups, $\mathcal{G}_{1},\cdots\mathcal{G}_{n}$; we defer the discussion of the strategies for partitioning to the next section. The goals of the index are simplicity (so that it incurs little computational and storage overhead) and effectiveness (providing high pruning efficiency). To this end, the TGM, $M$, with size $n*|\mathcal{T}|$, is constructed in the following way:

where $t\in[1,|\mathcal{T}|]$ and $g\in[1,n]$.

An example of TGM is given in Figure 1, where $\mathcal{T}=\{A,B,C,D\}$ and six sets are partitioned into two groups $\mathcal{G}_{0}$ and $\mathcal{G}_{1}$.

The design of the TGM is based on the observation that when deciding whether a group of sets is a candidate for a query set or not, the only information needed is the number of common tokens they share. Such information can be easily obtained by visiting some elements in $M$, and thus we can compute a similarity upper bound between a query set $Q$ and a group of sets $\mathcal{G}_{g}$, which are useful in pruning the search space, as follows:

Continuing the example above, we assume that the query set is $\{A\}$ and $\mathcal{G}_{0}$ and $\mathcal{G}_{1}$ in Figure 1 are candidates. Then the similarity bound between the query set and $\mathcal{G}_{0}$ is $\frac{M[\mathcal{G}_{0},A]}{|\{A\}|}=1$, and the upper bound for $\mathcal{G}_{1}$ is $\frac{M[\mathcal{G}_{1},A]}{|\{A\}|}=0$.

Although we assume $Q$ contains tokens in $\mathcal{T}$ only, the case where this does not hold can be handled by letting $M[*,t^{\prime}]=0$ for $t^{\prime}\notin\mathcal{T}$ in Equation (2). No further changes are required.

In the query processing step, if the upper bound of group $\mathcal{G}_{g}$ exceeds a threshold (can be $\delta$ in range query, or the minimal $k$NN similarity found so far), we compare all sets in $\mathcal{G}_{g}$ with the query set. The time complexity of computing the similarity bounds between the query set and all groups of sets is $O(n|Q|)$. It in general costs much less than computing the similarity between the query set and each set in $\mathcal{D}$, as the number of groups is usually orders of magnitude smaller than $|\mathcal{D}|$.

In terms of space consumption, each element in TGM is represented by a bit, and TGM is essentially a bitmap index. It is evident that $M$ is usually a very sparse matrix as each set usually contains a very small portion of the tokens from the universe. When necessary, many existing compression techniques (Salomon, 2004; Salomon and Motta, 2010) can be employed to reduce the size of $M$.

Although Equation (2) is computed assuming Jaccard index as the similarity metric, TGM works with many other set similarity measures as well, including measures that do not follow the triangle inequality, such as cosine similarity.

For example, let $Q=\{t_{1},t_{2},t_{3}\}$ and $Q\cap S=\{t_{1},t_{2}\}$. Then with Jaccard similarity, the set with the maximal similarity to $Q$ is $\{t_{1},t_{2}\}$ and the upper bound is $\frac{2}{3}$; with cosine similarity, the set with the maximal similarity to $Q$ is also $\{t_{1},t_{2}\}$, but the upper bound is $\frac{2}{\sqrt{3*2}}\approx 0.82$. Note that although most similarity measures satisfy the TGM Applicability Property, some exceptions do exist. One such example is the learned metric (Kim et al., 2019) which takes two samples (e.g., images) as the input and predicts their similarity.

In what follows, we call the two properties listed in Theorem 3.1 the TGM Applicability Property. Note that the token universe $\mathcal{T}$ does not need to be static. We will discuss how to adapt TGM to deal with cases where $\mathcal{T}$ is dynamically changing in Section 6.

We formally analyze the effect of partitioning on pruning efficiency when the following assumption on token distribution holds.

For an arbitrary query $Q$, the expected pruning efficiency can be computed as follows:

Given the way the TGM is constructed, we rewrite Equation (2) in the following way to ease subsequent discussion:

Accordingly, we rewrite Equation (3) as follows:

As we assume $Q$ follows the same distribution as $\mathcal{D}$, $E[PE]$ over all possible $Q$ can be estimated by the following equation:

Since $|\mathcal{D}|$ is a constant, we keep the nominator of Equation (6) only, and adjust the order as follows:

To ease following analysis, we define term $F$ in Equation (8), and claim that maximizing Equation (7) (and thus maximizing the pruning efficiency) is equivalent to minimizing $F$:

We derive several properties regarding the partitioning from Equation (8) so as to design practical partitioning algorithms.

Even though the optimal partitioning is expected to produce groups with almost equal sizes, evidently balance is not the only desired property, according to Equation (8). We temporarily omit the $|\mathcal{G}_{g}|$ in Equation (8) and discuss other properties the partitioning must satisfy in order to provide higher pruning efficiency.

In summary, we have the following two desired properties regarding the partitioning of database $\mathcal{D}$.

• •

  Property 1: Groups are balanced;

• •

  Property 2: $U=\sum_{g=1}^{n}|\bigcup_{S\in\mathcal{G}_{g}}S|$ is minimized.

The analysis in the preceding section depends on the uniform token distribution assumption. In real-life datasets, this assumption does not hold. However, following the same methodology to derive a formal treatment of an arbitrary set/token distribution would be challenging as a realistic mathematical model of arbitrary set/token distributions would be hard to justify. Although the two properties identified above may not be true for optimal partitioning in the general case, we draw inspirations from them and propose a heuristic objective function that strives to maximize PE.

In essence Property 2 directs that the more similar (in terms of token composition) the sets are within a group, the better. We thus design a general partitioning objective ($GPO$) we wish to minimize reflecting this property:

where $Sim(*)$ can be any measures discussed in Section 3.2.

Intuitively, $GPO$ aims to minimize the sum of the intra-group pair-wise distances, where distance is defined as $1-Sim(*)$. This is similar to Property 2. As an example, consider two groups $\mathcal{G}_{i}$ and $\mathcal{G}_{j}$ with $|\mathcal{G}_{i}|=|\mathcal{G}_{j}|$. Assume that $Sim(*)$ is Jaccard similarity, and we are to place a new set $S$ into one of the two groups. Then, if $\sum_{S_{i}\in\mathcal{G}_{i}}(1-Sim(S,S_{i}))<\sum_{S_{j}\in\mathcal{G}_{j}}(1-Sim(S,S_{j}))$, that would mean $S$ shares more common tokens with sets in group $\mathcal{G}_{i}$, and thus inserting $S$ into group $\mathcal{G}_{i}$ helps to minimize $U$.

However, considering only Property 2 results in highly skewed partitioning results, as placing all sets in the same group provides the minimal $U$ (which equals to $|\mathcal{T}|$). Evidently, Property 1 is used to prevent such skewed partitioning in the uniform case. Luckily, $GPO$ enjoys a similar functionality: placing all sets in the same group provides $GPO=\sum_{S_{x},S_{y}\in\mathcal{D}}(1-Sim(S_{x},S_{y}))$, which is the maximal possible $GPO$, and thus such a partitioning is never the optimal in terms of $GPO$. Thus, the design of $GPO$ implicitly incorporates both Property 1 and Property 2.

In order to better appreciate the distinctive value of the proposed partitioning objective, we compare $GPO$ with $k$-medians, perhaps the most popular clustering technique, and show by an example how optimizing $GPO$ leads to better results. We use a database of 21 sets, and the partitioning results based on different clustering objectives are given in Figure 2. Each set is represented by a point in the plot, and to better visualize the results we replace $(1-Sim(*))$ with Euclidean distance.

Assume that the query is to identify the nearest neighbors of all 21 points. According to the search strategy of $\mathsf{LES}^{3}$ given in Section 3.1, all points in the same group are candidates of each other. Therefore, with the clustering results given in Figure 2(b), the total number of distance calculations is $20*20+1*1=401$, while with the partitioning results in Figure 2(a) the number is $13*13+8*8=233$. Clearly, the results based on Equation (13) have better pruning efficiency.

In this section we propose several algorithmic approaches based on existing applicable clustering methods, which are expected to yield groups with low $GPO$ values. More specifically, we design a graph cut-based approach (PAR-G), a centroid-based approach (PAR-C), and a hierarchical approach (PAR-H).

Considering that the goal of optimizing $GPO$ is to maximize the overall intra-group similarity, we adopt Siamese networks (Bromley et al., 1994; Fan et al., 2018) to solve the partitioning task. Siamese networks have been successfully utilized in deep metric learning tasks (Mueller and Thyagarajan, 2016; Neculoiu et al., 2016) in computer vision, capturing both intra-class similarity and inter-class discrimination in many challenging tasks including face recognition.

We design a Siamese network as shown in Figure 3 to learn the optimal partitioning. It consists of a pair of twin networks sharing the same set of parameters working in tandem on two inputs and generate two comparable outputs.

We use $Rep(S_{x})$ and $Rep(S_{y})$ to denote the vector representations of two sets $S_{x}$ and $S_{y}$, a pair of inputs to the twin networks, and use $G(S_{x})$ and $G(S_{y})$ to represent their respective group assignment indicted by the outputs of the twin networks respectively. Following Equation (13) we define the loss function of the Siamese network as follows:

Equation (15) minimizes the intra-group dissimilarities by summing $(1-sim(S_{x},S_{y}))$ as the losses, and penalizes imbalanced groups by counting pairwise dissimilarities only between sets in the same group. We use an example to illustrate how Equation (15) penalizes imbalanced partitioning. Suppose there are $N$ sets and dissimilarity between any pair of sets is the same at $d$. The task is to partition these sets into 2 groups, containing $N_{1}$ and $N_{2}$ sets respectively ($N_{1}+N_{2}=N$). Then the overall loss is $\frac{N_{1}(N_{1}-1)d}{2}+\frac{N_{2}(N_{2}-1)d}{2}=\frac{d}{2}[N_{1}(N_{1}-1)+N_{2}(N_{2}-1)]=\frac{d}{2}(N_{1}^{2}+N_{2}^{2}-N)\geq\frac{d}{2}(\frac{(N_{1}+N_{2})^{2}}{2}-N)=\frac{d}{2}(\frac{N^{2}}{2}-N)$, and the bound is tight when $N_{1}=N_{2}$. Therefore, Equation (15) favors balanced partitioning.

By training the Siamese network with sufficient samples drawn from $\mathcal{D}$, theoretically we can minimize the overall distances between all pairs of sets which belong to the same group, and thus the Siamese network is expected to give the partitioning result in which $GPO$ is minimized. Practically, however, we expect to achieve near-optimal partitioning only as the network is essentially performing local search.

Although using Siamese networks to solve the optimization problem is a promising approach, training such networks turns out to be difficult for the following reasons:

1. (1)

   When dealing with real world data, we may need to partition sets into thousands of groups. Therefore, for an input set $S_{x}$, the network needs to make prediction on which group $S_{x}$ belongs to, among a collection of thousands of groups. It is well known (Gupta et al., 2014) that training networks to tackle prediction problems involving thousands or more labels is challenging.

2. (2)

   What makes this task even more difficult is that unlike a classification problem, the label for each input (i.e., the optimal group) in this optimization problem is unknown, i.e., there is no ground truth regarding the labels/groups available. The only information we have is the loss if the two input sets are assigned into the same group. This makes the problem even more challenging than typical classification problems.

The inherent difficulty of utilizing Siamese networks for this problem is the dimensionality (i.e., degrees of freedom) of the output space. In response to this challenge, we propose a learning framework consisting of a cascade of Siamese models, which partitions the database in a hierarchical fashion. Each Siamese network in the framework is responsible for partitioning a group of sets into two sub-groups. The framework is illustrated in Figure 4.

At Level 0 of the framework, we train a Siamese network which takes each set in the entire database $\mathcal{D}$ and assigns it into one of two groups, $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$, based on the loss function given in Equation (15). Then at Level 1, we train two Siamese networks working on $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ respectively in the same fashion. Thus, they partition the entire database into four groups. We continue adding more levels to the cascade framework until all groups are small enough or a pre-defined threshold on the number of levels is reached. Since each model in the cascade is specialized to partition a group of sets into only two sub-groups the resulting classification problem can be solved effectively.

The architecture of the cascade models motivates the use of a hierarchical indexing structure, which we call Hierarchical TGM (or HTGM). More specifically, assuming the level of the cascade framework is $l$, and $0\leq i<j<l$, we construct TGM_i and TGM_j based on the partitioning results at level $i$ and level $j$ respectively. Suppose a group at level $i$, say $\mathcal{G}_{g}$, is partitioned into several sub-groups at level $j$, say $\mathcal{SG}_{1},\cdots,\mathcal{SG}_{m}$. If for a query $Q$, group $\mathcal{G}_{g}$ can be pruned by checking TGM_i, then all verification operations involving groups $\mathcal{SG}_{1},\cdots,\mathcal{SG}_{m}$ can be eliminated. The construction can be easily generalized to HTGM with $h$ ($h>1$) levels.

A Siamese network accepts vectors as input and thus the sets in $\mathcal{D}$ cannot be directly fed into the network. As a result we have to build a vector representation for each set. Considering the time and space complexity of existing embedding methods such as Principal Component Analysis (PCA) or Multidimensional Scaling (MDS), they can hardly be applied to the target setting introduced in Section 7 where millions or billions of sets are involved (see comparison regarding embedding cost in Section 7.3). Besides, different from the objectives of these general-purpose embedding methods such as maximizing variance or preserving distance, our concern is to make sets containing different tokens more separable to benefit the training of the Siamese network. Intuitively, the representations that ease the training of the models are expected to bear the following property:

Next we discuss how to construct such representations. As the first step, we organize all tokens with a balanced binary tree such that tokens appear in leaf nodes and each leaf contains only one token. The height of the tree is thus $h=\lceil\log_{2}{|\mathcal{T}|}\rceil$. We mark the edge from a node to its left child with 1 and the edge to its right child with 0. An example of such a tree is depicted in Figure 5.

We use $path_{t}$ to denote the path from the root to an arbitrary token $t$. Since each leaf contains only one token, no two tokens share the same path. We build a path table (PT) of all tokens defined as follows:

An example of PT is provided in Table 1.

We propose a method called PTR (Path Table Representation) to build a representation for a given set $S$ as follows:

In the above example, the representation of $\{A,B,C\}$ is $[2,2,1,1]$ and the representation of $\{B,D\}$ is $[1,0,1,2]$. The second half of the path table (Positions 3 and 4) helps to reduce the chance that different sets have common representations. For example, if only the first half is used, then the representations of $\{A\}$, $\{B,C\}$, $\{A,D\}$, $\{B,C,D\}$ would all be $[1,1]$. We compare the set representations constructed on the full vs. half path tables in Section 7.3.

PTR also naturally differentiates multisets containing the same collection of tokens but with different number of occurrences. For example, $Rep(\{A\})=[1,1,0,0]$ while $Rep(\{A,A\})=[2,2,0,0]$.

The basic idea of the representation is to map the sets into a new space, in a way that determining collections of sets containing specific tokens can be easily performed. More specifically, set $S$ is placed in the representation space based on the presence or absence of all tokens in $S$, and consequently, given a collection of tokens $\mathcal{T}_{c}$, we can quickly locate all sets containing $\mathcal{T}_{c}$. This evidently yields the set separation-friendly property. To better illustrate this, we reuse the path table in Table 1 and show that sets containing $B$ can be separated from other sets. For better visualization, we project the representation space onto the first two dimensions (Positions 1 and 2), and keep tokens $B$, $C$, and $D$ only in Figure 6. Clearly all sets containing token $B$ fall into the striped area, defined by the axis aligned hyper-plane in the representation space passing from point $(1,0)$ (corresponding to $\{B\}$). Similarly all sets containing both $B$ and $C$ are located at the intersection of the axis aligned hyper-planes passing from $(1,0)$ and $(0,1)$ (corresponding to $\{C\}$). That way separating sets in the representation space based on token membership is conducted by determining hyper-plane intersections. We will demonstrate that such a representation is easier to learn and yields effective partitions in Section 7.

Environment. We run the experiments on a machine with an Intel(R) Core i7-6700 CPU, 16GB memory and a 500GB, 5400 RPM HDD (roughly 80MB/s data read rate). We use HDD for fair comparison as other disk-based methods require no random access of the data (see Section 7.6). However one could expect better performance of $\mathsf{LES}^{3}$ when running on SDD as it incurs random access of the data by skipping some groups, especially when the number of groups is large.

Implementation. L2P is implemented with PyTorch, embedding methods in Section 7.3 and partitioning methods in Section 7.4 are implemented with Python, and TGM and the set similarity search baselines are implemented in C++ and compiled using GCC 9.3 with -O3 flag. TGM is compressed by Roaring (Lemire et al., 2018), a well-performed bitmap compression technique.

Datasets. KOSARAK (KOS, [n.d.]), LIVEJ (Mislove et al., 2007), DBLP (DBL, [n.d.]), and AOL (Pass et al., 2006) are three popular datasets used for set similarity search problems and we adapt them for this reason. We also include a social network dataset from Friendster(Yang and Leskovec, 2015) (denoted by FS), where each user is treated as a set with his/her friends being the tokens; and a dataset from PubMed Central journal literature (Journal, ) (denoted by PMC), where each sentence is treated as a set with the words being the tokens³³3with basic data cleaning operations such as stop-words removal.. Table 2 presents a summary of the statistics on these datasets. Considering the size of FS and PMC, we utilize them for disk-based evaluation in Section 7.6 to examine the scalability of $\mathsf{LES}^{3}$.

Evaluation. Following previous studies (Deng et al., 2018; Mann et al., 2016; Zhang et al., 2020), we adopt Jaccard similarity as the metric in our experimental evaluation. We stress however that any similarity measures satisfying the TGM applicability property introduced in Section 3.2 can be adopted in our framework with highly similar results as those reported below. For each experiment, we randomly select $10$K sets in the corresponding dataset as the queries and report the average search time. Unless otherwise specified, the indexing structure (TGM) and the data are memory-resident. We conduct disk-based evaluation in Section 7.6. We compare TGM with HTGM in Section 7.7. We select $n$ (number of groups) for each dataset which results in the shortest query latency. The influence of $n$ is studied in Section 7.5.

Network and Loss Function. We consider Multi-Layer Perceptron (two hidden layers, each consisting of eight neurons) and Sigmoid activation function for L2P training in the experiment and leave the investigation of other networks as future work. Clearly the network has one neuron at the output layer. Let $O_{x}$ be the output on input set $S_{x}$. If $O_{x}<0.5$, then $S_{x}$ belongs to the first group; if $O_{x}\geq 0.5$, then $S_{x}$ belongs to the second group.

The loss function given in Equation (15) clearly describes the learning objective. However, it is difficult to train the network with that loss function as its gradient is 0 for most outputs (to be exact, the gradient is $(1-sim(S_{x},S_{y}))$ when $O_{x}=O_{y}=0.5$, and is 0 elsewhere). For efficient training, we use the following surrogate loss function, which leads to the same global optimum as Equation (15) while introducing non-zero gradients:

where $W(O_{x},O_{y})=(0.5-|O_{x}-O_{y}|)$, and $V(O_{x},O_{y})=[(O_{x}\geq 0.5\wedge O_{y}\geq 0.5)\vee(O_{x}<0.5\wedge O_{y}<0.5)]$.

Initialization. Models at the first few levels of the Cascade framework deal with a large number of sets and incur long training time. To improve the training efficiency, we first sort all sets based on the minimal token contained in each set, and then partition all sets into 128 groups such that each group contains consecutive $|\mathcal{D}|/128$ sets, inspired by the idea of imposing sequential constraint to clustering tasks (Szkaliczki, 2016). Since we always build TGM on the partitioning results at level 10 or higher which may contain thousands of groups, such initialization has minor impact on the performance but greatly reduces the training time. Note that initialization is not performed for the sampled dataset used in Section 7.3 due to its small size.

Training. For the Siamese network partitioning an arbitrary group, we randomly select 40,000 pairs of sets in the group to generate training samples, relatively small compared to the data size. It is observed that further increasing the number of training samples do not significantly improve the pruning efficiency of the partitioning results. We stop partitioning a group if it contains less than 50 sets, and thus the number of groups at level $i$ may be less than $2^{i}$. The batch size is set to 256, the number of epochs is set to 3 (except for Section 7.2 which reports the learning curves), and Adam is used as the optimizer. The same sampling-and-training procedure is repeated for each model in the cascade framework, starting from level 0.

In this section we report the learning curves and the training costs. We observe that different models in the cascade framework introduced in Section 5.2 yield similar learning curves, and thus we present the training loss of a random model at level 0 for each dataset (note that there are 128 models at level 0, see Section 7.1, paragraph Initialization). The training losses and costs are presented in Figure 7.

As is clear from Figure 7(a), on all datasets used in the experiment, the training loss decreases rapidly and the model converges after approximately two epochs, attesting to the efficiency of the model training process. Also, as can be observed from Figure 7(b), the training cost grows linearly with respect to the number of groups, making $\mathsf{LES}^{3}$ scalable for large datasets. Besides, models at the same level of the cascade framework can be trained in parallel to further reduce the training cost, which is an interesting direction for future investigation.

We compare PTR with other applicable set representation techniques. More specifically, we choose PCA (Jolliffe and Cadima, 2016), a widely-used linear embedding method, MDS (De Silva and Tenenbaum, 2004), a representative non-linear embedding approach, and Binary Encoding (Han et al., 2011), an efficient categorical data embedding technique. We also include the variant of PTR constructed on the first half of the path table (see Section 5.3), denoted by PTR-half. Considering the complexity of PCA and MDS, we conduct experiments on sampled KOSARAK (sample ratio of $5\%$). We report the representation construction time of each method and the query answering time using the resulting partitioning results for $k$NN query ($k=10$) and range query ($\delta=0.7$) in Figure 8; similar trends are observed on other datasets and queries.

As can be observed from Figure 8, compared with PCA and MDS, PTR incurs much lower embedding time (10 to 20,000 times faster) while results in similar search time; compared with Binary Encoding and PTR-half, PTR leads to faster query answering with comparable embedding cost. Binary Encoding assigns unique representations to different sets without considering set characteristics (e.g., tokens contained therein), and thus can hardly achieve any Set Separation-Friendly Property. PTR-half, as discussed in Section 5.3, suffers from the risk that different sets may have common representations, and consequently these (dissimilar) sets are partitioned into the same group as they are not separable in the representation space, and the resulting search time thus is slightly longer than that of PTR. The major advantage of PTR is that it integrates the Set Separation-Friendly Property introduced in Section 5.3 into set representations by allowing sets consisting of different tokens to be easily separable by axis-aligned hyper-planes in the embedding space, and thus eases the training of the downstream Siamese networks.

We compare the learning-based partitioning approach, L2P, to the algorithmic methods introduced in Section 4.3, namely the graph cut-based method (PAR-G), centroid-based method (PAR-C), divisive clustering method (PAR-D), and agglomerative clustering method (PAR-A), in terms of partitioning cost, including time cost and space cost, and query answering time.

For PAR-G, we adopt PaToH (Çatalyürek and Aykanat, 2011), a graph partitioning tool known to be efficient and performing well, to cut the graph. We report the cost of different methods in partitioning KOSARAK into 1024 groups and the query answering time for $k$NN with $k=10$ in Figure 9; similar trends are observed on other datasets and queries. Note that the partitioning time of L2P includes model training time and inference time (the time required to assign a set into a group), and the partitioning time of PAR-G consists of the $k$NN graph construction time and the graph cut time. PAR-G is specially optimized for $k=10$ and the construction of its $k$NN graph is accelerated by $\mathsf{LES}^{3}$.

As depicted in Figure 9, L2P provides the fastest search while only incurs a small fraction of partitioning time and space cost compared to competitors (saving $80\%$ partitioning time and $99\%$ space compared with PAR-G). The reason why L2P incurs less partitioning time and space overhead is that, as described in Section 5.1 and Section 7.1, by training the models on a small portion of data, L2P is better positioned to approach the optimal partitioning where the $GPO$ is minimized, while other techniques work on the entire dataset and require (sometimes repetitively) computing the $GPO$ of arbitrary groups (or pairs) of sets. Besides, only model parameters and the training samples in a mini batch have to be saved in memory for L2P, with minimal storage overhead, while other techniques require materializing a large amount of intermediate partitioning results (and the entire $k$NN graph for PAR-G) in memory, incurring prohibitive space consumption.

By directly optimizing the $GPO$ which integrates the two desired properties of a partitioning with higher pruning efficiency, L2P is able to outperform PAR-G, the objective of which is minimizing the number of edges in the similarity graph crossing different sub-graphs rather than $GPO$. PAR-C, PAR-D, and PAR-A, although also aim to optimize the $GPO$, suffer from severe local optimality problems: a set is moved to a group only if such movement reduces the overall $GPO$, while in many cases movements temporarily increasing the $GPO$ must be allowed to determine a global optimum. For example, let $S_{i}\in\mathcal{G}_{i}$, $S_{j}\in\mathcal{G}_{j}$ be two sets. Assume that moving $S_{i}$ to $\mathcal{G}_{j}$ and moving $S_{j}$ to $\mathcal{G}_{i}$ when individually carried out both increase the $GPO$, and consequently $S_{i}$ remains in $\mathcal{G}_{j}$ and $S_{j}$ in $\mathcal{G}_{i}$. However, swapping $S_{i}$ and $S_{j}$ may reduce the overall $GPO$ and thus leads to better partitioning. Such swapping cannot be achieved based on the strategy followed by PAR-C and PAR-D. Similarly, the strategy of PAR-A does not allow the merge of groups temporarily increasing the overall $GPO$, which however may be necessary in identifying a global optimum.

We test the performance of $\mathsf{LES}^{3}$   in terms of query processing time on $k$NN queries, varying the number of groups $n$ and the result size $k$. The results are presented in Figure 10.

Increasing $n$ accelerates query answering, regardless of the result size. This is because with more groups, as indicated by Equation (13), the overall pruning efficiency of $\mathsf{LES}^{3}$ can be improved, meaning fewer candidates have to be checked. Increasing $n$ benefits search time up to a point. In particular we observe a diminishing return behavior with respect to search performance as $n$ increases further. The reason is that, with a sufficiently large number of groups, sets are already well-separated, and further increasing $n$ brings no significant change to the pruning efficiency but incurs higher index (TGM) scan cost. Moreover, search time increases for larger $k$, which is consistent with our analysis in Equation (LABEL:eq:range-ub-analysis), as in general a larger $k$ in $k$NN search is analogous to a smaller $\delta$ in range search and thus the pruning efficiency is lower.

While determining the optimal number of groups for partitioning is a known NP-hard problem (James et al., 2013), we empirically observe from the experiments that setting the number of groups at approximately $0.5\%|\mathcal{D}|$ leads to the lowest search time, where $|\mathcal{D}|$ is the number of sets in the corresponding dataset.

In this section, we compare $\mathsf{LES}^{3}$ with existing set similarity search approaches to answering $k$NN and range queries in memory-based and disk-based settings respectively. Among tree-based set similarity search approaches to date, DualTrans (Zhang et al., 2020) provides the fastest query processing. For inverted index-based methods, we adopt the method proposed in (Wang et al., 2019) (denoted by InvIdx), which yields the state-of-the-art performance for set similarity join tasks. Note that we exclude methods requiring index construction during query time (Deng et al., 2018; Xiao et al., 2011; Deng et al., 2015) as the index construction cost is much higher than the query cost. Since inverted index-based methods are designed for range queries and do not naturally support $k$NN queries, we modify the query answering algorithm of InvIdx for $k$NN queries as follows. (1) Given a query set $Q$ and a result size $k$, start with threshold $\delta=1.0$ and use InvIdx to find candidate sets from $\mathcal{D}$ whose similarity with $Q$ exceeds $\delta$, denoted by $\mathcal{C}$. (2) Identify the temporary $k$NN results from $\mathcal{C}$, denoted by $\mathcal{R}_{k}$. If the minimal similarity between any set in $\mathcal{R}_{k}$ and $Q$ exceeds $\delta$, terminate. Otherwise, decrease $\delta$ by $z$, use InvIdx to find candidates sets with the new $\delta$, update $\mathcal{C}$ accordingly, and repeat the step. (3) Upon termination, $\mathcal{R}_{k}$ is guaranteed to be the $k$NN to $Q$, as the similarity between any sets in $\mathcal{D}\setminus\mathcal{C}$ and $Q$ does not exceed the current $\delta$. The value of $z$ is tuned for faster query answering.

In addition, we also include a brute-force approach, i.e., computing the similarity between the query set and all other sets to derive the results, for completeness of comparison.

In Figure 11, we show the index size and index construction time for all methods. It is clear that the indexing structure of $\mathsf{LES}^{3}$, namely TGM, is much more lightweight, requiring up to $90\%$ less space than DualTrans and InvIdx. The major time cost of constructing TGM comes from the model training, which however is a preprocessing step incurring only a one-time cost and can be further reduced as discussed in Section 7.2.

In Figure 12 we compare the performance of the four methods in a memory-based setting. We observe that $\mathsf{LES}^{3}$ outperforms competitors for both $k$NN queries and range queries, accelerating the query answering by 2 to 20 times. DualTrans incurs longer search time as it uses an R-tree to organize all sets, with each set being represented with a $d$-dimensional vector ($d$ can be tuned for faster pruning). When the value of $d$ is small, sets containing different tokens cannot be clearly separated based on their representations, while when the value of $d$ is large, using R-tree to organize the vectors incurs high overlap between the bounding boxes of nodes on the R-tree, as previous research indicates (Indyk and Motwani, 1998). Besides, scanning the R-tree is expensive, which is not worthwhile considering that set similarity (e.g., Jaccard similarity) can usually be computed efficiently. While InvIdx provides comparable performance with $\mathsf{LES}^{3}$ for range queries with large $\delta$, it incurs greater search latency for $k$NN queries, especially when the average set size is large (e.g., on KOSARAK and LIVEJ). The reason is that, with InvIdx filtering operations need to be repeated for each candidate set (or multiple candidates with some common characteristics), and larger set size and $k$NN queries both enlarge the number of candidates, leading to sub-par query performance.

In contrast, we use TGM to compute the upper bounds between a query set and a group of sets; obtaining all bounds requires only $O(|S|*|\mathcal{G}|)$ time, which is relatively cheap. Although the search time of $\mathsf{LES}^{3}$ increases for range query as $\delta$ decreases, $\mathsf{LES}^{3}$ provide much faster query answering under a wide range of $\delta$.

We compare the performance of the four methods in the disk-based setting in Figure 13. Note that for DualTrans and InvIdx, only the part of the index that is necessary to the query answering, such as R-nodes on the search path and inverted indexes related to the query set, is retrieved into memory to reduce I/O cost. We observe that $\mathsf{LES}^{3}$ generally provides faster search compared with competitors, accelerating the query answering by 2 to 10 times. The reasons why $\mathsf{LES}^{3}$ incurs lower search time are: (1) Sets sharing no or very few common tokens with the query set can be easily pruned without being retrieved into memory; and (2) Since sets in the same group are checked jointly during the searching process; materializing a group of sets continuously on disk minimizes the data transfer delay. DualTrans and InvIdx, on the contrary, incur longer search latency and are outperformed by the Brute-force method for a wide range of $k$ and $\delta$. Besides the drawbacks discussed above in the memory-based setting, the search strategies of DualTrans and InvIdx incur repetitive retrieval of data with random disk access, which results in higher I/O cost (more pages retrieved, higher seek and rotation overhead, etc.), making them less efficient in the disk-based setting.

We evaluate the performance of TGM and HTGM to determine whether building a hierarchical index pays off. Intuitively, whether it benefits the query processing largely depends on the similarity distribution. For example, in cases where very few sets share common tokens, one can prune a large number of candidates using the matrices at the first few levels of HTGM, avoiding scanning the larger matrices at finer levels. However, in cases where most sets are similar, the small matrices at the first few levels of HTGM may provide no pruning efficiency at all. We assume that the similarity between sets in $\mathcal{D}$ can be modeled by a power-law distribution $P[sim=v]\sim v^{-\alpha}$, where $P[sim=v]$ denotes the probability that the similarity between any two sets is $v$, $v\in[0,1]$, $\alpha\in[1,\infty)$. We generate multiple synthetic databases consisting of 20,000 sets and 20,000 tokens each, by varying the value of $\alpha$. We train a cascade model with 9 levels (including level 0). We use the partitioning results at level 8 (256 groups) to build the TGM, and use the partitioning results at level 5 (32 groups) and level 8 to build the HTGM. We compare HTGM and TGM from two aspects. First, the index access cost, measured by the number of columns in the HTGM or TGM that are checked when processing the query. Second, the computational cost, measured by the number of similarity calculations. We measure the ratio of cost between HTGM and TGM, and the results are shown in Figure 14. It is evident that HTGM outperforms TGM when the value of $\alpha$ is large, i.e., most sets are dissimilar. This is in line with the discussions in Section 7.7.

We evaluate the performance of the proposed approach under updates. Two cases are considered: (1) closed universe, meaning the new sets to be inserted contain only tokens from the original database, and (2) open universe, where the new sets may contain previously unseen tokens. Let $\mathcal{D}$ be the original database, $\mathcal{D}^{closed}$ be the collection of new sets to be inserted under a closed universe, and $\mathcal{D}^{open}$ be the collection of new sets to be inserted under an open universes. For the experiment, we set insertion ratio ($|\mathcal{D}^{closed}|/|\mathcal{D}|$ and $|\mathcal{D}^{open}|/|\mathcal{D}|$) in range $[0,1]$, and half of the tokens in $\mathcal{D}^{open}$ are from $\mathcal{D}$ and half are new. We compute the decrease in pruning efficiency after insertion compared to obtaining a partitioning from scratch (namely running L2P) on $\mathcal{D}\cup\mathcal{D}^{closed}$ or $\mathcal{D}\cup\mathcal{D}^{open}$ (referred to as re-build). We give the results for $k$NN query with $k=10$ on KOSARAK in Figure 15; the experiments on the other datasets show similar trends.

Figure 15 depicts the percentage of pe reduction compared to re-build. The pruning efficiency decreases slightly as more new sets are inserted into the database. Insertions under an open universe have a higher impact on performance. The reason is that the tokens from the same universe mainly follow a similar distribution and the partition results obtained on the original data are still sufficient, while there is no prior knowledge regarding the distribution of new tokens. We observe, however, that the overall pruning efficiency is resistant to insertions (experiencing a decrease by at most $8\%$), which attests to the robustness of the proposed approach.