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.

Spatial crowdsourcing (SC) is becoming increasingly popular recently. As a critical issue in SC, task assignment currently faces challenges due to the imbalanced spatiotemporal distribution of tasks. Hence, many related studies and applications focusing on cross-platform task allocation in SC have emerged. Existing work primarily focuses on the maximization of total revenue for inner platform in cross task assignment. In this work, we formulate a SC problem called Cross Dynamic Task Assignment (CDTA) to maximize the overall utility and propose improved solutions aiming at creating a win-win situation for inner platform, task requesters, and outer workers. We first design a hybrid batch processing framework and a novel cross-platform incentive mechanism. Then, with the purpose of allocating tasks to both inner and outer workers, we present a KM-based algorithm that gets the accurate assignment result in each batch and a density-aware greedy algorithm with high efficiency. To maximize the revenue of inner platform and outer workers simultaneously, we model the competition among outer workers as a potential game that is shown to have at least one pure Nash equilibrium and develop a game-theoretic method. Additionally, a simulated annealing-based improved algorithm is proposed to avoid falling into local optima. Last but not least, since random thresholds lead to unstable results when picking tasks that are preferentially assigned to inner workers, we devise an adaptive threshold selection algorithm based on multi-armed bandit to further improve the overall utility. Extensive experiments demonstrate the effectiveness and efficiency of our proposed algorithms on both real and synthetic datasets.

In-memory dynamic graph processing faces three critical challenges: limited DRAM capacity, inefficient concurrent update/query handling, and vulnerability to crashes. Traditional segment-level systems struggle with write amplification on emerging Storage-Class Memory (SCM), while existing persistent-memory systems suffer from coarse-grained synchronization and high recovery overhead. This study presents the Storage-Class Memory Dynamic Graph (SMDG) processing framework, an architecture-level redesign centered on the block as the atomic unit across storage, concurrency, and recovery. The system addresses these challenges through three key innovations. First, a block-granular storage design organizes adjacency data at fixed-size block granularity on heterogeneous DRAM-SCM architecture, employing buffered batched writes to significantly reduce write amplification while preserving logarithmic update complexity. Second, block-level multi-version concurrency control maintains timestamped block versions under per-vertex read-write synchronization to provide task-ordered snapshot visibility for concurrent queries without copying entire vertices or pages. Third, a block-granular crash recovery protocol with decentralized per-vertex logs enables independent parallel reconstruction, ensuring application-level semantic consistency while achieving substantially faster recovery than sequential approaches. Experimental results validate that this unified block-granular design improves update efficiency, sustains mixed update-query workloads with controlled memory overhead, and accelerates crash recovery compared with prior dynamic graph systems.

Structural Graph Clustering is a well-known problem that aims to identify clusters and distinguish between special roles, such as hub and outlier. However, SCAN, the fundamental structural clustering model, is designed for pairwise graphs and fails to capture the unique structural information inherent in hypergraphs when clustering hypergraphs. Motivated by this, we propose a new structural clustering model, HSCAN, specifically for hypergraphs. We further design an Order-Index to accelerate fetching the key information of the HSCAN and a Lightweight Similarity Bucket Index to reduce the index cost. Next, we present an index-based sequential query algorithm with high performance and a parallel query algorithm to process large hypergraphs faster. Additionally, we provide the algorithms for constructing Order-Index and Lightweight Similarity Bucket Index. Extensive experiments on both real-world and synthetic datasets show that HSCAN performs better than existing models, and the two index-based query algorithms are up to three orders of magnitude faster than the existing algorithm.

This paper addresses the pressing need for effective k-tips decomposition in dynamic bipartite graphs, a crucial aspect of real-time applications that analyze and mine binary relationship patterns. Recognizing the dynamic nature of these graphs, our study is the first to provide a solution for k-tips decomposition in such evolving environments. We introduce a pioneering projection-based algorithm, coupled with advanced incremental maintenance strategies for edge modifications, tailored specifically for dynamic graphs. This novel approach not only fills a significant gap in the analysis of dynamic bipartite graphs but also substantially enhances the accuracy and timeliness of data-driven decisions in critical areas like public health. Our contributions set a new benchmark in the field, paving the way for more nuanced and responsive analyses in various domains reliant on dynamic data interpretation.

