Time series forecasting always faces the challenge of concept drift, where data distributions evolve over time, leading to a decline in forecast model performance. Existing solutions are based on online learning, which continually organize recent time series observations as new training samples and update model parameters according to the forecasting feedback on recent data. However, they overlook a critical issue: obtaining ground-truth future values of each sample should be delayed until after the forecast horizon. This delay creates a temporal gap between the training samples and the test sample. Our empirical analysis reveals that the gap can introduce concept drift, causing forecast models to adapt to outdated concepts. In this paper, we present Proceed, a novel proactive model adaptation framework for online time series forecasting. Proceed first estimates the concept drift between the recently used training samples and the current test sample. It then employs an adaptation generator to efficiently translate the estimated drift into parameter adjustments, proactively adapting the model to the test sample. To enhance the generalization capability of the framework, Proceed is trained on synthetic diverse concept drifts. Extensive experiments on five real-world datasets across various forecast models demonstrate that Proceed brings more performance improvements than the state-of-the-art online learning methods, significantly facilitating forecast models' resilience against concept drifts. Code is available at https://github.com/SJTU-DMTai/OnlineTSF.

Large language model (LLM) inference serving systems are essential to various LLM-based applications. As demand for LLM services continues to grow, scaling these systems to handle high request rates while meeting latency Service-Level Objectives (SLOs), referred to as effective throughput, becomes critical. However, existing systems often struggle to improve effective throughput, primarily due to a significant decline in Time To First Token (TTFT) SLO attainment. We identify two major causes of this bottleneck: (1) memory-intensive KV cache that limits batch size expansion under GPU memory constraints, and (2) rigid batch composition enforced by the default First-Come-First-Serve scheduling policy. In this paper, we introduce Apt-Serve, a scalable framework designed to enhance effective throughput in LLM inference serving. Apt-Serve features a new hybrid cache scheme that combines KV cache with a memory-efficient hidden cache for reusable input hidden state vectors, allowing large batch sizes and improving request concurrency. Based on the hybrid cache, Apt-Serve employs an adaptive runtime scheduling mechanism that dynamically optimizes batch composition. We formally define the adaptive scheduling optimization problem and propose an efficient algorithm with theoretical guarantees. Extensive evaluations on three real-world datasets and LLMs ranging from 13B to 66B parameters demonstrate that Apt-Serve achieves up to 8.8x improvement in effective throughput compared to the state-of-the-art inference serving systems.

Graph Neural Networks (GNNs) have achieved remarkable success in various graph-related tasks. However, training GNNs on large-scale graphs is hindered by the neighbor explosion problem, rendering full-batch training computationally infeasible. Mini-batch training with neighbor sampling is a widely adopted solution, but it introduces gradient estimation errors that slow convergence and reduce model accuracy. In this work, we identify two primary sources of these errors: (1) missing gradient contributions from unsampled target nodes, and (2) inaccuracies in messages computed from sampled nodes. While existing methods largely focus on mitigating the second source, they often overlook the first, resulting in incomplete gradient estimation. To address this gap, we propose the Pseudo Full Neighborhood Compensation (PFNC) framework, which leverages historical information to simultaneously compensate for both errors. PFNC is designed to integrate seamlessly with any neighbor sampling technique and significantly lowers memory demands by maintaining only a partial cache of historical embed-dings and gradients. Theoretical analysis demonstrates that PFNC provides a closer approximation to the ideal gradient, enhancing convergence. Extensive experiments across multiple benchmark datasets confirm that PFNC accelerates convergence and improves generalization across diverse neighbor sampling strategies.

Representation learning over dynamic graphs is critical for many real-world applications such as social network services and recommender systems. Temporal graph neural networks (T-GNNs) are powerful representation learning methods and have demonstrated remarkable effectiveness on continuous-time dynamic graphs. However, T-GNNs still suffer from high time complexity, which increases linearly with the number of timestamps and grows exponentially with the model depth, making them not scalable to large dynamic graphs. To address the limitations, we propose Orca , a novel framework that accelerates T-GNN training by caching and reusing intermediate embeddings. We design an optimal caching policy, named MRD , for the uniform cache replacement problem, where embeddings at different intermediate layers have identical dimensions and recomputation costs. MRD not only improves the efficiency of training T-GNNs by maximizing the number of cache hits but also reduces the approximation errors by avoiding keeping and reusing extremely stale embeddings. For the general cache replacement problem, where embeddings at different intermediate layers can have different dimensions and recomputation costs, we solve this NP-hard problem by presenting a novel two-stage framework with approximation guarantees on the achieved benefit of caching. Furthermore, we have developed profound theoretical analyses of the approximation errors introduced by reusing intermediate embeddings, providing a thorough understanding of the impact of our caching and reuse schemes on model outputs. We also offer rigorous convergence guarantees for model training, adding to the reliability and validity of our Orca framework. Extensive experiments have validated that Orca can obtain two orders of magnitude speedup over state-of-the-art T-GNNs while achieving higher precision on various dynamic graphs.

Efficient indexing is fundamental to managing and analyzing multi-dimensional data. A growing trend is to directly learn the storage layout of multi-dimensional data using simple machine learning models, leading to the concept of Learned Index . Compared to conventional indexing methods that have been used for decades (e.g., k d-tree and R-tree variants), learned indexes have demonstrated empirical advantages in both space and time efficiency on modern architectures. However, there is a lack of comprehensive evaluation across existing multi-dimensional learned indexes under a standardized benchmark, making it challenging to identify the most suitable index for specific data types and query patterns. This gap also hinders the widespread adoption of learned indexes in practical applications. In this paper, we present the first in-depth empirical study to answer the question: how good are multi-dimensional learned indexes? We evaluate ten recently published indexes under a unified experimental framework, which includes standardized implementations, datasets, query workloads, and evaluation metrics. We thoroughly investigate the evaluation results and discuss the findings that may provide insights for future learned index design.

Abstract Graph neural networks (GNNs) have emerged due to their success at modeling graph data. Yet, it is challenging for GNNs to efficiently scale to large graphs. Thus, distributed GNNs come into play. To avoid communication caused by expensive data movement between workers, we propose Sancus and its advanced version Sancus"Equation missing", the staleness and quantization-aware communication-avoiding decentralized GNN system. By introducing a set of novel bounded embedding staleness metrics and adaptively skipping broadcasts, Sancus abstracts decentralized GNN processing as sequential matrix multiplication and uses historical embeddings via cache. To further mitigate the communication volume, Sancus"Equation missing" conducts quantization-aware communication on embeddings to reduce the size of broadcast messages. Theoretically, we show bounded approximation errors of embeddings and gradients with a known fastest convergence guarantee. Empirically, we evaluate Sancus and Sancus"Equation missing" with common GNN models via different system setups on large-scale benchmark datasets. Compared to SOTA works, Sancus"Equation missing" can avoid up to $$86\%$$ 86 % communication with $$3.0\times $$ 3.0 × faster throughput on average without accuracy loss.

Contrastive Learning (CL) enhances the training of sequential recommendation (SR) models through informative self-supervision signals. Existing methods often rely on data augmentation strategies to create positive samples and promote representation invariance. Some strategies such as item reordering and item substitution may inadvertently alter user intent. Supervised Contrastive Learning (SCL) based methods find an alternative to augmentation-based CL methods by selecting same-target sequences (interaction sequences with the same target item) to form positive samples. However, SCL-based methods suffer from the scarcity of same-target sequences and consequently lack enough signals for contrastive learning. In this work, we propose to use similar sequences (with different target items) as additional positive samples and introduce a Relative Contrastive Learning (RCL) framework for sequential recommendation. RCL comprises a dual-tiered positive sample selection module and a relative contrastive learning module. The former module selects same-target sequences as strong positive samples and selects similar sequences as weak positive samples. The latter module employs a weighted relative contrastive loss, ensuring that each sequence is represented closer to its strong positive samples than its weak positive samples. We apply RCL on two mainstream deep learning-based SR models, and our empirical results reveal that RCL can achieve 4.88% improvement averagely than the state-of-the-art SR methods on five public datasets and one private dataset.

