Federated learning (FL) has emerged as a prominent distributed learning paradigm to utilize datasets across multiple data providers. In FL, cross-silo data providers often hesitate to share their high-quality dataset unless their data value can be fairly assessed. Shapley value (SV) has been advocated as the standard metric for data valuation in FL due to its desirable properties. However, the computational overhead of SV is prohibitive in practice, as it inherently requires training and evaluating an FL model across an exponential number of dataset combinations. Furthermore, existing solutions fail to achieve high accuracy and efficiency, making practical use of SV still out of reach, because they ignore choosing suitable computation scheme for approximation framework and overlook the property of utility function in FL. We first propose a unified stratified-sampling framework for two widely-used schemes. Then, we analyze and choose the more promising scheme under the FL linear regression assumption. After that, we identify a phenomenon termed key combinations, where only limited dataset combinations have a high-impact on final data value. Building on these insights, we propose a practical approximation algorithm, IPSS, which strategically selects high-impact dataset combinations rather than evaluating all possible combinations, thus substantially reducing time cost with minor approximation error. Furthermore, we conduct extensive evaluations on the FL benchmark datasets to demonstrate that our proposed algorithm outperforms a series of representative baselines in terms of efficiency and effectiveness.

Early-exit networks (EENs), which adapt their computational depths based on input samples, are widely adopted to accelerate inference in edge computing applications. The effectiveness of EENs relies on difficulty-aware training, which tailors shallow exits for simple samples and deep exits for complex ones. However, existing difficulty-aware training schemes assume centralized environments with sufficient data, which become invalid with real-world edge devices. In this paper, we explore difficulty-aware training in a federated manner, where EENs are collaboratively trained on heterogeneous devices. We observe the cross-model exit unalignment phenomenon, a unique problem when aggregating local EENs into a cohesive global model. To address this problem, we design a novel Difficulty-Aligned Reverse Knowledge Distillation scheme named DarkDistill that preserves the difficulty-specific specialization for aggregating heterogeneous local models. Instead of direct parameter averaging, it trains difficulty-conditional data generators, and selectively transfers generated knowledge of specific difficulty among matched exits of heterogeneous EENs. Evaluations show that DarkDistill outperforms the state-of-the-arts in both full-parameter and parameter-efficient fine-tuning of EENs.

Metro passenger flow prediction is crucial for effective urban transportation management. However, its practical adoption is hindered by data silos from distributed automatic fare collection (AFC) systems, compromising prediction accuracy. While federated graph learning facilitates privacy-preserving collaboration, existing methods struggle with the unique challenges of cross-line metro passenger flow prediction, particularly in handling time-evolving spatial correlations and heterogeneous temporal correlations. To address these challenges, we present FedMetro, a novel metro passenger flow prediction system based on federated graph learning. We introduce a federated dynamic graph learning approach with cross-attention mechanisms to capture spatial-temporal correlations in passenger flow. Additionally, we propose a dynamic mask-based communication compression method to mitigate communication bottlenecks in federated inference. Extensive evaluations on three real-world metro AFC datasets demonstrate that FedMetro significantly outperforms baseline methods, achieving up to 17.08% higher accuracy while reducing federated inference communication overhead by 77.99%. Practical deployments further confirm its effectiveness in delivering accurate station-level predictions across metro lines. Our code is available at https://github.com/AlexMufeng/FedMetro.

Graph-based methods have witnessed tremendous success in traffic prediction, largely attributed to their superior ability in capturing and modeling spatial dependencies. However, urban-scale traffic data are usually distributed among various owners, limited in sharing due to privacy restrictions. This fragmentation of data severely hinders interaction across clients, impeding the utilization of inter-client spatial dependencies. Existing studies have yet to address this non-trivial issue, thereby leading to sub-optimal performance. To fill this gap, we propose FedGTP, a new federated graph-based traffic prediction framework that promotes adaptive exploitation of inter-client spatial dependencies to recover close-to-optimal performance complying with privacy regulations like GDPR. We validate FedGTP via large-scale application-driven experiments on real-world datasets. Extensive baseline comparison, ablation study and case study demonstrate that FedGTP indeed surpasses existing methods through fully recovering inter-client spatial dependencies, achieving 21.08%, 13.48%, 19.90% decrease on RMSE, MAE and MAPE, respectively. Our code is available at https://github.com/LarryHawkingYoung/KDD2024_FedGTP

