Spatial crowdsourcing platforms have become indispensable in addressing the evolving needs of modern society. These platforms facilitate essential services such as ride-sharing, on-demand food delivery, and efficient parcel distribution. However, the uneven distribution of workers and requests under a single-platform setting may lead to the loss of tasks. To address this issue, we introduce the Cross Online Matching (COM) problem, which facilitates collaboration among multiple platforms. We first propose DemCOM and RamCOM, which adopt deterministic greedy and randomized trade-off strategies, respectively. Furthermore, we develop a Utility-Distribution Aware Cooperative Online Matching (UDACOM) algorithm that leverages supply-demand relationships to optimize decision-making. Theoretical analysis confirms the competitive ratios of our algorithms. Validated on both real and synthetic datasets, our approach significantly outperforms state-of-the-art methods, achieving a 5% increase in total revenue and a 3% improvement in the successful matching rate.

Spatial crowdsourcing has become popular in recent years, but traditional tasks focus on one-to-one services with single skills like food delivery and ride-hailing. As societal needs grow more complex, there is a need for tasks requiring teams with multiple skills. Current team formation methods using workers from a single platform limit skill diversity, leading to potential task delays, lower quality, and revenue losses. Although cross-platform cooperation offers a potential solution to skill diversity limitations, it faces two challenges: (1) Data protection regulations mandate that platform's raw data must remain localized; (2) cross-platform cooperation incurs additional cooperation costs. To address these challenges, we first define the Cross-platform Online Team Formation (COTF) problem. We then propose a COTF framework and Random Cooperation Strategy to solve COTF problem. To enhance the effectiveness of cooperation, we further propose Precision Query Range Optimization Strategy (PQROS) for worker selection through adaptive range queries, and Dynamic Query Optimization (DQO) for cost-effective scheduling via predictive revenue modeling. Extensive experiments on real and synthetic datasets validate the effectiveness of our proposed methods.

With the explosive growth of online service platforms, an increasing number of people and enterprises are undertaking personal and professional tasks online. In real applications such as trip planning and online marketing, planning sessions for a sequence of activities or services will enable social users to receive the optimal services, improving their experience and reducing the cost of their activities. These online platforms are heterogeneous, including different types of services with different attributes. However, the problem of session planning over heterogeneous platforms has not been studied so far. In this paper, we propose a Motivation-Aware Session Planning (MASP) framework for session planning over heterogeneous social platforms. Specifically, we first propose a novel HeterBERT model to handle the heterogeneity of items at both type and attribute levels. Then, we propose to predict user preference using the motivations behind user activities. Finally, we propose an algorithm together with its optimisations for efficient session generation. The extensive tests prove the high effectiveness and efficiency of MASP.

Abstract In recent years, the task of knowledge graph completion has attracted significant attention from researchers. In practical scenarios, multi-source knowledge graph completion is quite common. Federated knowledge graph embedding enables joint learning across multiple knowledge graphs while ensuring data privacy and security. Generally, each data source has a different data distribution. They may exhibit various connections, such as combinatorial, hierarchical, and symmetric/asymmetric connections. Existing federated knowledge graph models overlook the data heterogeneity of knowledge graphs from different sources, using a unified scoring function to assess the quality of the generated embedding vectors from different clients. This limitation affects the quality of knowledge graph embeddings generated by each client. Therefore, this paper proposes a federated knowledge graph embedding framework based on the diffusion model. On the client side, we employ diffusion model to learn knowledge graph embeddings. We utilize the diffusion model's forward noise-adding process to learn the knowledge graph's distribution. We then use the reverse denoising process to generate knowledge embeddings directly. Additionally, we employ knowledge distillation during client model training to address the drift between local optimization and global convergence. Since the original data cannot leave the local environment in federated learning, we adopt a framework that shares diffusion models for federated knowledge graph completion. Extensive experiments demonstrate that our model significantly outperforms existing state-of-the-art methods in three benchmark datasets.