Sparse operators, i.e., operators that take sparse tensors as input, are of great importance in deep learning models. Due to the diverse sparsity patterns in different sparse tensors, it is challenging to optimize sparse operators by seeking an optimal sparse format, i.e., leading to the lowest operator latency. Existing works propose to decompose a sparse tensor into several parts and search for a hybrid of sparse formats to handle diverse sparse patterns. However, they often make a trade-off between search space and search time: their search spaces are limited in some cases, resulting in limited operator running efficiency they can achieve. In this paper, we try to extend the search space in its breadth (by doing flexible sparse tensor transformations) and depth (by enabling multi-level decomposition). We formally define the multi-level sparse format decomposition problem, which is NP-hard, and we propose a framework STile for it. To search efficiently, a greedy algorithm is used, which is guided by a cost model about the latency of computing a sub-task of the original operator after decomposing the sparse tensor. Experiments of two common kinds of sparse operators, SpMM and SDDMM, are conducted on various sparsity patterns, and we achieve 2.1-18.0× speedup against cuSPARSE on SpMMs and 1.5 - 6.9× speedup against DGL on SDDMM. The search time is less than one hour for any tested sparse operator, which can be amortized.

Dynamic graphs are essential in real-world scenarios like social media and e-commerce for tasks such as predicting links and classifying nodes. Temporal Graph Neural Networks (T-GNNs) stand out as a prime solution for managing dynamic graphs, employing temporal message passing to compute node embeddings at specific timestamps. Nonetheless, the high CPU-GPU data loading overhead has become the bottleneck for efficient training of T-GNNs over large-scale dynamic graphs. In this work, we present SIMPLE, a versatile system designed to address the major efficiency bottleneck in training existing T-GNNs on a large scale. It incorporates a dynamic data placement mechanism, which maintains a small buffer space in available GPU memory and dynamically manages its content during T-GNN training. SIMPLE is also empowered by systematic optimizations towards data processing flow. We compare SIMPLE to the state-of-the-art generic T-GNN training system TGL on four large-scale dynamic graphs with different underlying T-GNN models. Extensive experimental results show that SIMPLE effectively cuts down 80.5% ~ 96.8% data loading cost, and accelerates T-GNN training by 1.8× ~ 3.8× (2.6× on average) compared to TGL.

Dynamic graphs play a crucial role in various real-world applications, such as link prediction and node classification on social media and e-commerce platforms. Temporal Graph Neural Networks (T-GNNs) have emerged as a leading approach for handling dynamic graphs, using temporal message passing to compute temporal node embeddings. However, training existing T-GNNs on large-scale dynamic graphs is prohibitively expensive due to the ill-suited batching scheme and significant data access overhead. In this paper, we introduce ETC, a generic framework designed specifically for efficient T-GNN training at scale. ETC incorporates a novel data batching scheme that enables large training batches improving model computation efficiency, while preserving model effectiveness by restricting information loss in each training batch. To reduce data access overhead, ETC employs a three-step data access policy that leverages the data access pattern in T-GNN training, significantly reducing redundant data access volume. Additionally, ETC utilizes an inter-batch pipeline mechanism, decoupling data access from model computation and further reducing data access costs. Extensive experimental results demonstrate the effectiveness of ETC, showcasing its ability to achieve significant training speedups compared to state-of-the-art training frameworks for T-GNNs on real-world dynamic graphs with millions of interactions. ETC provides a training speedup ranging from 1.6X to 62.4X, highlighting its potential for efficient training on large-scale dynamic graphs.

Graph Neural Networks (GNNs) have gained significant popularity for learning representations of graph-structured data. Mainstream GNNs employ the message passing scheme that iteratively propagates information between connected nodes through edges. However, this scheme incurs high training costs, hindering the applicability of GNNs on large graphs. Recently, the database community has extensively researched effective solutions to facilitate efficient GNN training on massive graphs. In this tutorial, we provide a comprehensive overview of the GNN training process based on the graph data lifecycle, covering graph preprocessing, batch generation, data transfer, and model training stages. We discuss recent data management efforts aiming at accelerating individual stages or improving the overall training efficiency. Recognizing the distinct training issues associated with static and dynamic graphs, we first focus on efficient GNN training on static graphs, followed by an exploration of training GNNs on dynamic graphs. Finally, we suggest some potential research directions in this area. We believe this tutorial is valuable for researchers and practitioners to understand the bottleneck of GNN training and the advanced data management techniques to accelerate the training of different GNNs on massive graphs in diverse hardware settings.

Recently, substantial research has been conducted on sequential recommendation, with the objective of forecasting the subsequent item by leveraging a user's historical sequence of interacted items. Prior studies employ both capsule networks and self-attention techniques to effectively capture diverse underlying intents within a user's interaction sequence, thereby achieving the most advanced performance in sequential recommendation. However, users could potentially form novel intents from fresh interactions as the lengths of user interaction sequences grow. Consequently, models need to be continually updated or even extended to adeptly encompass these emerging user intents, referred as incremental multi-intent sequential recommendation. In this paper, we propose an effectiveIncremental learning framework for userMulti-intentAdaptation in sequential recommendation called IMA, which augments the traditional fine-tuning strategy with the existing-intents retainer, new-intents detector, and projection-based intents trimmer to adaptively expand the model to accommodate user's new intents and prevent it from forgetting user's existing intents. Furthermore, we upgrade the IMA into anElasticMulti-intentAdaptation (EMA) framework which can elastically remove inactive intents and compress user intent vectors under memory space limit. Extensive experiments on real-world datasets verify the effectiveness of the proposed IMA and EMA on incremental multi-intent sequential recommendation, compared with various baselines.

In recent years, sequential recommendation has been widely researched, which aims to predict the next item of interest based on user’s previously interacted item sequence. Existing works utilize capsule network and self-attention method to explicitly capture multiple underlying interests from a user’s interaction sequence, achieving the state-of-the-art sequential recommendation performance. In practice, the lengths of user interaction sequences are ever-increasing and users might develop new interests from new interactions, and a model should be updated or even expanded continuously to capture the new user interests. We refer to this problem as incremental multi-interest sequential recommendation, which has not yet been well investigated in the existing literature. In this paper, we propose an effective incremental learning framework for multi-interest sequential recommendation called IMSR, which augments the traditional fine-tuning strategy with the existing-interests retainer (EIR), new-interests detector (NID), and projection-based interests trimmer (PIT) to adaptively expand the model to accommodate user’s new interests and prevent it from forgetting user’s existing interests. Extensive experiments on real-world datasets verify the effectiveness of the proposed IMSR on incremental multi-interest sequential recommendation, compared with various baseline approaches.

With the upsurge of online banking, mobile payment, and virtual currency, new money-laundering crimes easily conceal in the enormous transaction volume. The traditional rule-based methods with large amounts of alerting thresholds are already incapable of handling the fast-changing transaction networks. Recently, the DL models represented by the graph neural networks (GNNs) show the potential to capture money-laundering modes with high accuracy. However, most related works are still far from practical deployment in the industry. Based on our practice at WeBank, there are three major challenges: Firstly, supervised learning is infeasible facing the extraordinarily large-scale but imbalanced data, with hundreds of millions of active accounts but only thousands of anomalies. Secondly, the real-world transactions form a sparse network with millions of isolated user groups, which overflows the expressive ability of current node-level GNNs. Thirdly, the explanation for each suspicious account is mandatory by the government for double check, which conflicts with the black-box nature of most DL models. Therefore, we proposed Diga, the first work to apply the diffusion probabilistic model to a graph anomaly detection problem with three novel techniques: the biased K-hop PageRank, the semi-supervised guided diffusion and the novel weight-sharing GNN layer. The effectiveness and efficiency of Diga are verified via intensive experiments on both industrial and public datasets.