Flight planning, a pivotal challenge in the airline industry, strives to achieve economic and flexible scheduling of airplanes to serve designated flight itineraries. As the demand for air transportation soars, traditional planning methods can be inefficient in managing large-scale flights. Thus, we introduce Swift, a data-driven system tailored to enhance the scalability and effectiveness of flight planning. Swift primarily employs the bipartite graph model to derive optimal and economic flight plans for airlines. Our method not only minimizes the number of required planes but also ensures a balanced workload across these planes. Furthermore, Swift offers the capability of dynamic updates to flight plans in response to unexpected incidents at airports, such as bad weather conditions. Besides, Swift incorporates other functionalities like predicting future flight demand and monitoring real-time flight trajectories. Conference participants can interact with this system and explore our flight planning solution in real-world scenarios.

Vector databases have emerged as crucial tools for managing and retrieving representation embeddings of unstructured data. Given the explosive growth of data, vector data is often distributed and stored across multiple organizations. However, privacy concerns and regulations like GDPR present new challenges in collaborative and secure queries, also known as federated queries, over those vector data distributed across various data owners. Although existing research has attempted to enable such query services for low-dimensional data, such as relational and spatial data, these solutions can be inefficient in answering vector similarity queries involving high-dimensional data. Therefore, we are motivated to develop a new prototype system called FedSQ that (1) ensures privacy protection across data owners and (2) balances query efficiency and result accuracy when processing federated vector similarity queries. To achieve these goals, FedSQ utilizes advanced secure multi-party computation techniques to prevent information leakage during query processing and incorporates indexing and sampling based optimizations to strike a proper performance balance.

Numerous spatial-temporal learning methods have been proposed for crowd flow modeling, which is an important problem in Intelligent Transportation Systems (ITS). However, most of the existing methods were designed to use data in one specific form to solve one particular task of crowd flow modeling and the shared patterns among different tasks have been largely ignored. In this paper, we investigate how to learn generic node representations that can simultaneously support various downstream tasks of crowd flow modeling. Along this line, we develop a continuous-time dynamic graph representation learning method based onBootstrapping forCrowdFlow modeling (BootCF). Our approach follows a training procedure with two phases. In the pre-training phase, the continuous-time dynamic encoder converts edges with timestamps into messages to update the representations of the related traffic nodes. Inspired by the recent progress of contrastive learning, a bootstrapping framework for continuous-time dynamic graphs is designed to calculate pre-training loss and update the model in a self-supervised way, and thus enabling the node representation learning to be task-agnostic. Moreover, a context-aware data augmentation on continuous-time dynamic graphs is proposed to generate the augmented view of input data. Once the general node representations are obtained, the second phase can learn an effective model for any downstream task. Experiments on two real-world datasets show that our approach can achieve significant performance gain on four downstream tasks, which demonstrates that the proposed method has the powerful generalization capability for learning task-agnostic node representations.

Multi-robot systems are deployed in modern warehouses to reduce operational cost. The robots are tasked to deliver items stored on racks to pickers for fast distribution. A central algorithmic problem is collision-aware route planning, which aims to plan shortest routes for robots to deliver racks while avoiding collision with racks, pickers, and other robots. Prior solutions are inefficient in real-world warehouses, where route planning requests emerge online and at large scale. In this paper, we identify collision judgement in grid-based warehouse representation as the primary efficiency bottleneck, and propose a novel Strip-based Route Planning framework (SRP). Specifically, we exploit the regularity in warehouse layouts, and aggregate grids into strips. The strip-based representation also converts collisions of 3-dimensional (2-dimensional space and 1-dimensional time) routes into 2-dimensional (1-dimensional space and 1-dimensional time) segment intersections, which can be fast checked via computational geometry. We further accelerate the collision judgement via indexing on segments within strips. Theoretical analysis shows a reduction of time complexity from square to linear-logarithmic. Experimental results on datasets collected from real-world robotized warehouses show that our SRP is up to 227× faster than existing methods.

In order to mine latent semantics from text data, word embedding and topic modeling are two major methodologies in industry. From a pragmatic perspective, each of these two lines of semantic models faces increasing challenges from real-life applications. However, modern text mining tasks typically require a panoramic view of the latent semantics. Hence, discovering heterogeneous semantics (e.g., heterogeneous types of latent topics) is critical for the performance of these tasks, and it is necessary to design a model that meets this demand. Furthermore, with the arrival of the big data era and the increasing awareness of data privacy, it is necessary to study the issues of mining heterogeneous semantics with high efficiency while avoiding compromising data privacy. In this work, we develop a novel method called Heterogeneous Latent Topic Discovery (HLTD) which seamlessly integrates topic modeling with word embedding to discover heterogeneous latent topics. By coupling parameter-server architecture with new private sampling algorithms, HLTD can be efficiently trained with effective protection of underlying data privacy. We evaluate HLTD through a wide range of qualitative and quantitative metrics in industry. Extensive experiments demonstrates the superiority of HLTD over the state-of-the-arts.

