With the increasing use of RDF graphs, storing and querying such data using SPARQL remains a critical problem. Current mainstream solutions rely on cloud-based data management architectures, but often suffer from performance bottlenecks in environments with limited bandwidth or high system load. To address this issue, this paper explores for the first time the integration of edge computing to move graph data storage and processing to edge environments, thereby improving query performance. This approach requires offloading query processing to edge servers, which involves addressing two challenges: data localization and network scheduling. First, the data localization challenge lies in computing the subgraphs maintained on edge servers to quickly identify the servers that can handle specific queries. To address this challenge, we introduce a new concept of pattern-induced subgraphs. Second, the network scheduling challenge involves efficiently assigning queries to edge and cloud servers to optimize overall system performance. We tackle this by constructing a overall system model that jointly captures data distribution, query characteristics, network communication, and computational resources. Accordingly, we further propose a joint formulation of query assignment and computational resource allocation, modeling it as a Mixed Integer Nonlinear Programming (MINLP) problem and solve this problem using a modified branch-and-bound algorithm. Experimental results on real datasets under a real cloud platform demonstrate that our proposed method outperforms the state-of-the-art baseline methods in terms of efficiency. The codes are available on GitHub

Graph pattern queries (GPQ) over RDF graphs extend basic graph patterns to support variable-length paths (VLP), thereby enabling complex knowledge retrieval and navigation. Generally, variable-length paths describe the reachability between two vertices via a given property within a specified range. With the increasing scale of RDF graphs, it is necessary to design a partitioning method to achieve efficient distributed queries. Although many partitioning strategies have been proposed for large RDF graphs, most existing methods result in numerous inter-partition joins when processing GPQs, which impacts query performance. In this paper, we formulate a new partitioning problem, MaxLocJoin, aims to minimize inter-partition joins during distributed GPQ processing. For MaxLocJoin, we propose a partitioning framework (PIP) based on property-induced subgraphs, which consist of edges with a specific set of properties. The framework first finds a locally joinable property set using a cost-driven algorithm, LJPS, where the cost depends on the sizes of weakly connected components within its property-induced subgraphs. Subsequently, the graph is partitioned according to the weakly connected components. The framework can achieve two key objectives: first, it enables complete local processing of all variable-length path queries (eliminating inter-partition joins); second, it can minimize the number of inter-partition joins required for traditional graph pattern queries. Moreover, we identify two types of independently executable queries (IEQ): the locally joinable IEQ and the single-property IEQ. After that, a query decomposition algorithm is designed to transform all GPQ into one of them for independent execution in distributed environments. In experiments, we implement two prototype systems based on Jena and Virtuoso, and evaluate them over both real and synthetic RDF graphs. The results show that MaxLocJoin achieves performance improvements from 2.8x to 10.7x over existing methods.

Variable-length path queries are essential for finding paths in a graph that adhere to a specified length constraint, utilizing only edges with labels from a restricted subset of the edge labels. These queries play a crucial role in graph analytics and are supported by practical graph query languages like Cypher in property graph systems and SPARQL 1.1 in RDF graph systems. In this paper, we present a novel solution for efficient evaluation of variable-length path queries, based on worst-case optimal joins. Our solution's core relies on a jumping-like worst-case optimal join technique, allowing us to select a query vertex order that differs completely from existing graph systems based on worst-case optimal joins. Furthermore, we introduce a cost-based dynamic programming optimizer that combines traditional and jumping-like worst-case optimal join techniques. We also propose an optimization technique to leverage intra-query parallelism during query evaluation. Through extensive experiments conducted on numerous synthetic and real RDF and property graphs, we demonstrate that the proposed technique achieves excellent performance.

Butterfly counting is widely used to analyze bipartite networks, but counting butterflies in original bipartite networks can reveal sensitive data and pose a risk of individual privacy, specifically edge privacy. Current privacy notions do not fully address the needs of both user-user and user-item bipartite networks. In this paper, we propose a novel privacy notion, edge decentralized differential privacy (edge DDP), which preserves edge privacy in any bipartite network. We also design the randomized edge protocol (REP) to perturb real edges in bipartite networks. However, a significant amount of noise in perturbed bipartite networks often leads to an overcount of butterflies. To achieve accurate butterfly counting, we design the randomized group protocol (RGP) to reduce noise. By combining REP and RGP, we propose a two-phase framework called butterfly counting in limitedly synthesized bipartite networks (BC-LimBN) to synthesize networks for accurate butterfly counting. BC-LimBN has been rigorously proven to satisfy edge DDP. Our experiments on various datasets confirm the high accuracy of BC-LimBN in butterfly counting and its superiority over competitors, with a mean relative error of less than 10% at most. Furthermore, our experiments show that BC-LimBN has a low time cost, requiring only a few seconds on our datasets.