Stock trend forecasting is a fundamental task of quantitative investment where precise predictions of price trends are indispensable. As an online service, stock data continuously arrive over time. It is practical and efficient to incrementally update the forecast model with the latest data which may reveal some new patterns recurring in the future stock market. However, incremental learning for stock trend forecasting still remains under-explored due to the challenge of distribution shifts (a.k.a. concept drifts). With the stock market dynamically evolving, the distribution of future data can slightly or significantly differ from incremental data, hindering the effectiveness of incremental updates. To address this challenge, we propose DoubleAdapt, an end-to-end framework with two adapters, which can effectively adapt the data and the model to mitigate the effects of distribution shifts. Our key insight is to automatically learn how to adapt stock data into a locally stationary distribution in favor of profitable updates. Complemented by data adaptation, we can confidently adapt the model parameters under mitigated distribution shifts. We cast each incremental learning task as a meta-learning task and automatically optimize the adapters for desirable data adaptation and parameter initialization. Experiments on real-world stock datasets demonstrate that DoubleAdapt achieves state-of-the-art predictive performance and shows considerable efficiency.

Graph neural networks (GNNs) have been widely studied for modeling graph-structured data. Thanks to the over-parameterization and large receptive field of deep GNNs, "deep" is a promising direction to develop GNNs further and has shown some superior performances. However, the over-stacked structures of deep architectures incur high inference cost in deployment. To compress deep GNNs, we can use knowledge distillation (KD) to make shallow student GNNs mimic teacher GNNs. Existing KD methods in graph domain focus on constructing diverse supervision on embedding or prediction produced by student GNNs, but overlook the gap of the receptive field (i.e., input information) between student and teacher, which brings difficulties to KD. We call this gap "input mismatch". To alleviate this problem, we propose a lightweight stochastic extended module to provide an estimation for missing input information for student GNNs. The estimator models the distribution of missing information. Specifically, we model the missing information as an independent distribution from graph level and a conditional distribution from node level (given the condition of observable input). These two estimates are optimized using a Bayesian methodology and combined into a balanced estimate as additional input to student GNNs. To the best of our knowledge, we are the first to address the "input mismatch" problem in deep GNNs distillation. Experiments on extensive benchmarks demonstrate that our method outperforms existing KD methods for GNNs in distillation performance, which confirms that the estimations are reasonable and effective.

The acquisition of accurate rainfall distribution in space is an important task in hydrological analysis and natural disaster pre-warning. However, it is impossible to install rain gauges on every corner. Spatial interpolation is a common way to infer rainfall distribution based on available raingauge data. However, the existing works rely on some unrealistic pre-settings to capture spatial correlations, which limits their performance in real scenarios. To tackle this issue, we propose the SSIN, which is a novel data-driven self-supervised learning framework for rainfall spatial interpolation by mining latent spatial patterns from historical observation data. Inspired by the Cloze task and BERT, we fully consider the characteristics of spatial interpolation and design the SpaFormer model based on the Transformer architecture as the core of SSIN. Our main idea is: by constructing rich self-supervision signals via random masking, SpaFormer can learn informative embeddings for raw data and then adaptively model spatial correlations based on rainfall spatial context. Extensive experiments on two real-world raingauge datasets show that our method outperforms the state-of-the-art solutions. In addition, we take traffic spatial interpolation as another use case to further explore the performance of our method, and SpaFormer achieves the best performance on one large real-world traffic dataset, which further confirms the effectiveness and generality of our method.

Representation learning over dynamic graphs is critical for many real-world applications such as social network services and recommender systems. Temporal graph neural networks (T-GNNs) are powerful representation learning methods and have achieved remarkable effectiveness on continuous-time dynamic graphs. However, T-GNNs still suffer from high time complexity, which increases linearly with the number of timestamps and grows exponentially with the model depth, causing them not scalable to large dynamic graphs. To address the limitations, we propose Orca, a novel framework that accelerates T-GNN training by non-trivially caching and reusing intermediate embeddings. We design an optimal cache replacement algorithm, named MRU, under a practical cache limit. MRU not only improves the efficiency of training T-GNNs by maximizing the number of cache hits but also reduces the approximation errors by avoiding keeping and reusing extremely stale embeddings. Meanwhile, we develop profound theoretical analyses of the approximation error introduced by our reuse schemes and offer rigorous convergence guarantees. Extensive experiments have validated that Orca can obtain two orders of magnitude speedup over the state-of-the-art baselines while achieving higher precision on large dynamic graphs.

Recently Graph Neural Networks (GNNs) have achieved great success in many applications. The mini-batch training has become the de-facto way to train GNNs on giant graphs. However, the mini-batch generation task is extremely expensive which slows down the whole training process. Researchers have proposed several solutions to accelerate the mini-batch generation, however, they (1) fail to exploit the locality of the adjacency matrix, (2) cannot fully utilize the GPU memory, and (3) suffer from the poor adaptability to diverse workloads. In this work, we propose DUCATI, aDual-Cache system to overcome these drawbacks. In addition to the traditionalNfeat-Cache, DUCATI introduces a newAdj-Cache to further accelerate the mini-batch generation and better utilize GPU memory. DUCATI develops a workload-awareDual-Cache Allocator which adaptively finds the best cache allocation plan under different settings. We compare DUCATI with various GNN training systems on four billion-scale graphs under diverse workload settings. The experimental results show that in terms of training time, DUCATI can achieve up to 3.33 times speedup (2.07 times on average) compared to DGL and up to 1.54 times speedup (1.32 times on average) compared to the state-of-the-artSingle-Cache systems. We also analyze the time-accuracy trade-offs of DUCATI and four state-of-the-art GNN training systems. The analysis results offer users some guidelines on system selection regarding different input sizes and hardware resources.

Temporal graph neural networks (T-GNNs) are state-of-the-art methods for learning representations over dynamic graphs. Despite the superior performance, T-GNNs still suffer from high computational complexity caused by the tedious recursive temporal message passing scheme, which hinders their applicability to large dynamic graphs. To address the problem, we build the theoretical connection between the temporal message passing scheme adopted by T-GNNs and the temporal random walk process on dynamic graphs. Our theoretical analysis indicates that it would be possible to select a few influential temporal neighbors to compute a target node's representation without compromising the predictive performance. Based on this finding, we propose to utilize T-PPR, a parameterized metric for estimating the influence score of nodes on evolving graphs. We further develop an efficient single-scan algorithm to answer the top- k T-PPR query with rigorous approximation guarantees. Finally, we present Zebra, a scalable framework that accelerates the computation of T-GNN by directly aggregating the features of the most prominent temporal neighbors returned by the top- k T-PPR query. Extensive experiments have validated that Zebra can be up to two orders of magnitude faster than the state-of-the-art T-GNNs while attaining better performance.

Prediction over tabular data is often a crucial task in many real-life applications. Recent advances in deep learning give rise to various deep models for tabular data prediction. A common and essential step in these models is to vectorize raw input features in tabular data into dense embeddings. Choosing a suitable dimension for each feature is challenging yet necessary to improve model’s performance and reduce memory cost of model parameters. Existing solutions to embedding dimensionality search always choose dimensions from a restricted candidate set. This restriction improves the search efficiency but would produce suboptimal embedding dimensions that hurt model’s predictive performance. In this paper, we develop AutoSrh, a flexible embedding dimensionality search framework that can select varying dimensions for different features through differentiable optimization. The key idea of AutoSrh is to relax the search space to be continuous and optimize the selection of embedding dimensions via gradient descent. After optimization, AutoSrh performs embedding pruning to derive the mixed embedding dimensions and retrains the model to further improve the performance. Extensive experiments on five real-world tabular datasets demonstrate that AutoSrh can achieve better predictive performance than the existing approaches with 1.1$\sim$1.6x lower training time cost and reserve model’s predictive performance while reducing 50$\sim$95% embedding parameters.