Ride hailing has become prevailing. Central in ride hailing platforms is taxi order dispatching which involves recommending a suitable driver for each order. Previous works use pure combinatorial optimization solutions for taxi dispatching, which suffer in practice due to complex dynamics of demand and supply and temporal dependency among dispatching decisions. Recent studies try to adopt data-driven method into combinatorial optimization hoping knowledge from history data would help overcome these challenges. Among these attempts, adoption of reinforcement learning shows great promise but current adoptions are a unidirectional integration which restricts the potential performance gains. In this work, we proposeLearningToDispatch(LTD), a systematic solution that allows synergic integration of reinforcement learning and combinatorial optimization for large-scale taxi order dispatching. We demonstrate the necessity of online learning and taxi scheduling for reinforcement learning to work in synergy with combinatorial optimization, and devise corresponding algorithms. We also devise many tricks for more efficient calculation of the bipartite matching. Experiments show our methods can improve$36.4\%$and$42.0\%$on utility and efficiency at most, respectively. Especially, it achieves state-of-the-art performance in terms of utility.

Skyline is a primitive operation in multi-objective decision applications and there is a growing demand to support such operations over a data federation, where the entire dataset is separately held by multiple data providers (a.k.a., silos). Data federations notably increase the amount of data available for data-intensive applications such as commercial recommendation and location based services. Yet they also challenge the conventional implementation of skyline queries because the raw data cannot be shared within the federation and the secure computation cross silos can be two or three orders of magnitude slower than plaintext computation. These constraints render existing solutions inefficient on data federation. In this work, we propose a novel local dominance based framework for efficient skyline queries over a vertical data federation. We decompose the skyline query into plaintext local dominance computations and secure result aggregations, which can perform as many computations in plaintext as possible without compromising security. We further propose a dedicate private set intersection based algorithm to accelerate the query processing. Extensive evaluations on both synthetic and real-world datasets show that compared with general-purpose secure multi-party computation techniques, our solutions reduce the time cost by up to 35.4× and communication cost by two orders of magnitude respectively.

kNN is a fundamental query in various location based services such as POI recommendation and ride planning. There is an increasing demand to scale such services by querying over a data federation, where the entire dataset is distributedly held by multiple data providers (a.k.a., silos), and each silo keeps its data partition private. However, it is challenging to provide secure kNN queries over a large-scale data federation. Prior secure kNN queries can be are highly inefficient if performed cross silos because they involve excessive secure distance operations, which can be two or three orders of magnitude slower than the corresponding plaintext operations. In this work, we propose a novel threshold based framework for efficient kNN queries over a spatial data federation. The key idea is to rewrite excessive secure distance computations as light-weight secure operations. We further propose an adaptive threshold algorithm to reduce the secure communication rounds and accelerate the query processing. Extensive evaluations on both synthetic and real-world datasets show that compared with the state-of-the-art secure kNN querying methods, our solutions reduce the time cost by up to 104.1 times and communication cost by three orders of magnitude.

Learning based order dispatching has witnessed tremendous success in ride hailing. However, the success halts within individual ride hailing platforms because sharing raw order dispatching data across platforms may leak user privacy and business secrets. Such data isolation not only impairs user experience but also decreases the potential revenues of the platforms. In this paper, we advocate federated order dispatching for cross-platform ride hailing, where multiple platforms collaboratively make dispatching decisions without sharing their local data. Realizing this concept calls for new federated learning strategies that tackle the unique challenges on effectiveness, privacy and efficiency in the context of order dispatching. In response, we devise Federated Learning-to-Dispatch (Fed-LTD), a framework that allows effective order dispatching by sharing both dispatching models and decisions while providing privacy protection of raw data and high efficiency. We validate Fed-LTD via large-scale trace-driven experiments with Didi GAIA dataset. Extensive evaluations show that Fed-LTD outperforms single-platform order dispatching by 10.24% to 54.07% in terms of total revenue.