Graph pattern query is a powerful tool for extracting crucial information from property graphs. With the exponential growth of sizes, property graphs are typically divided into multiple subgraphs (referred to as partitions ) and stored across various sites in distributed environments. Existing graph partitioning methods have not been efficiently optimized for pattern queries, resulting in numerous query matches across multiple partitions, called crossing matches. Identifying these matches requires much inter-partition communication, which is the primary performance bottleneck in distributed query processing. To address this issue, this paper introduces a novel connectivity-oriented relationship-disjoint partitioning method, namely RCP (Relationship Connectivity Partitioning), aimed at enhancing the efficiency of graph pattern query processing by reducing crossing matches. By employing each weakly connected component of the subgraph, which is induced by different relationship labels, as a basic unit of partition, RCP ensures that matches for both variable-length path and labeled graph pattern queries are not crossing matches. Here, variable-length path and labeled graph pattern are two common components in graph pattern queries to identify paths meeting specific label constraints and retrieve subgraphs with consistent relationship types, respectively. Moreover, in the query processing phase, we further demonstrate that all graph pattern queries, belonging to these two basic queries or their extensions, can be executed independently under RCP, thereby avoiding crossing matches. In experiments, we implemented two prototype distributed property graph systems based on Neo4j and JanusGraph, which use declarative and functional query language, respectively. Experimental results on billion-scale datasets demonstrate that our approach brings a performance improvement of nearly two orders of magnitude over state-of-the-art partitioning methods.

Abundant valuable knowledge can be obtained by learning frequencies of relations in a decentralized network, which benefits various further complex tasks, such as range query and commodity recommendation. Nonetheless, counting frequencies in original networks can reveal sensitive data and pose a risk to individual privacy, specifically relation privacy. Current privacy notions do not fully preserve both the privacy of relations’ values and existence. In this paper, we introduce an enhanced privacy notion, relation local differential privacy (relation LDP), which provides comprehensive preservation in relation privacy. However, a significant amount of noise in perturbed networks often leads to severe errors in the accuracy of relation frequencies. To obtain accurate frequencies, we propose a framework called frequency estimation based on combination (Fest-C), which decomposes relation frequencies into two independent parts, the total frequency of relations and relative proportions. Binning relations into hyper-relations, Fest-C reduces errors of total frequency and relative proportions, respectively, and then estimates frequencies by logically multiplying them. Finally, we rigorously prove that Fest-C satisfies relation LDP. Our experiments on various datasets confirm the high accuracy of Fest-C in estimating relation frequencies with a much lower time overhead compared to competitors.

This paper explores parallel computing systems for efficient subgraph query processing in large graphs. We investigate how to take advantage of the inherent parallelism of parallel computing systems for both intraquery and interquery optimization during subgraph query processing. Rather than relying on widely-used hash-based methods, we utilize and extend locality sensitive hashing methods. For intraquery optimization, we use the structures of both the data graph and subgraph query to design a query-constraint locality sensitive hashing method named QCMH, which can be used to merge multiple tasks during a single subgraph query processing. For interquery optimization, we propose a query locality sensitive hashing method named QMH, which can be used to detect common subgraphs among different subgraph queries, thereby merging multiple subgraph queries. Our proposed methods can reduce the redundant computation among multiple tasks duringa single subgraph query processing or multiple queries. Extensive experimental studies on large real and synthetic graphs show that our proposed methods can improve query performance compared to state-of-the-art methods by 10% to 50%.

RDF (Resource Description Framework) is a model widely used to construct knowledge bases, while SPARQL (SPARQL Protocol and RDF Query Language) is the standardized structured query language to manipulate RDF data. Recently, many data providers have published their RDF datasets in their own autonomous sites and provided SPARQL query interfaces, calledRDF sources. In order to integrate multiple RDF sources, researchers put forward the federated RDF system to support the federated SPARQL queries. However, existing studies can only support efficient basic queries but not top-k queries. Toward this end, we propose a cost-driven top-k queries optimization approach in federated RDF systems, which can support both top-k queries for single variable ordering and expression ordering. Firstly, we propose an optimized query decomposition method to decompose the federated query into multiple subqueries. Secondly, while considering the top-k operator, we propose a cost model to evaluate the query cost and join cost of subqueries. The optimal query plan can be obtained by the costed-based query plan generation algorithm. Finally, combined with the characteristics of top-k queries, an incremental query plan execution strategy is developed to minimize the total query cost. Experimental results show that the proposed method is effective, efficient and scalable.

