Nowadays, ride-sharing is developing rapidly because of its economic and environmental advantages. Recent studies investigate the benefits of introducing meeting points during task assignments, allowing riders to be picked up or dropped off near their requested locations. In this paper, we study the route and area matching (ROAM) problem in dynamic road networks. ROAM query aims to find a detour path from source to destination visiting an area, meanwhile satisfying a detour budget. Existing method excludes unmatched queries in a compacted sketch graph, but the Dijkstra-based routing process is still time-consuming. Moreover, maintaining the sketch graph in frequently changing road networks is challenging because it requires computing from scratch. To overcome the limitations, we propose a simple yet effective framework named meeting point search (MPS). A novel index structure named GS-Tree is constructed to integrate spatial information for selecting meeting points and graph shortcuts for routing queries. GSTree has structural stability and can be efficiently maintained in dynamic networks. Theoretical analysis and experimental studies demonstrate the superiority of our methods. The optimal MPS with GS-Tree averagely outperforms the existing methods by two orders of magnitude.

Path enumeration is a fundamental problem and has been extensively studied in the literature. Given two query vertices and a weight threshold, the problem aims to identify all simple paths with weight not exceeding the threshold. Existing studies on path enumeration include DFS-based solutions and join-based solutions, where the join-based solutions only work for unweighted graphs. In this paper, we are the first to propose a join-based framework for weighted graphs. By observing the characteristics of DFS, we design a series of novel data structures and operations based on the join-based framework. In this way, our final solution combines the advantages of both join and DFS. We conduct experiments on several real large graphs. For weighted graphs, our method is much more efficient than existing algorithms. For unweighted graphs, our method is still competitive compared with the state-of-the-art solution which only works for unweighted graphs.

With the increasing complexity of urban transportation systems and the growing demand for dynamic, real-time responsiveness, Time-Dependent Minimum Travel Time Queries (TD-MTTQs) in time-dependent road networks have become a core challenge in intelligent transportation system research. To address the trade-offs between preprocessing complexity and query efficiency in existing index-based methods for large-scale road network applications, this paper proposes a 4-hop index method, TD-TNR-CH. The core methodology involves establishing local indexes from each node to its nearest critical nodes (named transit nodes) through strategic critical node selection, while simultaneously constructing query tables associated with candidate sets between these critical nodes. This architecture enables rapid computation of medium-to-long distance queries through efficient index lookups, while ensuring high responsiveness for short-distance queries via TCH-based local searches. Extensive experimental results on large-scale real-world road networks demonstrate that our method exhibits superior scalability, achieving query efficiency of up to 103 times that of the fastest existing algorithms. Furthermore, it shows exceptional stability across queries of varying distances. Additionally, leveraging its parallelized architecture, TD-TNR-CH requires only approximately 30 minutes of preprocessing time for large-scale networks, significantly outperforming comparable methods in terms of preprocessing efficiency.

There are two fundamental problems in regular simple path queries (RSPQs). One is the reachability problem which asks whether there exists a simple path between the source and the target vertex matching the given regular expression, and the other is the enumeration problem which aims to find all the matched simple paths. As an important computing component of graph databases, RSPQs are supported in many graph database query languages such as PGQL and openCypher. However, answering RSPQs is known to be NP-hard, making it challenging to design scalable solutions to support a wide range of expressions. In this paper, we first introduce the class of transitive restricted expression , which covers more than 99% of real-world queries. Then, we propose an efficient algorithm framework to support both reachability and enumeration problems under transitive restricted expression constraints. To boost the performance, we develop novel techniques for reachability detection, the search of candidate vertices, and the reduction of redundant path computation. Extensive experiments demonstrate that our exact method can achieve comparable efficiency to the state-of-the-art approximate approach, and outperforms the state-of-the-art exact methods by up to 2 orders of magnitude.

Computing Multi-source Shortest Path query with Assembly points ($\mathsf {MSPA}$) is a fundamental graph problem. The$\mathsf {MSPA}$problem locates a set of assembly points to minimize the overall distance for transporting objects from different sources to a destination, where we can assemble objects at assembly points to reduce the total cost. We prove that the$\mathsf {MSPA}$problem is NP-hard. The intuitive method for computing the optimal set of assembly points and the corresponding set of paths is by Branch-and-Bound. However, the combination of different assembly points is exponential. By analyzing the structure of the path set based on the proposed distance graph, we find that the used paths can be combined into a tree. Hence, by defining the state of subtrees and the state transition equation, we propose a dynamic programming (DP) algorithm by pruning the redundant computation of subtrees. The experiment shows that the DP algorithm can achieve three orders of magnitude speedup in query processing time compared with the optimized Branch-and-Bound algorithm. Moreover, we reduce the transition candidates of the DP algorithm from the entire vertex set to certain neighbors. Extensive experiments are conducted on different types of real-world networks to demonstrate the performance of our DP algorithm.

