Text-to-Image (T2I) generation is a popular AI-generated content (AIGC) technology enabling diverse and creative image synthesis. However, some outputs may contain Not Safe For Work (NSFW) content (e.g., violence), violating community guidelines. Detecting NSFW content efficiently and accurately, known as external safeguarding, is essential. Existing external safeguards fall into two types: text filters, which analyze user prompts but overlook T2I model-specific variations and are prone to adversarial attacks; and image filters, which analyze final generated images but are computationally costly and introduce latency. Diffusion models, the foundation of modern T2I systems like Stable Diffusion, generate images through iterative denoising using a U-Net architecture with ResNet and Transformer blocks. We observe that: (1) early denoising steps define the semantic layout of the image, and (2) cross-attention layers in U-Net are crucial for aligning text and image regions. Based on these insights, we propose Wukong, a transformer-based NSFW detection framework that leverages intermediate outputs from early denoising steps and reuses U-Net's pre-trained cross-attention parameters. Wukong operates within the diffusion process, enabling early detection without waiting for full image generation. We also introduce a new dataset containing prompts, seeds, and image-specific NSFW labels, and evaluate Wukong on this and two public benchmarks. Results show that Wukong significantly outperforms text-based safeguards and achieves comparable accuracy of image filters, while offering much greater efficiency.

The World Wide Web increasingly relies on intelligent services that require accurate time series forecasting, from urban mobility platforms to adaptive web-based decision systems. In practice, building effective forecasting models typically requires abundant high-quality data, which may not always be available in all cities due to sensing limitations or data sparsity. To address this challenge, transfer learning methods aim to transfer knowledge from data-rich source cities to data-scarce target cities. However, source and target data distributions are often not identical: while some patterns from source cities may be beneficial, others can be irrelevant or even misleading. Existing transfer learning methods generally train the target model using all available source data without explicitly distinguishing between useful and non-useful knowledge, which may hinder performance. In this work, we propose xRAG4TS, a novel framework that integrates Retrieval-Augmented Generation (RAG) with Large Language Models (LLMs) for cross-city time series forecasting. xRAG4TS introduces a Cross-City Selective Retriever Module that filters semantically relevant historical patterns and documents from data-rich source cities, and incorporates them as structured prompts in an LLM Inference Module to guide forecasting in data-scarce target cities. By enabling selective, interpretable, and context-aware knowledge transfer, our method enhances robustness and scalability in web-oriented spatio-temporal applications. Extensive experiments on real-world cross-city datasets demonstrate that xRAG4TS significantly outperforms state-of-the-art baselines, highlighting its potential for powering adaptive and trustworthy web services under severe data scarcity.

Space-filling curves (SFC, for short) have been widely applied to index multi-dimensional data, which first maps the data to one dimension, and then a one-dimensional indexing method, e.g., the B-tree indexes the mapped data. Existing SFCs adopt a single mapping scheme for the whole data space. However, a single mapping scheme often does not perform well on all the data space. In this paper, we propose a new type of SFC called piecewise SFCs that adopts different mapping schemes for different data subspaces. Specifically, we propose a data structure termed the Bit Merging tree (BMTree) that can generate data subspaces and their SFCs simultaneously, and achieve desirable properties of the SFC for the whole data space. Furthermore, we develop a reinforcement learning-based solution to build the BMTree, aiming to achieve excellent query performance. To update the BMTree efficiently when the distributions of data and/or queries change, we develop a new mechanism that achieves fast detection of distribution shifts in data and queries, and enables partial retraining of the BMTree. The retraining mechanism achieves performance enhancement efficiently since it avoids retraining the BMTree from scratch. Extensive experiments show the effectiveness and efficiency of the BMTree with the proposed learning-based methods.

Cohesive subgraph mining has been extensively studied and finds numerous graph mining applications such as link farm identification, community detection, and product recommendation. Among various cohesive subgraph structures, the$k$-truss is particularly notable for its strong structural cohesiveness based on triangles. However, the classical$k$-truss problem aims to find the$k$-truss with the maximum number of vertices, which is often extremely large and complex in practice. To fully leverage the benefits of the$k$-truss, we consider a novel problem called theminimum$k$-truss problem, which seeks to identify a$k$-truss with the minimum number of vertices, where$k\geq 2$is a positive integer. We first formally prove the NP-hardness of the problem. We then design a baseline algorithmMTEnumthat is based on the vertex enumeration and a heuristic method for computing an upper bound. Despite these efforts,MTEnumstill faces practical efficiency issues which may be due to the fact that the$k$-truss lacks the hereditary property. To address this issue, we develop a novel decomposition-based frameworkDSA, which elegantly transforms the problem into a sequence of problems that are based on a new cohesive subgraph model callededge-based$s$-plex ($s$-eplex). With the hereditary property of$s$-eplex, we design a branch-and-bound algorithm with several customized techniques for the newly formulated problem. Extensive experiments demonstrate the effectiveness of our studied problem and the efficiency of our proposed algorithmDSA. In particular,DSAruns up to five orders of magnitude faster than the baselineMTEnum.

Finding frequent subgraph patterns in a big graph is an important problem with many applications such as classifying chemical compounds and building indexes to speed up graph queries. Since this problem is NP-hard, some recent parallel and distributed systems have been developed to accelerate the mining. However, they often have a huge memory cost, very long running time, suboptimal load balancing, poor scale-out capability, and possibly inaccurate results. In this article, we propose an efficient system called T-FSM for parallel mining of frequent subgraph patterns in a big graph. T-FSM supports a new anti-monotonic frequentness measure called Fraction-Score, which is more accurate than the widely used MNI measure. The execution engine of T-FSM supports both intra-machine parallelism and inter-machine parallelism. For intra-machine parallelism, T-FSM adopts a novel task-based execution model to ensure high multithreading concurrency, bounded memory consumption, and effective load balancing. For inter-machine parallelism, T-FSM ensures good scale-out performance with a lightweight pattern rebalancing approach that reduces workload skewness of pattern evaluations among machines. To avoid recomputing the contexts for migrated patterns, we design a novel context cache table to support concurrent and asynchronous requesting and caching of remote context data, which can timely evict and garbage collect used pattern contexts that are no longer needed to keep memory consumption bounded. Extensive experiments show that T-FSM is orders of magnitude faster than existing state-of-the-art parallel systems (more than 10×, 51×, 131×, 55× speedup over ScaleMine, DistGraph, Pangolin and Peregrine, respectively) and distributed systems (more than 42× and 88× over ScaleMine and DistGraph, respectively) for frequent subgraph pattern mining, and it scales out satisfactorily to 512 CPU cores on the Polaris supercomputer at Argonne National Laboratory.

Traffic congestion is becoming an increasingly prominent problem, and intelligent traffic signal control methods can effectively alleviate it. Recently, there has been a growing trend of applying reinforcement learning to traffic signal control for adaptive signal scheduling. However, most existing methods focus on improving traffic performance while neglecting the issue of scheduling fairness, resulting in long waiting time for some vehicles. Some works attempt to address fairness issues but often sacrifice transport performance. Furthermore, existing methods overlook the challenge of sample efficiency, especially when dealing with diversity-limited traffic data. Therefore, we propose a Fairess-aware and sample-Efficient traffic signal control method called FELight. Specifically, we first design a novel fairness metric and integrate it into decision process to penalize cases with high latency by setting a threshold for activating the fairness mechanism. Theoretical comparison with other fairness works proves why and when our fairness could bring advantages. Moreover, counterfactual data augmentation is employed to enrich interaction data, enhancing the sample efficiency of FELight. Self-supervised state representation is introduced to extract informative features from raw states, further improving sample efficiency. Experiments on real traffic datasets demonstrate that FELight provides relatively fairer traffic signal control without compromising performance compared to state-of-the-art approaches.

Human mobility prediction is a fundamental technique for many urban applications, e.g., location-based recommendation, traffic scheduling, and travel demand prediction. Over the past decades, many methods, e.g., Markov Model, RNN, Transformer, have been leveraged to tackle the problem. However, existing approaches mainly train a supervised model based on an offline training dataset, which overlooks the phenomenon that the mobility behaviors of humans vary across time, and the trained models may not achieve ideal performance when applied to the testing data. To tackle this challenge, in this paper, we propose AdaMove, an efficient Test-Time Adaptive (TTA) model for human mobility prediction. AdaMove has a Preference-aware Test-Time Adaptation module called PTTA, which can adjust the parameters of a trained model based on the input test trajectory such that the model can generalize to the test distribution. In addition, to address the issue of reduced inference efficiency caused by parameter adjustment during the testing phase, AdaMove is equipped with a Lightweight human Mobility prediction model called LightMob, which only requires the recent trajectory as input to accelerate the inference. It is enhanced by historical trajectory knowledge via contrastive learning during the training time, so it has competitive performance compared with existing models. Extensive experiments on three real-world human mobility datasets demonstrate that AdaMove outperforms the best baseline by 9.3% on average in accuracy, and accelerates the inference speed by 28.5% on average compared with the original TTA - based inference.

Multivariate time series forecasting (MTSF) endeavors to predict future observations given historical data, playing a crucial role in time series data management systems. With advancements in large language models (LLMs), recent studies employ textual prompt tuning to infuse the knowledge of LLMs into MTSF. However, the deployment of LLMs often suffers from low efficiency during the inference phase. To address this problem, we introduce TimeKD, an efficient MTSF framework that leverages the calibrated language models and privileged knowledge distillation. TimeKD aims to generate high-quality future representations from the proposed cross-modality teacher model and cultivate an effective student model. The cross-modality teacher model adopts calibrated language models (CLMs) with ground truth prompts, motivated by the paradigm of Learning Under Privileged Information (LUPI). In addition, we design a subtractive cross attention (SCA) mechanism to refine these representations. To cultivate an effective student model, we propose an innovative privileged knowledge distillation (PKD) mechanism including correlation and feature distillation. PKD enables the student to replicate the teacher's behavior while minimizing their output discrepancy. Extensive experiments on real data offer insight into the effectiveness, efficiency, and scalability of the proposed TimeKD.

Maximal clique enumeration (MCE) is crucial for tasks like community detection and biological network analysis. Existing algorithms typically adopt the branch-and-bound frame-work with the vertex-oriented Bron-Kerbosch (BK) branching strategy, which forms the sub-branches by expanding the partial clique with a vertex. In this paper, we present a novel approach, HBBMC, a hybrid framework combining vertex-oriented BK branching and edge-oriented BK branching, where the latter adopts a branch-and-bound framework which forms the sub-branches by expanding the partial clique with a edge. This hybrid strategy enables more effective pruning and helps achieve a worst-case time complexity better than the best-known one under a condition which holds for the majority of real-world graphs. To further enhance efficiency, we introduce an early termination technique, which leverages the topological information of the graphs and constructs the maximal cliques directly without branching. Our early termination technique is applicable to all branch-and-bound frameworks. Extensive experiments demonstrate the superior performance of our techniques.

Cohesive subgraph mining is a fundamental problem in graph theory with numerous real-world applications, such as social network analysis and protein-protein interaction modeling. Among various cohesive subgraphs, the γ-quasi-clique is widely studied for its flexibility in requiring each vertex to connect to at least a γ proportion of other vertices in the subgraph. However, solving the maximum γ-quasi-clique problem is NP-hard and further complicated by the lack of the hereditary property, which makes designing efficient pruning strategies challenging. Existing algorithms, such as DDA and FastQC, either struggle with scalability or exhibit significant performance declines for small values of γ. In this paper, we propose a novel algorithm, IterQC, which reformulates the maximum γ-quasi-clique problem as a series of k-plex problems that possess the hereditary property. IterQC introduces a non-trivial iterative framework and incorporates two key optimization techniques: (1) the pseudo lower bound (pseudo LB) technique, which leverages information across iterations to improve the efficiency of branch-and-bound searches, and (2) the preprocessing technique that reduces problem size and unnecessary iterations. Extensive experiments demonstrate that IterQC achieves up to four orders of magnitude speedup and solves significantly more graph instances compared to state-of-the-art algorithms DDA and FastQC.

In the era of large foundation models, data has become a crucial component in building high-performance AI systems. As the demand for high-quality and large-scale data continues to rise, data copyright protection is attracting increasing attention. In this work, we explore the problem of data watermarking for sequential recommender systems, where a watermark is embedded into the target dataset and can be detected in models trained on that dataset. We focus on two settings: dataset watermarking, which protects the ownership of the entire dataset, and user watermarking, which safeguards the data of individual users. We present a method named Dataset Watermarking for Recommender Systems (DWRS) to address them. We define the watermark as a sequence of consecutive items inserted into normal users' interaction sequences. We define a Receptive Field (RF) to guide the inserting process to facilitate the memorization of the watermark. Extensive experiments on five representative sequential recommendation models and three benchmark datasets demonstrate the effectiveness of DWRS in protecting data copyright while preserving model utility.

Large Language Models (LLMs) have emerged as a promising paradigm for time series analytics, leveraging their massive parameters and the shared sequential nature of textual and time series data.However, a cross-modality gap exists between time series and textual data, as LLMs are pre-trained on textual corpora and are not inherently optimized for time series.In this tutorial, we provide an up-to-date overview of LLM-based cross-modal time series analytics.We introduce a taxonomy that classifies existing approaches into three groups based on cross-modal modeling strategies, e.g., conversion, alignment, and fusion, and then discuss their applications across a range of downstream tasks.In addition, we summarize several open challenges.This tutorial aims to expand the practical application of LLMs in solving real-world problems in cross-modal time series analytics while balancing effectiveness and efficiency.Participants will gain a thorough understanding of current advancements, methodologies, and future research directions in cross-modal time series analytics.

Sequential recommendation (SR) systems excel at capturing users' dynamic preferences by leveraging their interaction histories. Most existing SR systems assign a single embedding vector to each item to represent its features, and various types of models are adopted to combine these item embeddings into a sequence representation vector to capture the user intent. However, we argue that this representation alone is insufficient to capture an item's multi-faceted nature (e.g., movie genres, starring actors). Besides, users often exhibit complex and varied preferences within these facets (e.g., liking both action and musical films in the facet of genre), which are challenging to fully represent. To address the issues above, we propose a novel structure called Facet-Aware Multi-Head Mixture-of-Experts Model for Sequential Recommendation (FAME). We leverage sub-embeddings from each head in the last multi-head attention layer to predict the next item separately. A gating mechanism integrates recommendations from each head and dynamically determines their importance. Furthermore, we introduce a Mixture-of-Experts (MoE) network in each attention head to disentangle various user preferences within each facet. Each expert within the MoE focuses on a specific preference. A learnable router network is adopted to compute the importance weight for each expert and aggregate them. We conduct extensive experiments on four public sequential recommendation datasets and the results demonstrate the effectiveness of our method over existing baseline models.