With the development of AI, big data, and mobile communication, intelligent transportation has become popular in recent years. Path planning is a typical topic of intelligent transportation, attracting significant attention from researchers. However, existing studies only focus on the path planning of a single platform, which may lead to unexpected traffic congestion. This is because multiple platforms can provide route planning services, the optimal planning calculated by one single platform may be not good in practice, since multiple platforms may lead the users to the same roads, which causes unexpected traffic congestion. Although in the view of each platform, the planning is optimal. Fortunately, with the rise of data sharing and cross-platform cooperation, the data silos between different platforms are gradually being broken. Based on this, we proposeCooperativeGlobalPathPlanning(CGPP) framework to overcome the above shortcoming. CGPP allows the path planning request target platform to send some queries to cooperative platforms to optimize its path planning results. Such queries should be “easy” enough to answer, and the query frequency should be small. Based on the above principle, we design a query decision model based on multi-agent reinforcement learning in CGPP framework to decide the query range and query frequency. We design action and reward specifically for the CGPP problem. Furthermore, we propose mechanisms to enhance query precision and reduce query overhead. Specifically, the Self-adjusting Query Area(SQA) concept allows refining query parameters, while the Query Reuse Optimization(QRO) algorithm aims to minimize the number of queries. To solve potential overestimation problems in queries, we propose a Distance-based Outer Query (DB-oq) and Distance-Based Vehicle Count Estimation (DB-VCE) Model. To address the issue that the time interval computed by the QRO algorithm might not fully adapt to dynamic traffic environments, we propose the Temporal Sequence Historical Integration for Time Interval Prediction(TSHI-TIP) algorithm. Extensive experiments on real and synthetic datasets confirm the effectiveness and efficiency of our algorithms.

The last few years have seen the wide applications of ride-sharing, a transportation service that allows users to share their travel routes. A typical problem for ride-sharing is to find an optimal route for each worker to serve the dynamically arriving requests with different objectives. Previous studies focus on the route planning on a single platform. However, a single platform may have an uneven distribution of supply and demand, which causes the platform to lose requests from lack of available workers. Luckily, some ride-sharing platforms provide the same service, which enables their collaborations. The inter-platform collaborations on ride-sharing can ease the worker shortages and greatly improve the service quality, but have not been studied yet. In this paper, we propose a Cross Online Ride-sharing (CORS) problem, which allows a platform to borrow the available workers from other platforms to serve its own requests. We first design two algorithms to select the optimal available worker from other platforms, ROWS and DOWS. ROWS randomly picks an available worker, while DOWS selects the optimal worker with the minimum additional travel distance calculated based on his/er predicted destination direction. Then, we design an efficient CORS framework that embeds the proposed optimal worker selection algorithms for the CORS problem. Extensive experiments on real and synthetic datasets demonstrate the effectiveness and efficiency of our algorithms.

With the development of AI, big data, and mobile communication, intelligent transportation has become popular in recent years. Path planning is a typical topic of intelligent transportation, attracting significant attention from researchers. However, existing studies only focus on the path planning of a single platform, which may lead to unexpected traffic congestion. This is because multiple platforms can provide route planning services, the optimal planning calculated by one single platform may be not good in practice, since multiple platforms may lead the users to the same roads, which causes unexpected traffic congestion. Although in the view of each platform, the planning is optimal. Fortunately, with the rise of data sharing and cross-platform cooperation, the data silos between different platforms are gradually being broken. Based on this, we propose Cooperative Global Path Planning (CG PP) framework to over-come the above shortcoming. CGPP allows the path planning request target platform to send some queries to cooperative platforms to optimize its path planning results. Such queries should be “easy” enough to answer, and the query frequency should be small. Based on the above principle, we design a query decision model based on multi-agent reinforcement learning in CGPP framework to decide the query range and query frequency. We design action and reward specifically for the CGPP problem. Furthermore, we propose the Self-adjusting Query Area algorithm to enhance the precision of query results and the Query Reuse Optimization algorithm to further minimize the number of queries. Extensive experiments on real and synthetic datasets confirm the effectiveness and efficiency of our algorithms.

