In this paper, we study the query optimization problem in HTAP systems and propose a cost-based approach that can judiciously generate a hybrid plan by leveraging a primary row store and an in-memory column store to maximize the query performance. We propose a new hybrid plan based optimization system, named SmartPlan, which is built upon such a hybrid architecture. We make three contributions. First, we design a new cost model to quantify the hybrid plan cost, and propose a plan search method that efficiently finds the optimal plan in a huge planning space. Second, we take into account the memory budget and design a plan-aware Monte Carlo Tree Search method to select the most beneficial columns into the memory. Third, we have implemented our method in PostgreSQL v15 and have evaluated its effectiveness using standard benchmarks. Experiments demonstrate that SmartPlan outperforms the state-of-the-art approaches in terms of end-to end performance with both analytical and HTAP benchmarks.

In this paper, we introduce CTFL, a fair, robust, and interpretable framework designed to estimate clients' contributions to federated learning, aiming to incentivize high-quality data providers to participate in the federation. Firstly, CTFL can precisely allocate contribution credits in a single pass of model training and inference, ensuring computational efficiency. This is accomplished by tracking the test performance gain brought by each participant through exploiting classification rules. Secondly, CTFL adheres to essential theoretical properties of an ideal contribution estimation algorithm, including symmetry, zero-element, and additivity, ensuring fair and rational estimations. Thirdly, CTFL demonstrates resilience against strategic and malicious behaviors due to carefully crafted micro and macro contribution estimation schemes. Fourthly, CTFL offers insights into participants' roles within the federation by interpreting their contribution scores through respective high-frequently activated rules. Finally, CTFL integrates logical neural networks and model binarization techniques to ensure effectiveness and efficiency while preserving data privacy. Extensive experiments validate that CTFL accurately estimates contributions, significantly reducing computation time by 2–3 orders of magnitude compared to state-of-the-art methods while maintaining robustness.

Federated Learning (FL) provides a privacy-preserving and decentralized approach to collaborative machine learning for multiple FL clients. The contribution estimation mechanism in FL is extensively studied within the database community, which aims to compute fair and reasonable contribution scores as incentives to motivate FL clients. However, designing such methods involves challenges in three aspects: effectiveness, robustness, and efficiency. Firstly, contribution estimation methods should utilize the data utility information of various client coalitions rather than that of individual clients to ensure effectiveness. Secondly, we should beware of adverse clients who may exploit tactics like data replication or label flipping. Thirdly, estimating contribution in FL can be time-consuming due to enumerating various client coalitions. Despite numerous proposed methods to address these challenges, each possesses distinct advantages and limitations based on specific settings. However, existing methods have yet to be thoroughly evaluated and compared in the same experimental framework. Therefore, a unified and comprehensive evaluation framework is necessary to compare these methods under the same experimental settings. This paper conducts an extensive survey of contribution estimation methods in FL and introduces a comprehensive framework to evaluate their effectiveness, robustness, and efficiency. Through empirical results, we present extensive observations, valuable discoveries, and an adaptable testing framework that can facilitate future research in designing and evaluating contribution estimation methods in FL.

Answering spatio-temporal range queries (RQs) on trajectory databases, i.e., finding all trajectories that intersect given ranges, is crucial in many real-world applications. Various kinds of indexes have been proposed to accelerate RQs. However, existing indexes typically use Euclidean distance to prune irrelevant regions without concerning the underlying road network information. Nevertheless, as vehicle trajectories are generated on road network edges, the road network could be seen as meta knowledge of trajectories and be used to index and query trajectories. To this end, we propose RP-Tree, aroad network-awarepartitiontreeto support efficient RQs. The basic idea is partitioning a road network graph into hierarchical subgraphs and generate a balanced tree structure, where each tree node maintains its associated trajectories. We compactly index the spatio-temporal information of trajectories on the corresponding road network edges. Then, we design efficient search algorithms to support RQs by pruning irrelevant trajectories through subgraph range borders associated with RP-Tree nodes. Last but not least, we scale RP-Tree to very large datasets by devising approximate algorithms with bounded confidence at an interactive speed. Experimental results on three real-world datasets from Porto, Chengdu, and Beijing show that our method outperform baselines by 1 to 2 orders of magnitude.

Modern location-based systems have stimulated explosive growth of urban trajectory data and promoted many real-world applications, e.g. , trajectory prediction. However, heavy big data processing overhead and privacy concerns hinder trajectory acquisition and utilization. Inspired by regular trajectory distribution on transportation road networks, we propose to model trajectory data privately with a deep generative model and leverage the model to generate representative trajectories for downstream tasks or directly support these tasks ( e.g. , popularity ranking), rather than acquiring and processing the original big trajectory data. Nevertheless, it is rather challenging to model high-dimensional trajectories with time-varying yet skewed distribution. To address this problem, we model and generate trajectory sequence with judiciously encoded spatio-temporal features over skewed distribution by leveraging an important factor neglected by the literature - the underlying road properties ( e.g. , road types and directions), which are closely related to trajectory distribution. Specifically, we decompose trajectory into map-matched road sequence with temporal information and embed them to encode spatio-temporal features. Then, we enhance trajectory representation by encoding inherent route planning patterns from the underlying road properties. Later, we encode spatial correlations among edges and daily and weekly temporal periodicity information. Next, we employ a meta-learning module to generate trajectory sequence step by step by learning generalized trajectory distribution patterns from skewed trajectory data based on the well-encoded trajectory prefix. Last but not least, we preserve trajectory privacy by learning the model differential privately with clipping gradients. Experiments on real-world datasets show that our method significantly outperforms existing methods.