Task assignment is a fundamental challenge in Spatial Crowdsourcing which aims to assign location-based tasks to workers under spatial-temporal constraints. Recently, some exciting research has introduced the preference of workers and tasks to improve assignment quality. However, they either primarily focus on the current preferences of both workers and tasks or only consider the unilateral prediction-based preference of workers, overlooking the impact of workers' interconnection and tasks' completed sequences. As a result, they gain suboptimal assignment results in most cases. Inspired by this, we propose a novel problem, named the Predictive Bi-preference Stable Match problem (PBSM), with the goal of maximizing the preferences of both workers and tasks by taking into account the social network of workers and task completion sequence. The PBSM problem is proven to be NP-hard. To tackle this challenging problem, we develop a GCN-enhanced Transformer-based Prediction and Bi-preference Stable Matching (GETBM) framework with two stages: the bi-preference prediction stage and the bilateral assignment stage. In the prediction stage, the Worker Preference Model (WPM) and Task Preference Model (TPM) models are presented to predict the worker-to-task (Worker2Task) and task-to-worker (Task2Worker) preference lists, respectively. Then, we design a bilateral preference-aware stable matching (BPM) algorithm and prove it can gain stable results. To generalize to multiple scenarios, three optimization strategies are devised based on spatial-temporal constraints and priority consideration to gain better assignment performance. Extensive experiments are conducted to prove the superiority of the GETBM framework on two real datasets.

This paper addresses the pressing need for effective k-tips decomposition in dynamic bipartite graphs, a crucial aspect of real-time applications that analyze and mine binary relationship patterns. Recognizing the dynamic nature of these graphs, our study is the first to provide a solution for k-tips decomposition in such evolving environments. We introduce a pioneering projection-based algorithm, coupled with advanced incremental maintenance strategies for edge modifications, tailored specifically for dynamic graphs. This novel approach not only fills a significant gap in the analysis of dynamic bipartite graphs but also substantially enhances the accuracy and timeliness of data-driven decisions in critical areas like public health. Our contributions set a new benchmark in the field, paving the way for more nuanced and responsive analyses in various domains reliant on dynamic data interpretation.

Continuous subgraph matching (CSM) is an important problem of graph analysis over dynamic graphs. Given a query graph, existing CSM efforts return numerous matches, which may overwhelm analysts. In addition, they do not consider weighted graphs that are ubiquitous in many real-world applications, such as payment networks where each edge has a weight to represent a transaction amount. Over these weighted graphs, matches of the given query graph have diverse priorities for analysis if they own different densities. In this paper, we propose a new problem of CSM-TopK to compute$k$matches of a given query graph with the highest densities over a dynamic weighted graph and prove it to be NP-hard. To compute the CSM-TopK effectively, we first define a star-structured subquery, based on which we design two lightweight indexes, called global and local MWstar, respectively. In particular, the global MWstar maintains the maximum weights of all partial matches of each specific star-structured subquery. Differently, the local MW star is designed based on the corresponding maximum weight distribution for each specific data vertex. Additionally, a query-dependent graph compacted technique is introduced to further improve the performance on both time and space. Extensive experiments over real-world datasets show that our MW star- based approaches surpass the comparative ones by at least two orders of magnitude.

Task assignment is a fundamental problem in spatial crowdsourcing. In many spatial crowdsourcing platforms, such as Didi, AMAP, and Uber, there are hybrid tasks, including real-time and reservation-type tasks, which are with different constraints and unevenly distributed in spatial and temporal. For these hybrid tasks, most existing studies suffer from low task completion rate and low profit for two reasons: firstly, they focus on homogeneous tasks with uniform constraints, and assign hybrid tasks separately; secondly, they cannot effectively address the uneven distribution of hybrid tasks. Inspired by this, we delve into the problem of online hybrid task assignment (HyTAO) with the goal of maximizing total revenue by simultaneously assigning both real-time and reservation-type tasks online for the first time. We prove the NP-hardness of the offline version of the HyTAO problem. To solve HyTAO effectively, we utilize a cross-platform cooperation model to tackle the challenge of non-uniform distribution. Following this, we design a binary tree-based search algorithm, namely BTS, which is capable of uniformly processing various types of tasks and quickly searching for available workers. Additionally, we discuss the parallel optimization strategies of BTS. To further enhance performance, we develop TBTS, which identifies tasks with high increased revenue based on a threshold. Finally, we conduct a comprehensive analysis of the complexity and competitive ratio of both BTS and TBTS. Extensive experiments are performed to demonstrate the efficiency of our approaches.