Despite the success of Heterogeneous Graph Neural Networks (HGNNs) in modeling real-world Heterogeneous Information Networks (HINs), challenges such as expressiveness limitations and over-smoothing have prompted researchers to explore Graph Transformers (GTs) for enhanced HIN representation learning. However, research on GT in HINs remains limited, with two key shortcomings in existing work: (1) A node's neighbors at different distances in HINs convey diverse semantics; for instance, a paper's direct neighbor (a paper) in an academic graph signifies a citation relation, whereas the indirect neighbor (another paper) implies a thematic association, reflecting distinct meanings. Unfortunately, existing methods ignore such differences and uniformly treat neighbors within a given distance in a coarse manner, which results in semantic confusion. (2) Nodes in HINs have various types, each with unique semantics, e.g., papers and authors in an academic graph carry distinct meanings. Nevertheless, existing methods mix nodes of different types during neighbor aggregation, hindering the capture of proper correlations between nodes of diverse types. To bridge these gaps, we design an innovative structure named (k,t)-ring neighborhood, where nodes are initially organized by their distance, forming different non-overlapping k-ring neighborhoods for each distance. Within each k-ring structure, nodes are further categorized into different groups according to their types, thus emphasizing the heterogeneity of both distances and types in HINs naturally. Based on this structure, we propose a novel Hierarchical Heterogeneous Graph Transformer (HHGT) model, which seamlessly integrates a Type-level Transformer for aggregating nodes of different types within each k-ring neighborhood, followed by a Ring-level Transformer for aggregating different k-ring neighborhoods in a hierarchical manner. Extensive experiments are conducted on downstream tasks to verify HHGT's superiority over 14 baselines, with a notable improvement of up to 24.75% in NMI and 29.25% in ARI for node clustering task on the ACM dataset compared to the best baseline.

Retrieval-Augmented Generation (RAG) has been an effective approach to mitigate hallucinations in large language models (LLMs) by incorporating up-to-date and domain-specific knowledge. Recently, there has been a trend of storing up-to-date or copyrighted data in RAG knowledge databases instead of using it for LLM training. This practice has raised concerns about Membership Inference Attacks (MIAs), which aim to detect if a specific target document is stored in the RAG system's knowledge database so as to protect the rights of data producers. While research has focused on enhancing the trustworthiness of RAG systems, existing MIAs for RAG systems remain largely insufficient. Previous work either relies solely on the RAG system's judgment or is easily influenced by other documents or the LLM's internal knowledge, which is unreliable and lacks explainability. To address these limitations, we propose a Mask-Based Membership Inference Attacks (MBA) framework. Our framework first employs a masking algorithm that effectively masks a certain number of words in the target document. The masked text is then used to prompt the RAG system, and the RAG system is required to predict the mask values. If the target document appears in the knowledge database, the masked text will retrieve the complete target document as context, allowing for accurate mask prediction. Finally, we adopt a simple yet effective threshold-based method to infer the membership of target document by analyzing the accuracy of mask prediction. Our mask-based approach is more document-specific, making the RAG system's generation less susceptible to distractions from other documents or the LLM's internal knowledge. Extensive experiments demonstrate the effectiveness of our approach compared to existing baseline models.

Approximate nearest neighbor (ANN) query in high-dimensional Euclidean space is a key operator in database systems. For this query, quantization is a popular family of methods developed for compressing vectors and reducing memory consumption. Among these methods, a recent algorithm called RaBitQ achieves the state-of-the-art performance and provides an asymptotically optimal theoretical error bound. RaBitQ uses 1 bit per dimension for quantization and compresses vectors with a large compression rate. In this paper, we extend RaBitQ to compress vectors with flexible compression rates - it achieves this by using B bits per dimension for quantization with B = 1, 2, ... It inherits the theoretical guarantees of RaBitQ and achieves the asymptotic optimality in terms of the trade-off between space and error bounds as to be proven in this study. Additionally, we present efficient implementations of the extended RaBitQ, enabling its application to ANN queries to reduce both space and time consumption. Extensive experiments on real-world datasets confirm that our method consistently outperforms the state-of-the-art baselines in both accuracy and efficiency when using the same amount of memory.

Approximate nearest neighbor (ANN) search in high-dimensional Euclidean space has a broad range of applications. Among existing ANN algorithms, graph-based methods have shown superior performance in terms of the time-accuracy trade-off. However, they face performance bottlenecks due to the random memory accesses caused by the searching process on the graph indices and the costs of computing exact distances to guide the searching process. To relieve the bottlenecks, a recent method named NGT-QG makes an attempt by integrating quantization and graph. It (1) replicates and stores the quantization codes of a vertex's neighbors compactly so that they can be accessed sequentially, and (2) uses a SIMD-based implementation named FastScan to efficiently estimate distances based on the quantization codes in batch for guiding the searching process. While NGT-QG achieves promising improvements over the vanilla graph-based methods, it has not fully unleashed the potential of integrating quantization and graph. For instance, it entails a re-ranking step to compute exact distances at the end, which introduces extra random memory accesses; its graph structure is not jointly designed considering the in-batch nature of FastScan, which causes wastes of computation in searching. In this work, following NGT-QG, we present a new method named SymphonyQG, which achieves more symphonious integration of quantization and graph (e.g., it avoids the explicit re-ranking step and refines the graph structure to be more aligned with FastScan). Based on extensive experiments on real-world datasets, SymphonyQG establishes the new state-of-the-art in terms of the time-accuracy trade-off: at 95% recall, SymphonyQG achieves 1.5x-4.5x QPS compared with the most competitive baselines and achieves 3.5x-17x QPS compared with the classical library HNSWlib across all tested datasets. At the same time, its indexing is at least 8x faster than NGT-QG.

The s -bundle, as a cohesive subgraph model which relaxes the clique, remains connected whenever fewer than n-s vertices are removed, where n is the number of vertices inside. Finding the largest s -bundle is a fundamental problem and has diverse applications in various fields such as social network analysis, graph visualization, and bioinformatics. Existing studies for solving the problem follow the same branch-and-bound framework and improve the efficiency by developing pruning techniques. As a result, all share the same worst-case time complexity of O* (2 n ), where O* suppresses the polynomial factors. In this paper, we propose a new branch-and-bound algorithm, called SymBD, which achieves improved theoretical guarantees and practical performance. It adopts the existing Symmetric-BK branching strategy whose performance highly depends on the ordering of vertices. We explore various vertex orderings for improving the performance. In particular, we propose two novel vertex orderings based on the local vertex connectivity. With the proposed vertex orderings, SymBD improves the worst-case time complexity to O* (λ n s ) where λ s is strictly less than 2. To further boost the practical efficiency, we introduce a heuristic algorithm for computing a large initial solution and a divide-and-conquer strategy. Extensive experiments on 664 graphs demonstrate that our algorithm is up to five orders of magnitude faster than existing solutions.

Community search has widespread applications in areas such as advertising, friend recommendation, and protein complex identification. In this paper, we revisit the Size-bounded Community Search (SCS) problem, which aims to identify a connected subgraph containing a query vertex q and between l and h vertices, while maximizing the minimum degree of the subgraph. Existing state-of-the-art exact solutions for SCS face challenges in practical efficiency due to ineffective strategies for searching candidate solutions and suboptimal method for finding optimal solution. To address these challenges, we propose a novel branch-and-bound algorithm that efficiently locating a subset of candidate solutions with favorable structural properties, forming the basis for three progressively refined frameworks to determine the optimal solution. Furthermore, we enhance practical performance through a new heuristic, two reduction rules, and a query decomposition technique. Extensive experiments on 12 large real-world graphs demonstrate that our most efficient framework significantly outperforms state-of-the-art methods, achieving an average speedup of two orders of magnitude while consistently identifying communities with higher cohesion.

Bimodal data, such as image-text pairs, has become increasingly prevalent in the digital era. The Hybrid Vector Query (HVQ) is an effective approach for querying such data and has recently garnered considerable attention from researchers. It calculates similarity scores for objects represented by two vectors using a weighted sum of each individual vector's similarity, with a query-specific parameter α to determine the weight. Existing methods for HVQ typically construct Approximate Nearest Neighbors Search (ANNS) indexes with a fixed α value. This leads to significant performance degradation when the query's α dynamically changes based on the different scenarios and needs. In this study, we introduce the Dynamic Edge Navigation Graph ( DEG ), a graph-based ANNS index that maintains efficiency and accuracy with changing α values. It includes three novel components: (1) a greedy Pareto frontier search algorithm to compute a candidate neighbor set for each node, which comprises the node's approximate nearest neighbors for all possible α values; (2) a dynamic edge pruning strategy to determine the final edges from the candidate set and assign each edge an active range. This active range enables the dynamic use of the Relative Neighborhood Graph's pruning strategy based on the query's α values, skipping redundant edges at query time and achieving a better accuracy-efficiency trade-off; and (3) an edge seed method that accelerates the querying process. Extensive experiments on real-world datasets show that DEG demonstrates superior performance compared to existing methods under varying α values.

Given two input graphs, finding the largest subgraph that occurs in both, i.e., finding the maximum common subgraph, is a fundamental operator for evaluating the similarity between two graphs in graph data analysis. Existing works for solving the problem are of either theoretical or practical interest, but not both. Specifically, the algorithms with a theoretical guarantee on the running time are known to be not practically efficient; algorithms following the recently proposed backtracking framework called McSplit, run fast in practice but do not have any theoretical guarantees. In this paper, we propose a new backtracking algorithm called RRSplit, which at once achieves better practical efficiency and provides a non-trivial theoretical guarantee on the worst-case running time. To achieve the former, we develop a series of reductions and upper bounds for reducing redundant computations, i.e., the time for exploring some unpromising branches of exploration that hold no maximum common subgraph. To achieve the latter, we formally prove that RRSplit incurs a worst-case time complexity which matches the best-known complexity for the problem. Finally, we conduct extensive experiments on four benchmark graph collections, and the results demonstrate that our algorithm outperforms the practical state-of-the-art by several orders of magnitude.

With the increasing popularity of GPS modules, there are various urban applications such as car navigation relying on trajectory data modeling. In this work, we study the problem of modeling on-road trajectories, which is to predict the next road segment given a partial GPS trajectory. Existing methods that model trajectories with Markov chain or recurrent neural network suffer from various issues, including limited capability of sequential modeling, insufficiency of incorporating the road network context, and lack of capturing the underlying semantics of trajectories. In this article, we propose a new trajectory modeling framework called Multi-task Modeling for Trajectories (MMTraj+), which avoids these issues. Specifically, MMTraj+ uses multi-head self-attention networks for sequential modeling, captures the overall road network as the context information for road segment embedding, and performs an auxiliary task of predicting the trajectory destination information (namely the ID and bearing angle) to better guide the main trajectory modeling task (controlled by a carefully designed gating mechanism). In addition, we tailor MMTraj+ for the cases where the destination information is known by dropping its auxiliary task of predicting the trajectory destination information. Extensive experiments conducted on real-world datasets demonstrate the superiority of the proposed method over the baseline methods.

Finding cohesive subgraphs from a directed graph is a fundamental approach to analyze directed graph data. We consider a new model called directed$(k,\ell )$-plex for a cohesive directed subgraph, which is generalized from the concept of$k$-plex that is only applicable to undirected graphs. Directed$(k,\ell )$-plex (or DPlex) has the connection requirements on both inbound and outbound directions of each vertex inside, i.e., each vertex disconnects at most$k$vertices and is meanwhile not pointed to by at most$\ell$vertices. In this paper, we study the maximum DPlex search problem which finds a DPlex with the most vertices. We formally prove the NP-hardness of the problem. We then design a heuristic algorithm calledDPHeuris, which finds a DPlex with the size close to the maximum one and runs practically fast in polynomial time. Furthermore, we propose a branch-and-bound algorithm calledDPBBto find the exact maximum DPlex and develop effective graph reduction strategies for boosting the empirical performance. We also consider the problem of querying personalized maximum DPlex, and design a new method calledDPBBQfor the problem. Finally, we conduct extensive experiments on real directed graphs. The experimental results show that (1) our heuristic method can quickly find a near-optimal solution and (2) our branch-and-bound method runs up to six orders of magnitude faster than other baselines.

Traffic prediction is a crucial component of data management systems, leveraging historical data to learn spatio-temporal dynamics for forecasting future traffic and enabling efficient decision-making and resource allocation. Despite efforts to develop increasingly complex architectures, existing traffic prediction models often struggle to generalize across diverse datasets and contexts, limiting their adaptability in real-world applications. In contrast to existing traffic prediction models, large language models (LLMs) progress mainly through parameter expansion and extensive pre-training while maintaining their fundamental structures. In this paper, we propose ST-LLM+, the graph enhanced spatio-temporal large language models for traffic prediction. Through incorporating a proximity-based adjacency matrix derived from the traffic network into the calibrated LLMs, ST-LLM+ captures complex spatio-temporal dependencies within the traffic network. The Partially Frozen Graph Attention (PFGA) module is designed to retain global dependencies learned during LLMs pre-training while modeling localized dependencies specific to the traffic domain. To reduce computational overhead, ST-LLM+ adopts the LoRA-augmented training strategy, allowing attention layers to be fine-tuned with fewer learnable parameters. Comprehensive experiments on real-world traffic datasets demonstrate that ST-LLM+ outperforms state-of-the-art models. In particular, ST-LLM+ also exhibits robust performance in both few-shot and zero-shot prediction scenarios. Additionally, our case study demonstrates that ST-LLM+ captures global and localized dependencies between stations, verifying its effectiveness for traffic prediction tasks.