Computing the shortest path distances between two vertices on road networks is a core operation in many real-world applications, e.g., finding the closest taxi/hotel. However existing techniques have several limitations. First, traditional Dijkstra-based methods have long latency and cannot meet the high-performance requirement. Second, existing indexing-based methods either involve huge index sizes or have poor performance. To address these limitations, in this paper we propose a learning-based method which can efficiently compute an approximate shortest-path distance such that (1) the performance is super fast, e.g., taking 60-150 nanoseconds; (2) the error ratio of the approximate results is super small, e.g., below 0.7%; (3) scales well to large road networks, e.g., millions of nodes. The key idea is to first embed the road networks into a low dimensional space for capturing the distance relations between vertices, get an embedded vector for each vertex, and then perform a distance metric (L1metric) on the embedded vectors to approximate shortest-path distances. We propose a hierarchical model to represent the embedding, and design an effective method to train the model. We also design a fine-tuning method to judiciously select high-quality training data. Extensive experiments on real-world datasets show that our embedding based approach significantly outperforms the state-of-the-art methods.

Data labelling is very important in many database and machine learning applications. Traditional methods rely on humans (workers or experts) to acquire labels. However, the human cost is rather expensive for a large dataset. Active learning based methods only label a small set of data with large uncertainty, train a model on these labelled data, and use the trained model to label the remainder unlabelled data. However they have two limitations. First, they cannot judiciously select appropriate data (task selection) and assign the tasks to proper humans (task assignment). Moreover, they independently process task selection and task assignment, which cannot capture the correlation between them. Second, they simply infer the truth of a task based on the answers from humans and the trained model (truth inference) by independently modeling humans and models. In other words, they ignore the correlation between them (the labelled data may have noise caused by humans with biases, and the model trained by the noisy labels may bring additional biases), and thus lead to poor inference results. To address these limitations, in this paper, we propose CrowdRL, an end-to-end reinforcement learning (RL) based framework for data labelling. To the best of our knowledge, CrowdRL is the first RL framework designed for the data labelling workflow by seamlessly integrating task selection, task assignment and truth inference together. CrowdRL fully utilizes the power of heterogeneous annotators (experts and crowdsourcing workers) and machine learning models together to infer the truth, which highly improves the quality of data labelling. CrowdRL uses RL to model task assignment and task selection, and designs an agent to judiciously assign tasks to appropriate workers. CrowdRL jointly models the answers of workers, experts and models, and designs a joint inference model to infer the truths. Experimental results on real datasets show that CrowdRL outperforms state-of-the-art approaches with the same (even fewer) monetary cost while achieving 5%-20% higher accuracy.

Ridesharing algorithms operate in environments that are dynamic and uncertain due to traffic effects. Evaluating an algorithm by deploying it in a real environment is costly and often inaccessible, yet the traditional approach of using static inputs and applying an objective function on the outputs may give unrealistic results. Jargo is a novel real-time simulator that provides more realistic evaluation. It lets users implement their own algorithms, speed field functions, and evaluators, and then it reports on multiple quality metrics that are useful to service providers. To support any new and existing algorithm, simulate traffic, and compute the metrics, it is supported by a new relational model of ridesharing. Relations naturally express empirical concepts such as customer pick-up time, and their flexibility can allow any feasible routing strategy. Relational algebra is also convenient for defining operations on the system as well as formalizing service-related metrics. We will show how a service provider considering whether or not to deploy the well-known greedy insertion algorithm could use Jargo to uncover its limits and guide the development of new techniques.

For real-world time dependent road networks (TDRNs), answering shortest path-based route queries and plans in real-time is highly desirable by many industrial applications. Unfortunately, traditional ( Dijkstra - or A *-like) algorithms are computationally expensive for such tasks on TDRNs. Naturally, indexes are needed to meet the real-time constraint required by real applications. In this paper, we propose a novel height-balanced tree-structured index, called TD-G-tree, which supports fast route queries over TDRNs. The key idea is to use hierarchical graph partitioning to split a road network into hierarchical partitions. This will produce a balanced tree, where each tree node corresponds to a partition and each parent-child relationship corresponds to a partition and its sub-partition. We then compute and index time dependent shortest paths (TDSPs) only for borders ( i.e ., vertices whose edges are cut by a partition). Based on TD-G-tree, we devise efficient algorithms to support TDSP queries, as well as time-interval based route planning, for computing optimal solutions through dynamic programming and chronological divide-and-conquer. Extensive experiments on real-world datasets show that our method significantly outperforms existing approaches.