Click-through Rate (CTR) prediction on cold users is a challenging task in recommender systems. Recent researches have resorted to meta-learning to tackle the cold-user challenge, which either perform few-shot user representation learning or adopt optimization-based meta-learning. However, existing methods suffer from information loss or inefficient optimization process, and they fail to explicitly model global user preference knowledge, which is crucial to complement the sparse and insufficient preference information of cold users. In this article, we propose a novel and efficient approach named RESUS, which decouples the learning of global preference knowledge contributed by collective users from the learning of residual preferences for individual users. Specifically, we employ a shared predictor to infer basis user preferences, which acquires global preference knowledge from the interactions of different users. Meanwhile, we develop two efficient algorithms based on the nearest neighbor and ridge regression predictors, which infer residual user preferences via learning quickly from a few user-specific interactions. Extensive experiments on three public datasets demonstrate that our RESUS approach is efficient and effective in improving CTR prediction accuracy on cold users, compared with various state-of-the-art methods.

Web tables are valuable resources that can enrich existing knowledge bases. Researchers try to make the predictions of columns and column pairs in web tables into entities and relations of knowledge bases, which are known as the Column Type Annotation (CT) and Relation Extraction (RE) tasks in web table interpretation. Learning useful and accurate column vector representations plays the central role in solving the two tasks. A column’s semantics can be determined by three kinds of relationships: Column-Cell, Column-Table, Column-Column relationships. Existing works only rely on the Column-Cell relationship to determine the semantics of columns and result in suboptimal performances. In this paper, we propose to solve the above CT and RE tasks with the heterogeneous graph neural network technique. First, we construct heterogeneous graphs for web tables. Next, a new model named Tab-HGNN is proposed to consider all the three kinds of relationships and learn target column representations. Extensive experiments on real-world web table datasets demonstrate the effectiveness of the proposed Tab-HGNN model on the CT and RE tasks. It outperforms the competitive baselines by achieving up to +7.9% and +1.6% macro F1scores, +2.6% and +0.2% weighted F1scores on two CT datasets, respectively. It also achieves +0.3% macro F1scores, +0.1% weighted F1scores on one RE dataset.

Relational databases are the main storage model of structured data in most businesses, which usually involves multiple tables with key-foreign-key relationships. In practice, data analysts often want to pose predictive classification queries over relational databases. To answer such queries, many existing approaches perform supervised learning to train classification models, which heavily rely on the availability of sufficient labeled data. In this paper, we propose a novel graph-based contrastive framework for semi-supervised learning on relational databases, achieving promising predictive classification performance with only a handful of labeled data. Our framework utilizes contrastive learning to exploit additional supervision signals from massive unlabeled data. Specifically, we develop two contrastive graph views that are 1) advantageous for modeling complex relationships and correlations among structured data in a relational database, and 2) complementary to each other for learning robust representations of structured data to be classified. We also leverage label information in contrastive learning to mitigate its negative effect in knowledge transfer on the supervised counterpart. We conduct extensive experiments on three real-world relational databases and the results demonstrate that our framework is able to achieve the state-of-the-art predictive performance in limited labeled data settings, compared with various supervised and semi-supervised learning approaches.

Recently Graph Neural Networks (GNNs) have achieved great success in many applications. To apply GNNs to large graphs, mini-batch training and sampling are widely adopted by recent works. However, existing works generate mini-batches following a topology-oriented sampling style, which first samples a subgraph and then fetches the corresponding node features to construct a mini-batch. This inevitably incurs intensive random access of graph data, the exponential growth of the batch size, and constrained candidates during sampling. In this work, we advocate adopting a feature-oriented sampling style which can overcome these drawbacks. We first sample the node features and then induce the corresponding subgraph to form a mini-batch. We apply the feature-oriented sampling method to three mainstream GNN models to demonstrate the effectiveness and efficiency of this sampling style. Experiments on four large-scale datasets show that feature-oriented sampling can achieve comparable accuracy as topology-oriented sampling while speeding up the training procedure by 2.2 ~ 7.9 times.

In recent years, sequential recommendation has been widely researched, which aims to predict the next item of interest based on user's previously interacted item sequence. Many works use RNN to model the user interest evolution over time. However, they typically compute a single vector as the user representation, which is insufficient to capture the variation of user diverse interests. Some non-RNN models employ the dynamic routing mechanism to automatically vote out multiple capsules that represent user's diverse interests, but they are ignorant of the temporal information of user's historical behaviors, thus yielding suboptimal performance. In this paper, we aim to establish a time-aware dynamic routing algorithm to effectively extract temporal user multiple interests for sequential recommendation. We observe that the significance of an item to user interests may change monotonically over time, and user interests may fluctuate periodically. Following the intuitive temporal patterns of user interests, we propose a novel time-aware multi-interest capsule network named TAMIC that leverages two kinds of time-aware voting gates, i.e., monotonic gates and periodic gates, to control the influence of each interacted item on user's current interests during the routing procedure. We further employ an aggregation module to form a temporal multi-interest user representation which is used for next item prediction. Extensive experiments on real-world datasets verify the effectiveness of the time gates and the superior performance of our TAMIC approach on sequential recommendation, compared with the state-of-the-art methods.

Many real-world applications rely on predictive models that are incrementally learned online. Specifically, models are updated with a single pass over continuously arriving data batches in a typical stream learning framework. However, this framework has three shortcomings: high training cost, low data effectiveness, and catastrophic forgetting. We describe Camel, a system that addresses the above issues. Camel includes two independent data management components: coreset selection and buffer update. To accelerate model training, Camel selects a coreset from each streaming data batch for model update. Selecting a coreset with worst-case guarantees is NP-hard. To solve this problem, we reformulate coreset selection as a submodular maximization problem by deriving an upper bound on the objective function. To mitigate catastrophic forgetting, Camel maintains a buffer of past representative samples as new data arrive. Moreover, Camel quantizes numerical data in buffer via a quantile sketch to reduce the memory footprint. Finally, extensive experiments validate the effectiveness and efficiency of Camel. In particular, our coreset selection algorithm can achieve a linear speedup with a marginal accuracy loss on redundant datasets. Furthermore, our buffer update algorithms can outperform the state-of-the-art methods for anti-forgetting on various data distributions.

The emerging deep learning techniques prefer mapping complex data objects (e.g., images, documents) to compact binary vectors (i.e., hash codes) for efficient similarity search. In this paper, we study the problem of indexing large-scale binary databases to support fast Hamming distance-based similarity queries. Existing Hamming space indices usually divide long binary vectors into short disjoint pieces and apply the Pigeonhole Principle to prune unnecessary candidates. In our work, we relax the disjoint partition constraint by allowing dimension redundancy, which yields a tighter pruning bound named Augmented Pigeonhole Principle (APP). Intuitively, APP enables more optimization opportunities by capturing the correlation between database and query workloads. Based on APP, we propose HAP, an efficient Hamming space index framework to support both Hamming range queries and k-NN queries.

Graph neural networks (GNNs) have emerged due to their success at modeling graph data. Yet, it is challenging for GNNs to efficiently scale to large graphs. Thus, distributed GNNs come into play. To avoid communication caused by expensive data movement between workers, we propose Sancus, a staleness-aware communication-avoiding decentralized GNN system. By introducing a set of novel bounded embedding staleness metrics and adaptively skipping broadcasts, Sancus abstracts decentralized GNN processing as sequential matrix multiplication and uses historical embeddings via cache. Theoretically, we show bounded approximation errors of embeddings and gradients with convergence guarantee. Empirically, we evaluate Sancus with common GNN models via different system setups on large-scale benchmark datasets. Compared to SOTA works, Sancus can avoid up to 74% communication with at least 1.86X faster throughput on average without accuracy loss.