The$k$-vertex connected ($k$-VC) subgraph, which remains connected with fewer than$k$vertices being removed, is an essential structure in graph mining. It has found many applications, such as survivable network design and web search optimization. However, existing studies focus on mining maximal$k$-VCs, which are excessively large yet less cohesive in real applications. In this paper, we study theminimum$k$-VC search (MinVC)problem, seeking to find a$k$-VC with the minimum number of vertices. We formally prove that this problem is NP-hard and then propose two algorithms to obtain the exact solution. The basic method, calledEnum, follows a branch-and-bound framework with some pruning rules, which directly enumerates all possible vertex sets. Nonetheless, it suffers from the efficiency issues due to the non-hereditary property of the$k$-VC model. To address this challenge, we propose an advanced method, calledVCtoB, which divides theMinVCproblem into several new sub-problems, called thefixed-size$k$-VCproblems. Each of them can be solved efficiently by exploiting the hereditary property of the$s$-bundle model. Finally, our empirical experiments on 139 real-world networks demonstrate thatVCtoBachieves performance improvement of up to six orders of magnitude over the baseline.

Intelligent logistics relies on accurately predicting the service time, which is a part of time cost in the last-mile delivery. However, service time prediction (STP) is non-trivial given complex delivery circumstances, location heterogeneity, and skewed observations in space, which are not well-handled by existing solutions. In our prior work, we treat STP at each location as a learning task to keep the location heterogeneity, propose a prior knowledge-enhanced meta-learning to tackle skewed observations, and introduce a Transformer-based representation module to encode complex delivery circumstances. Maintaining the design principles of prior work, in this extended paper, we propose MetaSTP+. In addition to fusing the prior knowledge after the meta-learning process, MetaSTP+also injects the prior knowledge before and during the meta-learning process to better tackle skewed observations. More specifically, MetaSTP+completes the support set of tasks with scarce samples from other tasks based on prior knowledge and is equipped with a prior knowledge-aware historical observation encoding module to achieve those purposes accordingly. Experiments show MetaSTP+outperforms the best baseline by 11.2% and 8.4% on two real-world datasets. Finally, an intelligent waybill assignment system based on MetaSTP+is deployed in JD Logistics.

Given a large graph$G$, a subgraph query$Q$finds the set of all subgraphs of$G$that satisfy certain conditions specified by$Q$. Examples of subgraph queries including finding a community containing designated members to organize an event, and subgraph matching. To overcome the weakness of existing graph-parallel systems that underutilize CPU cores when finding subgraphs, our prior system, G-thinker, was proposed that adopts a novel think-like-a-task (TLAT) parallel programming model. However, G-thinker targets offline analytics and cannot support interactive online querying where users continually submit subgraph queries with different query contents. The challenges here are (i) how to maintain fairness that queries are answered in the order that they are received: a later query is processed only if earlier queries cannot saturate the available computation resources; (ii) how to track the progress of active queries (each with many tasks under computation) so that users can be timely notified as soon as a query completes; and (iii) how to maintain memory boundedness and high task concurrency as in G-thinker. In this article, we propose a novel TLAT programming framework, called G-thinkerQ, for answering online subgraph queries. G-thinkerQ inherits the memory boundedness and high task concurrency of G-thinker by organizing the tasks of each query using a “task capsule” structure, and designs a novel task-capsule list is to ensure fairness among queries. A novel lineage-based mechanism is also designed to keep track of when the last task of a query is completed. Parallel counterparts of the state-of-the-art algorithms for 4 recent advanced subgraph queries are implemented on G-thinkerQ to demonstrate its CPU-scalability.

Recommender systems embody significant commercial value and represent crucial intellectual property. However, the integrity of these systems is constantly challenged by malicious actors seeking to steal their underlying models. Safeguarding against such threats is paramount to upholding the rights and interests of the model owner. While model watermarking has emerged as a potent defense mechanism in various domains, its direct application to recommender systems remains unexplored and non-trivial. In this paper, we address this gap by introducing Autoregressive Out-of-distribution Watermarking (AOW), a novel technique tailored specifically for recommender systems. Our approach entails selecting an initial item and querying it through the oracle model, followed by the selection of subsequent items with small prediction scores. This iterative process generates a watermark sequence autoregressively, which is then ingrained into the model's memory through training. To assess the efficacy of the watermark, the model is tasked with predicting the subsequent item given a truncated watermark sequence. Through extensive experimentation and analysis, we demonstrate the superior performance and robust properties of AOW. Notably, our watermarking technique exhibits high-confidence extraction capabilities and maintains effectiveness even in the face of distillation and fine-tuning processes.

Finding cohesive subgraphs from a directed graph is a fundamental approach to analyze directed graph data. We consider a new model called directed$(k,\ell)$-plex for a cohesive directed subgraph, which is generalized from the concept of$k$-plex that is only applicable to undirected graphs. Directed$(k,\ell)$-plex has the connection requirements on both inbound and outbound directions of each vertex inside, i.e., each vertex disconnects at most$K$vertices and is meanwhile not pointed to by at most$\ell$vertices. In this paper, we study the maximum directed$(k, \ell)$-plex search problem which finds a directed$(k, \ell)$-plex with the most vertices. We formally prove the NP-hardness of the problem. We then design a heuristic algorithm called DPHeuris, which finds a directed$(k, \ell)$-plex with the size close to the maximum one and runs practically fast in polynomial time. Furthermore, we propose a branch-and-bound algorithm called DPBB to find the exact maximum directed$(k, \ell)$-plex and develop effective graph reduction strategies for boosting the empirical performance. Finally, we conduct extensive experiments on real directed graphs. The experimental results show that (1) our heuristic method can quickly find a near-optimal solution and (2) our branch-and-bound method runs up to six orders of magnitude faster than other baselines.

In this demonstration paper, we describe FSM-Explorer, an interactive tool that makes it easier for end-users to mine frequent subgraph patterns from a big graph$G$, and to explore the subgraph instances in$G$that match the patterns. FSM-Explorer not only supports the popular MNI support measure, but also the recently proposed Fraction-Score measure that is more accurate. Its backend engine is built on top of our recently developed T-FSM system that ensures high concurrency, bounded memory consumption, and effective load balancing. Using real-world data, we showcase how users can mine frequent subgraph patterns by parameter tuning in FSM-Explorer, and how they can conveniently examine the many matched instances in$G$one batch at a time to improve productivity.

A cohesive subgraph of k-truss requires that each edge has at least$(k-2)$triangles, which has wide applications of modeling social communities and complex network visualization. Recently, the study of truss maximization has gained attention, which aims to enlarge$k$-truss most by inserting$b$new edges into a graph$G$. However, existing maximization methods suffer from a stiff strategy of complete truss conversion, that is either converting the whole$(k-1)$-truss component to k-truss or converting no edge to k-truss without using any budget. To tackle this bottleneck, we develop a novel partial conversion strategy to explore more insertion plans. Based on partial conversion strategy, we revisit the problem of truss maximization in this paper and propose adaptive solutions by achieving more new k-truss edges. Specifically, we first decompose all$(k-1)$-truss into a series of disjoint components via the triangle connectivity, where each component's conversion is independent to each other. Then, for each$(k-1)$-truss component, we explore possible insertion plans of partial conversions. An intuitive method is to randomly insert a budget no more than$b$new edges and check the expected profit of new$k$-truss edges. Obviously, this method is inefficient due to a large search space of edge insertions and many times of expensive$k$-truss verification. To improve it, we propose a new minimum-cut based approach, which converts a subgraph of$(k-1)$-truss component into a flow graph with weighted edges and finds a key of maximum-flow answer corresponding to a k-truss conversion plan with the minimum budget consumption. Next, we develop a new dynamic programming framework to find the best way to allocate the budget$b$to all components. We design two fast dynamic programming algorithms and analyze the complexities theoretically. In addition, we explore the case of a large given budget$b$and extend our techniques to handle the conversion of$(k-h)$-truss into$k$-truss for$2\leq h\leq k-2$. Extensive experiment results demonstrate the superiority of our algorithms against the state-of-the-art methods.

Increasing and massive volumes of trajectory data are being accumulated that may serve a variety of applications, such as mining popular routes or identifying ridesharing candidates. As storing and querying massive trajectory data is costly, trajectory simplification techniques have been introduced that intuitively aim to reduce the sizes of trajectories, thus reducing storage and speeding up querying, while preserving as much information as possible. Existing techniques rely mainly on hand-crafted error measures when deciding which point to drop when simplifying a trajectory. While the hope may be that such simplification affects the subsequent usability of the data only minimally, the usability of the simplified data remains largely unexplored. Instead of using error measures that indirectly may to some extent yield simplified trajectories with high usability, we adopt a direct approach to simplification and present the first study of query accuracy driven trajectory simplification, where the direct objective is to achieve a simplified trajectory database that preserves the query accuracy of the original database as much as possible. Specifically, we propose a multi-agent reinforcement learning based solution with two agents working cooperatively to collectively simplify trajectories in a database while optimizing query usability. Extensive experiments on four real-world trajectory datasets show that the solution is capable of consistently outperforming baseline solutions over various query types and dynamics.

Urban sensing aims to sense the status of the city, e.g., air quality, noise level, concentration of viruses, which can be completed by spatial crowdsourcing. Multi-destination people, who have many intermediate locations to visit before the final destination, e.g., couriers and tourists, are ideal recruitment candidates to conduct sensing tasks since they spend more time outside and have a wide spatio-temporal distribution. However, existing spatial crowdsourcing methods are only designed for workers who have single destinations, e.g., commuters, which are not applicable to recruit the multiple-destination people. Therefore, in this paper, we generalize the urban crowdsensing problem to the multi-destination scenario, namely, Urban Sensing for Multi-Destination Workers (USMDW). We prove its NP-hardness, and propose a framework Urban Sensing for Multi-destination Workers via Deep REinforcement learning, i.e., SMORE, to solve it effectively and efficiently. SMORE is composed of two steps: 1) candidate assignment initialization, which initializes all feasible sensing task-worker assignment pairs by a pre-trained reinforcement learning-based working route planning solver; and 2) reinforcement learning-based iterative selection, which iteratively selects a sensing task-worker pair to the current assignment via a novel policy network, i.e., Two-stage Assignment Selection Network (TASNet). Extensive experiments on three real-world datasets show SMORE outperforms the best baseline in data coverage by 5.2% on average with high efficiency.

Traffic prediction, an essential component for intelligent transportation systems, endeavours to use historical data to foresee future traffic features at specific locations. Although existing traffic prediction models often emphasize developing complex neural network structures, their accuracy has not improved. Recently, large language models have shown outstanding capabilities in time series analysis. Differing from existing models, LLMs progress mainly through parameter expansion and extensive pretraining while maintaining their fundamental structures. Motivated by these developments, we propose a Spatial-Temporal Large Language Model (ST-LLM) for traffic prediction. In the ST-LLM, we define timesteps at each location as tokens and design a spatial-temporal embedding to learn the spatial location and global temporal patterns of these tokens. Additionally, we integrate these embeddings by a fusion convolution to each token for a unified spatial-temporal representation. Furthermore, we innovate a partially frozen attention strategy to adapt the LLM to capture global spatial-temporal dependencies for traffic prediction. Comprehensive experiments on real traffic datasets offer evidence that ST-LLM is a powerful spatial-temporal learner that outperforms state-of-the-art models. Notably, the ST-LLM also exhibits robust performance in both few-shot and zero-shot prediction scenarios. The code is publicly available at https://github.com/ChenxiLiu-HNU/ST-LLM.

As a representative information retrieval task, site recommendation, which aims at predicting the optimal sites for a brand or an institution to open new branches in an automatic data-driven way, is beneficial and crucial for brand development in modern business. However, there is no publicly available dataset so far and most existing approaches are limited to an extremely small scope of brands, which seriously hinders the research on site recommendation. Therefore, we collect, construct and release an open comprehensive dataset, namely OpenSiteRec, to facilitate and promote the research on site recommendation. Specifically, OpenSiteRec leverages a heterogeneous graph schema to represent various types of real-world entities and relations in four international metropolises. To evaluate the performance of the existing general methods on the site recommendation task, we conduct benchmarking experiments of several representative recommendation models on OpenSiteRec. Furthermore, we also highlight the potential application directions to demonstrate the wide applicability of OpenSiteRec. We believe that our OpenSiteRec dataset is significant and anticipated to encourage the development of advanced methods for site recommendation. OpenSiteRec is available online at https://OpenSiteRec.github.io/.

The robustness of recommender systems has become a prominent topic within the research community. Numerous adversarial attacks have been proposed, but most of them rely on extensive prior knowledge, such as all the white-box attacks or most of the black-box attacks which assume that certain external knowledge is available. Among these attacks, the model extraction attack stands out as a promising and practical method, involving training a surrogate model by repeatedly querying the target model. However, there is a significant gap in the existing literature when it comes to defending against model extraction attacks on recommender systems. In this paper, we introduce Gradient-based Ranking Optimization (GRO), which is the first defense strategy designed to counter such attacks. We formalize the defense as an optimization problem, aiming to minimize the loss of the protected target model while maximizing the loss of the attacker's surrogate model. Since top-k ranking lists are non-differentiable, we transform them into swap matrices which are instead differentiable. These swap matrices serve as input to a student model that emulates the surrogate model's behavior. By back-propagating the loss of the student model, we obtain gradients for the swap matrices. These gradients are used to compute a swap loss, which maximizes the loss of the student model. We conducted experiments on three benchmark datasets to evaluate the performance of GRO, and the results demonstrate its superior effectiveness in defending against model extraction attacks.

Searching for approximate nearest neighbors (ANN) in the high-dimensional Euclidean space is a pivotal problem. Recently, with the help of fast SIMD-based implementations, Product Quantization (PQ) and its variants can often efficiently and accurately estimate the distances between the vectors and have achieved great success in the in-memory ANN search. Despite their empirical success, we note that these methods do not have a theoretical error bound and are observed to fail disastrously on some real-world datasets. Motivated by this, we propose a new randomized quantization method named RaBitQ, which quantizes D-dimensional vectors into D-bit strings. RaBitQ guarantees a sharp theoretical error bound and provides good empirical accuracy at the same time. In addition, we introduce efficient implementations of RaBitQ, supporting to estimate the distances with bitwise operations or SIMD-based operations. Extensive experiments on real-world datasets confirm that (1) our method outperforms PQ and its variants in terms of accuracy-efficiency trade-off by a clear margin and (2) its empirical performance is well-aligned with our theoretical analysis.