Continuous subgraph matching (CSM) is a critical task for analyzing dynamic graphs and has a wide range of applications, such as merchant fraud detection, cyber-attack hunting, and rumor detection. Although many efficient CSM algorithms have been recently proposed, they are mainly designed to process a single query. However, in some application scenarios, multi-query oriented continuous subgraph matching (MQCSM) may be of more interest. To our knowledge, the two existing solutions to MQCSM are outdated due to unsatisfactory performance. In this paper, we propose MQ-Match, an efficient approach to MQCSM. First, we design a compact yet effective index structure CCG, which maintains the local matching result of vertices in the data graph using a directed graph. The directed edges in CCG can be utilized as an effective pruning rule for the subsequent incremental matching algorithm when expanding a partial match. Then, we develop a computation sharing incremental matching algorithm. In specific, a set of matching trees is constructed based on the depth-first search trees of the query graphs. By utilizing CCG, we conduct subgraph matching for the matching tree to collect the incremental matches for the query graphs, where the common structures of query graphs are matched only once. Extensive experiments show that MQ-Match can achieve 3.1x-7071.4x speedup over the competitors, and consumes much less memory under the majority of the experiment settings.

With the popularity of GPS-equipped smart devices, spatial crowdsourcing (SC) techniques have attracted growing attention in both academia and industry. In existing trajectory-aware task assignment approaches, tasks assigned to a worker may be far apart from each other, resulting in a higher detour cost as the worker needs to deviate from the original trajectory more often than necessary. Motivated by the above observations, we investigate a trajectory-aware task coalition assignment (TCA) problem and prove it to be NP-hard. The goal is to maximize the number of assigned tasks by assigning task coalitions to workers based on their preferred trajectories. To tackle the TCA problem, we develop a batch-based three-stage framework consisting of task grouping, planning, and assignment. Extensive experiments on real and synthetic datasets demonstrate the effectiveness and efficiency of the proposed algorithms.

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.

The enumeration of hop-constrained simple paths is a building block in many graph-based areas. Due to the enormous search spaces in large-scale graphs, a single machine can hardly satisfy the requirements of both efficiency and memory, which causes an urgent need for efficient distributed methods. In practice, it is inevitable to produce plenty of intermediate results when directly extending centralized methods to the distributed environment, thereby causing a memory crisis and weakening the query performance. The state-of-the-art distributed method HybridEnum designed a hybrid search paradigm to enumerate simple paths. However, it makes massive exploration for the redundant vertices not located in any simple path, thereby resulting in poor query performance. To alleviate this problem, we design a distributed approach DistriEnum to optimize query performance and scalability with well-bound memory consumption. Firstly, DistriEnum adopts a graph reduction strategy to rule out the redundant vertices without satisfying the constraint of hop number. Then, a core search paradigm is designed to simultaneously reduce the traversal of shared subpaths and the storage of intermediate results. Moreover, DistriEnum is equipped with a task division strategy to theoretically achieve workload balance. Finally, a vertex migration strategy is devised to reduce the communication cost during the enumeration. The comprehensive experimental results on 10 real-world graphs demonstrate that DistriEnum achieves up to 3 orders of magnitude speedup than HybridEnum in query performance and exhibits superior performances on scalability, communication cost, and memory consumption.

Anomaly detection for multivariate time series is an essential task in the modern industrial field. Although several methods have been developed for anomaly detection, they usually fail to effectively exploit the metrical-temporal correlation and the other dependencies among multiple variables. To address this problem, we propose a stacked attention autoencoder for anomaly detection in multivariate time series (SA2E-AD); it focuses on fully utilizing the metrical and temporal relationships among multivariate time series. We design a multiattention block, alternately containing the temporal attention and metrical attention components in a hierarchical structure to better reconstruct normal time series, which is helpful in distinguishing the anomalies from the normal time series. Meanwhile, a two-stage training strategy is designed to further separate the anomalies from the normal data. Experiments on three publicly available datasets show that SA2E-AD outperforms the advanced baseline methods in detection performance and demonstrate the effectiveness of each part of the process in our method.