The increasing concerns on data security limit the sharing of data distributedly stored at multiple data owners and impede the scale of spatial queries over big urban data. In response, data federation systems have emerged to perform secure queries across multiple data owners leveraging secure multi-party computation. However, existing systems are designed for relational data. They are highly inefficient on spatial queries and limited in usability. In this demonstration, we introduce Hu-Fu, the first data federation system for secure spatial queries with high efficiency and usability. Hu-Fu is designed from the perspectives of the query user and the data owner for high usability and decomposes a spatial query into as many plaintext operators and as few secure operators as possible for high efficiency. We demonstrate the deployment and usage of Hu-Fu via cross-company taxi-calling, a popular smart city application.

Data isolation has become an obstacle to scale up query processing over big data, since sharing raw data among data owners is often prohibitive due to security concerns. A promising solution is to perform secure queries over a federation of multiple data owners leveraging secure multi-party computation (SMC) techniques, as evidenced by recent federation work over relational data. However, existing solutions are highly inefficient on spatial queries due to excessive secure distance operations for query processing and their usage of general-purpose SMC libraries for secure operation implementation. In this paper, we propose Hu-Fu, the first system for efficient and secure spatial query processing on a data federation. The idea is to decompose the secure processing of a spatial query into as many plaintext operations and as few secure operations as possible, where fewer secure operators are involved and all secure operators are implemented dedicatedly. As a working system, Hu-Fu supports not only query input in native SQL, but also heterogeneous spatial databases ( e.g. , PostGIS, Simba, GeoMesa, and SpatialHadoop) at the backend. Extensive experiments show that Hu-Fu usually outperforms the state-of-the-arts in running time and communication cost while guaranteeing security.

Dynamic ridesharing refers to services that arrange one-time shared rides on short notice. It underpins various real-world intelligent transportation applications such as car-pooling, food delivery and last-mile logistics. A core operation in dynamic ridesharing is the “insertion operator”. Given a worker and a feasible route which contains a sequence of origin-destination pairs from previous requests, the insertion operator inserts a new origin-destination pair from a newly arrived request into the current route such that certain objective is optimized. Common optimization objectives include minimizing the maximum/sum flow time of all requests and minimizing the total travel time of the worker. Despite its frequent usage, the insertion operator has a time complexity of$O(n^3)$, where$n$is the number of all requests assigned to the worker. The cubic running time of insertion fundamentally limits the efficiency of urban-scale dynamic ridesharing based applications. In this paper, we propose a novel partition framework and a dynamic programming based insertion with a time complexity of$O(n^2)$. We further improve the time efficiency of the insertion operator to$O(n)$harnessing efficient index structures, such as fenwick tree. Evaluations on two real-world large-scale datasets show that our methods can accelerate insertion by 1.5 to 998.1 times.

Bipartite matching between two sets of objects is widely applied in many applications such as crowdsourcing marketplaces, ride-hailing services and logistics.Depending on the applications, different objectives have been proposed, resulting in different matching problems.Among them, one that is recently proposed is online bottleneck matching with delays (OBM-D), where the objective is to optimize the maximum cost of matches and the cost of a match depends on when the match is formed (i.e., it is delay-aware).Existing solutions for OBM-D usually adopt a holding strategy, which holds the objects involved in a match available for a period so as to reduce the chance that a bad match is formed.Nevertheless, existing holding strategies are all based on humancrafted rules thus cannot adapt to the dynamics of how the objects arrive.In this paper, we propose an adaptive holding strategy which is based on reinforcement learning and develop a method called Adaptive-H on top of the new holding strategy.Besides, we prove theoretical results on how good a randomized algorithm could achieve for the OBM-D problem in terms of competitive ratio.We conduct extensive experiments on both real and synthetic datasets to verify that Adaptive-H outperforms existing algorithms in terms of both effectiveness and efficiency.

Dynamic ridesharing refers to services that arrange one-time shared rides on short notice. It underpins various real-world intelligent transportation applications such as car-pooling, food delivery and last-mile logistics. A core operation in dynamic ridesharing is the "insertion operator". Given a worker and a feasible route which contains a sequence of origin-destination pairs from previous requests, the insertion operator inserts a new origin-destination pair from a newly arrived request into the current route such that certain objective is optimized. Common optimization objectives include minimizing the maximum flow time of all requests and minimizing the total travel time of the worker. Despite its frequent usage, the insertion operator has a time complexity of O(n^3), where n is the number of all requests assigned to the worker. The cubic running time of insertion fundamentally limits the efficiency of urban-scale dynamic ridesharing based applications. In this paper, we propose a novel partition framework and a dynamic programming based insertion with a time complexity of O(n^2). We further improve the time efficiency of the insertion operator to O(n) harnessing efficient index structures, such as fenwick tree. Evaluations on two real-world large-scale datasets show that our methods can accelerate insertion by 1.5 to 998.1 times.