With the increasing availability of trajectory data, it is important to have good indexes to facilitate query processing. In this work, we propose BT-Tree, which is built through a recursive bi-partitioning approach, for the processing of range and KNN queries for past trajectory data. We first propose a cost function based method (CFBM) to build the BT-Tree. Specifically, we design a novel cost function, which incorporates the characteristics of both the data and historical query workload, to decide how to partition a BT-Tree node. Then we propose a reinforcement learning (RL) based method to address CFBM's limitations, such as making locally optimal decisions that may lead to global suboptimality. Experiments on three real datasets with up to 800 million data points show that the CFBM generally outperforms the baselines in terms of query processing time and the RL based method consistently outperforms the baselines and has more significant advantages on larger datasets.

k-clique listing is a vital graph mining operator with diverse applications in various networks. The state-of-the-art algorithms all adopt a branch-and-bound (BB) framework with a vertex-oriented branching strategy (called VBBkC), which forms a sub-branch by expanding a partial k-clique with a vertex. These algorithms have the time complexity of O(k · m · (δ/2)k-2 ), where m is the number of edges in the graph and δ is the degeneracy of the graph. In this paper, we propose a BB framework with a new edge-oriented branching (called EBBkC), which forms a sub-branch by expanding a partial k-clique with two vertices that connect each other (which correspond to an edge ). We explore various edge orderings for EBBkC such that it achieves a time complexity of O( m · δ + k · m · (τ/2)k-2 ), where τ is an integer related to the maximum truss number of the graph and we have τ < δ. The time complexity of EBBkC is better than that of VBBkC algorithms for k>3 since both O(m · δ) and O(k · m · (τ/2)k-2 ) are bounded by O(k · m · (δ/2)k-2 ). Furthermore, we develop specialized algorithms for sub-branches on dense graphs so that we can early-terminate them and apply the specialized algorithms. We conduct extensive experiments on 19 real graphs, and the results show that our newly developed EBBkC based algorithms with the early termination technique consistently and largely outperform the state-of-the-art (VBBkC based) algorithms.

Range-filtering approximate nearest neighbor (RFANN) search is attracting increasing attention in academia and industry. Given a set of data objects, each being a pair of a high-dimensional vector and a numeric value, an RFANN query with a vector and a numeric range as parameters returns the data object whose numeric value is in the query range and whose vector is nearest to the query vector. To process this query, a recent study proposes to build O(n 2 ) dedicated graph-based indexes for all possible query ranges to enable efficient processing on a database of n objects. As storing all these indexes is prohibitively expensive, the study constructs compressed indexes instead, which reduces the memory consumption considerably. However, this incurs suboptimal performance because the compression is lossy. In this study, instead of materializing a compressed index for every possible query range in preparation for querying, we materialize graph-based indexes, called elemental graphs, for a moderate number of ranges. We then provide an effective and efficient algorithm that during querying can construct an index for any query range using the elemental graphs. We prove that the time needed to construct such an index is low. We also cover an experimental study on real-world datasets that provides evidence that the materialized elemental graphs only consume moderate space and that the proposed method is capable of superior and stable query performance across different query workloads.

k -plexes relax cliques by allowing each vertex to disconnect to at most k vertices. Finding a maximum k -plex in a graph is a fundamental operator in graph mining and has been receiving significant attention from various domains. The state-of-the-art algorithms all adopt the branch-reduction-and-bound (BRB) framework where a key step, called reduction-and-bound (RB), is used for narrowing down the search space. A common practice of RB in existing works is SeqRB, which sequentially conducts the reduction process followed by the bounding process once at a branch. However, these algorithms suffer from the efficiency issues. In this paper, we propose a new alternated reduction-and-bound method AltRB for conducting RB. AltRB first partitions a branch into two parts and then alternatively and iteratively conducts the reduction process and the bounding process at each part of a branch. With newly-designed reduction rules and bounding methods, AltRB is superior to SeqRB in effectively narrowing down the search space in both theory and practice. Further, to boost the performance of BRB algorithms, we develop efficient and effective pre-processing methods which reduce the size of the input graph and heuristically compute a large k -plex as the lower bound. We conduct extensive experiments on 664 real and synthetic graphs. The experimental results show that our proposed algorithm kPEX with AltRB and novel preprocessing techniques runs up to two orders of magnitude faster and solves more instances than state-of-the-art algorithms.

Nowadays, it becomes a common practice to capture some data of sports games with devices such as GPS sensors and cameras and then use the data to perform various analyses on sports games, including tactics discovery, similar game retrieval, performance study, and so forth. While this practice has been conducted to many sports such as basketball and soccer, it remains largely unexplored on the billiards sports, which is mainly due to the lack of publicly available datasets. Motivated by this, we collect a dataset of billiards sports, which includes the layouts (i.e., locations) of billiards balls after performing break shots, called break shot layouts, the traces of the balls as a result of strikes (in the form of trajectories), and detailed statistics and performance indicators. We then study and develop techniques for three tasks on the collected dataset, including (1) prediction and (2) generation on the layouts data, and (3) similar billiards layout retrieval on the layouts data, which can serve different users such as coaches, players and fans. We conduct extensive experiments on the collected dataset and the results show that our methods perform effectively and efficiently.

Co-location patterns, which capture the phenomenon that objects with certain labels are often located in close geographic proximity, are defined based on a support measure which quantifies the prevalence of a pattern candidate in the form of a label set. Existing support measures share the idea of counting the number of instances of a given label set$C$as its support, where an instance of$C$is an object set whose objects collectively carry all labels in$C$and are located close to one another. However, they suffer from various weaknesses, e.g., fail to capture all possible instances, or overlook the cases when multiple instances overlap. In this paper, we propose a new measure called Fraction-Score which counts instancesfractionallyif they overlap. Fraction-Score captures all possible instances, and handles the cases where instances overlap appropriately (so that the supports defined are more meaningful and anti-monotonic). We develop efficient algorithms to solve the co-location pattern mining problem defined with Fraction-Score. Furthermore, to obtain representative patterns, we develop an efficient algorithm for mining the maximal co-location patterns, which are those patterns without proper superset patterns. We conduct extensive experiments using real and synthetic datasets, which verified the superiority of our proposals.

Traffic congestion is becoming an increasingly prominent problem, and intelligent traffic signal control methods can effectively alleviate it. Recently, there has been a growing trend of applying reinforcement learning to traffic signal control for adaptive signal scheduling. However, most existing methods focus on improving traffic performance while neglecting the issue of scheduling fairness, resulting in long waiting time for some vehicles. Some works attempt to address fairness issues but often sacrifice transport performance. Furthermore, existing methods overlook the challenge of sample efficiency, especially when dealing with diversity-limited traffic data. Therefore, we propose aFairness-aware and sample-Efficient traffic signal control method called FELight. Specifically, we first design a novel fairness metric and integrate it into decision process to penalize cases with high latency by setting a threshold for activating the fairness mechanism. Theoretical comparison with other fairness works proves why and when our fairness could bring advantages. Moreover, counterfactual data augmentation is employed to enrich interaction data, enhancing the sample efficiency of FELight. Self-supervised state representation is introduced to extract informative features from raw states, further improving sample efficiency. Experiments on real traffic datasets demonstrate that FELight provides relatively fairer traffic signal control without compromising performance compared to state-of-the-art approaches. Our codes are available athttps://github.com/dxnbbsw/FELight.

With the advance of the geo-positioning technology, the terrain surface data has become increasingly popular and has drawn much research attention from both academia and industry. Answering a shortest-path query for a given source and a given destination on a terrain surface is a fundamental problem and has many applications including Geographical Information System and 3D virtual games. We observe that all existing exact algorithms are only aware of the position of the source point and is unaware of the information of the destination point. Motivated by this, in this paper, we propose an efficient algorithm, namelydirection-oriented algorithm (DIO Algorithm), for answering shortest-path queries on a terrain surface. The algorithm properly guides the search along a direction towards the destination instead of blindly searching all possible directions from the source point. To this end, we convert the geodesic shortest path problem to a shortest obstacle-free euclidean path problem in the 2D planar unfolding of the terrain surface. Based on this conversion, we derive for each part of the terrain surface a lower bound on the length of the shortest path from the source to the destination passing through the part with a novel method. The lower bounds provide useful information that can be used to decide the visiting order of the parts on the terrain surface and guides the search of finding the destination quickly. Our experiments verified that our algorithm runs faster than the state-of-the-art by more than one order of magnitude.

In conversational recommender systems (CRSs), conversations usually involve a set of items and item-related entities or attributes, e.g., director is a related entity of a movie. These items and item-related entities are often mentioned along the development of a dialog, leading to potential sequential dependencies among them. However, most of existing CRSs neglect these potential sequential dependencies. In this article, we first propose a Transformer-based sequential conversational recommendation method, named TSCR, to model the sequential dependencies in the conversations to improve CRS. In TSCR, we represent conversations by items and the item-related entities, and construct user sequences to discover user preferences by considering both the mentioned items and item-related entities. Based on the constructed sequences, we deploy a Cloze task to predict the recommended items along a sequence. Meanwhile, in certain domains, knowledge graphs formed by the items and their related entities are readily available, which provide various different kinds of associations among them. Given that TSCR does not benefit from such knowledge graphs, we then propose a knowledge graph enhanced version of TSCR, called TSCRKG. In specific, we leverage the knowledge graph to offline initialize our model TSCRKG, and augment the user sequence of conversations (i.e., sequence of the mentioned items and item-related entities in the conversation) with multi-hop paths in the knowledge graph. Experimental results demonstrate that our TSCR model significantly outperforms state-of-the-art baselines, and the enhanced version TSCRKG further improves recommendation performance on top of TSCR.

Computing the densest subgraph is a primitive graph operation with critical applications in detecting communities, events, and anomalies in biological, social, Web, and financial networks. In this paper, we study the novel problem of Most Probable Densest Subgraph (MPDS) discovery in uncertain graphs: Find the node set that is the most likely to induce a densest subgraph in an uncertain graph. We further extend our problem by considering various notions of density, e.g., clique and pattern densities, studying the top-k MPDSs, and finding the node set with the largest containment probability within densest subgraphs. We show that it is #P-hard to compute the probability of a node set inducing a densest subgraph. We then devise sampling-based efficient algorithms, with end-to-end accuracy guarantees, to compute the MPDS. Our thorough experimental results and real-world case studies on brain and social networks validate the effectiveness, efficiency, and usefulness of our solution.

As the popularity of graph data increases, there is a growing need to count the occurrences of subgraph patterns of interest, for a variety of applications. Many graphs are massive in scale and also fully dynamic (with insertions and deletions of edges), rendering exact computation of these counts to be infeasible. Common practice is, instead, to use a small set of edges as a sample to estimate the counts. Existing sampling algorithms for fully dynamic graphs sample the edges with uniform probability. In this paper, we show that we can do much better if we sample edges based on their individual properties. Specifically, we propose a weighted sampling algorithm called WSD for estimating the subgraph count in a fully dynamic graph stream, which samples the edges based on their weights that indicate their importance and reflect their properties. We determine the weights of edges in a data-driven fashion, using a novel method based on reinforcement learning. We conduct extensive experiments to verify that our technique can produce estimates with smaller errors while often running faster compared with existing algorithms.

Detecting anomalous trajectories has become an important task in many location-based applications. While many approaches have been proposed for this task, they suffer from various issues including (1) incapability of detecting anomalous subtrajectories, which are finer-grained anomalies in trajectory data, and/or (2) non-data driven, and/or (3) requirement of sufficient supervision labels which are costly to collect. In this paper, we propose a novel reinforcement learning based solution called RL4OASD, which avoids all aforementioned issues of existing approaches. RL4OASD involves two networks, one responsible for learning features of road networks and trajectories and the other responsible for detecting anomalous subtrajectories based on the learned features, and the two networks can be trained iteratively without labeled data. Extensive experiments are conducted on two real datasets, and the results show that our solution can significantly outperform the state-of-the-art methods (with 20-30% improvement) and is efficient for online detection (it takes less than 0.1ms to process each newly generated data point).

Approximate K nearest neighbor (AKNN) search in the high-dimensional Euclidean vector space is a fundamental and challenging problem. We observe that in high-dimensional space, the time consumption of nearly all AKNN algorithms is dominated by that of the distance comparison operations (DCOs). For each operation, it scans full dimensions of an object and thus, runs in linear time wrt the dimensionality. To speed it up, we propose a randomized algorithm named ADSampling which runs in logarithmic time wrt the dimensionality for the majority of DCOs and succeeds with high probability. In addition, based on ADSampling we develop one generic and two algorithm-specific techniques as plugins to enhance existing AKNN algorithms. Both theoretical and empirical studies confirm that: (1) our techniques introduce nearly no accuracy loss and (2) they consistently improve the efficiency.

Learned indexes have been proposed to replace classic index structures like B-Tree with machine learning (ML) models. They require to replace both the indexes and query processing algorithms currently deployed by the databases, and such a radical departure is likely to encounter challenges and obstacles. In contrast, we propose a fundamentally different way of using ML techniques to build a better R-Tree without the need to change the structure or query processing algorithms of traditional R-Tree. Specifically, we develop reinforcement learning (RL) based models to decide how to choose a subtree for insertion and how to split a node when building and updating an R-Tree, instead of relying on hand-crafted heuristic rules currently used by the R-Tree and its variants. Experiments on real and synthetic datasets with up to more than 100 million spatial objects show that our RL based index outperforms the R-Tree and its variants in terms of query processing time.