With the popularity of GPS-equipped smart devices, spatial crowdsourcing (SC) techniques have attracted growing attention in both academia and industry. A fundamental problem in SC is assigning location-based tasks to workers under spatial-temporal constraints. In many real-life applications, workers choose tasks on the basis of their preferred trajectories. However, by existing trajectory-aware task assignment approaches, tasks assigned to a worker may be far apart from each other, resulting in a higher detour cost as the worker needs to deviate from the original trajectory more often than necessary. Motivated by the above observations, we investigate a trajectory-aware task coalition assignment (TCA) problem and prove it to be NP-hard. The goal is to maximize the number of assigned tasks by assigning task coalitions to workers based on their preferred trajectories. For tackling the TCA problem, we develop a batch-based three-stage framework consisting of task grouping, planning, and assignment. First, we design greedy and spanning grouping approaches to generate task coalitions. Second, to gain candidate task coalitions for each worker efficiently, we design task-based and trajectory-based pruning strategies to reduce the search space. Furthermore, a 2-approximate algorithm, termed MST-Euler, is proposed to obtain a route among each worker and task coalition with a minimal detour cost. Third, the MST-Euler Greedy (MEG) algorithm is presented to compute an assignment that results in the maximal number of tasks assigned and a parallel strategy is introduced to boost its efficiency. Extensive experiments on real and synthetic datasets demonstrate the effectiveness and efficiency of the proposed algorithms.

As a fundamental problem in graph data mining, Densest Subgraph Discovery (DSD) aims to find the subgraph with the highest density from a graph. It has been studied for several decades and found a large number of real-world applications, such as network community detection, regulatory motif discovery in DNA, graph index construction, and fake follower detection. Although there are many existing DSD algorithms, they are often not scalable or efficient to process large-scale graphs, since most of them are serial algorithms and can only leverage the computing resource of a single CPU core. To tackle these issues, in this paper we propose efficient parallel algorithms for solving the DSD problems on both undirected and directed graphs at scale. Our main idea is to use the k-cores (a kind of dense subgraph) to approximate the densest subgraph in the undirected graphs, and then propose efficient parallel algorithms for computing the cores by optimizing the iterative process and also reducing the number of iterations. We further extend this idea for directed graphs by introducing a novel concept, named w-induced subgraph, to avoid unnecessary enumerations of x or y when searching [x,y]-cores (a kind of directed dense subgraph to approximate the densest). To verify the scalability and efficiency of the proposed algorithms, we have conducted extensive experiments on 12 large real-world graphs, and four of them are billion-scale. The experimental results show that our proposed algorithms outperform the state-of-the-art algorithms on both undirected and directed graphs, in terms of scalability and efficiency.

As a novel intelligent sensing paradigm, spatial crowdsourcing has received extensive attention. Task assignment is a key issue in spatial crowdsourcing. In practice, tasks are unevenly distributed in time and space. Accordingly, the problem of cross task assignment attracts growing attention in both industry and academia. Although there has been a research on this problem, it focuses only on maximizing total revenues for inner platforms. Therefore, it can also be improved to bring a multi-win situation for outer workers and task requesters as well as the inner platform. Inspired by this, we first formulate a new cross dynamic task assignment (CDTA) problem by introducing the reputation scores of workers, and prove it to be NP-hard. For the CDTA problem, a hybrid batch-based framework is presented on the basis of a new cross-platform incentive mechanism and a hybrid batch processing strategy, which are efficient in solving the problem of uneven spatial and time distribution of tasks, respectively. After that, a KM-based algorithm and a density-aware greedy algorithm are proposed to gain an accurate assignment result of tasks in each batch and good performance, respectively. Furthermore, the CDTA problem is modeled as a potential game that is proven to have at least a pure Nash Equilibrium theoretically. Last but not least, a game-theoretic approach is developed to maximize the revenues of the inner platform and outer workers at the same time. Extensive experiments on both real and synthetic datasets are conducted to demonstrate the effectiveness and efficiency of the proposed algorithms.

Bipartite graph is an important data structure that widely exists in disease prevention and control, community detection, and other real-life applications. In a bipartite graph, edges not only connect entries of different types but also are bridges of different communities in the above applications. However, research to date has not yet focused on edge importance in bipartite graphs. Inspired by this, we study a new problem of top-k edge search in bipartite graphs with the goal of finding k most important edges for a given bipartite graph; these edges are crucial bridges among communities. In particular, we introduce the measure of ego-betweenness for evaluating the importance of edges. To handle this problem effectively, a lazy bound-based algorithm is first proposed by integrating an upper bound pruning strategy. After that, to further get better efficiency, a greedy bound-based heuristic algorithm is explored on the basis of a tighter upper bound which contributes to reducing redundant computation for calculating ego-betweenness. Last but not least, two parallel techniques with different levels of granularity, called P -src and P -task, are respectively introduced to further improve the search efficiency. The experimental results on both real-world and synthetic graphs demonstrate the efficiency and scalability of the proposed algorithms.

