In a wide spectrum of real-world applications such as social network analysis [7,25], friend recommendation [4,15,17], and community search/detection [9,28,29], a set intersection problem, which obtains common elements between any two sets, has been one of the most fundamental and important operators in graph algorithms/tasks such as the triangle counting [8,27], maximal clique enumeration [5], and subgraph listing [24,30].
Below, we give a motivation example of the friend recommendation in social networks.
Example 1.1 (Friend Recommendation in Social Networks). Consider an example of social network, 𝐺, in Figure 1, where each vertex is a user and each edge between two vertices indicates the friend relationship between the two users. One important function on the social network platform (e.g., Twitter or Facebook) is to help users find and connect their friends. Intuitively, if two users have many common friends on social networks, they are more likely to know each other in reality. Therefore, in this case, we need to obtain a set of common friends between these two users and recommend them to add each other as friends (if this set is large).
Figure 1 illustrates two users 𝑢 1 and 𝑢 2 who are not connected in social network 𝐺, where their 1hop neighbor sets are given by N (𝑢 1 ) = {𝑣 3 , 𝑣 4 , 𝑣 5 , 𝑣 7 , 𝑣 9 , 𝑣 22 } and N (𝑢 2 ) = {𝑣 3 , 𝑣 10 , 𝑣 11 , 𝑣 17 , 𝑣 18 , 𝑣 24 }, respectively. To find their common friends, we need to conduct the set intersection operator, N (𝑢 1 ) ∩ N (𝑢 2 ), between their 1-hop neighbor sets, and obtain common friends (i.e., {𝑣 3 } in this example). ■
Due to the large scale of social networks 𝐺 in Example 1, in the worst case, there are quadratic pairs of user vertices (or set intersections) that need to be checked. Therefore, it is rather important, yet challenging, to optimize the cost of performing each set intersection operator, which inspires our work in this paper.
Existing works on the set intersection [14,16,23] follows a widely-used framework, the merge intersection, which assumes two sorted sets 𝐴 and 𝐵 (w.l.o.g. in the ascending order) and scans to merge both lists at the same time. The time complexity of this merge intersection method is O (|𝐴| + |𝐵|) in the worst case, where |𝐴| and |𝐵| are the numbers of elements in 𝐴 and 𝐵, respectively. Another classic approach to perform the set intersection is the galloping search [10]. Let us assume that |𝐴| < |𝐵|. For each element 𝑢 in 𝐴, the galloping search determines whether 𝑢 is contained in 𝐵 by using a binary search. The time complexity of this method is O (|𝐴| log |𝐵|), thereby it is more efficient when |𝐴| ≪ |𝐵| holds.
A bunch of algorithms have been developed powered by SIMD [1,14,16]. For example, QFilter [14] improves the merge intersection by leveraging the SIMD instructions and a proposed bytechecking filter. However, due to the variability in available SIMD support across different processor architectures, the SIMD instruction sets are architecture-specific, leading to the inconvenience of implementing algorithms. In the worst-case scenario, some processors may not have SIMD instructions at all, making the SIMD-based algorithms even unable to work. Recently, a reducingmerging framework [31] has been devised to enhance the performance of merge intersection. The basic idea is to reduce the input sets as much as possible before conducting intersection. The corresponding time cost is O (log |𝐴| +log |𝐵| + |𝐴 ′ | + |𝐵 ′ |), where 𝐴 ′ and 𝐵 ′ refer to subsets retrieved from 𝐴 and 𝐵 with range code reduction, respectively. The reducing-merging framework highly depends on the reducing performance, however, it remains an open problem to maximize the reducing ability.
Although advanced techniques such as SIMD [14] and set reduction [31] have been proposed to boost the set intersection task, they all take merge intersection or galloping-search paradigms as the backbone. In contrast, we focus on the following question: Can we develop a novel and more powerful framework to make set intersections on graphs even faster in practice?
In order to speed up the intersection 𝐴 ∩ 𝐵 between two sets 𝐴 and 𝐵, in this paper, we design a novel multi-level set intersection framework, namely hierarchical set partitioning and join (HERO), which consists of offline set decomposition and online set intersection stages. The intuition behind our HERO framework is to decompose the task of the set intersection into several intersection subtasks with smaller subsets and avoid the computation cost if one of the two subsets to intersect in subtasks is empty.
Specifically, in the offline set decomposition phase, we divide the universal set into disjoint partitions and project each set 𝐴 (or 𝐵) onto these partitions (called set partitioning), leading to projected subsets. Then, we take the IDs of non-empty (projected) subsets and form a new partition ID set. We recursively project this new partition ID set into partition ID subsets. This way, we can offline build a hierarchical structure of (element or partition ID) subsets for the original set 𝐴 (or 𝐵).
In the online set intersection phase, we will start from the top of the hierarchical structures for sets 𝐴 and 𝐵 to perform the join over partition ID sets (called partition ID join). Then, we can traverse hierarchical structures of 𝐴 and 𝐵 to the next-level (sub)set intersection, based on the partition IDs in the join results, in a recursive top-down manner.
Under the HERO framework, we also propose an effective index, namely set intersection bitmap tree (SIB-tree) for the set intersection in the graph. We notice that the bitwise operators, supported by most computers, enable bit-level parallel comparisons, implying a great potential to accelerate the set intersection task. To the end, it is necessary to represent each set using a bitmap where each bit denotes whether or not a vertex appears in the set. However, maintaining bitmaps for sets of neighbors for all the vertices results in the overhead O (|𝑉 | 2 ), which is impractical for large-scale graphs. Moreover, due to the size limit of an operand register (namely word length), the bitwise operators (such as boolean AND operation) on over-width bitmaps cannot be completed by a single instruction. To handle the problems, we construct the SIB-tree, that is, plugging the bitwise operators into the HERO framework by decomposing the original set intersection into small-sized subtasks such that each subtask can be efficiently solved by a single instruction. The SIB-tree can facilitate the multi-level set intersection efficiently.
In fact, many different SIB-trees can be built based on distinct set partitionings, and thus affect the intersection performance. We find that any particular set partitioning can be achieved by applying the graph reorder technique. Therefore, we formulate a novel graph reordering task and develop an efficient heuristic algorithm to optimize the performance of our proposed HERO approach, by minimizing the total size of the SIB-tree for all vertices in the graph.
In summary, we make the following contributions in this paper.
(1) A novel set intersection framework: We propose a novel hierarchical set partitioning and join (HERO) framework in Section 3 that decomposes the set intersection task into small-sized subtasks and filters out unnecessary comparisons. (2) A well-designed index for the set intersection: We build an effective set intersection bitmap tree (SIB-tree) index for set intersection in the graph in Section 4, which can support efficient accomplishment of (sub)set intersection (sub)tasks via boolean AND operations over bitmaps. (3) Graph ordering optimization: We formulate a novel graph reordering problem and propose a heuristic algorithm to optimize the performance of the proposed HERO approach in Section 5. (4) Remarkable empirical studies: We have conducted extensive experiments in Section 6 to evaluate the proposed HERO approach. The results show that the speedup of our approach over the classic merge intersection achieves up to 188x and 176x for triangle counting and maximal clique enumeration, respectively.
In this section, we formally define several concepts used for the set intersection problem.
Set Over the Graph. A graph is denoted as 𝐺 = (𝑉 , 𝐸), where 𝑉 and 𝐸 represent the sets of vertices and edges, respectively. We define a (vertex) set in the graph 𝐺 below.
Definition 2.1 (Set in the Graph). Given a graph 𝐺 = (𝑉 , 𝐸), a set 𝐴 in the graph refers to a subset of 𝑉 , i.e., 𝐴 ⊆ 𝑉 . One example of the set 𝐴 in graph 𝐺 can be a set of neighbors of a vertex 𝑢 ∈ 𝑉 . In this paper, we assume that each vertex 𝑢 is assigned with a unique integer ID, and all vertices in a set 𝐴 in graph 𝐺 are sorted (e.g., in ascending order). Set Intersection Problem. Next, we define the set intersection over the graph as follows.
Definition 2.2 (Set Intersection in the Graph). Given two sets 𝐴 and 𝐵 in the graph 𝐺, the set intersection task returns a set, 𝐴 ∩ 𝐵, of common vertices between two sets 𝐴 and 𝐵, i.e., 𝐴
As discussed above, two classical methods, merge intersection and galloping search, can be used to handle the set intersection problem in graphs. However, they often fail to fully leverage the intrinsic relationships among vertices, which can be improved. For instance, the merge intersection often involves unnecessary comparisons, leading to inefficiency. Furthermore, due to the limitation of comparing only one pair of elements per machine instruction, they are unable to fully exploit parallel advantages offered by bit-level computations. To address these limitations, we develop a novel HERO framework, which effectively filters out unnecessary comparisons and seamlessly integrates efficient boolean AND operations.
In Section 3.1, we introduce a two-level intersection method that decomposes set intersection into two subtasks of intersection to be performed in two stages. We then expand the two-level method to a multi-level intersection framework by recursively abstracting set intersection to a higher-level task in Section 3.2.
Set Partitioning: Let 𝑆 be a universal set that contains all possible elements in the domain of set elements (e.g., all the vertex IDs in the graph). Given a positive integer 𝑛, our two-level set partitioning and join approach partitions the universal set 𝑆 into 𝑛 disjoint subsets 𝑆 1 , 𝑆 2 , . . . , and 𝑆 𝑛 . We also call such subsets, 𝑆 𝑖 , space partitions of the set 𝑆, where 𝑖 is the partition ID of the subset 𝑆 𝑖 . Definition 3.1 (Subset Projection). Given a set 𝐴 ⊆ 𝑆 and a subset 𝑆 𝑖 of 𝑆, the subset projection, 𝐴 𝑖 , of 𝐴 over 𝑆 𝑖 contains common vertices between 𝐴 and 𝑆 𝑖 , i.e., 𝐴 𝑖 = 𝐴 ∩ 𝑆 𝑖 .
Problem Reduction Based on the Set Partitioning: Given any two sets 𝐴 ⊆ 𝑆 and 𝐵 ⊆ 𝑆 to be intersected, it holds that:
where 𝐴 𝑖 and 𝐵 𝑖 (for 1 ≤ 𝑖 ≤ 𝑛) are the subsets projected from 𝐴 and 𝐵 onto the partition 𝑆 𝑖 , respectively, that is, 𝐴 𝑖 = 𝐴 ∩ 𝑆 𝑖 and 𝐵 𝑖 = 𝐵 ∩ 𝑆 𝑖 . Note that, when 𝐴 𝑖 = ∅ or 𝐵 𝑖 = ∅ holds, we have 𝐴 𝑖 ∩ 𝐵 𝑖 = ∅. Therefore, in this case, we can actually avoid the set intersection cost of the 𝑖-th subtask 𝐴 𝑖 ∩ 𝐵 𝑖 , if either 𝐴 𝑖 or 𝐵 𝑖 is empty. Partition ID Join: Based on the observation above, we can record whether or not subsets 𝐴 𝑖 (or 𝐵 𝑖 ) are empty, by keeping their partition IDs 𝑖 in a so-called support set defined below (i.e., partition ID set) Sup 𝐴 (or Sup 𝐵 ) if 𝐴 𝑖 (or 𝐵 𝑖 ) are not empty. Then, we can join the two support sets Sup 𝐴 and Sup 𝐵 to obtain a list of subset pairs (or partition IDs) that need to perform the actual set intersection (i.e., subtasks).
Below we give the definition of the support set.
Definition 3.2 (Support Set). Given two sets 𝐴 and 𝐵 to be intersected, their support sets, Sup 𝐴 and Sup 𝐵 , over the space partition 𝑆 1 , 𝑆 2 , . . . , 𝑆 𝑛 of the universal set 𝑆 are defined as Sup 𝐴 = {𝑖 | 𝐴 𝑖 ≠ ∅, for 1 ≤ 𝑖 ≤ 𝑛} and Sup 𝐵 = {𝑖 | 𝐵 𝑖 ≠ ∅, for 1 ≤ 𝑖 ≤ 𝑛}, where 𝐴 𝑖 and 𝐵 𝑖 are subset projections for 𝐴 and 𝐵 over 𝑆 𝑖 , respectively.
Further Problem Reduction Based on the Partition ID Join: By using the concept of the support set (as given in Definition 3.2), we can rewrite the set intersection task in Equation (1) as:
Two-Level Intersection (Set Partitioning and Join): From Equation (2), we can: 1) first conduct the partition ID join, Sup 𝐴 ∩ Sup 𝐵 , over the two support sets (Level 2, partition ID join), and 2) then perform the set intersection, 𝐴 𝑖 ∩ 𝐵 𝑖 , only on those non-empty subsets 𝐴 𝑖 and 𝐵 𝑖 (Level 1, subset intersection), where partition IDs 𝑖 are in the join result Sup 𝐴 ∩ Sup 𝐵 . The above two steps exactly correspond to two levels of set intersection join, respectively. In summary, our principle is that the original task of the set intersection is decomposed into smaller subtasks of set intersections on two levels. We will later discuss in Section 3.2 how to generalize this principle to that of multiple levels in a hierarchical structure.
Example 3.3. Assume that we have a universal set 𝑆 = {𝑣 ∈ Z | 1 ≤ 𝑣 ≤ 27}, which can be partitioned into 9 disjoint subsets, 𝑆 1 ∼ 𝑆 9 , where
Given two sets 𝐴 = {1, 4, 5, 7, 9, 22} and 𝐵 = {1, 2, 10, 17, 18,24}, as shown in Figure 2(a), we first compute subset projections, 𝐴 𝑖 , of 𝐴 over 9 partitions 𝑆 𝑖 . That is, we have 𝐴 1 = {1}, 𝐴 2 = {4, 5}, 𝐴 3 = {7, 9}, and 𝐴 8 = {22} (note: other subsets 𝐴 𝑖 = ∅ for 𝑖 ≠ 1, 2, 3, 8). Similarly, for set 𝐵, we have non-empty subset projections 𝐵 1 = {1, 2}, 𝐵 4 = {10}, 𝐵 6 = {17, 18}, and 𝐵 8 = {24}.
Hence, the support set of 𝐴 is Sup 𝐴 = {1, 2, 3, 8}, whereas that of 𝐵 is Sup 𝐵 = {1, 4, 6, 8}.
In order to do the set intersection task 𝐴 ∩ 𝐵, as illustrated in Figure 2(b), we first compute the support set intersection Sup 𝐴 ∩ Sup 𝐵 = {1, 8} on the support set level (Level 2), and then perform the intersection of subsets for those partition IDs appearing in Sup 𝐴 ∩ Sup 𝐵 (i.e., 1-st and 8-th partitions), that is,
Superiority of Two-Level Set Partitioning and Join: We illustrate the superiority of the two-level set intersection join mentioned above, by using Example 3.3. Figure 3 shows the computation costs of merge intersection [12] and our two-level set intersection frameworks, where each line segment represents one comparison between two elements in the sets. We can see that our framework only takes 8 (=6+2) comparisons, which is lower than 10 comparisons of the merge intersection algorithm. This is because the set intersection over some partitions (e.g., Partitions 2, 3, 4, and 6) can be avoided, and thus their computation costs can be saved.
From Figure 3, we can see that the major cost of our two-level set partitioning and join is now on Level 2 (i.e., 6 out of 8). It inspires us to further reduce the cost on this support set level, by introducing hierarchical set partitioning and join in the next section.
In this section, we generalize our idea of set intersection partitioning and join (as mentioned in Section 3.1) from two levels to multiple levels in a hierarchical structure. Algorithm 1 shows our hierarchical set partitioning and join (HERO) framework for the set intersection operator. It has two stages, i.e., offline set decomposition (lines 1-8) and online set intersection stages (lines 9-13). Offline Set Decomposition: Given a set intersection task 𝐴∩𝐵, we consider an ℎ-level intersection framework. Specifically, similar to the two-level case discussed in Section 3.1, on Level 1, we decompose the universal set 𝑆 into 𝑛 1 disjoint partitions 𝑆 1 1 , 𝑆 1 2 , . . . , and 𝑆 1 𝑛 1 , and obtain projected subsets {𝐴 1 𝑖 } 𝑛 1 𝑖=1 and {𝐵 1 𝑖 } 𝑛 1 𝑖=1 from sets 𝐴 and 𝐵, respectively. For ease of presentation, we use the superscript to denote the level number.
Then, on Level 2, we maintain two support sets, Sup
1 𝐴 and Sup 1 𝐵 , containing partition IDs of nonempty projected subsets 𝐴 1 𝑖 and 𝐵 1 𝑖 . The universal set on this level becomes 𝑆 2 = { 𝑗 ∈ Z|1 ≤ 𝑗 ≤ 𝑛 1 }. In order to enable the intersection between support sets, Sup 1 𝐴 ∩ Sup 1 𝐵 , similar to Level 1, we recursively divide the new universal set into at most 𝑛 2 partitions 𝑆 2 1 , 𝑆 2 2 , ..., and 𝑆 2 𝑛 2 , and project Sup 1 𝐴 and Sup 1 𝐵 onto these partitions, leading to 𝐴 2 𝑖 and 𝐵 2 𝑖 , where
In general, on Level 𝑙 (2 < 𝑙 ≤ ℎ), we maintain two support sets Sup 𝑙 -1 𝐴 and Sup 𝑙 -1 𝐵 , containing partition IDs of non-empty projected subsets 𝐴 𝑙 -1 𝑖 and 𝐵 𝑙 -1 𝑖 . The universal set in this level should be 𝑆 𝑙 = { 𝑗 ∈ Z|1 ≤ 𝑗 ≤ 𝑛 𝑙 -1 } and we divide it into 𝑛 𝑙 partitions 𝑆 𝑙 1 , 𝑆 𝑙 2 , . . . , and 𝑆 𝑙 𝑛 𝑙 . The support sets Sup 𝑙 -1 𝐴 and Sup 𝑙 -1 𝐵 will be projected onto these partitions, leading to the projected subsets 𝐴 𝑙 𝑖 and 𝐵 𝑙 𝑖 , where
Online Set Intersection: In contrast to the offline set decomposition, the online set intersection operates following a top-down paradigm. Initially, 𝑅 ℎ is calculated directly by intersecting the two support sets, Sup ℎ 𝐴 ∩ Sup ℎ 𝐵 , (line 8). The filtering result 𝑅 𝑙 determines which subsets in the 𝑙-th level subtasks need to be joined, where 𝑙 ranges from ℎ to 1. That is, for any element 𝑖 in 𝑅 𝑙 , we Algorithm 1: The Hierarchical Set Partitioning and Join (HERO) Framework Input: a universal set 𝑆, set 𝐴, set 𝐵, and level ℎ Output: the intersection result 𝑅 = 𝐴 ∩ 𝐵 // offline set decomposition 1 Initialize 𝑆 1 as 𝑆, Sup 0 𝐴 as 𝐴, Sup 0 𝐵 as 𝐵
Details of the invoked procedure 12 Procedure Project(𝑋, {𝑍 𝑖 } 𝑛 𝑖=1 ) 13 for 𝑖 = 1 to 𝑛 do 14 𝑋 𝑖 ← 𝑍 𝑖 ∩ 𝑋 15 return {𝑋 𝑖 } 𝑛 𝑖=1 16 Procedure Join (𝑅, {𝑋 𝑖 } 𝑛 𝑖=1 , {𝑌 𝑖 } 𝑛 𝑖=1 ) 17 𝑅 ′ ← ∅ 18 for 𝑖 ∈ 𝑅 do 19 𝑅 ′ ← 𝑅 ′ ∪ Intersect(𝑋 𝑖 , 𝑌 𝑖 ) 20 return 𝑅 ′ .
need to solve the subtask Intersection(𝐴 𝑙 𝑖 , 𝐵 𝑙 𝑖 ) and add the results into 𝑅 𝑙 -1 , while other subtasks can be safely skipped (lines [17][18][19]. The above process also holds for 𝑙 = 1, where the 𝑅 𝑙 -1 (i.e., 𝑅 0 ) denotes result of 𝐴 ∩ 𝐵. The involved procedure Intersection(𝑋, 𝑌 ) is used to complete the subtask of computing the intersection between two sets 𝑋 and 𝑌 . Notice that any particular algorithm for set intersection, such as the merge intersection, can be applied.
Example 3.4. Following the settings of 𝑆, 𝐴, 𝐵, and the space partition of 𝑆 in Example 3.3, we can easily have the following results.
• Sup 1 𝐴 = {1, 2, 3, 8} and Sup 1 𝐵 = {1, 4, 6, 8};
, and 𝐵 1 𝑙 = ∅ for any 𝑙 ∉ Sup 1 𝐵 . To deal with the support set intersection of Sup 1 𝐴 and Sup 1 𝐵 , we define the 2nd level space partition as 𝑆 2 1 = {1, 2, 3}, 𝑆 2 2 = {4, 5, 6} and 𝑆 2 3 = {7, 8, 9}, where the new universal set is {𝑖 ∈ Z|1 ≤ 𝑖 ≤ 9}. Then, as illustrated in Figure 4(a), we project the support set Sup 1 𝐴 and Sup
1 𝐵 into the partitions, and the non-empty projections should be 𝐴 2 1 = {1, 2, 3}, 𝐴 2 3 = {8}, 𝐵 2 1 ={1}, 𝐵 2 2 = {4, 6} and 𝐵 2 3 = {8}. Correspondingly, the support set should be Sup 2 𝐴 = {1, 3} and Sup 2 𝐵 = {1, 2, 3}. With the above pre-computation, we can execute the multi-layer intersection as follows, which is also illustrated in Figure 4(b).
(1)
1 8 = {1}. ■ Time Complexity. The complexity of online set intersection in our HERO framework is highly related to a particular algorithm used in the subtask Intersection(•, •). Assume that the complexity of procedure Intersection(𝐴, 𝐵) is O (𝑓 (|𝐴|, |𝐵|)), where |𝐴| and |𝐵| are the size of sets 𝐴 and 𝐵, respectively. The complexity of hierarchical online set intersection comprises of the cost of all the subtasks involved, i.e., O ( ℎ 𝑙=1 𝑖 ∈𝑅 ℎ 𝑓 (|𝐴 𝑙 𝑖 |, |𝐵 𝑙 𝑖
In the HERO framework (as illustrated in Algorithm 1), one of the most fundamental and important operators is the subset intersections in subtasks (i.e., join two subsets to obtain their common elements). While we can plug in any existing set intersection method, in this paper, we use bitmap synopses to encode subsets and apply bit AND operator to enable the subset intersection.
Bitmap: Let 𝑑 be the size of the set element domain. We define the bitmap, 𝐵𝑀 (𝑍 ), for a subset 𝑍 as follows.
Definition 4.1 (Bitmap for a Subset, 𝐵𝑀 (𝑍 )). Given a set 𝑍 , a bitmap, 𝐵𝑀 (𝑍 ), of set 𝑍 is a bit vector containing 𝑑 bits. If there exists an element 𝑧 ∈ 𝑍 such that 𝑓 (𝑧) = 𝑝𝑜𝑠, then 𝐵𝑀 (𝑍 ) [𝑝𝑜𝑠] = 1 holds; otherwise, we have 𝐵𝑀 (𝑍 ) [𝑝𝑜𝑠] = 0, where 𝑓 (𝑧) is a hash function that maps an element 𝑧 to an integer 𝑝𝑜𝑠 within the range [0, 𝑑).
Boolean AND Over Bitmaps: Given two subsets 𝑋 𝑖 and 𝑌 𝑖 , we can obtain their intersection 𝑋 𝑖 ∩ 𝑌 𝑖 (i.e., subtask) by using Boolean AND over their bitmaps, that is, 𝐵𝑀 (𝑋 𝑖 ) ∧ 𝐵𝑀 (𝑌 𝑖 ). Then, we can obtain those non-zero bit positions, 𝑝𝑜𝑠, in the bitmap AND result, and their corresponding elements are common elements between subsets 𝑋 𝑖 and 𝑌 𝑖 . Discussions on the Advantages of Using Bitmaps for HERO:
Boolean AND operators are strictly constrained by the size of an operand register, also known as the word length. Thus, for the universal set 𝑆 of large size (i.e., large element domain size), it is not efficient to directly perform Boolean AND operators over bitmaps of large size 𝑑. Assuming the word length is 64 and the graph contains more than a million vertices, it implies that more than 10,000 words are needed to encode a set using bitmaps, which leads to costly boolean AND operations to conduct a set intersection task. There are several methods that adopt the bitmap, such as the compressed bitmap method Roaring [6] and the SIMD-based method QFilter [14]. However, these methods have to conduct merge operations that perform vertex-wise comparisons during the intersection procedure. In other words, the set intersection partially benefits from the advantage of bitmaps (i.e., supporting bit-wise parallel comparisons).
In contrast, our HERO framework recursively decomposes the set intersection task into smallsized subtasks, until each subtask can be efficiently handled by a single boolean AND instruction. Hence, our HERO is scalable for the intersection over sets of large domain sizes.
In this subsection, we discuss how to design a set intersection bitmap tree (SIB-tree) structure to facilitate our proposed HERO framework for the set intersection. Ordered Partitioning. Before introducing the details of the SIB-tree, we would like to unify the space partitioning in a natural way at first. To sufficiently leverage the advantage of the boolean AND operator, for subsets in varying-level space partitions, it is necessary to maintain a shared size of 𝑤 which refers to the machine's word length. Given a universal set 𝑆 𝑙 , it can be simply partitioned into
We call this partitioning strategy an ordered partitioning. Clearly, the ordered partitioning is sensitive to the element orderings, and we will discuss the impact of various orderings in Section 5.
Let us recall the offline set decomposition in the HERO framework. Subset projections are performed from the 𝑙-th level to ( 𝑗 + 1)-th level recursively. It naturally produces a tree structure, where each node represents a non-empty subset projection as shown in Figure 5. Following the tree, we can build an SIB-tree for each set to facilitate the boolean AND operation.
Definition 4.2 (Set Intersection Bitmap Tree, SIB-tree). Given a set 𝐴, its SIB-tree is denoted by 𝑇 (𝐴), where each node 𝑇 𝑙 𝑖 (𝐴) represents a non-empty subset projection 𝐴 𝑙 𝑖 in a bitmap format and contains two attributes: base value and bitmap value.
• The base value, denoted by 𝑇 𝑙 𝑖 (𝐴).base, is set to 𝑖, which implies that the elements of 𝐴 𝑙 𝑖 fall in the range (𝑤
• (𝑖 -1), 𝑤 • 𝑖]. • The bitmap value, denoted by 𝑇 𝑙 𝑖 (𝐴).𝑏𝑖𝑡, is a 𝑤-bit bitmap whose 𝑘-th bit indicates whether or not the element 𝑤 • (𝑖 -1) + 𝑘 is involved in 𝐴 𝑙 𝑖 . • The root node of the SIB-tree 𝑇 (𝐴) is 𝑇 ℎ 1 (𝐴), where ℎ = ⌈log 𝑤 |𝑆 |⌉. The ℎ-th level universal set 𝑆 ℎ has no more than 𝑤 elements, such that the corresponding ℎ-th level subtask can be solved by a single boolean AND instruction. • The nodes {𝑇 1 𝑖 (𝐴)} 𝑛 1 𝑖=1 constitute the leaf nodes. • For each node 𝑇 𝑙 𝑖 (𝐴), its child nodes are {𝑇 𝑙 -1 𝑢 (𝐴)} 𝑢 ∈𝐴 𝑙 𝑖 . It is clear that the 𝑙-th layer nodes of the SIB-tree 𝑇 (𝐴) represent the 𝑙-th level non-empty subset projections {𝐴 𝑙 𝑖 } 𝑖 ∈Sup 𝑙 𝐴
. Furthermore, the base value of a node tells which subset projection it represents in the corresponding level. Therefore, according to the HERO framework, the boolean AND operators only occur between nodes from two SIB-trees that locate on the same level and share the same base value.
Example 4.3. We follow the setting of 𝑆, 𝐴, 𝐵, and the space partition of 𝑆 in Example 3.4. We first consider the bottom layer of 𝑇 (𝐴). According to the Example 3.4, the non-empty 1st-level subset projections of 𝐴 are 𝐴 1 1 = {1}, 𝐴 1 2 = {4, 5}, 𝐴 1 3 = {7, 9}, 𝐴 1 8 = {22}. Hence, there are 4 nodes 𝑇 1 1 (𝐴), 𝑇 1 2 (𝐴), 𝑇 1 3 (𝐴), and 𝑇 1 8 (𝐴) in the bottom layer of 𝑇 (𝐴). The corresponding pairs of base value and bitmap value are (1, 001), (2, 011), (3, 101), and (8, 001), respectively. We then consider the 2nd layer. The non-empty 2nd-level subset projections of 𝐴 are 𝐴 2 1 = {1, 2, 3}, and 𝐴 2 3 = {8}. Thus, the 2nd layer nodes are 𝑇 2 1 (𝐴) and 𝑇 2 3 (𝐴), together with the pairs of base value and bitmap value
(1, 111), and (3, 010), respectively. The 3rd level has only one subset projection 𝐴 3 1 = {1, 3}, which refers to the root node 𝑇 3 1 (𝐴) with the base and bitmap value (1, 101). We deliver an illustration of 𝑇 (𝐴) in Figure 5(a). The construction of 𝑇 (𝐵) is similar, so we skip the description and just show its illustration in Figure 5(b). ■ SIB-Tree Construction: Given a set 𝐴, we construct 𝑇 (𝐴) in a bottom-up manner, progressing layer by layer. To construct the lowest layer (leaf nodes) of 𝑇 (𝐴), it is necessary to compute subset projections 𝐴 1 𝑖 = 𝐴 ∩ 𝑆 1 𝑖 , where 𝑖 ranges from 1 to 𝑛 1 . For each non-empty subset projection 𝐴 1 𝑖 , a leaf node 𝑇 1 𝑖 (𝐴) should be generated based on the SIB-tree definition. To establish the 𝑙-th layer of 𝑇 (𝐴), where 2 ≤ 𝑗 ≤ 𝑑, we need to follow the subsequent steps.
(1) Collect the base value of the nodes in the ( 𝑗 -1)-th layer, where each node corresponds to a non-empty subset projection. Thus, all the base values in this layer constitute the support set Sup
𝑙 -1 𝐴 . (2) Project Sup 𝑙 -1 𝐴 into the 𝑙-th level space partitions {𝑆 𝑙 𝑖 } 𝑛 𝑙 𝑖=1 , leading to the subset projections {𝐴 𝑙 𝑖 } 𝑛 𝑙 𝑖=1 . (3) For each non-empty subset projection 𝐴 𝑙 𝑖 , a new node 𝑇 𝑙 𝑖 (𝐴) is created. For each 𝑒 ∈ 𝐴 𝑙 𝑖 , we set 𝑇 𝑙
𝑖 (𝐴) as the parent node of 𝑇 𝑙 -1 𝑒 (𝐴). Offline Complexity: For a wide range of graph analytics algorithms, the set intersection operations are conducted on the neighborhoods of several vertices. Therefore, we can construct an SIB-tree for the neighbors of each vertex during the offline stage. Since the total number of leaf nodes is no more than |𝐸|, and the height of the SIB-tree is bounded by O (log |𝐸|), the space complexity of such an offline computation is bounded by O (|𝐸| log |𝐸|). Furthermore, each SIB-tree node will be traversed at most once during the SIB-tree construction. Hence, the time complexity of the offline computation is also bounded by O (|𝐸| log |𝐸|).
Algorithm 2 shows how to calculate the set intersection using the SIB-tree structure in a depth-first manner. The algorithm employs a recursive approach, utilizing a helper function that takes a pair of vertices, denoted as (𝑣 𝑎 , 𝑣 𝑏 ), from 𝑇 (𝐴) and 𝑇 (𝐵) respectively, as input. These vertices share the same base value and depth (line 4).
Helper Function: The helper function first performs a boolean AND operation on the bitmap values of 𝑣 𝑎 and 𝑣 𝑏 (lines 5-6). Then, an iterator is created based on the shared base value of 𝑣 𝑎 and 𝑣 𝑏 , along with the result of the boolean AND operation (lines [15][16][17][18][19][20]. The subsequent steps depend on whether the input vertices 𝑣 𝑎 and 𝑣 𝑏 are leaf vertices. If they are, each element in the iterator is directly added to the intersection result (lines 8-9). However, if they are not leaf vertices, the helper function iterates through each element in the iterator. If the iterator is empty, it backtracks to the last uncompleted subtask. For each element, it identifies the child vertices of 𝑣 𝑎 and 𝑣 𝑏 (referred to as child 𝑎 and child 𝑏 , respectively) whose base value matches the given element from the iterator (lines 12-13). Finally, the helper function recursively executes itself with child 𝑎 and child 𝑏 as input parameters (line 14).
Iterator Function: A base value and a bitmap value actually encode a set given a word length 𝑤. This iterator function is used to enumerate the elements contained in the set it encodes. The process is depicted in Algorithm 2 (lines 15-20). More specifically, in each iteration, the minimum element contained in the encoded set is computed by line 18, and then the bitmap value is updated by setting the first "1" bit to "0" (line 19).
Auxiliary Functions: Algorithm 2 includes two functions that require further clarification. The first function is FindChildNode(•). It takes a vertex 𝑣 from the SIB-tree 𝑇 and a query 𝑝𝑜𝑠 as inputs.
Algorithm 2: SIB-Tree Based Intersection Input: 𝑇 (𝐴),𝑇 (𝐵), word length 𝑤, and tree height ℎ. Output: the result of intersection 𝑅 = 𝐴 ∩ 𝐵. 1 res ← ∅ 2 Helper (𝑇 ℎ 1 (𝐴),𝑇 ℎ 1 (𝐵), res) 3 return res 4 Function Helper(𝑣 𝑎 , 𝑣 𝑏 , res): 5 𝑏𝑖𝑡 𝑎 ← 𝑣 𝑎 .𝑏𝑖𝑡, 𝑏𝑖𝑡 𝑏 ← 𝑣 𝑏 .𝑏𝑖𝑡 6 𝑏𝑖𝑡 ← bit a & bit b 7 base ← 𝑣 𝑎 .base 8 if 𝑣 𝑎 and 𝑣 𝑏 are leaf vertices then 9 res.extend(Iterator(base, 𝑏𝑖𝑡, 𝑤)) 10 else 11 for 𝑖 in Iterator (base, 𝑏𝑖𝑡, 𝑤) do 12 child 𝑎 ←FindChildNode (𝑣 𝑎 , 𝑖) 13 child 𝑏 ←FindChildNode (𝑣 𝑏 , 𝑖) 14 Helper (child 𝑎 , child 𝑏 , res) 15 Function Iterator(base, 𝑏𝑖𝑡, 𝑤): It returns a child vertex of 𝑣 whose base value matches 𝑝𝑜𝑠. The specific implementation details of FindChildNode(•) are dependent on the structure of the SIB-tree. The second function is Ffs(•), which is the acronym for "Find First Significant". Taking a bitmap as the input, the Ffs(•) function finds its lowest significant bit (i.e., the first "1" bit) and returns the corresponding index. With the help of Ffs(•) function, we can construct an iterator to enumerate the elements contained in the set encoded by a base value and bitmap value pair as discussed above. The GCC compiler provides efficient implementations of Ffs(•), such as the __builtin_ffs(•) for 32-bit unsigned integers and the __builtin_ffsll(•) for 64-bit unsigned integers. Discussion on On-the-fly Intersection: If the sets for intersection are given on the fly, we have to construct the SIB-trees online. However, as long as the SIB-tree index is constructed, the subsequent intersection calculation can be accelerated. Especially, for the sets that are frequently involved in the intersection tasks, it will be beneficial if the corresponding SIB-trees are constructed.
Trade-off Between Online and Offline Computations. As mentioned in Section 4.2, we would like to construct SIB-trees for the neighbors of all vertices offline if it is allowed. However, if the offline computation resource (either time or space) is limited, there is an alternative to construct SIB-trees only for a subset of vertices. Intuitively, vertices that are frequently involved in the graph set intersection tasks are recommended to be selected.
Section 4.2 recursively partitions/projects (support) sets onto subsets (partition ID subsets) by using the ordered partitioning as the space partition. Different space partitioning/projections may lead to different subsets, which in turn result in distinct SIB-tree performance. We find that different orderings of graph vertices may lead to different space partitions. Therefore, our basic idea of the graph reordering is to assign each vertex in the data graph 𝐺 a new vertex ID, which equivalently reorders those vertices and obtains a better partitioning/projection strategy for the SIB-tree.
Example 5.1. We follow the settings of 𝑆, 𝐴, and 𝐵 in Example 3.4. The reorder rule is illustrated at the top of Figure 6. Each vertex in 𝑆 will be assigned a new ID, and the reordered set will be sorted according to the new IDs. Sets 𝐴 and 𝐵 are {1, 2, 3, 4, 5, 6} and {1, 7, 8, 9, 10, 11} after reordering, respectively. We also present the SIB-trees of reordered sets 𝐴 and 𝐵 in the Figure 6. The reordered SIB-trees of both sets 𝐴 and 𝐵 contain fewer tree nodes than the original SIB-trees in Figure 5 (4 v.s. 7, and 6 v.s. 8). Furthermore, the intersection task 𝐴 ∩ 𝐵 needs to handle only 3 subtasks based on new SIB-trees, which gains a significant improvement over the original order that has 5 subtasks.■ In fact, arbitrary partitioning can be exploited to build the SIB-tree only if it can produce equalsized partitions 𝑆 1 , 𝑆 2 , . . . , and 𝑆 𝑛 . Any such a partitioning can obtained by performing the graph reordering and ordered partitioning. More specifically, we derive the vertex ID assignment rule 𝜙 : Z → Z, where for each vertex 𝑢's ID 𝑢.𝐼 𝐷 ∈ 𝑆 𝑖 it holds that 𝜙 (𝑢) = 𝑤 • (𝑖 -1) + |{𝑣 ∈ 𝑆 𝑖 |𝑣 .𝐼 𝐷 ≤ 𝑢.𝐼𝐷 }|. We can find that {𝜙 (𝑣)|𝑣 ∈ 𝑆 𝑖 } = { 𝑗 ∈ Z|𝑤 • (𝑖 -1) < 𝑗 ≤ 𝑤 • 𝑖}. In other words, if we conduct the ordered partitioning according to new vertex IDs, the vertices contained in any 𝑆 𝑖 will still be contained in the same partition. Hence, the new partitioning results are equivalent to the original partitions.
In this section, we aim to develop a novel graph reordering method to optimize the performance of the proposed HERO approach. As discussed in Section 4.3, the time complexity of Algorithm 2 is bounded by the size of the SIB-tree as each vertex in the SIB-tree will be traversed at most once. Thus, the objective for the graph reordering task is to minimize the total size of the SIB-tree for all vertices 𝑣 in the graph 𝐺 = (𝑉 , 𝐸). This target serves as a starting point in our approach
1 2 4 5 7 9 10 17 18 22 24 1 7 2 3 4 5 8 9 10 6 11 111 000 000 000 000 000 000 110 000 000 100 1 3 1 2 1 1 2 1 000 000 000 000 000 000 100 110 000 110 1 3 1 2 1 1 4 1 5 1 000 2 2 111 001 111 011
SIB-tree of reordered set A SIB-tree of reordered set B
3 12 6 13 8 14 10 11 12 13 8 15 16 17 14 15 16 19 18 19 20 21 20 21 22 23 23 24 25 25 26 26 27 27 Original ID New ID Reordered set A = 1,2,3,4,5,6 Reordered set B = 1,7,8,9,10,11 and can be mathematically formulated as follows:
where |𝑇 (N (𝑣))| is the size of the SIB-tree 𝑇 (N (𝑣)). For simplicity, we would like to abbreviate 𝑇 (N (𝑣)) as 𝑇 (𝑣). Please note that the SIB-tree of the set which contains a single element 𝑣 is denoted as 𝑇 ({𝑣 }). Thus, the abbreviation will not lead to ambiguity.
Although we can consider different graph orders that lead to distinct SIB-trees and different intersection performance, it is computationally expensive to determine the optimal graph order (e.g., if we construct an SIB-tree for each graph order). To address this problem, we propose a hierarchical balanced graph partitioning (HBGP) strategy, which helps us compute the size of the SIB-tree index without constructing it. Next, we first introduce the definition of HBGP in Section 5.1. Then, we will describe how to compute the size of the SIB-tree index through HBGP, followed by the hardness analysis in Section 5.2. Finally, we develop an efficient heuristic algorithm to solve the HBGP problem in Section 5.3.
Balanced Graph Partitioning: Given a graph 𝐺 = (𝑉 , 𝐸) and an integer 𝑛, the classical balanced graph partitioning (BGP) problem asks to split the vertices 𝑉 into 𝑛 disjoint and equal-sized subsets 𝑃 1 , . . . , 𝑃 𝑛 such that the edge cut is minimized, where the edge cut is the number of the edges whose two vertices belong to different subsets [2]. The BGP is known as an NP-complete problem [2].
In BGP, the optimization target is to minimize the number of crossing edges, which can be reformulated as:
By denoting the cost of a subset 𝑃 𝑖 as cost(𝑃 𝑖 ) =
Algorithm 3: General Greedy Paradigm for BGP Input: Graph 𝐺 = (𝑉 , 𝐸), number of partitions 𝑛 Output: The partition result P.
12 return P we can rewrite the cost function of BGP as a general form
where P = {𝑃 1 , . . . , 𝑃 𝑛 }. Therefore, by defining different partitioning costs, it is easy to derive a wide class of generalized BGP. Note that we say the partitioning cost satisfies the locality if the cost of a partition is determined only by itself and is independent of other partitions, such that the cost of a partition can be computed during the construction procedure. Thus, the generalized BGP can be approximately solved by using a general greedy paradigm, as shown in Algorithm 3.
It sequentially constructs the subsets following the greedy heuristic. Each subset 𝑃 𝑖 is initialized as an empty set (line 2), and a candidate set 𝐶 is initialized as 𝑉 (line 3). The construction of each subset 𝑃 𝑖 is an iterative procedure (lines 5-11). In each iteration, a vertex in the candidate set 𝐶 is selected (line 9) and inserted into the subset (line 11), such that the cost of the subset after insertion is maximized. Meanwhile, the vertex will be removed from the candidate set 𝐶 once it has been selected (line 10).
Hierarchical Balanced Graph Partitioning: The graph partitioning problems above just divide the vertices through a unified granularity, however, it is required to partition the graph hierarchically in some cases. The hierarchy can be comprehended from two different perspectives. The first one is from top-down, that is, first dividing the graph into coarse-grained partitions and then dividing each partition into finer-grained partitions recursively. The second one is from bottom-up, that is, first dividing the graph into fine-grained partitions and then merging the partitions into coarser-grained partitions recursively. The partitioning result of HBGP is a balanced tree, where each node refers to a subset of the vertices, i.e., the union of the subsets referred to by its child nodes.
Definition 5.2 (Hierarchical Balanced graph partitioning problem, HBGP). Given a graph 𝐺 = (𝑉 , 𝐸) and a width parameter 𝑤, a ℎ-level HBGP aims at partitioning 𝑉 into ℎ groups of subsets
(2) For 𝑙 = 1 to ℎ, {𝑃
𝑙 𝑖 } 𝑛 𝑙 𝑖=1 is a group of disjoint subsets of |𝑉 |, where each subset 𝑃 𝑙 𝑖 has no more than 𝑤 • 𝑗 vertices. (3) For 𝑙 = 2 to ℎ, each subset in {𝑃 𝑙 𝑖 } 𝑛 𝑙 𝑖=1 is the union of 𝑤 subsets in {𝑃 𝑙 -1 𝑖 } 𝑛 𝑙 -1 𝑖=1 at most. (4) The total cost L (P) = ℎ 𝑙=1 𝑛 𝑙 𝑖=1 cost(𝑃 𝑙 𝑖 ) is minimized, where cost(𝑃 𝑙 𝑖 ) is defined as | 𝑢 ∈𝑃 𝑙 𝑖 N (𝑢)|. Similar to the BGP, it is convenient to represent a result of HBGP by reordering the graph. That is, for each subset 𝑃 𝑙 𝑖 , we always assign the ID of its vertices from 1 + 𝑤 𝑑+1-𝑗 • (𝑖 -1) to 𝑤 𝑑+1-𝑗 • 𝑖. 5.2 Computing SIB-Tree Size via HBGP Given a hierarchical partitioning P, we can build a bipartite graph B = (B 𝑙 , B 𝑟 , 𝐸 B ) as follows. For each vertex 𝑢 in 𝐺, it will be contained in the left part B 𝑙 . While for each subset 𝑃 𝑙 𝑖 in P, we abstract it as a vertex in the right part B 𝑟 . For each pair of vertices (𝑢, 𝑃 𝑙 𝑖 ), we add an edge between them if and only if the intersection of the corresponding subset 𝑃 𝑙 𝑖 and N (𝑢) is non-empty. Let 𝑇 𝑙 𝑖 (𝑢) ∈ 𝑇 (𝑢) denote that there exists a node in the 𝑙-th layer of SIB-tree 𝑇 (𝑢) such that its base value equals 𝑖. Lemma 5.3. Given a graph 𝐺 = (𝑉 , 𝐸), a hierarchical partitioning P and the corresponding bipartite graph 𝐴 = (B 𝑙 , B 𝑟 , 𝐸 B ), for each 𝑢 ∈ B 𝑙 and 𝑝 𝑙 𝑖 ∈ B 𝑟 , it holds that (𝑢, 𝑝 𝑙 𝑖 ) ∈ 𝐸 B if and only if 𝑇 𝑙 𝑖 (𝑢) ∈ 𝑇 (𝑢).
Proof. We just give a proof sketch of mathematical induction. For each 𝑇 𝑙 𝑖 (𝑢) ∈ 𝑇 (𝑢), the target is to prove that N (𝑢) contains at least one vertex in the 𝑃 𝑙 𝑖 . It is trivial for 𝑙 = 1. For the case 𝑙 ≥ 2, the key idea lies in that 𝑇 𝑙 𝑖 (𝑢) ∈ 𝑇 (𝑢) is equivalent to 𝑇 𝑙 -1 𝑖 ′ ∈ 𝑇 (𝑢) for at least one of the 𝑤 (𝑖 -1) < 𝑖 ′ ≤ 𝑤𝑖. Then, combining the proved case of 𝑙 -1, the correctness of case 𝑙 is achieved. □
Proof. The proof can be achieved by counting the edges in the bipartite graph B in two different ways, i.e., summing up the degrees of all vertices in the left and right parts. Lemma 5.3 implies that the sum of degrees of the left part equals L (𝐺). According to the definition of edges in B, the sum of degrees of the right part equals L (P). Hence, the theorem is proved. □ Theorem 5.4 implies that optimizing the graph ordering is as difficult as solving the HBGP problem. which is NP-hard as shown next.
Theorem 5.5. The hierarchical graph partitioning problem cannot be solved in polynomial time unless P = NP.
Proof. The proof can be achieved by reducing from the 3-partition problem, which is known as an NP-complete problem [13], to the HBGP problem. For each 3-partition problem instance 𝑃1, we can construct a corresponding HBGP instance 𝑃2. Then, determining whether 𝑃 1 has feasible solutions or not according to the solution of 𝑃2 will be given, and its correctness will be proved. In this way, we can prove that HBGP is not easier than the 3-partition problem, which implies that HBGP is NP. □ Due to space limitations, we will provide complete proofs of lemmas/theorems in a technical report after the paper publication (for the double-blind reason) and omit them here.
Since the hierarchical balanced graph partitioning problem is intractable, we propose an efficient greedy heuristic algorithm. Based on the HBGP definition, a naive heuristic idea is to divide the HBGP problem into several BGP problems and solve them orderly, either top-down or bottom-up. In this paper, we adopt the top-down heuristic. The reason behind this is that the top-down heuristic prioritizes minimizing the number of high-level nodes in the SIB-tree. Consequently, space pruning is more likely to occur at the high-level intersection subtasks. The pseudocode of the heuristic algorithm is outlined in Algorithm 4, where the cost function in Line 15 is defined as
For the procedure Reorder(left, right, 𝑤), we would like to store the set of candidate vertices 𝐶 in a heap. Hence, each greedy selection (Line 13 and Line 15 in Algorithm 4) equals popping an element from the heap. The time complexity of a pop operation is O (log |𝐶 |). However, for each vertex 𝑣 which is still in the heap, we need to update the cost(𝑃 ∪ {𝑣 }) according to the Equation ( 8) such that we can correctly pop the next element. The fact is that the update procedure dominates the time complexity of Algorithm 4. Consequently, we need to design an efficient way for the update. Consider line 15 in Algorithm 4, an equivalent way to make the greedy selection is computing the increment of the cost. That is, by denoting Δ(𝑣 |𝑃) = cost(𝑃 ∪ {𝑣 })cost(𝑃), we can easily in C++ and compiled by GCC v7.3.0 with -O3 option. Anonymous source code and data are available at: https:// anonymous.4open.science/ r/ HEROFramework-126E/ .
Following the previous research [31], we use two groups of query sets for global intersection and local intersection for each graph. The global intersection group contains 100, 00 pairs of randomly selected vertices to compute their common neighbors. The local intersection group contains 10, 000 pairs of randomly selected adjacent vertices to compute common neighbors. The results of global intersection and local intersection are presented in Figure 7 and Table 3. Speedup of our approach. To evaluate the performance of the proposed SIB method, we compare it with the merge intersection and three state-of-the-art algorithms, that is, the compressed bitmap method Roaring [6], the SIMD-based method QFilter [14], and the reducing-merging method Range [31]. We report the speedups compared to the merge intersection as shown in Figure 7, where the elapsed time of the merge intersection is taken as the baseline with speedup=1.0x. We find that the SIB method consistently outperforms three baselines on 8 of 10 graphs for both global intersection and local intersection tasks. Specifically, on the graph web-BerkStan, the SIB method achieves significant speedups, up to 181.00x and 83.33x on global and local intersection tasks, respectively. Averaged on 10 graphs, the SIB method accelerates the global and local intersection tasks by 26.50x and 16.17x, respectively. We show the running time of the merge intersection algorithm in Table 4 (the columns "GI" and "LI" refer to global and local intersections, respectively). The running time of other algorithms can be easily inferred through the corresponding speedups. The number of comparisons. Table 3 reports how many comparisons each intersection method demands on the global and local intersection tasks. For the merge intersection method, one comparison just refers to comparing a pair of vertices. For our proposed SIB method, one comparison refers to invoking the boolean AND operator once. Although the specific comparison operations are different, we find that there is a significant gap in the number of comparisons. For both global intersection and local intersection tasks, the merge intersection takes 10x-100x comparisons more than our proposed SIB, which may explain why the SIB method is much faster than the merge intersection method.
In this section, we evaluate the performance of SIB method through three graph algorithms, that is triangle counting (TC), maximal clique enumeration (MC), and subgraph listing (SL). For each task, we report the speedups compared with the merge intersection method, where the merge intersection is taken as the baseline with speedup= 1.0x.
In this section, we explore how different graph orderings benefit the SIB approach. In addition to the proposed ordering HBGP, we adopt 6 existing graph orderings, including the original order, BFSR [3], DFS [26], Hybrid [1], MLOGGAPA [11], and SlashBurn [22] as competitors, since they are often used for the graph set intersection in previous studies like QFilter [14] and Range [31].
We report the performance of the ordering through two metrics, that is, the size of the SIB-tree index and the speedup of SIB method on TC, MC, and SL algorithms. Note it is extremely expensive to enumerate MC on the whole graph, we enumerate MC on 1% vertices for each graph in this section.
Effect on the size of SIB-tree. The size information of the SIB-tree index is depicted in Figure 9(a). For simplicity of comparison, we scale the data by the size of the SIB-tree index in original order. We first consider the size of the SIB-tree index, which evaluates how well the ordering solves the graph reorder problem proposed in Section 5. As shown in Figure 9(a), our proposed HBGP-based ordering always constructs the SIB-tree index with minimal size among all the compared graph orderings. We also find that the performance of each order becomes pretty similar when the average degree of the graph is small. This phenomenon is intuitive because the small degree implies a corresponding small optimization space. Effect on the speedups. As for the speedups of three graph algorithms, we report each ordering's average speedup over 10 graphs in Table 6. For detailed speedup on each graph, the results are shown in Figures 9(b), 9(c), and 9(d), respectively. Since the final target of reordering the graph is to improve the performance of SIB method, we then focus on the speedups brought by different orderings. According to the average speedups shown in Table 6, our proposed HBGP-based ordering beats all the ordering baselines in the TC and MC tasks. As for the SL task, our proposed HBGP ordering performs second only to the MLOGGAPA ordering. More specifically, the HBGP-based ordering performs the best on all 10 graph datasets in the TC task. Similarly, except for the MLOGGAPA multi-level intersection framework using bitmap and boolean AND operation. Consequently, the intersection algorithm can totally get rid of the merge intersection framework.
Proc. ACM Manag. Data, Vol. 2, No. 1 (SIGMOD), Article 29. Publication date: February 2024.