The rapid development of the spatial crowdsourcing platform in the fields of express delivery, food delivery, and intelligent transportation has attracted widespread attention. As a typical problem in spatial crowdsourcing, online task matching problem has been widely studied. Most of the existing researches are based on the task allocation of different optimizations under one single platform. Recently, in order to solve the situation of non-uniform distribution of tasks and crowd workers on a single platform, cross online task assignment has been proposed aiming at increasing the mutual benefit through cooperations. However, existing methods lead to the situation where the local platform lends workers to other platforms, resulting in a lack of workers of itself. In this paper, we propose a Batch-Based Cooperative Task Assignment(BCTA) problem, which enables multi-platform task assignment to be completed within a tolerant time. We design a BCTA model and propose fixed-t BCTA(FT-BCTA) algorithm and adaptive BCTA(Adt-BCTA) algorithm to solve the BCTA problem. FT-BCTA focuses on a fixed batching strategy, while Adt-BCTA considers the batching strategy adaptively according to the supply and demand of multi-platforms. Extensive experiments on both real datasets and synthetic datasets show the effectiveness and efficiency of our algorithms.

Spatial platforms have become increasingly important in people's daily lives. Task assignment is a critical problem in these platforms that matches real-time orders to suitable workers. Most studies only focus on independent platforms that are in a competitive relationship. Recently, an emerging service model was proposed, where orders are shared with multiple similar platforms. It aims to solve the imbalance between supply and demand through cooperation. However, it faces the following main challenges: 1) Coordinating independent platforms fairly based on the limited information; 2) Building a task assignment process with personalized algorithms. In this paper, we study real applications and define the Autonomy and Coordination Task Assignment problem (ACTA) to maximize the global revenue and fairness. We propose a framework to solve ACTA that consists of public order sending, local matching, global conflict adjustment and results notification. The framework uses mid-products and public data to train a revenue estimation model to coordinate participants. We further propose dynamic weight task assignment algorithms to guarantee fairness. Through the experiments, we prove that the platforms can obtain higher revenue, which shows the effectiveness and efficiency of our work.

Online spatial crowdsourcing platforms provide popular O2O services in people's daily. Users submit real-time tasks through the Internet and require the platform to immediately assign workers to serve them. However, the imbalance distribution of tasks and workers leads to the rejection of some tasks, which reduces the profit of the platform. In this paper, we propose that similar platforms can form an alliance to make full use of the global service supply through cooperation. We name the problem asGlobalTaskAssignment (GTA), in which platforms are allowed to hire idle workers from other platforms to improve the profit of all the platforms together. Different from relevant works, the decision-makers in GTA are platforms rather than individual workers, which can better assign workers in all platforms and improve the overall profit. We design an auction-based incentive mechanism (AIM), to motivate platforms to rent idle workers to other platforms so that increase their own profit. Based on the mechanism, we propose a greedy-based assignment algorithm (BaseGTA), in which platforms greedily maximizes their current profit. We further propose a prediction-based assignment algorithm (ImpGTA), in which platforms make decisions based on the spatial-temporal distribution in the future time. Experimental results show that platforms using our algorithms can achieve higher profit than the existing studies.

With the continuous development of spatial crowdsourcing platform, online task assignment problem has been widely studied as a typical problem in spatial crowdsourcing. Most of the existing studies are based on a single-platform task assignment to maximize the platform's revenue. Recently, cross online task assignment has been proposed, aiming at increasing the mutual benefit through cooperations. However, existing methods fail to consider the data privacy protection in the process of cooperation and cause the leakage of sensitive data such as the location of a request and the historical data of cooperative platforms. In this paper, we propose Privacy-preserving Cooperative Online Matching (PCOM), which protects the privacy of the users and workers on their respective platforms. We design a PCOM framework and provide theoretical proof that the framework satisfies the differential privacy property. We then propose two PCOM algorithms based on two different privacy-preserving strategies. Extensive experiments on real and synthetic datasets confirm the effectiveness and efficiency of our algorithms.