As an important cohesive subgraph model in bipartite graphs, the (α, β)-core (a.k.a. bi-core) has found a wide spectrum of real-world applications, such as product recommendation, fraudster detection, and community search. In these applications, the bipartite graphs are often large and dynamic, where vertices and edges are inserted and deleted frequently, so it is costly to recompute (α, β)-cores from scratch when the graph has changed. Recently, a few works have attempted to study how to maintain (α, β)-cores in the dynamic bipartite graph, but their performance is still far from perfect, due to the huge size of graphs and their frequent changes. To alleviate this issue, in this paper we present efficient (α, β)-core maintenance algorithms over bipartite graphs. We first introduce a novel concept, called bi-core numbers, for the vertices of bipartite graphs. Based on this concept, we theoretically analyze the effect of inserting and deleting edges on the changes of vertices' bi-core numbers, which can be further used to narrow down the scope of the updates, thereby reducing the computational redundancy. We then propose efficient (α, β)-core maintenance algorithms for handling the edge insertion and edge deletion respectively, by exploiting the above theoretical analysis results. Finally, extensive experimental evaluations are performed on both real and synthetic datasets, and the results show that our proposed algorithms are up to two orders of magnitude faster than the state-of-the-art approaches.

Influential community search aims to find cohesive subgraphs (communities) with considerable influence. It is a fundamental graph management operator that can play a crucial role in biological network analysis, activity organization, and other real-life applications. Existing research on influential community search is mainly focused on deterministic graphs with the assumption that influences between entities are certain. This assumption is invalid in many cases because it ignores the uncertainty which is an inherent property of influence. Against this backdrop, in this paper, we introduce an uncertain influential community model, namely$(k, \eta)$-influential community, based on which the influential community search problem over uncertain graphs is formulated. Furthermore, we propose an online approach by integrating a peeling-pruning strategy that can progressively refine the given uncertain graph to find the$(k, \eta)$-influential communities. To further improve the search performance, two novel indexes, ICU-Index and FICU-Index, are developed to organize the$(k, \eta)$-influential communities at different probabilistic intervals. The indexes decompose the probabilistic interval into multiple subintervals and based on this, the$(k, \eta)$-influential communities are divided into different groups in turn. Compared with ICU-Index, FICU-Index requires considerably less space with the introduction of two optimization strategies. These indexes help obtain results of an influential community search problem more efficiently. Extensive experiments on large real and synthetic datasets demonstrate the efficiency and effectiveness of our proposed algorithms.

As a typical most-to-most connected quasi-biclique model, k-biplex is a superset of bicliques, which allows nodes on each side of a fully connected subgraph to lose at most$k$connections. In this paper, we investigate the maximum biplex search problem for the first time. The goal here is to find a k-biplex with the maximum number of edges and we have proved that the problem is NP-hard. It is widely used in fraudulent reviewer group detection, gene expression analysis, social recommendation, and other real-life applications. To solve this problem, a maximum k-biplex search algorithm (MBS) is first presented by integrating two pruning strategies, including degree-based and 2-hop-based pruning. In addition, we define a new dense subgraph over bipartite graphs,$\langle x, y\rangle$-core, and develop a core-based maximum k-biplex search algorithm (MBS-Core) which can significantly reduce the search space with the introduction of a core-based graph reduction technique. In particular, it only needs to search these cores instead of the entire graph to obtain the maximum k-biplex. Moreover, a parallel algorithm and a heuristic algorithm are developed to achieve better query performance on larger-scale bipartite graphs. Extensive experiments have been conducted on real-life and synthetic datasets to verify the efficiency and effectiveness of the proposed algorithms. Our results show that MBS-Core is up to 3 orders of magnitude faster than the existing approaches.