Enumerating maximal k-biplexes (MBPs) of a bipartite graph has been used for applications such as fraud detection. Nevertheless, there usually exists an exponential number of MBPs, which brings up two issues when enumerating MBPs, namely the effectiveness issue (many MBPs are of low values) and the efficiency issue (enumerating all MBPs is not affordable on large graphs). Existing proposals of tackling this problem impose constraints on the number of vertices of each MBP to be enumerated, yet they are still not sufficient (e.g., they require to specify the constraints, which is often not user-friendly, and cannot control the number of MBPs to be enumerated directly). Therefore, in this paper, we study the problem of finding K MBPs with the most edges called MaxBPs, where K is a positive integral user parameter. The new proposal well avoids the drawbacks of existing proposals (i.e., the number of MBPs to be enumerated is directly controlled and the MBPs to be enumerated tend to have high values since they have more edges than the majority of MBPs). We formally prove the NP-hardness of the problem. We then design two branch-and-bound algorithms, among which, the better one called FastBB improves the worst-case time complexity to O*(γkn), where O* suppresses the polynomials, γk is a real number that relies on k and is strictly smaller than 2, and n is the number of vertices in the graph. For example, for k=1, γk is equal to 1.754. We further introduce three techniques for boosting the performance of the branch-and-bound algorithms, among which, the best one called PBIE can further improve the time complexity to O*(γkd3) for large sparse graphs, where d is the maximum degree of the graph (note that d<

Mining cohesive subgraphs from a graph is a fundamental problem in graph data analysis. One notable cohesive structure is γ-quasi-clique (QC), where each vertex connects at least a fraction γ of the other vertices inside. Enumerating maximal γ-quasi-cliques (MQCs) of a graph has been widely studied and used for many applications such as community detection and significant biomolecule structure discovery. One common practice of finding all MQCs is to (1) find a set of QCs containing all MQCs and then (2) filter out non-maximal QCs. While quite a few algorithms have been developed (which are branch-and-bound algorithms) for finding a set of QCs that contains all MQCs, all focus on sharpening the pruning techniques and devote little effort to improving the branching part. As a result, they provide no guarantee on pruning branches and all have the worst-case time complexity of O*(2n), where O* suppresses the polynomials and n is the number of vertices in the graph. In this paper, we focus on the problem of finding a set of QCs containing all MQCs but deviate from further sharpening the pruning techniques as existing methods do. We pay attention to both the pruning and branching parts and develop new pruning techniques and branching methods that would suit each other better towards pruning more branches both theoretically and practically. Specifically, we develop a new branch-and-bound algorithm called FastQC based on newly developed pruning techniques and branching methods, which improves the worst-case time complexity to O*(αkn), where αk is a positive real number strictly smaller than 2. Furthermore, we develop a divide-and-conquer strategy for boosting the performance of FastQC. Finally, we conduct extensive experiments on both real and synthetic datasets, and the results show that our algorithms are up to two orders of magnitude faster than the state-of-the-art on real datasets.

Finding frequent subgraph patterns in a big graph is an important problem with many applications such as classifying chemical compounds and building indexes to speed up graph queries. Since this problem is NP-hard, some recent parallel systems have been developed to accelerate the mining. However, they often have a huge memory cost, very long running time, suboptimal load balancing, and possibly inaccurate results. In this paper, we propose an efficient system called T-FSM for parallel mining of frequent subgraph patterns in a big graph. T-FSM adopts a novel task-based execution engine design to ensure high concurrency, bounded memory consumption, and effective load balancing. It also supports a new anti-monotonic frequentness measure called Fraction-Score, which is more accurate than the widely used MNI measure. Our experiments show that T-FSM is orders of magnitude faster than SOTA systems for frequent subgraph pattern mining. Our system code has been released at https://github.com/lyuheng/T-FSM.

To index multi-dimensional data, space-filling curves (SFCs) have been used to map the data to one dimension, and then a one-dimensional indexing method such as the B-tree is used to index the mapped data. The existing SFCs all adopt a single mapping scheme for the whole data space. However, a single mapping scheme often does not perform well on all the data space. In this paper, we propose a new type of SFC called piecewise SFCs, which adopts different mapping schemes for different data subspaces. Specifically, we propose a data structure called Bit Merging tree (BMTree), which can generate data subspaces and their SFCs simultaneously and achieve desirable properties of the SFC for the whole data space. Furthermore, we develop a reinforcement learning based solution to build the BMTree, aiming to achieve excellent query performance. Extensive experiments show that our proposed method outperforms existing SFCs in terms of query performance.

A user-item utility matrix represents the utility (or preference) associated with each (user, item) pair, such as citation counts, rating/vote on items or locations, and clicks on items. A high utility value indicates a strong association of the pair. In this work, we consider the problem of summarizing strong association for a large user-item matrix using a small summary size. Traditional techniques fail to distinguish user groups associated with different items (such as top- l item selection) or fail to focus on high utility (such as similarity- based subspace clustering and biclustering). We formulate a new problem, called Group Utility Maximization (GUM), to summarize the entire user population through k user groups and l items for each group; the goal is to maximize the total utility of selected items over all groups collectively. We show this problem is NP-hard even for l =1. We present two algorithms. One greedily finds the next group, called Greedy algorithm, and the other iteratively refines existing k groups, called k -max algorithm. Greedy algorithm provides the \((1-\frac{1}{e})\) approximation guarantee for a nonnegative utility matrix, whereas k -max algorithm is more efficient for large datasets. We evaluate these algorithms on real-life datasets.

Road network is a critical infrastructure powering many applications including transportation, mobility and logistics in real life. To leverage the input of a road network across these different applications, it is necessary to learn the representations of the roads in the form of vectors, which is namedroad network representation learning(RNRL). While several models have been proposed for RNRL, they capture the pairwise relationships/connections among roads only (i.e., as a simple graph), and fail to capture among roads the high-order relationships (e.g., those roads that jointly form a local region usually have similar features such as speed limit) and long-range relationships (e.g., some roads that are far apart may have similar semantics such as being roads in residential areas). Motivated by this, we propose to construct ahypergraph, where each hyperedge corresponds to a set of multiple roads forming a region. The constructed hypergraph would naturally capture the high-order relationships among roads with hyperedges. We then allow information propagation via both the edges in the simple graph and the hyperedges in the hypergraph in a graph neural network context. In addition, we introduce different pretext tasks based on both the simple graph (i.e., graph reconstruction) and the hypergraph (including hypergraph reconstruction and hyperedge classification) for optimizing the representations of roads. The graph reconstruction and hypergraph reconstruction tasks are conventional ones and can capture structural information. The hyperedge classification task can capture long-range relationships between pairs of roads that belong to hyperedges with the same label. We call the resulting modelHyperRoad. We further extend HyperRoad to problem settings when additional inputs of road attributes and/or trajectories that are generated on the roads are available. We conduct extensive experiments on two real datasets, for five downstream tasks, and under four problem settings, which demonstrate that our model achieves impressive improvements compared with existing baselines across datasets, tasks, problem settings, and performance metrics. CCS Concepts: • Information systems→Data mining; • Urban computing; • Spatial-temporal systems;

With the proliferation of location-based services, geo-textual data is becoming ubiquitous. Objects involved in geo-textual data include geospatial locations, textual descriptions or keywords, and various attributes (e.g., a point-of-interest has its expenses and users' ratings). One prominent type of spatial keyword queries is to find, for a query consisting of a location and keywords, a set of objects that covers all the keywords and is of good quality according to some criteria. Existing studies define the criteria either based on the geospatial information of the objects solely or simply treat the geospatial and attribute information of the objects together without differentiation. As a result, they cannot provide users flexibility to express finer grained preferences on the objects. In this paper, we propose a new criterion which is to find a set of objects where the distance (defined based on the geospatial information) is at most a threshold specified by users and the cost (defined based on the attribute information) is optimized. We develop a suite of three algorithms including an exact algorithm and two approximation algorithms with provable guarantees for the problem. We conducted extensive experiments on real datasets which verified the efficiency and effectiveness of proposed algorithms.

k-Regret Querying is a well studied problem to query a dataset$D$for a small subset$S$of size$k$with the minimal regret ratio for unknown utility functions. In this paper, we point out some issues in$k$-Regret Querying, including the assumption of non-negative dataset and the lack of shift invariance. Known algorithms for$k$-Regret Querying are limited in scope and result quality, and are based on the assumption of non-negative data. We introduce a new problem definition called$k$-pleased querying for dealing with the shift variance issue, and propose a strategy of random sampling of the utility functions. This strategy is based on a study of the theoretical guarantee of the sampling approach. We also introduce a dimensionality reduction strategy, an improved greedy algorithm, and a study of other utility function sampling methods. All of our solutions can handle negative data. Theoretically, we derive a guarantee on the approximation attained by our sampling algorithm. Experimental results on numerous real datasets show that our proposed method is effective even with a small number of samples and small values of$k$.

Nowadays, couriers are still the main solution to address the "last mile" problem in logistics. They are usually required to record the delivery time of each parcel manually, which is essential for delivery insurances, delivery performance evaluations, and customer available time discovery. Stay points extracted from couriers' trajectories provide a chance to fill the delivery time automatically to ease their burdens. However, it is challenging due to inaccurate delivery locations and various stay scenarios. To this end, we propose the improved Delivery Time Inference (DTInf+), to infer the delivery time of waybills based on couriers' trajectories. Our solution is composed of three steps: 1) Data Pre-processing, which organizes waybills and stay points by delivery trips, 2) Delivery Location Mining, which obtains the delivery location for each address and each Geocoded waybill location by mining historical delivery caused stay points, and 3) Delivery Event-based Matching, which jointly selects the best-matched stay point for waybills at the same delivery location based on Pointer Network-like model SPSelector to infer the delivery time. Extensive experiments and case studies based on real-world datasets from JD Logistics confirm the effectiveness of our approach. Finally, a system powered by DTInf+ is deployed in JD Logistics.

With the proliferation of commercial tracking systems, sports data is being generated at an unprecedented speed and the interest in sports play retrieval has grown dramatically as well, where a play corresponds to a fragment of a game. Existing solutions for similar play retrieval usually assume that a database of plays are materialized, which, however, is not well aligned with the practice that data is stored in units of game. In this paper, we propose to search for similar plays directly from a database of games. We tackle three challenges of the task, namely (1) how to measure the similarity between two plays, (2) how to efficiently find a similar play to a query play within a game, and (3) how to efficiently find a similar play within a database of many games. For the first challenge, we propose a deep learning approach called play2vec to learn the representations of sports plays. play2vec is robust against noise and runs in linear time. For the second challenge, we develop a suite of algorithms including two based on reinforcement learning, which use learned policies for deciding where to split a game to generate candidate plays. For the third challenge, we develop a method called ScoreSearch based on deep metric learning, which is able to prune games from being searched for better efficiency. We conduct experiments on real-world soccer match data to evaluate the techniques developed in this paper.

Online lot sizing for perishable materials in an uncertain environment is a fundamental problem for inventory planning and has been studied for several decades. In this article, we study a novel setting of thelotsizing problem, consideringperishable materials,multiple suppliers,uncertain demands and lead time (LS-PMU), which captures the inventory planning task in real life better than existing lot sizing problems. We present theoretical results of the best possible competitive ratio an online algorithm can achieve for the LS-PMU problem. We then develop a reinforcement learning-based algorithm calledRL4LSto intelligently choose the supplier and decide the order quantity in each time period. We conduct extensive experiments on both real and synthetic datasets to verify thatRL4LSoutperforms existing algorithms in terms of effectiveness and efficiency, e.g.,RL4LSimproves the effectiveness by 44% and runs two orders of magnitude faster than the state-of-the-art algorithmIBFA.

Cohesive subgraph discovery is an important problem in bipartite graph mining. In this paper, we focus on one kind of cohesive structure, called k-biplex, where each vertex of one side is disconnected from at most k vertices of the other side. We consider the large maximal k-biplex enumeration problem which is to list all those maximal k-biplexes with the number of vertices at each side at least a non-negative integer . This formulation, we observe, has various applications and targets to find non-redundant results by excluding non-maximal ones. Existing approaches suffer from massive redundant computations and can only run on small and moderate datasets. Towards improving scalability, we propose an efficient tree-based algorithm with two advanced strategies and powerful pruning techniques. Experimental results on real and synthetic datasets show the superiority of our algorithm over existing approaches.

Unsupervised region representation learning aims to extract dense and effective features from unlabeled urban data. While some efforts have been made for solving this problem based on multiple views, existing methods are still insufficient in extracting representations in a view and/or incorporating representations from different views. Motivated by the success of contrastive learning for representation learning, we propose to leverage it for multi-view region representation learning and design a model called ReMVC (Region Embedding with Multi-View Contrastive Learning) by following two guidelines:$i$) comparing a region with others within each view for effective representation extraction and$ii$) comparing a region with itself across different views for cross-view information sharing. We design the intra-view contrastive learning module which helps to learn distinguished region embeddings and the inter-view contrastive learning module which serves as a soft co-regularizer to constrain the embedding parameters and transfer knowledge across multi-views. We exploit the learned region embeddings in two downstream tasks named land usage clustering and region popularity prediction. Extensive experiments demonstrate that our model achieves impressive improvements compared with seven state-of-the-art baseline methods, and the margins are over 30% in the land usage clustering task.

When users move in a physical space (e.g., an urban space), they would have some records called mobility records (e.g., trajectories) generated by devices such as mobile phones and GPS devices. Naturally, mobility records capture essential information of how users work, live and entertain in their daily lives, and therefore, they have been used in a wide range of tasks such as user profile inference, mobility prediction and traffic management. In this paper, we expand this line of research by investigating the problem of inferring user socioeconomic statuses (such as prices of users’ living houses as a proxy of users’ socioeconomic statuses) based on their mobility records, which can potentially be used in real-life applications such as the car loan business. For this task, we propose a socioeconomic-aware deep model called DeepSEI. The DeepSEI model incorporates two networks called deep network and recurrent network, which extract the features of the mobility records from three aspects, namely spatiality, temporality and activity, one at a coarse level and the other at a detailed level. We conduct extensive experiments on real mobility records data, POI data and house prices data. The results verify that the DeepSEI model achieves superior performance than existing studies. All datasets used in this paper will be made publicly available.

The phenomena of data missing are common in the field of traffic, yet existing solutions for data imputation are not sufficient due to challenges of data sparsity, complex traffic situations and the lack of complete ground truths. In this paper, we propose a novel solution called STCPA for the speed imputation problem. STCPA captures complex traffic correlations among the spatial and temporal dimensions via the attention mechanism, which helps mitigate the data sparsity issue. In addition, STCPA adopts an imputation cycle consistency constraint for providing reliable supervisions on unobserved entries, which improves the training. Furthermore, it incorporates an extra Road-aware Perceptual Loss, which helps encourage to preserve more meaningful semantics for imputation. Extensive experiments are conducted on two real-world datasets, namely, Chengdu and New York, to demonstrate the effectiveness of STCPA, e.g., it outperforms the best baseline by 7.64% and 5.00% on Chengdu and New York datasets, respectively. The code is available at https://github.com/Sam1224/STCPA.