In this paper, we study the problem of maximal biclique enumeration on large signed bipartite graphs. Given a signed bipartite graph$G=(U,V,E,s)$, a parameter$\theta \in [0.5, 1.0]$, our goal is to efficiently enumerate all maximal$\theta$-bicliques in$G$, where a maximal$\theta$-biclique$B(L,R)$is a complete subgraph of$G$with (1) the proportion of positive neighbors for each vertex in$B$is at least$\theta$, and (2)$B$is not contained in another biclique$B^{\prime }$, while$B^{\prime }$also satisfies (1). This problem has many applications, such as biclustering for genes, recommendation of similar groups, collaboration in communities, etc. However, it is computationally challenging due to its #P-completeness. Besides, we prove that even determining the maximality of a$\theta$-biclique is NP-hard. To the best of our knowledge, there is no efficient and scalable solution to this problem in the literature. In this paper, we first propose a branch-and-bound framework, namely${\sf MSiBE}$, which enumerates all maximal$\theta$-bicliques in a depth-first manner. Then, we develop three effective optimizations to improve the performance of${\sf MSiBE}$. (1) The local information of each search space is utilized to enhance the pruning capacity. (2) When expanding the partial biclique, we always focus on the side with fewer candidates first, by which fruitless search branches can be skipped early. (3) We implement${\sf MSiBE}$with efficient array reordering techniques and set intersection strategy. To further accelerate the computation, we introduce useful graph reduction techniques. Comprehensive performance studies on 10 real datasets demonstrate that our proposals can significantly outperform the baseline methods by up to 3 orders of magnitude.

As a fundamental graph problem, community search is applied in various areas, e.g., social networks, the world wide web, and biology. A common requirement from real applications is to return a community with a bounded size while most existing solutions do not constrain community size. Recent studies on size-constrained community search still have some critical issues, e.g., the existence of a better cohesiveness objective, some queries returning empty results, and inefficiency on partial queries. Thus, in this paper, we study the size-constrained truss community search (STCS). Given a graph$G$, a query vertex$q$, and size constraint$[l,h]$, the STCS problem aims to find a subgraph containing$q$with the largest min-support among all connected subgraphs having at least$l$and at most$h$vertices. We prove the STCS problem is NP-hard and APX-hard unless P = NP. An effective heuristic is proposed to quickly find a high-quality initial result. Then, a branch and bound algorithm is introduced to find the exact result, with novel optimizations, e.g., budget-cost-based bounding and branching strategies. Extensive experiments verify that the community quality returned by our algorithm is better and our algorithm is faster by up to 5 orders of magnitude, compared with the state-of-the-art.

Hop-constrained s-t simple path (k-st path) enumeration is a fundamental problem in graph databases and plays an important role in many real-world applications. Given a dynamic graph G, a source-target pair s-t, and a hop constraint k, we aim to efficiently compute k-st paths: list all simple paths within length k from s to t, and then continuously maintain the results against edge updates. Although the k-st path enumeration has been well studied in static setting, the existing works on static graphs cannot be applied or adapted to handle dynamic graphs efficiently. To address the challenges on dynamic computation, we propose a partial path-based index structure and an efficient enumeration algorithm based on the index. We also propose several well-designed techniques to efficiently maintain the index and locate the affected results with graph updates. Comprehensive experiments verify that our proposed CPEupdatealgorithm outperforms the state-of-the-art methods by up to 4 orders of magnitude on dynamic graphs. The experiment results also show that the time cost of our initialization step CPEstartup(including index construction) is similar to the state-of-the-art static method.

The existence of anomalies is quite common, but they are hidden within the complex structure and high-dimensional node attributes of the attributed networks. As a latent hazard in existing systems, anomalies can be transformed into important instruction information once we detect them, e.g., computer network admins can react to the leakage of sensitive data if network traffic anomalies are identified. Extensive research in anomaly detection on attributed networks has proposed various techniques, which do improve the quality of data in networks, while they rarely cope with the few-shot anomaly detection problem. Few-shot anomaly detection task with only a few dozen labeled anomalies is more practical since anomalies are rare in number for real-world systems.