Real-life graph datasets extracted from the Web are inevitably full of incompleteness, conflicts, and redundancies, so graph data cleaning shows its necessity. Although rules like data dependencies have been widely studied in relational data repairing, very few works exist to repair graph data. In this article, we introduce a repairing semantics for graphs, calledGraph-Repairing Rules(${\sf GRR}$s). This semantics can capture the incompleteness, conflicts, and redundancies in graphs and indicate how to correct these errors. However, this graph repairing semantics can only repair the graphs strictly isomorphic to the rule patterns, which decreases the utility of the rules. To overcome this shortcoming, we further propose a flexible rule-based graph repairing semantics (called$\delta$-GRR). We study three fundamental problems associated with both${\sf GRR}$s and$\delta$-GRRs, consistency, implication, and termination, which show whether a given set of rules make sense. Repairing the graph data using${\sf GRR}$s or$\delta$-GRRs involves a problem of finding isomorphic subgraphs of the graph data, which is NP-complete. To efficiently circumvent the complex calculation of subgraph isomorphism, we design a decomposition-and-join strategy to solve this problem. Extensive experiments on real datasets show that our two graph repairing semantics and corresponding repairing algorithms can effectively and efficiently repair real-life graph data.

Route planning problem has been well studied in static road networks, since it has wide applications in transportation networks. However, recently there have been more actual requirements that current path planning algorithms cannot solve, such as food delivery, ride-sharing and crowdsourced parcel delivery. These requirements are in a dynamic scenario, but the existing algorithms are offline. These requirements need to find the least total travel time path from the source through the nodes that appear dynamically over time to the destination, which referred to as the online route planning. On the other hand, the costs of edges in road networks always change over time, since real road networks are dynamic. Such road networks can be modelled as time-dependent road networks. Therefore, in this paper, we study the online route planning over time-dependent road networks (ORPTD). We formally proof that the ORPTD problem is NP-complete and its competitive ratio cannot be guaranteed. To attack the hard problem, we first propose two efficient heuristic algorithms. To adapt to large-scale time-dependent road networks, we further speed up the two heuristic algorithms by incorporating indexing techniques into them. Finally, we verify the effectiveness and efficiency of the proposed methods through extensive experiments on real datasets.

In recent years, online Event Based Social Network (EBSN) platforms have become increasingly popular. One typical task of EBSN platforms is to help users make suitable and personalized plans for participating in different interesting social events. Existing techniques either ignore the minimum-participant requirement constraint for each event, which is crucially needed for some events to be held successfully, or assume that events would not change once announced. In this paper, we address the above inadequacies of existing EBSN techniques. We formally define the Global Event Planning with Constraints (GEPC) problem, and its incremental variant. Since these problems are NP-hard, and provide approximate solutions. Finally, we verify the effectiveness and efficiency of our proposed algorithms through extensive experiments over real and synthetic datasets.

With the development of mobile communication techniques, spatial crowdsourcing has become popular recently. A typical topic of spatial crowdsourcing is task assignment, which assigns crowd workers to users' requests in real time and maximizes the total revenue. However, it is common that the available crowd workers over a platform are too far away to serve the requests, so some user requests may be rejected or responded at high money cost after long waiting. Fortunately, the neighbors of a platform usually have available resources for the same services. Collaboratively conducting the task allocation among different platforms can greatly improve the quality of services, but have not been investigated yet. In this paper, we propose a Cross Online Matching (COM), which enables a platform to "borrow" unoccupied crowd workers from other platforms for completing the user requests. We propose two algorithms, deterministic cross online matching (DemCOM) and randomized cross online matching (RamCom) for COM. DemCOM focuses on the largest obtained revenue in a greedy manner, while RamCom considers the trade-off between the obtained revenue and the probability of request being accepted by the borrowed workers. Extensive experimental results verify the effectiveness and efficiency of our algorithms.

Periodicity is a frequently happening phenomenon for social interactions in temporal networks. Mining periodic communities are essential to understanding periodic group behaviors in temporal networks. Unfortunately, most previous studies for community mining in temporal networks ignore the periodic patterns of communities. In this paper, we study a problem of seeking periodic communities in a temporal network, where each edge is associated with a set of timestamps. We propose a novel model, called maximal σ-periodic k-clique, that represents a periodic community in temporal networks. Specifically, a maximal σ-periodic k-clique is a clique with size larger than k that appears at least σ times periodically in the temporal graph. We show that the problem of enumerating all those periodic cliques is NP-hard. To compute all of them efficiently, we first develop two effective graph reduction techniques to significantly prune the temporal graph. Then, we present an efficient enumeration algorithm to enumerate all maximal σ-periodic k-cliques in the reduced graph. The results of extensive experiments on five real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.