Next basket recommendation aims at predicting the next set of items that a user would likely purchase together, which plays an important role in e-commerce platforms. Unlike conventional item recommendation, the next basket recommendation focuses on capturing item correlations among baskets and learning the user’s temporal interest from the past purchasing basket sequence. In practice, most users interact with items in various kinds of behaviors. The multi-behavior data sheds light on user’s potential purchasing intention and resolves noisy signals from accidentally purchased items. In this article, we conduct an empirical study on real datasets to exploit the characteristics of multi-behavior data and confirm its positive effects on next basket recommendation. We develop a novel Multi-Behavior Network (MBN) model that captures item correlations and acquires meta-knowledge from multi-behavior basket sequences effectively. MBN employs the meta multi-behavior sequence encoder to model temporal dependencies of each individual behavior and extract meta-knowledge across different behaviors. Furthermore, we design the recurring-item-aware predictor in MBN to realize the high degree of the repeated occurrences of items, leading to better recommendation performance. We conduct extensive experiments to evaluate the performance of our proposed MBN model using real-world multi-behavior data. The results demonstrate the superior recommendation performance of MBN compared with various state-of-the-art methods.

The success of deep learning presents exciting opportunities for reusing pre-trained models from source domains to solve a target task with possibly limited training data. While various pre-trained models have been developed and become available, there is no principled way to select appropriate models for reuse. Although it is suggested that source and target tasks should be sufficiently similar, the calculation of task relevance usually requires extra storage of source training data and great efforts from domain experts, which is impractical in many applications. In this paper, we study the Multi-source Model Selection and Ensemble (MSMSE) problem. Given a collection of source models, we aim to select a subset of source models and develop an ensemble model that achieves the best performance for a target task. An ensemble of multiple models enables a boarder utilization of various underlying source knowledge and leads to better generalization ability. To this end, we present Palette, a generic framework that first selects potentially well-performed models from a source model pool, and then builds an ensemble with refinement. We introduce different model selection strategies that combine multi-armed bandits with adaptive resource allocation and Bayesian optimization techniques to accelerate the selection process. Extensive experimental results validate the effectiveness and efficiency of Palette and our model selection strategies.

Data synopsis is widely adopted to speed-up query processing over large spatial databases. As one of the most popular spatial data synopses, multi-dimensional histograms (MH) have been studied and adopted by modern DBMS and analytical systems for decades. However, existing MH construction techniques highly rely on expert knowledge and statistical assumptions, making them hard to achieve consistently satisfactory performance across different datasets. Inspired by the emerging learned index techniques where the widely used index structures like B-tree can be further improved by integrating simple machine learning models, in this paper, we propose a learned data synopsis technique named Learned Multi-dimensional Histogram (LHist). Compared with the traditional data synopsis techniques, LHist is fully data-driven, easy-to-implement, and has the potential to achieve better storage-accuracy trade-off. On the typical task of range COUNT query estimation, the extensive experimental studies on large-scale real-world datasets and synthetic benchmarks reveal that LHist can outperform the existing synopsis structures in terms of storage cost, query processing efficiency, and estimation accuracy.

Recently, knowledge-graph-enhanced recommendation systems have attracted much attention, since knowledge graph (KG) can help improving the dataset quality and offering rich semantics for explainable recommendation. However, current KG-enhanced solutions focus on analyzing user behaviors on the product level and lack effective approaches to extract user preference towards product category, which is essential for better recommendation because users shopping online normally have strong preference towards distinctive product categories, not merely on products, according to various user studies. Moreover, the existing pure embedding-based recommendation methods can only utilize KGs with a limited size, which is not adaptable to many real-world applications. In this paper, we generalize the recommendation problem with preference mining as a compound knowledge reasoning task and propose a novel multi-agent system, called Mcore, which can promote model performance by mining users’ high-level interests and is adaptable to large KGs. Specifically, we split the overall problem and allocate sub-task to each agent: Coordinate Agent takes charge of recognizing the product-category preference of current user, while Relation Agent and Entity Agent perform KG reasoning cooperatively from a user node towards the preferred categories and terminate at a product node as recommendation. To train this heterogeneous multi-agent system, where agents own various functionalities, we propose an asynchronous reinforcement training pipeline, called Multi-agent Collaborative Learning. The extensive experiments on real datasets demonstrate the effectiveness and adaptability of Mcore on recommendation tasks.

Graph neural networks (GNNs) have gained increasing attention in their great success at graph representation learning. In GNNs, the neighborhood of the target node is aggregated iteratively to capture and learn its local structure and neighbor information. Observing that different nodes often require a distinct number of iterations to better learn the representation, we propose an adaptive and structure-aware graph sampling scheme GraphANGEL for GNNs. However, it is quite challenging because both the suitable range of exploration and the important substructure in the neighborhood are difficult to determine. Exploiting the unique feature of random walk mixing time and various node structural role importance measures, we first propose a lightweight component to flexibly estimate the proper neighborhood exploration depth for each target node. Then we investigate different importance metrics to identify and sample the most structurally critical subgraphs that carry a larger influence in messaging passing. Moreover, since different importance metrics unveil different aspects of the graph, we combine and ensemble various importance measures with attention to boost the final performance. In this manner, our method adaptively and explicitly embeds the structural importance information of a node and its critical neighborhood at the same time for finer structure-aware graph representation learning. Evaluation on the benchmark datasets suggests the competitive performance of GraphANGEL to the state-of-the-art approaches, demonstrating the effectiveness of our adaptive and structure-aware sampling approach.

Anomaly detection in time series is a research area of increasing importance. In order to safeguard the availability and stability of services, large companies need to monitor various time-series data to detect anomalies in real time for troubleshooting, thereby reducing potential economic losses. However, in many practical applications, time-series anomaly detection is still an intractable problem due to the huge amount of data, complex data patterns, and limited computational resources. SPOT is an efficient streaming algorithm for anomaly detection, but it is only sensitive to extreme values in the whole data distribution. In this paper, we propose FluxEV, a fast and effective unsupervised anomaly detection framework. By converting the non-extreme anomalies to extreme values, our framework addresses the limitation of SPOT and achieves a huge improvement in the detection accuracy. Moreover, Method of Moments is adopted to speed up the parameter estimation in the automatic thresholding. Extensive experiments show that FluxEV greatly outperforms the state-of-the-art baselines on two large public datasets while ensuring high efficiency.

Entity Matching is a classic research problem in any data analytics pipeline, aiming to identify records referring to the same real-world entity. It plays an important role in data cleansing and integration. Advanced entity matching techniques focus on extracting syntactic or semantic features from record pairs via complex neural architectures or pre-trained language models. However, the performances always suffer from noisy or missing attribute values in the records. We observe that comparing one record with several relevant records in a collective manner allows each pairwise matching decision to be made by borrowing valuable insights from other pairs, which is beneficial to the overall matching performance. In this paper, we propose a generic one-to-set neural framework named GNEM for entity matching. GNEM predicts matching labels between one record and a set of relevant records simultaneously. It constructs a record pair graph with weighted edges and adopts the graph neural network to propagate information among pairs. We further show that GNEM can be interpreted as an extension and generalization of the existing pairwise matching techniques. Extensive experiments on real-world data sets demonstrate that GNEM consistently outperforms the existing pairwise entity matching techniques and achieves up to 8.4% improvement on F1-Score compared with the state-of-the-art neural methods.

Recently, deep neural networks (DNNs) have achieved great success in various applications, where low inference latency is important. Existing solutions either manually tune the kernel library or utilize search-based compilation to reduce the operator latency. However, manual tuning requires significant engineering effort, and the huge search space makes the search cost of the search-based compilation unaffordable in some situations. In this work, we propose ETO, a framework for speeding up DNN operator optimization based on reusing the information of performant tensor programs. Specifically, ETO defines conditions for the information reuse between two operators. For operators satisfying the conditions, based on the performant tensor program information of one operator, ETO uses a reuse-based tuner to significantly prune the search space of the other one, and keeps optimization effectiveness at the same time. In this way, for a set of operators, ETO first determines the information reuse relationships among them to reduce the total search time needed, and then tunes the operators either by the backend compiler or by the reuse-based tuner accordingly. ETO further increases the reuse opportunities among the operators by injecting extra operators as bridges between two operators which do not satisfy the reuse conditions. Compared with various existing methods, the experiments show that ETO is effective and efficient in optimizing DNN operators.