Multilayer graphs are very powerful in representing the multiplex relationships among entities. The truss decomposition on single-layer graphs is a well-studied problem which divides a graph into a hierarchy structure, and has a series of applications. However, little attention has been paid to the truss decomposition on multilayer graphs. In addition, truss decomposition on multilayer graphs derives new challenges compared to the scenario on single-layer graphs. In this paper, we devise an efficient algorithm to compute the truss decomposition on multilayer graphs. Extensive experiments on 5 real-life datasets validate the effectiveness and efficiency of our methods.

Graph similarity search retrieves from a database all graphs whose edit distance (GED) to a query graph is within a threshold. As GED computation is NP-hard, the existing works adopt the filtering-and-verification paradigm to reduce the number of GED verifications, and they mainly focus on designing filtering techniques while using the now out-dated algorithm A*GED for verification. In this paper, we aim to speed up GED verification, which is orthogonal to the index structures used in the filtering phase. We propose a best-first search algorithm AStar+-LSa which improves A*GED by (1) reducing memory consumption, (2) tightening lower bound estimation, and (3) improving the time complexity for lower bound computation. We formally show that AStar+-LSa has a lower space and time complexity than A*GED. We further modify AStar+-LSa into a depth-first search algorithm to contrast these two search paradigms, and we extend our algorithms for exact GED computation. We conduct extensive empirical studies on real graph datasets, and show that our algorithm AStar+-LSa outperforms the state-of-the-art algorithms by several orders of magnitude for both GED verification and GED computation.

Computing top-k nearest neighbors (kNN) is a fundamental problem in road networks. Existing solutions either need a complicated parameter configuration in index construction or incur high costs when scanning an unbounded number of vertices in query processing. In this paper, we propose a novel parameter-free index-based solution for the kNN query based on the concept of tree decomposition in large road networks. Based on our index structure, we propose an efficient and progressive algorithm that returns each result in a bounded delay. We also optimize the index structure, which improves the efficiency of both index construction and index maintenance in large road networks. We conduct extensive experiments to show the efficiency of our proposed algorithms and the effectiveness of our optimization techniques in real-world road networks from ten regions.

Computing the shortest path between two vertices is a fundamental problem in road networks that is applied in a wide variety of applications. To support efficient shortest path query processing, a plethora of index-based methods have been proposed in the literature, but few of them can support dynamic road networks commonly encountered in practice, as their corresponding index structures cannot be efficiently maintained when the input road network is dynamically updated. Motivated by this, we study the shortest path index maintenance problem on dynamic road networks in this paper. We adopt Contraction Hierarchies (CH) as our underlying shortest path computation method because of its outstanding overall performance in pre-processing time, space cost, and query processing time and aim to design efficient algorithms to maintain the index structure, shortcut index , of CH when the input road network is dynamically updated. To achieve this goal, we propose a shortcut-centric paradigm focusing on exploring a small number of shortcuts to maintain the shortcut index. Following this paradigm, we design an auxiliary data structure named SS-Graph and propose a shortcut weight propagation mechanism based on the SS-Graph. With them, we devise efficient algorithms to maintain the shortcut index in the streaming update and batch update scenarios with non-trivial theoretical guarantees. We experimentally evaluate our algorithms on real road networks and the results demonstrate that our approach achieves 2--3 orders of magnitude speedup compared to the state-of-the-art algorithm for the streaming update.

Computing the shortest distance between two vertices is a fundamental problem in road networks. Since a direct search using the Dijkstra's algorithm results in a large search space, researchers resort to indexing-based approaches. State-of-the-art indexing-based solutions can be categorized into hierarchy-based solutions and hopbased solutions. However, the hierarchy-based solutions require a large search space for long-distance queries while the hop-based solutions result in a high computational waste for short-distance queries. To overcome the drawbacks of both solutions, in this paper, we propose a novel hierarchical 2-hop index (H2H-Index) which assigns a label for each vertex and at the same time preserves a hierarchy among all vertices. With the H2H-Index, we design an efficient query processing algorithm with performance guarantees by visiting part of the labels for the source and destination based on the vertex hierarchy. We also propose an algorithm to construct the H2H-Index based on distance preserved graphs. The algorithm is further optimized by computing the labels based on the partially computed labels of other vertices. We conducted extensive performance studies using large real road networks including the whole USA road network. The experimental results demonstrate that our approach can achieve a speedup of an order of magnitude in query processing compared to the state-of-the-art while consuming comparable indexing time and index size.