The popularity of mobile Internet techniques and Online-To-Offline(O2O) business models has led to the emergence of various spatial crowdsourcing (SC) platforms in our daily life. A core issue of SC platforms is to assign tasks to suitable crowd workers. Existing approaches usually focus on the matching of two types of objects,tasks and workers, and let workers to travel to the location of usersto provide services, which is a 2D matching problem. However, recent services provided by some new platforms, such as person-alized haircut service1and station ride-sharing, need users andworkers travel together to a third workplace to complete the service, which is indeed a 3D matching problem. Approaches in the existingstudies either cannot solve such 3D matching problem, or lack aassignment plan satisfying both users' and workers' preference inreal applications. Thus, in this paper, we propose a 3-Dimensional Stable Spatial Matching(3D-SSM) for the 3D matching problem innew SC services. We prove that the 3D-SSM problem is NP-hard, and propose two baseline algorithms and two efficient approximatealgorithms with bounded approximate ratios to solve it. Finally, weconduct extensive experiment studies which verify the efficiencyand effectiveness of the proposed algorithms on real and synthetic datasets.

Real-life graph datasets extracted from Web are inevitably full of incompleteness, conflicts, and redundancies, so graph data cleaning shows its necessity. One of the main issues is to automatically repair the graph with some repairing rules. Although rules like data dependencies have been widely studied in relational data repairing, very few works exist to repair the graph data. In this paper, we introduce an automatic repairing semantic for graphs, calledGraph-Repairing Rules(GRRs). This semantic can capture the incompleteness, conflicts, and redundancies in the graphs and indicate how to correct these errors. We study three fundamental problems associated with GRRs, implication, consistency and termination, which show whether a given set of GRRs make sense. Repairing the graph data using GRRs involves a problem of finding isomorphic subgraphs of the graph data for each GRR, which is NP-complete. To efficiently circumvent the complex calculation of subgraph isomorphism, we design a decomposition-and-join strategy to solve this problem. Extensive experiments on real datasets show that our GRR semantic and corresponding repairing algorithms can effectively and efficiently repair real-life graph data.

In recent years, online Event Based Social Network (EBSN) platforms have become increasingly popular. One typical task of EBSN platforms is to help users make suitable and personalized plans for participating in different interesting social events. Existing techniques either ignore the minimum-participant requirement constraint for each event, which is crucially needed for some events to be held successfully, or assume that events would not change once announced. In this paper, we address the above inadequacies of existing EBSN techniques. We formally define the Global Event Planning with Constraints (GEPC) problem, and its incremental variant. We prove that both are NP-hard, and provide approximate solutions. Finally, we verify the effectiveness and efficiency of our proposed algorithms through extensive experiments over real and synthetic datasets.

In recent years, due to the wide applications of uncertain data, mining frequent itemsets over uncertain databases has attracted much attention. In uncertain databases, the support of an itemset is a random variable instead of a fixed occurrence counting of this itemset. Thus, unlike the corresponding problem in deterministic databases where the frequent itemset has a unique definition, the frequent itemset under uncertain environments has two different definitions so far. The first definition, referred as the expected support-based frequent itemset, employs the expectation of the support of an itemset to measure whether this itemset is frequent. The second definition, referred as the probabilistic frequent itemset, uses the probability of the support of an itemset to measure its frequency. Thus, existing work on mining frequent itemsets over uncertain databases is divided into two different groups and no study is conducted to comprehensively compare the two different definitions. In addition, since no uniform experimental platform exists, current solutions for the same definition even generate inconsistent results. In this paper, we firstly aim to clarify the relationship between the two different definitions. Through extensive experiments, we verify that the two definitions have a tight connection and can be unified together when the size of data is large enough. Secondly, we provide baseline implementations of eight existing representative algorithms and test their performances with uniform measures fairly. Finally, according to the fair tests over many different benchmark data sets, we clarify several existing inconsistent conclusions and discuss some new findings.