Among various recommendation methods, latent factor models are usually considered to be state-of-the-art techniques, which aim to learn user and item embeddings for predicting user-item preferences. When applying latent factor models to the recommendation with implicit feedback, the quality of embeddings always suffers from inadequate positive feedback and noisy negative feedback. Inspired by the idea of NSVD that represents users based on their interacted items, this article proposes a dual-embedding based deep latent factor method for recommendation with implicit feedback. In addition to learning a primitive embedding for a user (resp. item), we represent each user (resp. item) with an additional embedding from the perspective of the interacted items (resp. users) and propose attentive neural methods to discriminate the importance of interacted users/items for dual-embedding learning. We design two dual-embedding based deep latent factor models, DELF and DESEQ, for pure collaborative filtering and temporal collaborative filtering (i.e., sequential recommendation), respectively. The novel attempt of the proposed models is to capture each user-item interaction with four deep representations that are subtly fused for preference prediction. We conducted extensive experiments on four real-world datasets. The results verify the effectiveness of user/item dual embeddings and the superior performance of our methods on item recommendation.

For the emerging mobility-on-demand services, it is of great significance to predict passenger demands based on historical mobility trips towards better vehicle distribution. Prior works have focused on predicting next-step passenger demands at selected locations or hotspots. However, we argue that multi-step citywide passenger demands encapsulate both time-varying demand trends and global statuses, and hence are more beneficial to avoiding demand-service mismatching and developing effective vehicle distribution/scheduling strategies. Furthermore, we find that adaptations of single-step methods are unable to achieve robust prediction with high accuracy for further steps. In this paper, we propose an end-to-end deep neural network model to the prediction task. We employ an encoder-decoder framework based on convolutional and ConvLSTM units to identify complex features that capture spatiotemporal influence and pickup-dropoff interactions on citywide passenger demands. We introduce a multi-level attention model (global attention and temporal attention) to emphasize the effects of latent citywide mobility regularities and capture relevant temporal dependencies. We evaluate our proposed method using real-world mobility trips (taxis and bikes) and the experimental results show that our method achieves higher prediction accuracy than the state-of-the-art approaches.

The goal of traffic prediction is to predict future traffic values such as speeds or flows in a transportation network. Existing studies mainly focus on exploring spatiotemporal dependencies in time and space domains. However, they generally neglect the frequency information encoded in the traffic data, which sheds light on the true spatiotemporal correlations among any vertices in the transportation network. In this paper, we aim to incorporate two kinds of frequency information, time-frequency and space-frequency, into the modeling of spatiotemporal dependencies towards more accurate traffic prediction. We investigate the importance of two frequencies using real traffic data and develop an end-to-end neural approach to utilizing both frequencies for traffic prediction effectively. Specifically, we propose an attention module to aggregate features from semantically related vertices according to their time-frequency similarities, and derive a semantic representation. A novel space-frequency-based gating mechanism is designed to control how much local information is propagated to the state updating, enforced with the graph convolution to generate an effective local representation. Finally, our model combines the semantic and local representations with gated recurrent units to predict future traffic values. Extensive experiments on two real-world traffic datasets demonstrate that our proposed approach yields better prediction performance than the state-of-the-art methods.

Entity matching (EM) is a classic research problem that identifies data instances referring to the same real-world entity. Recent technical trend in this area is to take advantage of deep learning (DL) to automatically extract discriminative features. DeepER and DeepMatcher have emerged as two pioneering DL models for EM. However, these two state-of-the-art solutions simply incorporate vanilla RNNs and straightforward attention mechanisms. In this paper, we fully exploit the semantic context of embedding vectors for the pair of entity text descriptions. In particular, we propose an integrated multi-context attention framework that takes into account self-attention, pair-attention and global-attention from three types of context. The idea is further extended to incorporate attribute attention in order to support structured datasets. We conduct extensive experiments with 7 benchmark datasets that are publicly accessible. The experimental results clearly establish our superiority over DeepER and DeepMatcher in all the datasets.

Business location selection is crucial to the success of businesses. Traditional approaches like manual survey investigate multiple factors, such as foot traffic, neighborhood structure, and available workforce, which are typically hard to measure. In this article, we propose to explore both satellite data (e.g., satellite images and nighttime light data) and urban data for business location selection tasks of various businesses. We extract discriminative features from the two kinds of data and perform empirical analysis to evaluate the correlation between extracted features and the business popularity of locations. A novel neural network approach named R 2 Net is proposed to learn deep interactions among features and predict the business popularity of locations. The proposed approach is trained with a regression-and-ranking combined loss function to preserve accurate popularity estimation and the ranking order of locations simultaneously. To support the location selection for multiple businesses, we propose an approach named AR 2 Net with three attention modules, which enable the approach to focus on different latent features according to business types. Comprehensive experiments on a real-world dataset demonstrate that the satellite features are effective and our models outperform the state-of-the-art methods in terms of four metrics.

The increasing amount of trajectory data facilitates a wide spectrum of practical applications in which large numbers of trajectory range and similarity queries are issued continuously. This calls for high-throughput trajectory query processing. Traditional in-memory databases lack considerations of the unique features of trajectories, while specialized trajectory query processing systems are typically designed for only one type of trajectory queries. This paper introduces GAT, a unified GPU-accelerated framework to process batch trajectory queries with the objective of high throughput. GAT follows the filtering-and-verification paradigm where we develop a novel index GTIDX for effectively filtering invalid trajectories on the CPU, and exploit the massive parallelism of the GPU for verification. To optimize the performance of GAT, we first greedily partition batch queries to reduce the amortized query processing latency. We then apply the Morton-based encoding method to coalesce data access requests from the GPU cores, and maintain a hash table to avoid redundant data transfer between CPU and GPU. To achieve load balance, we group size-varying cells into balanced blocks with similar numbers of trajectory points. Extensive experiments have been conducted over real-life trajectory datasets. The results show that GAT is efficient, scalable, and achieves high throughput with acceptable indexing cost.

Latent factor models (LFMs) such as matrix factorization have achieved the state-of-the-art performance among various collaborative filtering approaches for recommendation. Despite the high recommendation accuracy of LFMs, a critical issue to be resolved is their lack of interpretability. Extensive efforts have been devoted to interpreting the prediction results of LFMs. However, they either rely on auxiliary information which may not be available in practice, or sacrifice recommendation accuracy for interpretability. Influence functions, stemming from robust statistics, have been developed to understand the effect of training points on the predictions of black-box models. Inspired by this, we propose a novel explanation method named FIA (Fast Influence Analysis) to understand the prediction of trained LFMs by tracing back to the training data with influence functions. We present how to employ influence functions to measure the impact of historical user-item interactions on the prediction results of LFMs and provide intuitive neighbor-style explanations based on the most influential interactions. Our proposed FIA exploits the characteristics of two important LFMs, matrix factorization and neural collaborative filtering, and is capable of accelerating the overall influence analysis process. We provide a detailed complexity analysis for FIA over LFMs and conduct extensive experiments to evaluate its performance using real-world datasets. The results demonstrate the effectiveness and efficiency of FIA, and the usefulness of the generated explanations for the recommendation results.