With the proliferation of location-based services, geo-textual data is becoming ubiquitous. Objects involved in geo-textual data include geospatial locations, textual descriptions or keywords, and various attributes (e.g., a point-of-interest has its expenses and users' ratings). Many types of spatial keyword queries have been proposed on geo-textual data. Among them, one prominent type is to find, for a query consisting of a query location and some query keywords, a set of multiple objects such that the objects in the set collectively cover all the query keywords, and the object set is of good quality according to some criterion. Existing studies define the criterion either based on the geospatial information of the objects solely, or simply treat the geospatial information and the attribute information of the objects together without differentiation though they may have different semantics and scales. As a result, they cannot provide users flexibility to express finer grained preferences on the objects. In this paper, we propose a new criterion which is to find a set of objects where the distance (defined based on the geospatial information) is at most a threshold specified by users and the cost (defined based on the attribute information) is optimized. We develop a suite of two algorithms including an exact algorithm and an approximation algorithm with provable guarantees for the problem. We conducted extensive experiments on both real and synthetic datasets, which verified the efficiency and effectiveness of proposed algorithms.

$k$-Regret Querying is a well studied problem to query a dataset$D$for a small subset$S$of size$k$with the minimal regret ratio for unknown utility functions. In this paper, we point out some issues in$k$- Regret Querying, including the assumption of non-negative dataset and the lack of shift invariance. Known algorithms for$k$- Regret Querying are limited in scope and result quality, and are based on the assumption of non-negative data. We introduce a new problem definition called k-pleased querying for dealing with the shift variance issue, and propose a strategy of random sampling of the utility functions. This strategy is based on a study of the theoretical guarantee of the sampling approach. We also introduce a dimensionality reduction strategy, an improved greedy algorithm, and a study of other utility function sampling methods. All of our solutions can handle negative data. Theoretically, we derive a guarantee on the approximation attained by our sampling algorithm. Experimental results on numerous real datasets show that our proposed method is effective even with a small number of samples and small values of$k$.

Quasi-cliques are a type of dense subgraphs that generalize the notion of cliques, important for applications such as community/module detection in various social and biological networks. However, the existing quasi-clique definition and algorithms are only applicable to undirected graphs. In this paper, we generalize the concept of quasi-cliques to directed graphs by proposing (γ1, γ2) -quasi-cliques which have density requirements in both inbound and outbound directions of each vertex in a quasi-clique subgraph. An efficient recursive algorithm is proposed to find maximal (γ1,γ2)-quasi-cliques which integrates many effective pruning rules that are validated by ablation studies. We also study the finding of top-k large quasi-cliques directly by bootstrapping the search from more compact quasi-cliques, to scale the mining to larger networks. The algorithms are parallelized with effective load balancing, and we demonstrate that they can scale up effectively with the number of CPU cores.

Delivery locations are fundamental data source for intelligent logistics, which can be used in route planning, arrival time estimation, parcel allocation, etc. Using the Geocoded way-bill location of an address as the delivery location is not sufficient, due to wrong address parsing, coarse-grained POI database, or different preferences of customers. To mitigate the insufficiency of Geocoding, some methods have been proposed, which utilize couriers' locations when waybills are confirmed to be delivered for delivery location inference. Nevertheless, these methods highly rely on the quality of couriers' annotations and fail when couriers confirm deliveries with delays. We propose to infer actual delivery locations of addresses from couriers' trajectories. This idea lies on an observation that the semantics of delivering a parcel are well captured by couriers' trajectories (e.g., a stay point would be generated when a delivery occurs), which holds even couriers confirm deliveries with delays. Specifically, we design Delivery Location Inference under Mis-Annotation (DLInfMA), which (1)generates location candidates from stay points in couriers' trajectories; (2) extracts features from both an address and its location candidates; and (3) uses an attention-based neural network model LocMatcher to predict the delivery location for each address. Experiments on two real-world datasets from JD Logistics as well as synthetic datasets demonstrate the effectiveness, robustness and scalability of DLInfMA. We also present a deployed system along with two applications based on DLInfMA.

Cohesive subgraph discovery is an important problem in bipartite graph mining. In this paper, we focus on one kind of cohesive structure, called$k$-biplex, where each vertex of one side is disconnected from at most$k$vertices of the other side. We consider the large maximal$k$-biplex enumeration problem which is to list all those maximal$k$-biplexes with the number of vertices at each side at least a non-negative integer$\theta$. This formulation aims to find non-redundant results by excluding non-maximal ones and has various applications. Existing approaches suffer from massive redundant computations and can only run on small and moderate datasets. Towards improving scalability, we propose an efficient tree-based algorithm with two advanced strategies and powerful pruning techniques. Experimental results show the superiority of our algorithm over existing approaches.

Service time is a part of time cost in the last-mile delivery, which is the time spent on delivering parcels at a certain location. Predicting the service time is fundamental for many downstream logistics applications, e.g., route planning with time windows, courier workload balancing and delivery time prediction. Nevertheless, it is non-trivial given the complex delivery circumstances, location heterogeneity, and skewed observations in space. The existing solution trains a supervised model based on aggregated features extracted from parcels to deliver, which cannot handle above challenges well. In this paper, we propose MetaSTP, a meta-learning based neural network model to predict the service time. MetaSTP treats the service time prediction at each location as a learning task, leverages a Transformer-based representation layer to encode the complex delivery circumstances, and devises a model-based meta-learning method enhanced by location prior knowledge to reserve the uniqueness of each location and handle the imbalanced distribution issue. Experiments show MetaSTP outperforms baselines by at least 9.5% and 7.6% on two real-world datasets. Finally, an intelligent waybill assignment system based on MetaSTP is deployed and used internally in JD Logistics.

The ubiquity of mobile internet has led to the success of Spatial Crowdsourcing platforms like real-time taxi-hailing services, online food ordering services, etc. A critical component of such services is the task assignment algorithm employed for assigning the tasks to the workers of the platform. Our study of the literature in this domain shows that most of the task assignment algorithms developed for spatial crowdsourcing platforms address the problem from a utilitarian perspective, i.e., they optimise for only kind of entity. In contrast, we address the task assignment problem in spatial crowdsourcing platforms from an egalitarian perspective. An egalitarian approach aims to optimise the expectation of all entities involved. Specifically, we aim to minimise the waiting time for the customers and workers, while maximising the profit earned by the platform. To the best of our knowledge, ours is the only study that achieves this objective in a fully-online setting, with deadlines for both customers and workers. We propose two heuristic algorithms to solve the problem, and evaluate our algorithms on a real taxi-trips records dataset. Our algorithms exhibit a superior performance than the state-of-the-art algorithm for the fully-online bottleneck matching problem with deadlines, in terms of solution quality, running time and response time.

With the increasing popularity of GPS modules, there are various urban applications relying on trajectory data modeling. In this work, we study the problem to model the vehicle trajectories by predicting the next road segment given a partial trajectory. Existing methods that model trajectories with Markov chain or recurrent neural network suffer from issues of modeling, context and semantics. In this paper, we propose a new trajectory modeling framework called Multi-task Modeling for Trajectories (MMTraj), which avoids these issues. Specifically, MMTraj uses multi-head self-attention networks for sequential modeling, captures the overall road network as the context information for road segment embedding, and performs an auxiliary task of predicting the trajectory destination to better guide the main trajectory modeling task (controlled by a carefully designed gating mechanism). Extensive experiments conducted on real-world datasets demonstrate the superiority of the proposed method over the baseline methods.

With the proliferation of tracking devices such as cameras and/or GPS sensors, sports data is being generated at an unprecedented speed and the interest in collecting some data from sports games has grown dramatically as well. The collected data facilitates various sports analytic tasks; however, these studies are mainly concerning with sports such as football and basketball. It remains largely unexplored for billiards sports though it is a popular sport of both strategy and physical skill, and this is mainly due to the lack of publicly available datasets. Motivated by this, we collect a dataset of billiards sports, which includes the layouts (i.e., locations) of billiards balls after performing break shots, called break shot layouts, the traces of the balls as a result of strikes (in the form of trajectories), and detailed statistics and performance indicators. On top of the dataset, we investigate several tasks, including prediction and generation on the layouts data and similarity search on the trajectory data, which can serve different users such as coaches, players and fans. We conduct extensive experiments on the collected dataset for the tasks, and the results demonstrate the superior performance of the methods proposed in this paper.

In Conversational Recommender Systems (CRSs), conversations usually involve a set of related items and entities e.g., attributes of items. These items and entities are mentioned in order following the development of a dialogue. In other words, potential sequential dependencies exist in conversations. However, most of the existing CRSs neglect these potential sequential dependencies. In this paper, we propose a Transformer-based sequential conversational recommendation method, named TSCR, which models the sequential dependencies in the conversations to improve CRS. We represent conversations by items and entities, and construct user sequences to discover user preferences by considering both mentioned items and entities. Based on the constructed sequences, we deploy a Cloze task to predict the recommended items along a sequence. Experimental results demonstrate that our TSCR model significantly outperforms state-of-the-art baselines.

Mining maximal subgraphs with cohesive structures from a bipartite graph has been widely studied. One important cohesive structure on bipartite graphs is k-biplex, where each vertex on one side disconnects at most k vertices on the other side. In this paper, we study the maximal k-biplex enumeration problem which enumerates all maximal k-biplexes. Existing methods suffer from efficiency and/or scalability issues and have the time of waiting for the next output exponential w.r.t. the size of the input bipartite graph (i.e., an exponential delay). In this paper, we adopt a reverse search framework called bTraversal, which corresponds to a depth-first search (DFS) procedure on an implicit solution graph on top of all maximal k-biplexes. We then develop a series of techniques for improving and implementing this framework including (1) carefully selecting an initial solution to start DFS, (2) pruning the vast majority of links from the solution graph of bTraversal, and (3) implementing abstract procedures of the framework. The resulting algorithm is called iTraversal, which has its underlying solution graph significantly sparser than (around 0.1% of) that of bTraversal. Besides, iTraversal provides a guarantee of polynomial delay. Our experimental results on real and synthetic graphs, where the largest one contains one billion edges, show that our algorithm is up to four orders of magnitude faster than existing algorithms.

Multi-task learning (MTL) has been widely utilized in various industrial scenarios, such as recommender systems and search engines. MTL can improve learning efficiency and prediction accuracy by exploiting commonalities and differences across tasks. However, MTL is sensitive to relationships among tasks and may have performance degradation in real-world applications, because existing neural-based MTL models often share the same network structures and original input features. To address this issue, we propose a novel multi-task learning model based on Prototype Feature Extraction (PFE) to balance task-specific objectives and inter-task relationships. PFE is a novel component to disentangle features for multiple tasks. To better extract features from original inputs before gating networks, we introduce a new concept, namely prototype feature center, to disentangle features for multiple tasks. The extracted prototype features fuse various features from different tasks to better learn inter-task relationships. PFE updates prototype feature centers and prototype features iteratively. Our model utilizes the learned prototype features and task-specific experts for MTL. We implement PFE on two public datasets. Empirical results show that PFE outperforms state-of-the-art MTL models by extracting prototype features. Furthermore, we deploy PFE in a real-world recommender system (one of the world’s top-tier short video sharing platforms) to showcase that PFE can be widely applied in industrial scenarios.

Given a data matrix \( D \) , a submatrix \( S \) of \( D \) is an order-preserving submatrix (OPSM) if there is a permutation of the columns of \( S \) , under which the entry values of each row in \( S \) are strictly increasing. OPSM mining is widely used in real-life applications such as identifying coexpressed genes and finding customers with similar preference. However, noise is ubiquitous in real data matrices due to variable experimental conditions and measurement errors, which makes conventional OPSM mining algorithms inapplicable. No previous work on OPSM has ever considered uncertain value intervals using the well-established possible world semantics. We establish two different definitions of significant OPSMs based on thepossible world semantics: (1) expected support-based and (2) probabilistic frequentness-based. An optimized dynamic programming approach is proposed to compute the probability that a row supports a particular column permutation, with a closed-form formula derived to efficiently handle the special case of uniform value distribution and an accurate cubic spline approximation approach that works well with any uncertain value distributions. To efficiently check the probabilistic frequentness, several effective pruning rules are designed to efficiently prune insignificant OPSMs; two approximation techniques based on the Poisson and Gaussian distributions, respectively, are proposed for further speedup. These techniques are integrated into our two OPSM mining algorithms, based on prefix-projection and Apriori, respectively. We further parallelize our prefix-projection-based mining algorithm using PrefixFPM, a recently proposed framework for parallel frequent pattern mining, and we achieve a good speedup with the number of CPU cores. Extensive experiments on real microarray data demonstrate that the OPSMs found by our algorithms have a much higher quality than those found by existing approaches.

Due to the advance of the geo-spatial positioning and the computer graphics technology, digital terrain data has become increasingly popular nowadays. Query processing on terrain data has attracted considerable attention from both the academic and the industry communities. Proximity queries such as the shortest path/distance query, k nearest/farthest neighbor query, and top- k closest/farthest pairs query are fundamental and important queries in the context of the terrain surfaces, and they have a lot of applications in Geographical Information System, 3D object feature vector construction, and 3D object data mining. In this article, we first study the most fundamental type of query, namely, shortest distance and path query, which is to find the shortest distance and path between two points of interest on the surface of the terrain. As observed by existing studies, computing the exact shortest distance/path is very expensive. Some existing studies proposed ϵ -approximate distance and path oracles, where ϵ is a non-negative real-valued error parameter. However, the best-known algorithm has a large oracle construction time, a large oracle size, and a large query time. Motivated by this, we propose a novel ϵ -approximate distance and path oracle called the S pace E fficient distance and path oracle (SE), which has a small oracle construction time, a small oracle size, and a small distance and path query time, thanks to its compactness of storing concise information about pairwise distances between any two points-of-interest. Then, we propose several algorithms for the k nearest/farthest neighbor and top- k closest/farthest pairs queries with the assistance of our distance and path oracle SE . Our experimental results show that the oracle construction time, the oracle size, and the distance and path query time of SE are up to two, three, and five orders of magnitude faster than the best-known algorithm, respectively. Besides, our algorithms for other proximity queries including k nearest/farthest neighbor queries and top- k closest/farthest pairs queries significantly outperform the state-of-the-art algorithms by up to two orders of magnitude.

In this work, we propose a robust road network representation learning framework called Toast, which comes to be a cornerstone to boost the performance of numerous demanding transport planning tasks. Specifically, we first propose a traffic context aware skip-gram module to incorporate auxiliary tasks of predicting the traffic context of a target road segment. Furthermore, we propose a trajectory-enhanced Transformer module that utilizes trajectory data to extract traveling semantics on road networks. Apart from obtaining effective road segment representations, this module also enables us to obtain the route representations. With these two modules, we can learn representations which can capture multi-faceted characteristics of road networks to be applied in both road segment based applications and trajectory based applications. Last, we design a benchmark containing four typical transport planning tasks to evaluate the usefulness of Toast and comprehensive experiments verify that Toast consistently outperforms the state-of-the-art baselines across all tasks.

Deep metric learning is a supervised learning paradigm to construct a meaningful vector space to represent complex objects. A successful application of deep metric learning to pointsets means that we can avoid expensive retrieval operations on objects such as documents and can significantly facilitate many machine learning and data mining tasks involving pointsets. We propose a self-supervised deep metric learning solution for pointsets. The novelty of our proposed solution lies in a self-supervision mechanism that makes use of a distribution distance for set ranking called the Earth's Mover Distance (EMD) to generate pseudo labels. Our experimental studies on four documents datasets show that our proposed solutions outperform baselines and state-of-the-art approaches on unsupervised deep metric learning in most settings.

Trajectory data is used in various applications including traffic analysis, logistics, and mobility services. It is usually collected continuously by sensors and accumulated at a server resulting in big volume. A common practice is to conduct trajectory simplification which is to drop some points of a trajectory when they are being collected (online mode) and/or after they are accumulated (batch mode). Existing algorithms usually involve some decision making tasks (e.g., deciding which point to drop), for which, some human-crafted rules are used. In this paper, we propose to learn a policy for the decision making tasks via reinforcement learning (RL) and develop trajectory simplification methods based on the learned policy. Compared with existing algorithms, our RL-based methods are data-driven and can adapt to different dynamics underlying the problem. We conduct extensive experiments to verify that our RL-based methods compute simplified trajectories with smaller errors while running comparably fast (and faster in the batch mode) compared with existing methods.

The e-commerce era is witnessing rising new arrivals of items on e-commerce platforms every day. Identifying potential popular items accurately is of great importance in creating commercial value. Click-Through Rate (CTR) is a general indicator to evaluate item popularity. However, existing methods fail in new arrivals prediction because of sparse item features, missing item statistics and high time complexity of computing for all pairs of users and items. To tackle these challenges, we propose a novel Adversarial Two-tower Neural Network (ATNN) model for new arrivals CTR predictions by introducing an adversarial network to a two-tower network. We design a generator and a discriminator to better learn an item vector based on item profiles without item statistics. We also develop a strategy with an O(1) time complexity for a new item's popularity prediction by constructing a user group and utilizing its mean user vector in a time-efficient manner. We implement ATNN on a largescale real-world dataset from one of the world's largest ecommerce platforms, “Tmall.com”. Empirical results show that ATNN is strongly capable of learning item vectors from item profiles for e-commerce. Furthermore, by introducing multi-task learning technology, we extend ATNN to food delivery service. Experimental results on one popular food delivery platform, “Ele.me”, demonstrate that ATNN can recognize attractive and welcoming new restaurants that have higher Value per Page View (VpPV) and generate more Gross Merchandise Volume (GMV).

A user-item matrix conveniently represents the utility measure associated with (user, item) pairs, such as citation counts, users’ rating/vote on items or locations, and clicks on items. A high utility value indicates a strong association of the pair. In this work, we consider the problem of summarizing strong associations for a large user-item matrix using a small summary size. The traditional techniques fail to distinguish user groups associated with different items, such as top-l item selection, or fail to focus on high utility, such as similarity based subspace clustering and biclustering. We define a new problem, called Group Utility Maximization, to summarize the entire user population through k groups and l items for each group; the goal is to maximize the sum of utility of selected items over all groups collectively. We propose the k-max algorithm for it, which iteratively refines existing k groups. We evaluate the proposed algorithm on two real-life datasets. The results provide an easyto-understand overview of the whole dataset efficiently.

Trajectory data has been widely used in various applications, including taxi services, traffic management, mobility analysis, etc. It is usually collected at a sensor's side in real time and corresponds to a sequence of sampled points. Constrained by the storage and/or network bandwidth of a sensor, it is common to simplify raw trajectory data when it is collected by dropping some sampled points. Many algorithms have been proposed for the error-bounded online trajectory simplification (EB-OTS) problem, which is to drop as many points as possible subject to that the error is bounded by an error tolerance. Nevertheless, these existing algorithms rely on pre-defined rules for decision making during the trajectory simplification process and there is no theoretical ground supporting their effectiveness. In this paper, we propose a multi-agent reinforcement learning method called MARL4TS for EB-OTS. MARL4TS involves two agents for different decision making problems during the trajectory simplification processes. Besides, MARL4TS has its objective equivalent to that of the EB-OTS problem, which provides some theoretical ground of its effectiveness. We conduct extensive experiments on real-world trajectory datasets, which verify that MARL4TS outperforms all existing algorithms in effectiveness and provides competitive efficiency.

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

As a fundamental component in location-based services, inferring the relationship between points-of-interests (POIs) is very critical for service providers to offer good user experience to business owners and customers. Most of the existing methods for relationship inference are not targeted at POI, thus failing to capture unique spatial characteristics that have huge effects on POI relationships. In this work we propose PRIM to tackle POI relationship inference for multiple relation types. PRIM features four novel components, including a weighted relational graph neural network, category taxonomy integration, a self-attentive spatial context extractor, and a distance-specific scoring function. Extensive experiments on two real-world datasets show that PRIM achieves the best results compared to state-of-the-art baselines and it is robust against data sparsity and is applicable to unseen cases in practice.

Vehicular path flow (trajectories) is an important data source for smart mobility, from which many road traffic parameters can be inferred. However, it has been a long-existing challenge that single source of trajectory data is biased in terms of its spatiotemporal coverage. In this paper, we leverage two types of large traffic datasets - point flows and sample trajectories - to generate the full city-scale vehicular paths. Our method consists of a low-granularity data fusion (LGDF) module, which uses point flow data to estimate the sparse paths that pass through some specific links (where sensors are mounted), and a high-granularity model training (HGMT) component, which uses sample trajectory data to pre-train a bi-gram sequence generation model. Afterwards, the results from LGDF and HGMT are combined to produce detailed on-road spatiotemporal paths. In this way, the data safety of single trajectory is protected while the full-scale city traffic can be reproduced for transportation analytics. The proposed method is verified via real-data case studies. As a result, starting from August 2019, this method has been implemented in Alibaba's city brain project and successively deployed in many cities in China for the purpose of traffic analysis and optimization.

Large-scale online promotions, such as Double 11 and Black Friday, are of great value to e-commerce platforms nowadays. Traditional methods are not successful when we aim to maximize global Gross Merchandise Volume (GMV) in the promotion scenarios due to three limitations. The first is that the GMV of sellers varies significantly from daily scenarios to promotions. Second, these methods do not consider explosive demands in promotions, so that a consumer may fail to purchase some popular items due to sellers' limited capacities. Third, the traffic distribution over sellers presents divergence in different channels, thus rendering the performance of the traditional single-channel methods far from optimal in creating commercial values. To address these problems, we design a Multi-Channel Sellers Traffic Allocation (MCSTA) optimization model to obtain optimal page view (PV) distribution concerning global GMV. Then we propose a general constrained non-smooth convex optimization solution with a Multi-Objective Shortest Distance (MOSD) hyperparameter tuning method to solve MCSTA. This is the first work to systematically address this issue in the scenario of large-scale online promotions. The empirical results show that MCSTA achieves significant improvement of GMV by 1.1% based on A/B test during Alibaba's "Global Shopping Festival", one of the world's largest online sales events. Furthermore, we deploy MCSTA in other popular scenarios, including everyday promotion and video live stream service, to showcase that MCSTA can be widely applied in e-commerce and online entertainment services.

Geo-textual data is ubiquitous nowadays, where each object has a location and is associated with some keywords. Many types of queries based on geo-textual data, termed as spatial keyword queries, have been proposed, and are to find optimal object(s) in terms of both its (their) location(s) and keywords. In this paper, we propose a new type of query called nearby-fit spatial keyword query (NSKQ), where an optimal object is defined based not only on the location and the keywords of the object itself, but also on those of the objects nearby. For example, in an application of finding a hotel, not only the location of a hotel but also the objects near the hotel (e.g., shopping malls, restaurants and bus stops nearby) might need to be taken into consideration.The query is proved to be NP-hard, and in order to perform the query efficiently, we developed two approximate algorithms with small constant approximation factors equal to 1.155 and 1.79. We conducted extensive experiments based on both real and synthetic datasets, which verified our algorithms.

The rapid development of e-commerce requires efficient and reliable logistics services. Nowadays, couriers are still the main solution to address the "last mile" problem in logistics. They are usually required to record the accurate delivery time of each parcel manually, which provides vital information for applications like delivery insurances, delivery performance evaluations, and customer available time discovery. Couriers' trajectories generated by their PDAs provide a chance to infer the delivery time automatically to ease the burdens on the couriers. However, directly using the nearest stay point to infer the delivery time is under satisfactory due to two challenges: 1) inaccurate delivery locations, and 2) various stay scenarios. To this end, we propose Delivery Time Inference (DTInf), to automatically infer the delivery time of waybills based on couriers' trajectories. Our solution is composed of three steps: 1) Data Pre-processing, which detects stay points from trajectories, and separates stay points and waybills by delivery trips, 2) Delivery Location Correction, which infers true delivery locations of waybills by mining historical deliveries, and 3) Delivery Event-based Matching, which selects the best-matched stay point for waybills in the same delivery location to infer the delivery time. Extensive experiments and case studies based on large scale real-world waybill and trajectory data from JD Logistics confirm the effectiveness of our approach. Finally, we introduce a system based on DTInf, which is deployed and used internally in JD Logistics.