The issue of keyword search in federated resource description framework(RDF) systems is revisited in this paper. Numerous independent SPARQL endpoints that solely offer SPARQL query interfaces make up a federated RDF system. Others find it challenging to remotely build up the global inverted indices over the full RDF network by downloading the dataset at various SPARQL endpoints. This poses a challenge for existing keyword search approaches. In this paper, we propose a keyword search approach for federated RDF systems without building up global inverted indices on the entire RDF graph. We build an offline schema graph for the federated RDF system. During query evaluation, the full-text search interfaces provided by existing SPARQL endpoints were used to map keywords to vertices in the schema graph. Subsequently, the schema graph was explored to construct SPARQL queries from the keywords. The constructed queries were evaluated over the underlying federated RDF systems. Some cost models were proposed to measure keyword mapping and query construction. On the other hand, to further improve the efficiency, a multiple query optimization strategy was designed to rewrite the queries and share the common computation during evaluation. Extensive experiments on real RDF datasets show that the proposed techniques are effective.

Scaling-out RDF processing to deal with graph size usually requires partitioning the RDF graph. Typical partitioning approaches minimize edge-cuts or vertex-cuts. In this paper we argue that these approaches do not avoid or reduce joins between different partitions (i.e., inter-partition join), and propose an approach based on minimizing the number of distinct crossing properties, which we call Minimum Property-Cut (MPC). This approach enables more queries to be independently evaluated without inter-partition join. However, the minimum property-cut partitioning is a NP-hard problem and we propose a heuristic greedy algorithm to address that. Extensive experiments over a variety of synthetic and real RDF graphs show that the proposed technique can significantly avoid joins and results in good performance.

With the rapid growth of graph scale, challenges emerge for subgraph search when the data graph cannot reside in the memory of a single machine. It is important to develop practical algorithms to answer subgraph queries in distributed systems and has attracted extensive attention in recent years. The existing join-based algorithms are natively supported in many distributed engines, but they often suffer from a large number of invalid intermediate results and duplicate computation. The exploration-based algorithms minimize invalid intermediate results, while they are likely to produce results of exponential size. In this paper, we propose an efficient hybrid subgraph matching framework that integrates the advantages of both join-based and exploration-based paradigms. We formulate a novel decomposition for the query graph, namely sketch tree, which can reduce invalid intermediate results and avoid duplicate computation. We implement the proposed algorithm in the Pregel + system and optimize the communication cost powered by the sketch tree. Extensive experiments on real graphs demonstrate that our proposed algorithm significantly outperforms the state-of-the-art join-based and exploration-based methods.

As a fundamental problem in graph analysis, core decomposition aims to compute the core numbers of vertices in a given graph. It is a powerful tool for mining important graph structures. For dynamic graphs with real-time updates of vertices/edges, core maintenance has been utilized to update the core numbers of vertices. The previous approaches to core maintenance face challenges in terms of storage and efficiency. In this article, we investigate distributed approaches to core maintenance on a pregel-like system, which is a famous graph computing system. We first design a core decomposition algorithm to obtain core numbers of vertices in a given graph. Based on it, a distributed batch-stream combined algorithm (DBCA) is devised to efficiently maintain the core numbers when vertex/edge updates happen. In particular, we introduce a new task assignment strategy to DBCA based on diversity of the edge-cores of updated edges. To ensure that DBCA can accurately process core maintenance, we develop a message interaction protocol to resolve the problem of crosstalk among different tasks. Comprehensive experiments have been conducted on real/synthetic graphs, more specifically, in two typical distributed environments built on Supercomputing Center and Alibaba Cloud. The experiment results demonstrate that our proposed algorithms are efficient and scalable.

The vertices in many graphs are weighted unequally in real scenarios, but the previous studies on the maximum independent set (MIS) ignore the weights of vertices. Therefore, the weight of an MIS may not necessarily be the largest. In this paper, we study the problem of maximum weighted independent set (MWIS) that is defined as the set of independent vertices with the largest weight. Since it is intractable to deliver the exact solution for large graphs, we design a reducing and tie-breaking framework to compute a near-maximum weighted independent set. The reduction rules are critical to reduce the search space for both exact and greedy algorithms as they determine the vertices that are definitely (or not) in the MWIS while preserving the correctness of solutions. We devise a set of novel reductions including low-degree reductions and high-degree reductions for general weighted graphs. Extensive experimental studies over real graphs confirm that our proposed method outperforms the state-of-the-arts significantly in terms of both effectiveness and efficiency.

With the Internet of Things (IoT) gradually showing a trend of socialization, the community structure has been widely used in IoT applications, such as the smart home and smart city. Therefore, using the IoT and data mining technology to detect and analyze the relevant communities in the network is worth studying. In this article, we aim to identify the r most influential communities in a network, where an influential community is a cohesive subgraph with a considerable level of influence. In the literature, several efficient methods have been proposed to address this problem. These methods are all devised based on the assumption that nodes in the network are associated with different weights; in other words, every pair of nodes cannot have the same weight. Otherwise, these methods may retrieve imprecise results. However, nodes in a network may inevitably have the same weight in lots of real-world scenarios, such as mobile-edge computing networks. In this article, we are motivated to efficiently compute the top- r influential communities in a general case where nodes in the network may have arbitrary weights. To this end, we first proposed a unified search framework by improving the existing techniques. Then, we developed an efficient algorithm to judge the connectivity of nodes with the same weight, whose time complexity is linear to the size of the subgraph accessed by the algorithm. We conducted extensive performance studies on real data sets to demonstrate the effectiveness and efficiency of the proposed approaches.