Relation extraction in knowledge base construction has been researched for the last decades due to its applicability to many problems. Most classical works, such as supervised information extraction and distant supervision, focus on how to construct the knowledge base (KB) by utilizing the large number of labels or certain related KBs. However, in many real-world scenarios, the existing methods may not perform well when a new knowledge base is required but only scarce labels or few related KBs available. In this paper, we propose a novel approach called, Relation Extraction via Domain-aware Transfer Learning (ReTrans), to extract relation mentions from a given text corpus by exploring the experience from a large amount of existing KBs which may not be closely related to the target relation. We first propose to initialize the representation of relation mentions from the massive text corpus and update those representations according to existing KBs. Based on the representations of relation mentions, we investigate the contribution of each KB to the target task and propose to select useful KBs for boosting the effectiveness of the proposed approach. Based on selected KBs, we develop a novel domain-aware transfer learning framework to transfer knowledge from source domains to the target domain, aiming to infer the true relation mentions in the unstructured text corpus. Most importantly, we give the stability and generalization bound of ReTrans. Experimental results on the real world datasets well demonstrate that the effectiveness of our approach, which outperforms all the state-of-the-art baselines.

In this paper, we propose a dynamic forecasting framework, named DMDP (dynamic multi-source default probability prediction), to predict the default probability of a company. The default probability is a very important factor to assess the credit risk of listed companies on a stock market. Aiming at aiding financial institutions in decision making, our DMDP framework not only analyzes financial data to capture the historical performance of a company, but also utilizes long short-term memory model to dynamically incorporate daily news from social media to take the perceptions of market participants and public opinions into consideration. The study of this paper makes two key contributions. First, we make use of unstructured news crawled from social media to alleviate the impact of financial fraud issue made on default probability prediction. Second, we propose a neural network method to integrate both structured financial factors and unstructured social media data with appropriate time alignment for default probability prediction. Extensive experimental results demonstrate the effectiveness of DMDP in predicting default probability for the listed companies in mainland China, compared with various baselines.

Air quality has gained much attention in recent years and is of great importance to protecting people’s health. Due to the influence of multiple factors, the limited air quality monitoring stations deployed in cities are unable to provide fine-grained air quality information. One cost-effective way is to infer air quality with records from existing monitoring stations. However, the severe data sparsity problem (e.g., only 0.2% data are known) leads to the failure of most inference methods. We observe that remote sensing data are of high quality and have a strong correlation with the air quality. Therefore, we propose to integrate remote sensing data and ubiquitous urban data for the air quality inference. But there are two main challenges, i.e., data heterogeneity and incompleteness of the remote sensing data. To address the challenges, we propose a two-stage approach. In the first stage, we infer and predict air quality conditions of some places leveraging the remote sensing data and meteorological data with two proposed ANN-based methods, respectively. This stage significantly alleviates the data sparsity problem. In the second stage, the records and estimated air quality data are put in a tensor. A tensor decomposition method is applied to complete the tensor. The features extracted from urban data are classified into the spatial features (i.e., road features and POI features) and the temporal features (i.e., meteorological features) as the constraints to further address the data sparsity problem. In addition, an iterative training framework is proposed to improve the inference performance. Experiments on a real-world dataset show that our approach outperforms state-of-the-art methods, such as U-Air.

There is a growing need for distributed graph processing systems to have many more compute nodes processing graph-based Big Data applications, which, however, increases the chance of node failures. To address the issue, we propose a novel recovery scheme to accelerate the recovery process by parallelizing the recomputation. Once a failure occurs, all recomputations are confined to subgraphs that originally reside in the failed compute nodes. When the recovery starts, these subgraphs are reassigned to another set of compute nodes, where the recomputation over these subgraphs are conducted in parallel. To minimize the recovery latency, we also develop a reassignment strategy, from these subgraphs to the replaced compute nodes, by properly leveraging the computation and communication cost. We integrate the proposed recovery scheme into Giraph system, a widely used graph processing system. The experimental results over a variety of real graph datasets demonstrate that our proposed recovery scheme outperforms existing recovery methods by up to 30x on a cluster of 40 compute nodes.

The increasing amount of trajectory data facilitates a wide spectrum of practical applications. In many such applications, large numbers of trajectory range and similarity queries are issued continuously, which calls for high-throughput trajectory query processing. Traditional in-memory databases lack considerations of the unique features of trajectories, thus suffering from inferior performance. Existing trajectory query processing systems are typically designed for only one type of trajectory queries, i.e., either range or similarity query, but not for both. Inspired by the massive parallelism on GPUs, in this paper, we develop a GPU-accelerated framework, named GAT, to support both types of trajectory queries (i.e., both range and similarity queries) with high throughput. For similarity queries, we adopt the Edit Distance on Real sequence (EDR) as the similarity measure which is accurate and robust to noise in real-world trajectories. GAT employs a GPU-friendly index called GTIDX to effectively filter invalid trajectories for both range and similarity queries, and exploits the GPU to perform parallel verifications. To accelerate the verification process on the GPU, we apply the Morton-based encoding method to reorganize trajectory points and facilitate coalesced data accesses for individual point data in global memory, which reduces the global memory bandwidth requirement significantly. We also propose a technique of grouping size-varying cells into balanced blocks with similar numbers of trajectory points, to achieve load balancing among the Streaming Multiprocessors (SMs) of the GPU. We conduct extensive experiments to evaluate the performance of GAT using two real-life trajectory datasets. The results show that GAT is scalable and achieves high throughput with acceptable indexing cost.

With the prosperity of the location-based social networks, next Point-of-Interest (POI) recommendation has become an important service and received much attention in recent years. The next POI is dynamically determined by the mobility pattern and various contexts associated with user check-in sequence. However, exploring spatial-temporal mobility patterns and incorporating heterogeneous contextual factors for recommendation are challenging issues to be resolved. In this paper, we introduce a novel neural network model named TMCA (Temporal and Multi-level Context Attention) for next POI recommendation. Our model employs the LSTM-based encoder-decoder framework, which is able to automatically learn deep spatial-temporal representations for historical check-in activities and integrate multiple contextual factors using the embedding method in a unified manner. We further propose the temporal and multi-level context attention mechanisms to adaptively select relevant check-in activities and contextual factors for next POI preference prediction. Extensive experiments have been conducted using two real-world check-in datasets. The results verify (1) the superior performance of our proposed method in different evaluation metrics, compared with several state-of-the-art methods; and (2) the effectiveness of the temporal and multi-level context attention mechanisms on recommendation performance.

This paper studies the problem of time series forecasting. A time series is defined as a sequence of data points listed in time order. Many real-life time series data are driven by multiple latent components which occur at different frequencies. Existing solutions to time series forecasting fail to identify and discriminate these frequency-domain components. Inspired by the recent advent of signal processing and speech recognition techniques that decompose a time series signal into its time-frequency representation - a scalogram (or spectrogram), this paper proposes to explicitly disclose frequency-domain information from a univariate time series using wavelet transform, towards improving forecasting accuracy. Based on the transformed data, we leverage different neural networks to capture local time-frequency features and global long-term trend simultaneously. We further employ the attention mechanism to fuse local and global features in an effective manner. The experimental results on real time series show that our proposed approach achieves better performance than various baseline methods.

Transfer learning has gained increasing attention due to the inferior performance of machine learning algorithms with insufficient training data. Most of the previous homogeneous or heterogeneous transfer learning works aim to learn a mapping function between feature spaces based on the inherent correspondence across the source and target domains or labeled instances. However, in many real world applications, existing methods may not be robust when the correspondence across domains is noisy or labeled instances are not representative. In this paper, we develop a novel transfer learning framework called Transfer Learning via Feature Isomorphism Discovery (abbreviated to TLFid), which owns high tolerance for noisy correspondence between domains as well as scarce or non-existing labeled instances. More specifically, we propose a feature isomorphism approach to discovering common substructures across feature spaces and learning a feature mapping function from the target domain to the source domain. We evaluate the performance of TLFid on the cross-lingual sentiment classification tasks. The results show that our method achieves significant improvement in terms of accuracy compared with the state-of-the-art methods.