Given two vertices of interest (POIs) s and t on a spatial network, a distance (path) query returns the shortest network distance (shortest path) from s to t. This query has a variety of applications in practice and is a fundamental operation for many database and data mining algorithms. In this paper, we propose an efficient distance and path oracle on dynamic road networks using the randomization technique. Our oracle has a good performance in practice and remarkably, and at the same time, it has a favorable theoretical bound. Specifically, it has O(n log2 n) (resp. O(n log2n)) preprocessing time (resp. space) and O(log4n log log n) (resp. O(log4n log log n+l)) distance query time (resp. shortest path query time) as well as O(log3n) update time with high probability (w.h.p.), where n is the number of vertices in the spatial network and l is the number of edges on the shortest path. Our experiments show that the existing oracles suffer from a huge updating time that renders them impractical and our oracle enjoys a negligible updating time and meanwhile has comparable query time and indexing cost with the best existing oracle.

Mobility prediction, which is to predict where a user will arrive based on the user's historical mobility records, has attracted much attention. We argue that it is more useful to know not only where but also when a user will arrive next in many scenarios such as targeted advertising and taxi service. In this paper, we propose a novel context-aware deep model called DeepJMT for jointly performing mobility prediction (to know where) and time prediction (to know when). The DeepJMT model consists of (1) a hierarchical recurrent neural network (RNN) based sequential dependency encoder, which is more capable of capturing a user's mobility regularities and temporal patterns compared to vanilla RNN based models; (2) a spatial context extractor and a periodicity context extractor to extract location semantics and the user's periodicity, respectively; and (3) a co-attention based social & temporal context extractor which could extract the mobility and temporal evidence from social relationships. Experiments conducted on three real-world datasets show that DeepJMT outperforms the state-of-the-art mobility prediction and time prediction methods.

Geo-textual data is ubiquitous nowadays, where each object has a location and is associated with some keywords. Many types of queries based on geo-textual data, termed as spatial keyword queries, have been proposed, and are to find optimal object(s) in terms of both its (their) location(s) and keywords. In this paper, we propose a new type of query called nearby-fit spatial keyword query (NSKQ), where an optimal object is defined based not only on the location and the keywords of the object itself, but also on those of the objects nearby. For example, in an application of finding a hotel, not only the location of a hotel but also the objects near the hotel (e.g., shopping malls, restaurants, and bus stops nearby) might need to be taken into consideration. The query is proved to be NP-hard, and in order to perform the query efficiently, we developed two approximate algorithms with small constant approximation factors equal to 1.155 and 1.79. We conducted extensive experiments based on both real and synthetic datasets, which verified our algorithms.

With the proliferation of spatial-textual data such as location-based services and geo-tagged websites, spatial keyword queries are ubiquitous in real life. One example of spatial-keyword query is the so-called collective spatial keyword query (CoSKQ) which is to find, for a given query consisting a query location and several query keywords, a set of objects which covers the query keywords collectively and has the smallest cost wrt the query location. Quite a few cost functions have been proposed for CoSKQ and correspondingly, different approaches have been developed. However, given these cost functions in different forms and approaches in different structures, one could hardly compare existing cost functions systematically and needs to implement all approaches in order to tackle the CoSKQ problem with different cost functions, which is effort-consuming. In this paper, we design a unified cost function which generalizes the majority of existing cost functions for CoSKQ and develop a unified approach which works as well as (and sometimes better than) best-known approaches based on different cost functions. Experiments were conducted on both real and synthetic datasets which verified our proposed approach.

Co-location patterns are well-established on spatial objects with categorical labels, which capture the phenomenon that objects with certain labels are often located in close geographic proximity. Similar to frequent itemsets, co-location patterns are defined based on a support measure which quantifies the popularity (or prevalence) of a pattern candidate (a label set). Quite a few support measures exist for defining co-location patterns and they share an idea of counting the number of instances of a given label set C as its support, where an instance of C is an object set whose objects carry all the labels in C and are located close to one another. Unfortunately, these measures suffer from various weaknesses, e.g., some fail to capture all possible instances while some others overlook the cases when multiple instances overlap. In this paper, we propose a new measure called Fraction-Score whose idea is to count instances fractionally if they overlap. Compared to existing measures, Fraction-Score not only captures all possible instances, but also handles the cases where instances overlap appropriately (so that the supports defined are more meaningful and consistent with the desirable anti-monotonicity property). To solve the co-location pattern mining problem based on Fraction-Score, we develop efficient algorithms which are significantly faster than a baseline that adapts the state-of-the-art. We conduct extensive experiments using both real and synthetic datasets, which verified the superiority of Fraction-Score and also the efficiency of our developed algorithms.