This paper revisits the classical problem of multiple query optimization in federated RDF systems. We propose a heuristic query rewriting-based approach to optimize the evaluation of multiple queries. This approach can take advantage of SPARQL 1.1 to share the common computation of multiple queries while considering the cost of both query evaluation and data shipment. Although we prove that finding the optimal rewriting for multiple queries is NP-complete, we propose a heuristic rewriting algorithm with a bounded approximation ratio. Furthermore, we propose an efficient method to use the interconnection topology between RDF sources to filter out irrelevant sources, and utilize some characteristics of SPARQL 1.1 to optimize multiple joins of intermediate matches. The extensive experimental studies show that the proposed techniques are effective, efficient and scalable.

As a well-known optimization problem, the maximum independent set (MIS) has attracted a lot of effort due to its significance in graph theory and wide applications. Nevertheless, the vertices of many graphs are weighted unequally in real scenarios, but the previous studies ignore the intrinsic weights on the graphs. Therefore, the weight of an MIS may not necessary to be the largest. Generalizing the traditional MIS problem, we study the problem of maximum weighted independent set (MWIS) that returns the set of independent vertices with the largest weight in this paper, which is computationally expensive. Following the reduction-and-branching strategy, we propose an exact algorithm to compute the maximum weighted independent set. Since it is intractable to deliver the exact solution for large graphs, we design an efficient greedy algorithm to compute a near-maximum weighted independent set. We devise a set of novel reductions for general weighted graphs. To confirm the effectiveness and efficiency of the proposed methods, we conduct extensive experimental studies over a bunch of real graphs.

Partial evaluation has recently been used for processing SPARQL queries over a large resource description framework (RDF) graph in a distributed environment. However, the previous approach is inefficient when dealing with complex queries. In this study, we further improve the "partial evaluation and assembly" framework for answering SPARQL queries over a distributed RDF graph, while providing performance guarantees. Our key idea is to explore the intrinsic structural characteristics of partial matches to filter out irrelevant partial results while providing performance guarantees on the data shipment and the response time. We also propose an efficient assembly algorithm to utilize the characteristics of partial matches to merge them and form final results. To improve the efficiency of finding partial matches further, we propose an optimization that communicates variables' candidates among sites to avoid redundant computations. In addition, although our approach is partitioning-tolerant, different partitioning strategies result in different performances, and we evaluate different partitioning strategies for our approach. Experiments over both real and synthetic RDF datasets confirm the superiority of our approach.

As massive volumes of Resource Description Framework (RDF) data are growing, designing a distributed RDF database system to manage them is necessary. In designing this system, it is very common to partition the RDF data into some parts, called fragments, which are then distributed. Thus, the distribution design comprises two steps: fragmentation and allocation. In this study, we explore the workload for fragmentation and allocation, which aims to reduce the communication cost during SPARQL query processing. Specifically, we adaptively maintain some frequent access patterns (FAPs) to reflect the characteristics of the workload while ensuring the data integrity and approximation ratio. Based on these frequent access patterns, we propose three fragmentation strategies, namely vertical, horizontal, and mixed fragmentation, to divide RDF graphs while meeting different types of query processing objectives. After fragmentation, we discuss how to allocate these fragments to various sites while balancing the fragments. Finally, we discuss how to process queries based on the results of fragmentation and allocation. Experiments over large RDF datasets confirm the superior performance of our proposed solutions.

As the volume of the RDF data becomes increasingly large, it is essential for us to design a distributed database system to manage it. For distributed RDF data design, it is quite common to partition the RDF data into some parts, called fragments, which are then distributed. Thus, the distribution design consists of two steps: fragmentation and allocation. In this paper, we propose a method to explore the intrinsic similarities among the structures of queries in a workload for fragmentation and allocation, which aims to reduce the number of crossing matches and the communication cost during SPARQL query processing. Specifically, we mine and select some frequent access patterns to reflect the characteristics of the workload. Based on the selected frequent access patterns, we propose two fragmentation strategies, vertical and horizontal fragmentation strategies, to divide RDF graphs while meeting different kinds of query processing objectives. Vertical fragmentation is for better throughput and horizontal fragmentation is for better performance. After fragmentation, we discuss how to allocate these fragments to various sites. Finally, we discuss how to process a query based on the results of fragmentation and allocation. Extensive experiments confirm the superior performance of our proposed solutions.