Dockless shared bikes, which aim at providing a more flexible and convenient solution to the first-and-last mile connection, come into China and expand to other countries at a very impressing speed. The expansion of shared bike business in new cities brings many challenges among which, the most critical one is the parking chaos caused by too many bikes yet insufficient demands. To allow possible actions to be taken in advance, this paper studies the problem of detecting parking hotspots in a new city where no dockless shared bike has been deployed. We propose to measure road hotness by bike density with the help of the Kernal Density Estimation. We extract useful features from multi-source urban data and introduce a novel domain adaption network for transferring hotspots knowledge learned from one city with shared bikes to a new city. The extensive experimental results demonstrate the effectiveness of our proposed approach compared with various baselines.

Recently, dockless shared bike services have achieved great success and reinvented bike sharing business in China. When expanding bike sharing business into a new city, most start-ups always wish to find out how to cover the whole city with a suitable bike distribution. In this paper, we study the problem of inferring bike distribution in new cities, which is challenging. As no dockless bikes are deployed in the new city, we propose to learn insights on bike distribution from cities populated with dockless bikes. We exploit multi-source data to identify important features that affect bike distributions and develop a novel inference model combining Factor Analysis and Convolutional Neural Network techniques. The extensive experiments on real-life datasets show that the proposed solution provides significantly more accurate inference results compared with competitive prediction methods.

Predicting passenger pickup/dropoff demands based on historical mobility trips has been of great importance towards better vehicle distribution for the emerging mobility-on-demand (MOD) services. Prior works focused on predicting next-step passenger demands at selected locations or hotspots. However, we argue that multi-step citywide passenger demands encapsulate both time-varying demand trends and global statuses, and hence are more beneficial to avoiding demand-service mismatching and developing effective vehicle distribution/scheduling strategies. In this paper, we propose an end-to-end deep neural network solution to the prediction task. We employ the encoder-decoder framework based on convolutional and ConvLSTM units to identify complex features that capture spatiotemporal influences and pickup-dropoff interactions on citywide passenger demands. A novel attention model is incorporated to emphasize the effects of latent citywide mobility regularities. We evaluate our proposed method using real-word mobility trips (taxis and bikes) and the experimental results show that our method achieves higher prediction accuracy than the adaptations of the state-of-the-art approaches.

Shortest path query is one of the most fundamental and classic problems in graph analytics, which returns the complete shortest path between any two vertices. However, in many real-life scenarios, only critical vertices on the shortest path are desirable and it is unnecessary to search for the complete path. This paper investigates the shortest path sketch by defining a top- $k$ critical vertices ( $k$ CV) query on the shortest path. Given a source vertex $s$ and target vertex $t$ in a graph, $k$ CV query can return the top- $k$ significant vertices on the shortest path $SP(s,t)$ . The significance of the vertices can be predefined. The key strategy for seeking the sketch is to apply off-line preprocessed distance oracle to accelerate on-line real-time queries. This allows us to omit unnecessary vertices and obtain the most representative sketch of the shortest path directly. We further explore a series of methods and optimizations to answer $k$ CV query on both centralized and distributed platforms, using exact and approximate approaches, respectively. We evaluate our methods in terms of time, space complexity and approximation quality. Experiments on large-scale real-world networks validate that our algorithms are of high efficiency and accuracy.

Modern Non-Volatile Memory (NVM) promises persistence, byte-addressability and DRAM-like read and write latency, which offers great opportunities for big data storage architecture. These excellent properties indicate that NVM has the potential to be incorporated with key-value stores to achieve high performance and durability simultaneously.

The web is a rich resource of structured data. There has been an increasing interest in using web structured data for many applications such as data integration, web search and question answering. In this paper, we present Dexter, a system to find product sites on the web, and detect and extract product specifications from them. Since product specifications exist in multiple product sites, our focused crawler relies on search queries and backlinks to discover product sites. To perform the detection, and handle the high diversity of specifications in terms of content, size and format, our system uses supervised learning to classify HTML fragments (e.g., tables and lists) present in web pages as specifications or not. To perform large-scale extraction of the attribute-value pairs from the HTML fragments identified by the specification detector, D exter adopts two lightweight strategies: a domain-independent and unsupervised wrapper method, which relies on the observation that these HTML fragments have very similar structure; and a combination of this strategy with a previous approach, which infers extraction patterns by annotations generated by automatic but noisy annotators. The results show that our crawler strategy to locate product specification pages is effective: (1) it discovered 1:46A M product specification pages from 3; 005 sites and 9 different categories; (2) the specification detector obtains high values of F-measure (close to 0:9) over a heterogeneous set of product specifications; and (3) our efficient wrapper methods for attribute-value extraction get very high values of precision (0.92) and recall (0.95) and obtain better results than a state-of-the-art, supervised rule-based wrapper.

An enterprise information worker is often aware of a few example tuples (but not the entire result) that should be present in the output of the query. We study the problem of discovering the minimal project join query that contains the given example tuples in its output. Efficient discovery of such queries is challenging. We propose novel algorithms to solve this problem. Our experiments on real-life datasets show that the proposed solution is significantly more efficient compared with na\"{i}ve adaptations of known techniques.

Distributed graph processing systems increasingly require many compute nodes to cope with the requirements imposed by contemporary graph-based Big Data applications. However, increasing the number of compute nodes increases the chance of node failures. Therefore, provisioning an efficient failure recovery strategy is critical for distributed graph processing systems. This paper proposes a novel recovery mechanism for distributed graph processing systems that parallelizes the recovery process. The key idea is to partition the part of the graph that is lost during a failure among a subset of the remaining nodes. To do so, we augment the existing checkpoint-based and log-based recovery schemes with a partitioning mechanism that is sensitive to the total computation and communication cost of the recovery process. Our implementation on top of the widely used Giraph system outperforms checkpoint-based recovery by up to 30x on a cluster of 40 compute nodes.

Some complex problems, such as image tagging and natural language processing, are very challenging for computers, where even state-of-the-art technology is yet able to provide satisfactory accuracy. Therefore, rather than relying solely on developing new and better algorithms to handle such tasks, we look to the crowdsourcing solution -- employing human participation -- to make good the shortfall in current technology. Crowdsourcing is a good supplement to many computer tasks. A complex job may be divided into computer-oriented tasks and human-oriented tasks, which are then assigned to machines and humans respectively. To leverage the power of crowdsourcing, we design and implement a Crowdsourcing Data Analytics System, CDAS. CDAS is a framework designed to support the deployment of various crowdsourcing applications. The core part of CDAS is a quality-sensitive answering model, which guides the crowdsourcing engine to process and monitor the human tasks. In this paper, we introduce the principles of our quality-sensitive model. To satisfy user required accuracy, the model guides the crowdsourcing query engine for the design and processing of the corresponding crowdsourcing jobs. It provides an estimated accuracy for each generated result based on the human workers' historical performances. When verifying the quality of the result, the model employs an online strategy to reduce waiting time. To show the effectiveness of the model, we implement and deploy two analytics jobs on CDAS, a twitter sentiment analytics job and an image tagging job. We use real Twitter and Flickr data as our queries respectively. We compare our approaches with state-of-the-art classification and image annotation techniques. The results show that the human-assisted methods can indeed achieve a much higher accuracy. By embedding the quality-sensitive model into crowdsourcing query engine, we effectively reduce the processing cost while maintaining the required query answer quality.

k nearest neighbor join ( k NN join), designed to find k nearest neighbors from a dataset S for every object in another dataset R , is a primitive operation widely adopted by many data mining applications. As a combination of the k nearest neighbor query and the join operation, k NN join is an expensive operation. Given the increasing volume of data, it is difficult to perform a k NN join on a centralized machine efficiently. In this paper, we investigate how to perform k NN join using MapReduce which is a well-accepted framework for data-intensive applications over clusters of computers. In brief, the mappers cluster objects into groups; the reducers perform the k NN join on each group of objects separately. We design an effective mapping mechanism that exploits pruning rules for distance filtering, and hence reduces both the shuffling and computational costs. To reduce the shuffling cost, we propose two approximate algorithms to minimize the number of replicas. Extensive experiments on our in-house cluster demonstrate that our proposed methods are efficient, robust and scalable.