Set label-constrained reachability (SLCR) query in edge-labeled graphs is a building block of many graph-based applications. Formally, given two sets$S$and$T$of source and target vertices and a label set (, it returns all reachable vertex pairs (s, t) under the constraint of (, where$s$∊$S$and$t$∊T. There have been abundant index-based approaches to be applied to process the SLCR query. However, distributed approaches are desirable to process large-scale graphs because of the advantages of good scalability and real-time response. Now, there is no efficient distributed approach to the SLCR query. Most index-based approaches face limitations in terms of index construction and query performance when being extended to the distributed environment for processing large-scale graphs. To alleviate these problems, we first build a boundary graph-based index (BoundG) to reduce the time overhead of index construction. Consider the query performance of the BoundG-based approach has no noticeable improvement. We further construct a novel two layers 2-hop index (TL2hop), and a TL2hop-based query algorithm (TLQA) is designed by integrating an early termination strat-egy that reduces the communication overhead and boosts the query performance. Experimental results over eight data graphs demonstrate that the index time of BoundG is comparable to that of the state-of-the-art, and TL2hop significantly outperforms the state-of-the-art technique in terms of query response time (up to 4 orders of magnitude speedup).

Task assignment is a crucial issue in spatial crowd-sourcing. In most existing studies, the results of the task assignment cannot satisfy the workers and tasks at the same time. This is because only one-sided preferences are taken into account. Moreover, tasks are always assigned based on the locations of workers instead of the trajectories. Accordingly, they are not appropriate to the specific applications, such as carpool. Inspired by this, we investigate an interesting problem of task assignment, namely bilateral preference-aware task assignment (BPTA), with the goal of maximizing the overall satisfaction of workers and tasks by assigning tasks to suitable workers based on their routine trajectories. To tackle this problem effectively, we first propose greedy algorithms, namely task preference priority greedy and worker preference priority greedy algorithms, which are task-driven and worker-driven, respectively. Although these algorithms can solve the BPTA problem effectively, they cannot ensure the stability of the task assignment results. In other words, there can be better choices for some workers and tasks. Accordingly, we further explore deferred acceptance algorithms to find a stable matching for workers and tasks by simultaneously considering the preferences of workers and tasks. Moreover, two optimizing strategies, including a parallel strategy and a top-$k$strategy, are introduced to boost the performance in handling the BPTA problem. Extensive experiments on both real and synthetic datasets have validated the efficiency and effectiveness of our proposed algorithms.

Time-series forecasting is an important problem across a wide range of domains. Designing accurate and prompt forecasting algorithms is a non-trivial task, as temporal data that arise in real applications often involve both non-linear dynamics and linear dependencies, and always have some mixtures of sequential and periodic patterns, such as daily, weekly repetitions, and so on. At this point, however, most recent deep models often use Recurrent Neural Networks (RNNs) to capture these temporal patterns, which is hard to parallelize and not fast enough for real-world applications especially when a huge amount of user requests are coming. Recently, CNNs have demonstrated significant advantages for sequence modeling tasks over the de-facto RNNs, while providing high computational efficiency due to the inherent parallelism. In this work, we propose HyDCNN, a novel hybrid framework based on fully Dilated CNN for time-series forecasting tasks. The core component in HyDCNN is a proposed hybrid module, in which our proposed position-aware dilated CNNs are utilized to capture the sequential non-linear dynamics and an autoregressive model is leveraged to capture the sequential linear dependencies. To further capture the periodic temporal patterns, a novel hop scheme is introduced in the hybrid module. HyDCNN is then composed of multiple hybrid modules to capture the sequential and periodic patterns. Each of these hybrid modules targets on either the sequential pattern or one kind of periodic patterns. Extensive experiments on five real-world datasets have shown that the proposed HyDCNN is better compared with state-of-the-art baselines and is at least 200% better than RNN baselines. The datasets and source code will be published in Github to facilitate more future work.

The G-Skyline (GSky) query is a powerful tool to analyze optimal groups in decision support. Compared with other group skyline queries, it releases users from providing an aggregate function. Besides, it can get much comprehensive results without overlooking some important results containing non-skylines. However, it is hard for the users to make sensible choices when facing so many results the GSky query returns, especially over a large, high-dimensional dataset or with a large group size. In this article, we investigate k representative G-Skyline ( k GSky) queries to obtain a manageable size of optimal groups. The k GSky query can also inherit the advantage of the GSky query; its results are representative and diversified. Next, we propose three exact algorithms with novel techniques including an upper bound pruning, a grouping strategy, a layered optimum strategy, and a hybrid strategy to efficiently process the k GSky query. Consider these exact algorithms have high time complexity and the precise results are not necessary in many applications. We further develop two approximate algorithms to trade off some accuracy for efficiency. Extensive experiments on both real and synthetic datasets demonstrate the efficiency, scalability, and accuracy of the proposed algorithms.

Nowadays, with the development of e-commerce, a growing number of customers choose to go shopping online. To find attractive products from online shopping marketplaces, the skyline query is a useful tool which offers more interesting and preferable choices for customers. The skyline query and its variants have been extensively investigated. However, to the best of our knowledge, they have not taken into account the requirements of customers in certain practical application scenarios. Recently, online shopping marketplaces usually hold some price promotion campaigns to attract customers and increase their purchase intention. Considering the requirements of customers in this practical application scenario, we are concerned about product selection under price promotion. We formulate a constrained optimal product combination (COPC) problem. It aims to find out the skyline product combinations which both meet a customer's willingness to pay and bring the maximum discount rate. The COPC problem is significant to offer powerful decision support for customers under price promotion, which is certified by a customer study. To process the COPC problem effectively, we first propose a two list exact (TLE) algorithm. The COPC problem is proven to be NP-hard, and the TLE algorithm is not scalable because it needs to process an exponential number of product combinations. Additionally, we design a lower bound approximate (LBA) algorithm that has a guarantee about the accuracy of the results and an incremental greedy (IG) algorithm that has good performance. The experiment results demonstrate the efficiency and effectiveness of our proposed algorithms.

Group skyline query is a powerful tool for optimal group analysis. Most of the existing group skyline queries select optimal groups by comparing the dominance relationship between aggregate-based points; such feature creates difficulties for users to specify an appropriate aggregate function. Besides, many significant groups that have great attractions to users in practice may be overlooked. To address these issues, the group skyline (GSky) query is formulated on the basis of a general definition of group dominance operator. While the existing GSky query algorithms are effective, there is still room for improvement in terms of progressiveness and efficiency. In this paper, we propose some new lemmas which facilitate direct generation of the GSky query results. Consecutively, we design a layered unit-based (LU) algorithm that applies a layered optimum strategy. Additionally, for the GSky query over the data that are dynamically produced and cannot be indexed, we propose a novel index-independent algorithm, called sorted-based progressive (SP) algorithm. The experimental results demonstrate the effectiveness, efficiency, and progressiveness of the proposed algorithms. By comparing with the state-of-the-art algorithm for the GSky query, our LU algorithm is more scalable and two orders of magnitude faster.

With the development of the economy, products are significantly enriched, and uncertainty has been their inherent quality. The probabilistic dynamic skyline (PDS) query is a powerful tool for customers to use in selecting products according to their preferences. However, this query suffers several limitations: it requires the specification of a probabilistic threshold, which reports undesirable results and disregards important results; it only focuses on the objects that have large dynamic skyline probabilities; and, additionally, the results are not stable. To address this concern, in this paper, we formulate an uncertain dynamic skyline (UDS) query over a probabilistic product set. Furthermore, we propose effective pruning strategies for the UDS query, and integrate them into effective algorithms. In addition, a novel query type, namely the top$k$favorite probabilistic products (TFPP) query, is presented. The TFPP query is utilized to select$k$products which can meet the needs of a customer set at the maximum level. To tackle the TFPP query, we propose a TFPP algorithm and its efficient parallelization. Extensive experiments with a variety of experimental settings illustrate the efficiency and effectiveness of our proposed algorithms.

Query processing over uncertain data has gained growing attention, because it is necessary to deal with uncertain data in many real-life applications. In this paper, we investigate skyline queries over uncertain data in distributed environments (DSUD query) whose research is only in an early stage. The state-of-the-art algorithm, called e-DSUD algorithm, is designed for processing this query. It has the desirable characteristics of progressiveness and minimum bandwidth consumption. However, it still needs to be perfected in three aspects. (1) Progressiveness. Each time it only returns one query result at most. (2) Efficiency. There are a significant amount of redundant I/O cost and numerous iterations which causes a long total query time. (3) Universality. It is restricted to the case where local skyline tuples are incomparability. To address these concerns, we first present a detailed analysis of the e-DSUD algorithm and then develop an improved framework for the DSUD query, namely IDSUD. Based on the new framework, we propose an adaptive algorithm, called ADSUD, for the DSUD query. In the algorithm, we redefine the approximate global skyline probability and choose local representative tuples due to minimum probabilistic bounding rectangle adaptively. Furthermore, we design a progressive pruning method and apply the reuse mechanism to improve its efficiency. The results of extensive experiments verify the better overall performance of our algorithm than the e-DSUD algorithm.