Online bipartite graph matching is attracting growing research attention due to the development of dynamic task assignment in sharing economy applications, where tasks need be assigned dynamically to workers. Past studies lack practicability in terms of both problem formulation and solution framework. On the one hand, some problem settings in prior online bipartite graph matching research are impractical for real-world applications. On the other hand, existing solutions to online bipartite graph matching are inefficient due to the unnecessary real-time decision making. In this paper, we propose the dynamic bipartite graph matching (DBGM) problem to be better aligned with real-world applications and devise a novel adaptive batch-based solution framework with a constant competitive ratio. As an effective and efficient implementation of the solution framework, we design a reinforcement learning based algorithm, called Restricted Q-learning (RQL), which makes near-optimal decisions on batch splitting. Extensive experimental results on both real and synthetic datasets show that our methods outperform the state-of-the-arts in terms of both effectiveness and efficiency.

With the proliferation of commercial tracking systems, sports data is being generated at an unprecedented speed and the interest in sports play retrieval has grown dramatically as well. However, it is challenging to design an effective, efficient and robust similarity measure for sports play retrieval. To this end, we propose a deep learning approach to learn the representations of sports plays, called play2vec, which is robust against noise and takes only linear time to compute the similarity between two sports plays. We conduct experiments on real-world soccer match data, and the results show that our solution performs more effectively and efficiently compared with the state-of-the-art methods.

Online social network (OSN) analysis has attracted much attention in recent years. One important distinguishing feature of OSNs is that every user provides his/her personal profile online, which can be regarded as the labels or attributes of this user. Knowing the number of nodes or edge with a particular label will give us deeper insight of the OSNs and can provide valuable information in many real-world applications such as web marketing and advertising. For many OSNs, one can only access parts of the network using the application programming interfaces (APIs). In such cases, conventional algorithms become infeasible. In this paper, we introduce efficient algorithms for estimating the number of edges with target labels in OSNs based on random walk. We also derive theoretical bounds on the sample size and the number of APIs calls needed in our algorithms for a probabilistic accuracy guarantee. We ran experiments on several publicly available real-world networks and the results demonstrate the effectiveness of our algorithms.

Extracting interesting tuples from a large database is an important problem in multi-criteria decision making. Two representative queries were proposed in the literature: top- k queries and skyline queries. A top- k query requires users to specify their utility functions beforehand and then returns k tuples to the users. A skyline query does not require any utility function from users but it puts no control on the number of tuples returned to users. Recently, a k-regret query was proposed and received attention from the community because it does not require any utility function from users and the output size is controllable, and thus it avoids those deficiencies of top- k queries and skyline queries. Specifically, it returns k tuples that minimize a criterion called the maximum regret ratio .

In many commercial campaigns, we observe that there exists a tradeoff between the number of customers satisfied by the company and the profit gained. Merely satisfying as many customers as possible or maximizing the profit is not desirable. To this end, in this article, we propose a new problem called k - Satisfiability Assignment for Maximizing the Profit ( k -SAMP), where k is a user parameter and a non-negative integer. Given a set P of products and a set O of customers, k -SAMP is to find an assignment between P and O such that at least k customers are satisfied in the assignment and the profit incurred by this assignment is maximized. Although we find that this problem is closely related to two classic computer science problems, namely maximum weight matching and maximum matching, the techniques developed for these classic problems cannot be adapted to our k -SAMP problem. In this work, we design a novel algorithm called Adjust for the k -SAMP problem. Given an assignment A , Adjust iteratively increases the profit of A by adjusting some appropriate matches in A while keeping at least k customers satisfied in A . We prove that Adjust returns a global optimum. Extensive experiments were conducted that verified the efficiency of Adjust .

With the proliferation of spatial-textual data such as location-based services and geo-tagged websites, spatial keyword queries are ubiquitous in real life. One example of spatial-keyword query is the so-called collective spatial keyword query (CoSKQ) which is to find for a given query consisting a query location and several query keywords a set of objects which covers the query keywords collectively and has the smallest costwrt the query location. In the literature, many different functions were proposed for defining the cost and correspondingly, many different approaches were developed for the CoSKQ problem. In this paper, we study the CoSKQ problem systematically by proposing a unified cost function and a unified approach for the CoSKQ problem (with the unified cost function). The unified cost function includes all existing cost functions as special cases and the unified approach solves the CoSKQ problem with the unified cost function in a unified way. Experiments were conducted on both real and synthetic datasets which verified our proposed approach.

Due to the advance of the geo-spatial positioning and the computer graphics technology, digital terrain data become more and more popular nowadays. Query processing on terrain data has attracted considerable attention from both the academic community and the industry community. One fundamental and important query is the shortest distance query and many other applications such as proximity queries (including nearest neighbor queries and range queries), 3D object feature vector construction and 3D object data mining are built based on the result of the shortest distance query. In this paper, we study the shortest distance query which is to find the shortest distance between a point-of-interest and another point-of-interest on the surface of the terrain due to a variety of applications. As observed by existing studies, computing the exact shortest distance is very expensive. Some existing studies proposed ε-approximate distance oracles where ε is a non-negative real number and is an error parameter. However, the best-known algorithm has a large oracle construction time, a large oracle size and a large distance query time. Motivated by this, we propose a novel ε-approximate distance oracle called the Space Efficient distance oracle (SE) which has a small oracle construction time, a small oracle size and a small distance query time due to its compactness storing concise information about pairwise distances between any two points-of-interest. Our experimental results show that the oracle construction time, the oracle size and the distance query time of SE are up to two orders of magnitude, up to 3 orders of magnitude and up to 5 orders of magnitude faster than the best-known algorithm.

In this article, we study an optimal location query based on a road network. Specifically, given a road network containing clients and servers, an optimal location query finds a location on the road network such that when a new server is set up at this location, a certain cost function computed based on the clients and servers (including the new server) is optimized. Two types of cost functions, namely, MinMax and MaxSum, have been used for this query. The optimal location query problem with MinMax as the cost function is called the MinMax query, which finds a location for setting up a new server such that the maximum cost of a client being served by his/her closest server is minimized. The optimal location query problem with MaxSum as the cost function is called the MaxSum query, which finds a location for setting up a new server such that the sum of the weights of clients attracted by the new server is maximized. The MinMax query and the MaxSum query correspond to two types of optimal location query with the objectives defined from the clients' perspective and from the new server's perspective, respectively. Unfortunately, the existing solutions for the optimal query problem are not efficient. In this article, we propose an efficient algorithm, namely, MinMax-Alg ( MaxSum-Alg ), for the MinMax (MaxSum) query, which is based on a novel idea of nearest location component . We also discuss two extensions of the optimal location query, namely, the optimal multiple-location query and the optimal location query on a 3D road network. Extensive experiments were conducted, showing that our algorithms are faster than the state of the art by at least an order of magnitude on large real benchmark datasets. For example, in our largest real datasets, the state of the art ran for more than 10 (12) hours while our algorithm ran within 3 (2) minutes only for the MinMax (MaxSum) query, that is, our algorithm ran at least 200 (600) times faster than the state of the art.

Trajectory data is becoming more and more popular nowadays and extensive studies have been conducted on trajectory data. One important research direction about trajectory data is the anomaly detection which is to find all anomalies based on trajectory patterns in a road network. In this paper, we introduce a road segment-based anomaly detection problem, which is to detect the abnormal road segments each of which has its “real” traffic deviating from its “expected” traffic and to infer the major causes of anomalies on the road network. First, a deviation-based method is proposed to quantify the anomaly of reach road segment. Second, based on the observation that one anomaly from a road segment can trigger other anomalies from the road segments nearby, a diffusion-based method based on a heat diffusion model is proposed to infer the major causes of anomalies on the whole road network. To validate our methods, we conduct intensive experiments on a large real-world GPS dataset of about 23,000 taxis in Shenzhen, China to demonstrate the performance of our algorithms.

In this paper, we study the optimal location query problem based on road networks. Specifically, we have a road network on which some clients and servers are located. Each client finds the server that is closest to her for service and her cost of getting served is equal to the (network) distance between the client and the server serving her multiplied by her weight or importance. The optimal location query problem is to find a location for setting up a new server such that the maximum cost of clients being served by the servers (including the new server) is minimized. This problem has been studied before, but the state-of-the-art is still not efficient enough. In this paper, we propose an efficient algorithm for the optimal location query problem, which is based on a novel idea of \emph{nearest location component}. We also discuss three extensions of the optimal location query problem, namely the optimal multiple-location query problem, the optimal location query problem on 3D road networks, and the optimal location query problem with another objective. Extensive experiments were conducted which showed that our algorithms are faster than the state-of-the-art by at least an order of magnitude on large real benchmark datasets. For example, on our largest real datasets, the state-of-the-art ran for more than 10 hours but our algorithm ran within 3 minutes only (i.e., >200 times faster).

Hyperspheres are commonly used for representing uncertain objects (in uncertain databases) and for indexing spatial objects (in spatial databases). An interesting operator on hyperspheres called dominance is to decide for two given hyperspheres whether one dominates (or is closer than) the other wrt a given query hypersphere. In this paper, we propose an approach called Hyperbola which is optimal in the sense that it gives neither false positives nor false negatives and runs in linear time wrt the dimensionality. To the best of our knowledge, Hyperbola is the first optimal approach for the dominance problem on hyperespheres with any dimensionality. We also study an application of the dominance problem which relies on the dominance operator as the core component. We conducted extensive experiments on both real and synthetic datasets which verified our approaches.

Trajectory data is central to many applications with moving objects. Raw trajectory data is usually very large, and so is simplified before it is stored and processed. Many trajectory simplification notions have been proposed, and among them, the direction-preserving trajectory simplification (DPTS) which aims at protecting the direction information has been shown to perform quite well. However, existing studies on DPTS require users to specify an error tolerance which users might not know how to set properly in some cases (e.g., the error tolerance could only be known at some future time and simply setting one error tolerance does not meet the needs since the simplified trajectories would usually be used in many different applications which accept different error tolerances). In these cases, a better solution is to minimize the error while achieving a pre-defined simplification size. For this purpose, in this paper, we define a problem called Min-Error and develop two exact algorithms and one 2-factor approximate algorithm for the problem. Extensive experiments on real datasets verified our algorithms.

Terrain data is becoming increasingly popular both in industry and in academia. Many tools have been developed for visualizing terrain data. However, we find that (1) they usually accept very few data formats of terrain data only; (2) they do not support terrain simplification well which, as will be shown, is used heavily for query processing in spatial databases; and (3) they do not provide the surface distance operator which is fundamental for many applications based on terrain data. Motivated by this, we developed a tool called Terrain-Toolkit for terrain data which accepts a comprehensive set of data formats, supports terrain simplification and provides the surface distance operator.

There are a bulk of studies on proposing algorithms for composing the melody of a song automatically with algorithms, which is known as algorithmic composition. To the best of our knowledge, none of them took the lyric into consideration for melody composition. However, according to some recent studies, within a song, there usually exists a certain extent of correlation between its melody and its lyric. In this demonstration, we propose to utilize this type of correlation information for melody composition. Based on this idea, we design a new melody composition algorithm and develop a melody composer called T-Music which employs this composition algorithm.

Peer review has become the most common practice for judging papers submitted to a conference for decades. An extremely important task involved in peer review is to assign submitted papers to reviewers with appropriate expertise which is referred to as paper-reviewer assignment. In this paper, we study the paper-reviewer assignment problem from both the goodness aspect and the fairness aspect. For the goodness aspect, we propose to maximize the topic coverage of the paper-reviewer assignment. This objective is new and the problem based on this objective is shown to be NP-hard. To solve this problem efficiently, we design an approximate algorithm which gives a 1/3-approximation. For the fairness aspect, we perform a detailed study on conflict-of-interest (COI) types and discuss several issues related to using COI, which, we hope, can raise some open discussions among researchers on the COI study. Finally, we conducted experiments on real datasets which verified the effectiveness of our algorithm and also revealed some interesting results of COI.

Recently, spatial keyword queries become a hot topic in the literature. One example of these queries is the collective spatial keyword query (CoSKQ) which is to find a set of objects in the database such that it covers a set of given keywords collectively and has the smallest cost. Unfortunately, existing exact algorithms have severe scalability problems and existing approximate algorithms, though scalable, cannot guarantee near-to-optimal solutions. In this paper, we study the CoSKQ problem and address the above issues.

Bichromatic reverse nearest neighbor (BRNN) queries have been studied extensively in the literature of spatial databases. Given a set P of service-providers and a set O of customers, a BRNN query is to find which customers in O are "interested" in a given service-provider in P. Recently, it has been found that this kind of queries lacks the consideration of the capacities of service-providers and the demands of customers. In order to address this issue, some spatial matching problems have been proposed, which, however, cannot be used for some real-life applications like emergency facility allocation where the maximum matching cost (or distance) should be minimized. In this paper, we propose a new problem called Spatial Matching for Minimizing Maximum matching distance (SPM-MM). Then, we design two algorithms for SPM-MM, Threshold-Adapt and Swap-Chain. Threshold-Adapt is simple and easy to understand but not scalable to large datasets due to its relatively high time/space complexity. Swap-Chain, which follows a fundamentally different idea from Threshold-Adapt, runs faster than Threshold-Adapt by orders of magnitude and uses significantly less memory. We conducted extensive empirical studies which verified the efficiency and scalability of Swap-Chain.

Trajectories of moving objects are collected in many applications. Raw trajectory data is typically very large, and has to be simplified before use. In this paper, we introduce the notion of direction-preserving trajectory simplification, and show both analytically and empirically that it can support a broader range of applications than traditional position-preserving trajectory simplification. We present a polynomial-time algorithm for optimal direction-preserving simplification, and another approximate algorithm with a quality guarantee. Extensive experimental evaluation with real trajectory data shows the benefit of the new techniques.

Viral marketing has attracted considerable concerns in recent years due to its novel idea of leveraging the social network to propagate the awareness of products. Specifically, viral marketing is to first target a limited number of users (seeds) in the social network by providing incentives, and these targeted users would then initiate the process of awareness spread by propagating the information to their friends via their social relationships. Extensive studies have been conducted for maximizing the awareness spread given the number of seeds. However, all of them fail to consider the common scenario of viral marketing where companies hope to use as few seeds as possible yet influencing at least a certain number of users. In this paper, we propose a new problem, called J-MIN-Seed, whose objective is to minimize the number of seeds while at least J users are influenced. J-MIN-Seed, unfortunately, is proved to be NP-hard in this work. In such case, we develop a greedy algorithm that can provide error guarantees for J-MIN-Seed. Furthermore, for the problem setting where J is equal to the number of all users in the social network, denoted by Full-Coverage, we design other efficient algorithms. Extensive experiments were conducted on real datasets to verify our algorithm.