Modern large-scale graph processing faces a critical challenge: conventional adjacency lists incur excessive L3 cache misses due to irregular memory access. We introduce GraphTwin, a hybrid graph representation system combining: (1) Cache-optimized k -bit vectors (termed GT-vectors, 64 bits per vertex), where each bit indicates vertex membership in a precomputed independent set; and (2) Memory-resident adjacency lists for exact verification of queries unresolved by GT-vectors. This dual-component design enables 95% of negative edge queries, which are dominant in sparse graphs, to be resolved in 1 CPU cycle via in-cache bitwise-AND operations, reducing latency from 54ns (adjacency list) to 18ns per query. Unresolved queries delegate to adjacency lists, guaranteeing zero false positives/negatives. Crucially, GT-vectors scales linearly with vertex count ( k|V| bits ), decoupling the space overhead from edge density and minimizing cache dependency. For example, GT-vectors for a graph with |V|=10 7 vertices occupy 80MB, fitting entirely within modern CPU caches (e.g., AMD Ryzen 7 9800X3D's 96MB L3). We formalize the GT-vectors construction as an NP-hard and submodular optimization problem and introduce GTWICE, a linear-time heuristic algorithm that iteratively extracts diversified maximal independent sets to maximize non-edge coverage. Experiments on 15 graphs show that GraphTwin reduces L3 cache misses by 63% on average, achieves 6.2× speedup for edge queries and accelerates triangle counting and set inclusion by 1.7× and 5.4×, respectively. By optimizing cache residency and accelerating foundational primitives, GraphTwin addresses cache inefficiencies in graph processing, enabling fast graph queries without sacrificing exactness.

Graphs have been widely used in many applications. One important graph analytics is to explore cohesive subgraphs in a large graph. Among several cohesive subgraphs studied,$k$-core is one that can be computed in linear time for a static graph. Since graphs are evolving in real applications, in this paper, we study core maintenance which is to reduce the computational cost to compute$k$-cores for a graph when graphs are updated from time to time dynamically. We identify drawbacks of the existing efficient algorithm, which needs a large search space to find the vertices that need to be updated, and has high overhead to maintain the index built, when a graph is updated. We propose a new order-based approach to maintain an order, called$k$-order, among vertices, while a graph is updated. Our new algorithm can significantly outperform the state-of-the-art algorithm up to 3 orders of magnitude for the 11 large real graphs tested. In addition, we also study the problem of partial core maintenance, which is to maintain the top-$t$cores of the graph for a given positive integer$t$. By instead maintaining only a small subset of cores, further improvement in performance can be obtained.

Computing the shortest path for any two given vertices is an important problem in road networks. Since real road networks are dynamically updated due to real-time traffic conditions and it is costly to recompute the oracle O in use from scratch, O needs to be updated to reflect the changes in the network using incremental algorithms. An incremental algorithm is said to be bounded if its cost is polynomial in |CHANGED|, where CHANGED comprises both the changes to the graph and the resulting changes to O. An incremental problem is bounded if it has a bounded algorithm and is unbounded otherwise. We study the boundedness of the incremental counterparts of two state-of-the-art oracles, namely contraction hierarchy (CH) and hierarchical 2-hop index (H2H). We prove that under specific computational models, both CH and H2H are unbounded to maintain. Despite this fact, we introduce relative subboundedness as an alternative to boundedness. We prove that the state-of-the-art incremental algorithm for CH is relatively subbounded, and moreover, we propose a relatively subbounded algorithm for H2H. Our experimental study on real road networks shows that the algorithms studied are faster than recomputing from scratch even when 10% of the index needs to be updated, thereby verifying the effectiveness of relative subboundedness.

In this paper, we study parallel query processing with a focus on reducing the communication cost, which is the dominating factor in parallel query processing. The communication cost becomes large if the intermediate results between operators are large in intra-operator parallelism. In the existing approaches, it optimizes an SQL query by arranging relational algebra operators to reduce the total cost, where, for each operator, it involves (i) distribution of data partitioned to computing nodes by communication, and (ii)computation on computing nodes locally. The communication and computation are dealt with inside an operator and are not separable. In other words, it is difficult to avoid large intermediate results and hence reduce the communication cost. To reduce communication cost, we separate communication from computation using several new operators proposed in this paper. One is a pair operator () to pair the partitions of a relation R with the partitions of a relation S, where a partition is specified by a hash function. With the pair operator defined, we can explicitly deal with communication to deliver pairs of partitions to computing nodes. Together with , we can also explicitly treat the local computation on a computing node as op for any RA (relational algebra) operator op. We give a merge operator (U), to collect all partial results from computing nodes as they are. In short, with , op, and U, we are able to explicitly specify communication and computation for RA operators. Furthermore, we propose new techniques, namely, partitioning push-down and computation push-up to separate communication from computation for RA expressions. We prove that we can push-down/up for a wide range of relational expressions. We have developed a distributed system named Secco (Separate Communication from Computation) by revamping SparkSQL on Spark, and confirmed the efficiency of our approach in our performance studies using real datasets.

Cliques refer to subgraphs in an undirected graph such that vertices in each subgraph are pairwise adjacent. The maximum clique problem, to find the clique with most vertices in a given graph, has been extensively studied. Besides its theoretical value as an NP-hard problem, the maximum clique problem is known to have direct applications in various fields, such as community search in social networks and social media, team formation in expert networks, gene expression and motif discovery in bioinformatics and anomaly detection in complex networks, revealing the structure and function of networks. However, algorithms designed for the maximum clique problem are expensive to deal with real-world networks. In this paper, we first devise a randomized algorithm for the maximum clique problem. Different from previous algorithms that search from each vertex one after another, our approachRMC, for the randomized maximum clique problem, employs a binary search while maintaining a lower bound$\underline{\omega _c}$and an upper bound$\overline{\omega _c}$of$\omega (G)$. In each iteration,RMCattempts to find a$\omega _t$-clique where$\omega _t=\lfloor (\underline{\omega _c}+\overline{\omega _c})/2\rfloor$. As finding$\omega _t$in each iteration is NP-complete, we extract a seed set$S$such that the problem of finding a$\omega _t$-clique in$G$is equivalent to finding a$\omega _t$-clique in$S$with probability guarantees ($\geq$$ 1-n^{-c}$). We propose a novel iterative algorithm to determine the maximum clique by searching a$k$-clique in$S$starting from$k=\underline{\omega _c}+1$until$S$becomes$\lbrace \rbrace$, when more iterations benefit marginally. Due to the potential inconsistency of maximum clique algorithms, we study the problem of maximum clique enumeration and propose an efficient algorithmRMCEto enumerate all maximum cliques in a given graph. As confirmed by the experiments, bothRMCandRMCEare much more efficient and robust than previous solutions,RMCcan always find the exact maximum clique, andRMCEcan always enumerate all maximum cliques in a given graph.

The notion of shortest path is fundamental in graph analytics. While many works have devoted to devising efficient distance oracles to compute the shortest distance between any vertices s and t, we study the problem of efficiently counting the number of shortest paths between s and t in light of its applications in tasks such as betweenness-related analysis. Specifically, we propose a hub labeling scheme based on hub pushing and discuss several graph reduction techniques to reduce the index size. Furthermore, we prove several theoretical results on the performance of the scheme for some special graph classes. Our empirical study verifies the efficiency and effectiveness of the algorithms. In particular, a query evaluation takes only hundreds of microseconds in average for graphs with up to hundreds of millions of edges. We report our findings in this paper.

Due to the ubiquity of graphs, graph analytics has attracted much attention from both research and industry communities. The notion of k-truss is widely used in graph analytics. Since graphs are continuously evolving in real applications and it is costly to compute trusses from scratch, we study the problem of truss maintenance which aims at designing efficient incremental algorithms to update trusses when graphs are updated with changes. An incremental algorithm is desired to be bounded; that is, its cost is of $O(f(\|\textttCHANGED \|_c))$ for some polynomial function f and some positive integer c, where $\textttCHANGED $ comprises the changes to both the graph and the result and $\|\textttCHANGED \|_c$ is the size of the c-hop neighborhood of $\textttCHANGED $. An incremental problem is bounded if it has a bounded incremental algorithm and is unbounded otherwise. Under the model of locally persistent algorithms, we prove that truss maintenance is bounded under edge removals but is unbounded even for unit edge insertions. To address the unboundedness, we formulate a new notion $\textttAFF ^\preceq$ which, as a practically effective alternative to $\textttCHANGED $, represents a set of edgesaffected by the changes to the graph, and devise an insertion algorithm that is bounded with respect to $\textttAFF ^\preceq$, while retaining the boundedness for edge removals. More specifically, our insertion algorithm runs in $O(f(\|\textttAFF ^\preceq\|_c))$ time for some polynomial function f and some positive integer c with $\|\textttAFF ^\preceq\|_c$ being the size of the c-hop neighborhood of $\textttAFF ^\preceq$. Our extensive performance studies show that our new algorithms can significantly outperform the state-of-the-art by up to 3 orders of magnitude for the 12 large real graphs tested and are more efficient than computing trusses from scratch even for changes of non-trivial size. We report our findings in this paper.

Finding the shortest path in road networks becomes one of important issues in location based services (LBS). The problem of finding the optimal meeting point for a group of users has also been well studied in existing works. In this paper, we investigate a new problem for two users. Each user has his/her own source and destination. However, whether to meet before going to their destinations is with some uncertainty. We model it as minimum path pair (MPP) query, which consists of two pairs of source and destination and a user-specified weight α to balance the two different needs. The result is a pair of paths connecting the two sources and destinations respectively, with minimal overall cost of the two paths and the shortest route between them. To solve MPP queries, we devise algorithms by enumerating node pairs. We adopt a location-based pruning strategy to reduce the number of node pairs for enumeration. An efficient algorithm based on point-to-point shortest path calculation is proposed to further improve query efficiency. We also give two fast approximate algorithms with approximation bounds. Extensive experiments are conducted to show the effectiveness and efficiency of our methods.

Graphs have been widely used in many applications such as social networks, collaboration networks, and biological networks. One important graph analytics is to explore cohesive subgraphs in a large graph. Among several cohesive subgraphs studied, k-core is one that can be computed in linear time for a static graph. Since graphs are evolving in real applications, in this paper, we study core maintenance which is to reduce the computational cost to compute k-cores for a graph when graphs are updated from time to time dynamically. We identify drawbacks of the existing efficient algorithm, which needs a large search space to find the vertices that need to be updated, and has high overhead to maintain the index built, when a graph is updated. We propose a new order-based approach to maintain an order, called k-order, among vertices, while a graph is updated. Our new algorithm can significantly outperform the state-of-theart algorithm up to 3 orders of magnitude for the 11 large real graphs tested. We report our findings in this paper.

Cliques refer to subgraphs in an undirected graph such that vertices in each subgraph are pairwise adjacent. The maximum clique problem, to find the clique with most vertices in a given graph, has been extensively studied. Besides its theoretical value as an NP-hard problem, the maximum clique problem is known to have direct applications in various fields, such as community search in social networks and social media, team formation in expert networks, gene expression and motif discovery in bioinformatics and anomaly detection in complex networks, revealing the structure and function of networks. However, algorithms designed for the maximum clique problem are expensive to deal with real-world networks. In this paper, we devise a randomized algorithm for the maximum clique problem. Different from previous algorithms that search from each vertex one after another, our approach RMC , for the randomized maximum clique problem, employs a binary search while maintaining a lower bound ω c and an upper bound [EQUATION] of ω ( G ). In each iteration, RMC attempts to find a ω t -clique where [EQUATION]. As finding ω t in each iteration is NP-complete, we extract a seed set S such that the problem of finding a ω t -clique in G is equivalent to finding a ω t -clique in S with probability guarantees (≥1− n −c ). We propose a novel iterative algorithm to determine the maximum clique by searching a k -clique in S starting from k = ω c +1 until S becomes [EQUATION], when more iterations benefit marginally. As confirmed by the experiments, our approach is much more efficient and robust than previous solutions and can always find the exact maximum clique.

Locality-Sensitive Hashing (LSH) and its variants are the well-known indexing schemes for the c -Approximate Nearest Neighbor ( c -ANN) search problem in high-dimensional Euclidean space. Traditionally, LSH functions are constructed in a query-oblivious manner in the sense that buckets are partitioned before any query arrives. However, objects closer to a query may be partitioned into different buckets, which is undesirable. Due to the use of query-oblivious bucket partition, the state-of-the-art LSH schemes for external memory, namely C2LSH and LSB-Forest, only work with approximation ratio of integer c ≥ 2. In this paper, we introduce a novel concept of query-aware bucket partition which uses a given query as the "anchor" for bucket partition. Accordingly, a query-aware LSH function is a random projection coupled with query-aware bucket partition, which removes random shift required by traditional query-oblivious LSH functions. Notably, query-aware bucket partition can be easily implemented so that query performance is guaranteed. We propose a novel query-aware LSH scheme named QALSH for c -ANN search over external memory. Our theoretical studies show that QALSH enjoys a guarantee on query quality. The use of query-aware LSH function enables QALSH to work with any approximation ratio c > 1. Extensive experiments show that QALSH outperforms C2LSH and LSB-Forest, especially in high-dimensional space. Specifically, by using a ratio c < 2, QALSH can achieve much better query quality.