High-level automation is increasingly critical in AI, driven by rapid advances in large language models (LLMs) and AI agents. However, LLMs, despite their general reasoning power, struggle significantly in specialized, data-sensitive tasks such as designing Graph Neural Networks (GNNs). This difficulty arises from (1) the inherent knowledge gaps in modeling the intricate, varying relationships between graph properties and suitable architectures and (2) the external noise from misleading descriptive inputs, often resulting in generic or even misleading model suggestions. Achieving proficiency in designing data-aware models—defined as the meta-level capability to systematically accumulate, interpret, and apply data-specific design knowledge—remains challenging for existing automated approaches, due to their inefficient construction and application of meta-knowledge. To achieve meta-level proficiency, we propose DesiGNN, a knowledge-centered framework that systematically converts past model design experience into structured, fine-grained knowledge priors well-suited for meta-learning with LLMs. To account for the inherent variability and external noise, DesiGNN aligns empirical property filtering from extensive benchmarks with adaptive elicitation of literature insights via LLMs. By constructing a solid meta-knowledge between unseen graph understanding and known effective architecture patterns, DesiGNN can deliver top-5.77% initial model proposals for unseen datasets within seconds and achieve consistently superior performance with minimal search cost compared to baselines.

Spatio-temporal data proliferates in numerous real-world domains, such as transportation, weather, and energy. Spatio-temporal deep learning models aims to utilize useful patterns in such data to support tasks like prediction, imputation, and anomaly detection. However, previousone-to-onedeep learning models designed for specific tasks typically require separate training for each use case, leading to increased computational and storage costs. To address this issue,one-to-manyspatio-temporal foundation models have emerged, offering a unified framework capable of solving multiple spatio-temporal tasks. These foundation models achieve remarkable success by learning general knowledge with spatio-temporal data or transferring the general capabilities of pre-trained language models. While previous surveys have explored spatio-temporal data and methodologies separately, they have ignored a comprehensive examination of how foundation models are designed, selected, pre-trained, and adapted. As a result, the overall pipeline for spatio-temporal foundation models remains unclear. To bridge this gap, we innovatively provide an up-to-date review of previous spatio-temporal foundation models from the pipeline perspective. The pipeline begins with an introduction to different types of spatio-temporal data, followed by details of data preprocessing and embedding techniques. The pipeline then presents a novel data property taxonomy to divide existing methods according to data sources and dependencies, providing efficient and effective model design and selection for researchers. On this basis, we further illustrate the training objectives of primitive models, as well as the adaptation techniques of transferred models. Overall, our survey provides a clear and structured pipeline to understand the connection between core elements of spatio-temporal foundation models while guiding researchers to get started quickly. Additionally, we introduce emerging opportunities such as multi-objective training in the field of spatio-temporal foundation models, providing valuable insights for researchers and practitioners.

Given a social network$G=(V, E)$, the unconstrained profit maximization problem aims to identify a subset$S \subseteq V$that maximizes the net profit, defined as the expected influence spread$\Gamma (S)$of set$S$minus the associated cost$c(S)$, i.e.,$\Gamma (S) - c(S)$. However, this problem presupposes an unlimited budget, which is often impractical in real scenarios. Motivated by this, we investigate the budgeted profit maximization (BPM) problem by adding a budget constraint. Unfortunately, addressing the BPM problem with a theoretical approximation guarantee remains relatively under-explored in the literature. In response, assuming$\Gamma (S)$is known for any$S \subseteq V$, we propose an algorithm that guarantees returning a set$S^{o}$such that$\Gamma (S^{o}) - c(S^{o}) \geq (1 - \frac{1}{e}) \frac{\Gamma (S^*)}{2} - \frac{c(S^*)}{2}$, where$S^*$denotes an optimal solution for BPM. Then, we develop a practical solution, which uses the reverse reachable set (RR-set) technique for influence estimation, without assuming knowledge of$\Gamma (S)$, while still maintaining a strong approximation guarantee. Additionally, similar to existing RR-set-based solutions for influence cascade-related problems, our RR-set-based solution relies on generating a large number of random RR-sets to accurately estimate$\Gamma (S)$. However, the existing RR-set generation method suffers from high memory stall rates due to its irregular memory access patterns, leaving room for further efficiency improvement. Therefore, we propose a new RR-set generation method that utilizes batch execution and cache prefetching. When a memory access is required, instead of stalling while waiting for data, the CPU first issues an asynchronous prefetch request to load the target data into the cache, and then switches to processing the generation of other RR-sets within the same batch, effectively hiding memory access latency. This method can be seamlessly integrated into existing RR-set-based solutions to improve their efficiency. Finally, we conduct extensive experiments on real, large-scale datasets to demonstrate the effectiveness and efficiency of our proposed solutions.

The diversified route planning finds multiple paths that are sufficiently different from each other while as short as possible. It is of great significance to traffic alleviation through provided alternative routes during navigation. However, it is NP-H to find the optimal result and the existing solutions have either high quality (exact path enumeration-based) or high efficiency (alternative path), which is highly affected by the network properties and query parameters but has never been investigated before. Therefore, this paper proposes a hybrid diversified routing system that can handle any query efficiently with quality as high as possible. Specifically, we first analyze the path enumeration problem from the ground up and unify all the existing algorithms theoretically to identify the factors that affect algorithm performance. After that, we review and select the alternative path methods to identify the suitable ones for our system. Finally, we propose a query classification module to estimate the hardness of a query and determine how it should be processed. Extensive experiments on real-life networks validate the effectiveness and efficiency of our hybrid system compared with state-of-the-art solutions.

Cellular Trajectory Map-Matching (CTMM) aims to align cellular location sequences to road networks, which is a necessary preprocessing in location-based services on web platforms like Google Maps, including navigation and route optimization. Current approaches mainly rely on ID-based features and region-specific data to learn correlations between cell towers and roads, limiting their adaptability to unexplored areas. To enable high-accuracy CTMM without additional training in target regions, Zero-shot CTMM requires to extract not only region-adaptive features, but also sequential and location uncertainty to alleviate positioning errors in cellular data. In this paper, we propose a pixel-based trajectory calibration assistant for zero-shot CTMM, which takes advantage of transferable geospatial knowledge to calibrate pixelated trajectory, and then guide the path-finding process at the road network level. To enhance knowledge sharing across similar regions, a Gaussian mixture model is incorporated into VAE, enabling the identification of scenario-adaptive experts through soft clustering. To mitigate high positioning errors, a spatial-temporal awareness module is designed to capture sequential features and location uncertainty, thereby facilitating the inference of approximate user positions. Finally, a constrained path-finding algorithm is employed to reconstruct the road ID sequence, ensuring topological validity within the road network. This process is guided by the calibrated trajectory while optimizing for the shortest feasible path, thus minimizing unnecessary detours. Extensive experiments demonstrate that our model outperforms existing methods in zero-shot CTMM by 16.8\%.

Velocity control in autonomous driving is an emerging technology that has achieved rapid progress over the last decade. However, existing velocity control studies ignore cascading disturbances in multi-lane scenarios and usually ignore the negative impact caused by harsh velocity decisions. To address these issues, we propose a reinforcement learning-based framework, called RISE (contRol velocIty for autonomouSvEhicle) to make velocity decisions for an autonomous vehicle in multi-lane traffic scenarios. To detect latent disturbances in the traffic flow, we propose a novel state encoder to learn the spatio-temporal correlation between different vehicles based on a well-designed impact graph. Afterward, we introduce an actor-critic paradigm to make velocity decisions with the aid of a hybrid reward function considering four optimization objectives: safety, efficiency, comfort, and impact. In particular, the impact term can penalize the harsh decisions of the autonomous vehicle, thus encouraging it to reduce the negative impacts on traffic flow. Further, we propose an improved RISE (RISE++) framework that incorporates a motion prediction model to augment state features for reasonable decisions, a modification of the reward function for energy efficiency, and a multi-worker paradigm for training efficiency. Extensive experiments offer evidence that the proposed framework can advance the state of the art in terms of effectiveness and efficiency.

Autonomous driving is an emerging technology that has developed rapidly over the last decade, with decision-making remaining a critical challenge, particularly due to its significant role in traffic congestion. In this paper, we propose a novel perception-and-decision framework, calledHEAD, which consists of an enHanced pErception module and a mAneuverDecision module to address this challenge. In the enhanced perception module, a graph-based state prediction model with a strategy of phantom vehicle construction is proposed to address incomplete vehicle features and predict future states in parallel. Then in the maneuver decision module, a deep reinforcement learning-based model is designed to learn a driving policy based on a parameterized action Markov decision process. A hybrid reward function takes into account aspects of safety, efficiency, comfort, and impact to guide the autonomous vehicle to make optimal maneuver decisions. To make our framework applicable to more scenarios, we further propose an improvedHEAD(HEAD++) framework that makes the autonomous vehicle adapt to various road structures, such as lane merging and diverging scenarios. Besides, we develop a style tuning module inHEAD++, which supports personalized driving style tuning. To mitigate high training costs, an efficient style tuning method with approximate gradient descent is proposed to reduce the number of training iterations. Extensive experiments demonstrate the effectiveness of our framework. Compared to state-of-the-art methods,HEAD++ reduces overall traffic disturbance by 23.3%-40.9%, lowers collision risk by 4.5%-17.8%, and improves passenger comfort by 13.1%-30.5%, while maintaining high traffic efficiency.

Trust relationships play a crucial role in various domains, such as social spam detection, retweet behavior analytics, and recommendation systems. Trust is often implicit and difficult to observe directly in the real world, as it is driven by people's underlying intentions and motivations. Therefore, when evaluating trust, it is critical to analyze not only user behavior data but also the intentions behind these behaviors that lead to trust. Existing trust evaluation methods often neglect the underlying reasons behind connections, such as shared hobbies or belonging to the same community. Therefore, these methods cannot differentiate the genuine intentions that lead to trust, resulting in an inaccurate evaluation of hidden trust relationships. To address this issue, we propose a novel Intent-based model for Trust Evaluation (INTRUST). This model can distinguish the intent behind high-order information in social communities using hypergraphs. Initially, we used hyperedges to represent high-order correlations between user-to-item and user-to-user interactions. Then, we construct K intent prototypes, which serve as foundational elements to build trust. Furthermore, we distinguish K-independent intent subgraphs from these high order correlations. To enhance the generalization and robustness of the model, we employ self-supervised learning and construct contrastive views at the node-level, hyperedge-level, and node hyperedge-level. Extensive experiments on real-world datasets demonstrate that our model outperforms state-of-the-art approaches in terms of trust evaluation accuracy and efficiency.

Surging e-commerce and global trade necessitate highly efficient cargo terminal operations. Modern automated terminals, crucial for supply chains, employ complex networks of static and movable equipment. This integration introduces a core challenge: movable equipment creates dynamic connectivity and state-dependent travel times, rendering classic shortest path algorithms based on static edge weights ineffective. Unlike typical time-dependent problems driven by external factors such as traffic congestion or fixed schedules, our dynamics stem from internal equipment state, presenting a unique optimization challenge. We address the problem of finding optimal cargo routes within these dynamic environments. We propose a novel approach by modeling the terminal as a cargo network, where virtual edges induced by movable equipment are explicitly materialised and edge costs reflect the status of the real-time equipment. We propose an efficient Dijkstra's-based algorithm to solve the cargo routing problem within this framework considering the system dynamics. The primary contributions of this paper are this novel modeling technique for dynamic terminals and the adapted algorithm for optimal routing, offering significant benefits for logistics optimization and automated warehouse design. Experimental results demonstrate that our approach significantly reduces cargo travel times compared to baseline methods, offering substantial improvements for logistics efficiency in automated terminals.

The advancement of navigation systems has generated numerous future route data. However, neglecting such data could deteriorate the future traffic condition, as it reflects the actual state of future traffic flow. In this demonstration, we propose a route data management system (RouteSys), for the efficient and accurate prediction of future traffic conditions. First, a macroscopic traffic simulation algorithm integrated with multiple light weight machine learning models is developed to simulate the future traffic condition of routes. Then, the future temporal information is stored in a route record index structure. In real-world scenarios, it can efficiently update simulated traffic conditions in response to dynamic changed future route data, such as newly added routes. To demonstrate the functionality of RouteSys, we design a front-end platform within a real-world road network scenario with the generated route data. A video demonstration is available at https://youtu.be/3xuF2t_pV2M.

Anomaly detection is one of the most significant tasks in industrial automatic maintenance, such as in distributed cloud systems. However, the implementation of existing anomaly detection methods is still challenging in (i) capturing the complex spatial and temporal correlations of multivariate time series, (ii) effectively adapting to the unsupervised condition, and (iii) generalizing across nodes in distributed systems. To address these challenges, we design a multi-perspective spatio-temporal attention model, called STAMP, which consists of a prediction module ST-ATTN, a reconstruction module AutoEncoder, and an adversarial optimizing module. Specifically, ST-ATTN leverages multiple attention mechanisms to perform spatio-temporal learning from both local and global perspectives, AutoEncoder is utilized to fit implicit representations, and the adversarial optimization module employs a min-max training strategy to enhance the learning capability. By introducing pre-training strategies, STAMP can be effectively adapted to distributed systems with a strong generalization ability. Furthermore, to cope with the practical unlabeled data conditions, we propose an unsupervised framework compatible with not only STAMP but also other advanced detection models. In this framework, a screening process is first conducted by traditional methods to generate a training set of pseudo-normal samples. Second, the models are trained and then used for detection. The framework can be further optimized by performing feature selection based on model-derived information for a better detectability. Extensive experiments in real-world datasets demonstrate that the proposed model and framework achieve superior performance when compared with baselines under both semi-supervised and unsupervised conditions. In particular, the detection framework has already been applied in Huawei's GaussDB (DWS) system.

Vertical Federated Learning (VFL) has emerged as a popular machine learning paradigm, enabling model training between the data and the task parties with different features about the same user set while preserving data privacy. In a production environment, VFL usually involves one task party and one data party. Fair and economically efficient feature trading is crucial to the commercialization of VFL, where the task party is considered the data consumer who buys the data party's features. However, current VFL feature trading practices often price the data party's data as a whole and assume transactions occur before performing VFL. Neglecting the performance gains resulting from traded features may lead to underpayment and overpayment issues. In this study, we propose a bargaining-based feature trading approach in VFL to facilitate economically efficient transactions. Our model incorporates performance gain-based pricing, taking into account the revenue-based optimization objectives of both parties. We analyze the proposed bargaining model under perfect and imperfect performance information settings, proving the existence of an equilibrium that optimizes the parties' objectives. Moreover, we develop performance gain estimation-based bargaining strategies for imperfect performance information scenarios and discuss potential security concerns and solutions. Experiments on three real-world datasets demonstrate the effectiveness of the proposed bargaining model.

Traffic forecasting is essential for intelligent transportation systems, aiming to predict future traffic dynamics such as speed and travel time through the analysis of past observations. However, mainstream deep learning frameworks, which rely heavily on historical data, often struggle in realworld applications due to their inadaptability to dynamic future changes, neglect of future traffic flow as the root cause of traffic conditions, and the complexity of model structures for city-scale road networks. To solve these limitations, we propose a Route Data Management System (RouteSys) that integrates a macroscopic simulation module with lightweight traffic prediction models to estimate the future traffic conditions on individual road segments by accurately and efficiently simulating vehicle travel sequences and traffic states in advance. Additionally, we integrate the microscopic traffic simulation tool SUMO with the custom route planning logic to generate synthetic route data, supporting model training and application evaluation. RouteSys has been validated on real-world road networks in various scenarios, showing substantial improvements in prediction accuracy, efficiency, and scalability compared to the mainstream structures.

Anomaly diagnosis is a fundamental problem in operation and maintenance of distributed cloud databases. Existing deep learning based methods solve this problem by classifying the anomalies with different root causes. However, since anomalies seldom occur, and anomalies with the same root cause may exhibit significantly different behaviors across different cloud database clusters, existing methods often lack sufficient training data, and they cannot generalize well from some clusters to others. Therefore, we take both anomaly and normal data into consideration, based on an observation that the discrepancy between the anomaly and normal data is relatively consistent compared to the behaviours of anomalies themselves. We design a Siamese Discrepancy Network (SDN) to learn representations of such discrepancy under the case that only a small amount of training data is available. In addition, a discrepancy-based diagnosis paradigm is proposed to construct training data for SDN and diagnose based on representations of discrepancy learned by SDN. Finally, we develop an anomaly interpretation method based on SDN, which accurately locates the symptom KPIs and root cause KPIs. Extensive experiments are conducted on both synthetic and real-world datasets. The experimental results demonstrate that the proposed method outperforms existing methods with respect to anomaly diagnosis and anomaly interpretation. In particular, the anomaly diagnosis framework has already been applied in Huawei's GaussDB (DWS) system.

Traffic prediction plays a crucial role in urban transportation systems, yet existing methods face challenges in achieving real-time performance when handling large-scale road networks. This paper introduces a novel Just-In-Time Traffic Prediction framework that integrates traffic condition with routing queries for efficient localized predictions in multi-query urban environments. Unlike traditional approaches that perform global predictions across entire networks, our framework partitions the road network into non-overlapping small regions and selectively updates traffic conditions based on query demands. Specifically, we propose three key components: (i) a Search Space Estimation (SSE) model that reformulates search space determination of routing queries as a binary classification task to accurately identify the searched regions; (ii) a Region-based Traffic Speed Prediction (RTSP) model that incorporates the temporal validity of speed profiles in adjacent regions and comprehensive spatio-temporal features for precise region-based traffic prediction; (iii) a Global Region Prediction Scheduling that efficiently coordinates the SSE and RTSP models to maintain up-to-date traffic data for running queries while minimizing computational overhead from both spatio and temporal dimensions. Experimental results on real-world road networks demonstrate significant improvements in both effectiveness and efficiency compared to state-of-the-arts.

Shortest path (SP) computation is the building block for many location-based services, and achieving high throughput SP query processing with real-time response is crucial for those services. However, existing solutions can hardly handle high throughput queries on large dynamic road networks due to either slow query efficiency or poor dynamic adaption. In this paper, we leverage graph partitioning and propose novel Partitioned Shortest Path (PSP) indexes to address this problem. Specifically, we first put forward a cross-boundary strategy to accelerate the query processing of PSP index and analyze its efficiency upper bound theoretically. After that, we propose a non-trivial Partitioned Multi-stage Hub Labeling (PMHL) that subtly aggregates multiple PSP strategies to achieve fast index maintenance and consecutive query efficiency improvement during index update. Lastly, to further optimize throughput, we design tree decomposition-based graph partitioning and propose Post-partitioned MHL (PostMHL) with faster query processing and index update. Experiments on real-world road networks show that our methods outperform state-of-the-art baselines in query throughput, yielding up to 2 orders of magnitude improvement.

Few-Shot Fake News Detection (FS-FND) aims to distinguish inaccurate news from real ones in extremely lowresource scenarios. This task has garnered increased attention due to the widespread dissemination and harmful impact of fake news on social media. Large Language Models (LLMs) have demonstrated competitive performance with the help of their rich prior knowledge and excellent in-context learning abilities. However, existing methods face significant limitations, such as the Understanding Ambiguity and Information Scarcity, which significantly undermine the potential of LLMs. To address these shortcomings, we propose a Dual-perspective Knowledge-guided Fake News Detection (DKFND) model, designed to enhance LLMs from both inside and outside perspectives. Specifically, DKFND first identifies the knowledge concepts of each news article through a Detection Module. Subsequently, DKFND creatively designs an Investigation Module to retrieve inside and outside valuable information concerning to the current news, followed by another Judge Module to evaluate the relevance and confidence of them. Finally, a Determination Module further derives two respective predictions and obtain the final result. Extensive experiments on two public datasets show the efficacy of our proposed method, particularly in low-resource settings.

Recent advances in machine learning, particularly in Natural Language Processing (NLP), have produced powerful models trained on vast datasets. However, these models risk leaking sensitive information, raising privacy concerns. In response, regulatory measures such as the European Union's General Data Protection Regulation (GDPR) have driven increasing interest in Machine Unlearning techniques, which enable models to selectively forget specific data entries. Early unlearning approaches primarily relied on pre-processing methods, while more recent research has shifted towards training-based solutions. Despite their effectiveness, a key limitation persists: most methods require access to original training data, which is often unavailable. Additionally, directly applying unlearning techniques bears the cost of undermining the model's expressive capabilities. To address these challenges, we introduce the Iterative Contrastive Unlearning (ICU) framework, which consists of three core components: A Knowledge Unlearning Induction module designed to target specific knowledge for removal using an unlearning loss; A Contrastive Learning Enhancement module to preserve the model's expressive capabilities against the pure unlearning goal; And an Iterative Unlearning Refinement module that dynamically adjusts the unlearning process through ongoing evaluation and updates. Experimental results demonstrate the efficacy of our ICU method in unlearning sensitive information while maintaining the model's overall performance, offering a promising solution for privacy-conscious machine learning applications.

Approximate nearest neighbor (ANN) search on high-dimensional vector data is core functionality in an increasing number of real-world applications. However, most existing methods only focus on accelerating search by means of indexing that assumes that the data is static. The few methods capable of contending with dynamic data often face challenges such as decreased query accuracy following updates and low update efficiency. In this study, we propose Wolverine, the first proposal that, to our knowledge, enables efficient monotonic search path repair, thereby solving the graph-based ANN index update problem. Wolverine repairs disrupted monotonic search paths by adding in-edges to the out-neighbors of a point to be deleted. To improve efficiency, Wolverine+ restricts the search space to be within the 2-hop neighbors of the point to be deleted. In addition, Wolverine++ employs a sophisticated candidate selection policy to find high-quality candidates in the reduced search space, simultaneously improving accuracy and efficiency. An experimental study on 9 real-world datasets demonstrates that Wolverine is capable of accelerating the deletion throughput by up to 11X and achieving more stable recall during updates compared to the state-of-the-art dynamic ANN search method.

Graph Edit Distance (GED) is a widely recognized metric for measuring graph similarity, yet its NP-complete nature poses challenges for fast and accurate computation. This paper introduces FGWAlign, an Optimal Transport (OT)-based approach for graph alignment and GED computation. We take the first step to theoretically demonstrate and that computing GED can be transformed into optimizing a particular OT variant—the Fused Gromov-Wasserstein distance. Tailored to the GED problem structure, we further implement three key enhancements to the standard FGW solver: (1) a random exploration scheme to better locate the global optimum, (2) a diverse projection strategy for post-processing the transportation plan to escape local optima, and (3) a novel extension to accommodate multi-relational graphs with edge labels. With O (| V || E |) time complexity and O (| V | 2 ) space complexity, where | V | and | E | are the maximum number of nodes and edges between the two compared graphs, FGWAlign achieves a superior balance of efficiency, accuracy, and scalability. Empirical results show that, compared with 12 representative GED computation methods across different categories on 4 real-world graph datasets, FGWAlign reduces computation errors by over 80% and achieves 15–60× speedup. It also demonstrates promising resutls on downstream applications including labeled graph alignment and graph-level anomaly detection, highlighting its versatility. FGWAlign opens up promising avenues for future applications in graph data management.

Designing a proper scoring function is the key to ensuring the excellent performance of knowledge base (KB) embedding. Recently, the scoring function search method introduces the automated machine learning technique to design the data-aware scoring function for the given binary relational data (a.k.a. knowledge graph, KG), which can consistently achieve good performance on different data sets. However, the current data-aware search method is still not as good as desired. First, the existing model can only search scoring functions on the given binary relational data, which is a special form of N-ary relational KBs. Second, observing that existing scoring functions can exhibit distinct performance on different semantic patterns, we are motivated to explore such semantics by searching pattern-aware scoring functions. Unfortunately, it is hard to extend existing search approaches to the scenarios of N-ary and pattern-aware due to the search efficiency and effectiveness issues. In this paper, we propose latent-based factors to model relational patterns and an efficient search algorithm on the N-ary scenario, i.e., efficient LA tent-based SCO ring function search for N-ary relational KBs (LASCO). The empirical results of LASCO on binary and N-ary relational data sets demonstrate that the proposed method can efficiently search pattern-aware scoring functions and achieve better embedding performance than advanced baselines.

Distantly supervised named entity recognition (DS-NER) has emerged as a cheap and convenient alternative to traditional human annotation methods, enabling the automatic generation of training data by aligning text with external resources. Despite the many efforts in noise measurement methods, few works focus on the latent noise distribution between different distant annotation methods. In this work, we explore the effectiveness and robustness of DS-NER by two aspects: (1) distant annotation techniques, which encompasses both traditional rule-based methods and the innovative large language model supervision approach, and (2) noise assessment, for which we introduce a novel framework. This framework addresses the challenges by distinctly categorizing them into theunlabeled-entity problem (UEP)and thenoisy-entity problem (NEP), subsequently providing specialized solutions for each. Our proposed method achieves significant improvements on eight real-world distant supervision datasets originating from three different data sources and involving four distinct annotation techniques, confirming its superiority over current state-of-the-art methods.

To address the issue of label sparsity in heterogeneous graphs (HGs), heterogeneous graph few-shot learning (HGFL) has recently emerged. HGFL aims to extract meta-knowledge from source HGs with rich-labeled data and transfers it to a target HG, facilitating learning new classes with few-labeled training data and improving predictions on unlabeled testing data. Existing methods typically assume the same distribution across the source HG, training data, and testing data. However, in practice, distribution shifts in HGFL are inevitable due to (1) the scarcity of source HGs that match the target HG's distribution, and (2) the unpredictable data generation mechanism of the target HG. Such distribution shifts can degrade the performance of existing methods, leading to a novel problem of out-of-distribution (OOD) generalization in HGFL. To address this challenging problem, we propose COHF, aCausalOODHeterogeneous graphFew-shot learning model. In COHF, we first adopt a bottom-up data generative perspective to identify the invariance principle for OOD generalization. Then, based on this principle, we design a novel variational autoencoder-based heterogeneous graph neural network (VAE-HGNN) to mitigate the impact of distribution shifts. Finally, we propose a novel meta-learning framework that incorporates VAE-HGNN to effectively transfer meta-knowledge in OOD environments. Extensive experiments on seven real-world datasets have demonstrated the superior performance of COHF over the state-of-the-art methods.

Traffic prediction has long been a focal and pivotal area in research, witnessing both significant strides from city-level to road-level predictions in recent years. With the advancement of Vehicle-to-Everything (V2X) technologies, autonomous driving, and large-scale models in the traffic domain, lane-level traffic prediction has emerged as an indispensable direction. However, further progress in this field is hindered by the absence of comprehensive and unified evaluation standards, coupled with limited public availability of data and code. In this paper, we present the first systematic classification framework for lane-level traffic prediction, offering a structured taxonomy and analysis of existing methods. We construct three representative datasets from two real-world road networks, covering both regular and irregular lane configurations, and make them publicly available to support future research. We further establishes a unified spatial topology structure and prediction task formulation, and proposes a simple yet effective baseline model, GraphMLP, based on graph structure and MLP networks. This unified framework enables consistent evaluation across datasets and modeling paradigms. We also reproduce previously unavailable code from existing studies and conduct extensive experiments to assess a range of models in terms of accuracy, efficiency, and applicability, providing the first benchmark that jointly considers predictive performance and training cost for lane-level traffic scenarios. All datasets and code are released athttps://github.com/ShuhaoLii/LaneLevel-Traffic-Benchmark.

Disentanglement techniques used in collaborative filtering uncover interaction intents between nodes, improving the interpretability of node representations and enhancing recommendation performance. However, existing disentanglement methods still face the following two problems. 1) They focus on local structural features derived from direct node interactions, overlooking the comprehensive graph structure, which limits disentanglement accuracy. 2) The disentanglement process depends on backpropagation signals derived from recommendation tasks, lacking direct supervision, which may lead to biases and overfitting. To address the issues, we propose theIntentPropagationContrastiveCollaborativeFiltering (IPCCF) algorithm. Specifically, we design a double helix message propagation framework to more effectively extract the deep semantic information of nodes, thereby improving the model's understanding of interactions between nodes. An intent message propagation method is also developed that incorporates graph structure information into the disentanglement process, thereby expanding the consideration scope of disentanglement. In addition, contrastive learning techniques are employed to align node representations derived from the structure and intents, providing direct supervision for the disentanglement process, mitigating biases, and enhancing the model's robustness to overfitting. The experiments on three real data graphs illustrate the superiority of the proposed approach.

The popularity of location-aware devices has boosted urban systems with massive volumes of anonymous trajectory data, presenting both challenges and opportunities for enhancing smart city initiatives through Trajectory-User Linking (TUL). Typically, TUL aims to match anonymous trajectories with specific users by exploring spatiotemporal patterns and insightful mobility behaviors. However, current TUL models face significant limitations due to their reliance on singular data sources and insufficient consideration of real-world scenarios. Furthermore, these models often lack evaluation in fair and comprehensive environments, hindering accurate assessment of their performance and applicability. This paper systematically investigates prevalent challenges encountered by existing TUL models, conducts a comprehensive review of state-of-the-art models, and proposes a structured framework that encompasses three core components: point-level representation learning, trajectory-level representation learning, and user linking. Through meticulously designed experiments, we examine the effectiveness and efficiency of leading TUL models in handling the complexities of real-world data, such as data imbalance, sparsity, new users, and scalability. This in-depth analysis uncovers limitations in existing methodologies and offers guidance for future advancements, contributing to the development of robust TUL solutions for urban mobility analysis and smart city technologies.

Shortest path computation is ubiquitous in various applications in road networks and the index-based algorithms, especially hub labeling, can boost the query performance dramatically. However, traffic conditions keep changing in real life, making the precomputed index unable to answer the query correctly. In this work, we adopt the state-of-the-arttree decomposition-based hub labeling (TDHL)as the underlying index and design efficient algorithms to incrementally maintain the index. Specifically, we first analyze the structural stability of the index in dynamic road networks which enables us to concentrate on label value maintenance. We then introduce theminimum weight propertyandminimum distance propertyto guarantee index correctness without graph traversal. Moreover, we propose thestar-centric paradigmfor tracing index change and design various pruning techniques to further accelerate index maintenance. We also extend our algorithms to batch mode for shared computation, to structural maintenance for full types of updates, and generalize to all kinds ofTDHL. Finally, we further improve the index maintenance efficiency and scalability of our algorithms by leveraging graph partition. Our experimental results validate the superiority of our proposals over existing solutions on both index maintenance and query processing.

Abstract With the development of location-based services, smart cities, and intelligent transportation, route planning has evolved beyond shortest path finding to satisfy user’s flexible travel purposes through the Optimal Routes with Collective Spatial Keywords (ORCSK) routing. Because different Points of Interest (POIs) contain different sets of keywords, the user usually needs to visit multiple POIs to fulfill all needs. Moreover, the POIs’ stop hardness (time and cost) also influences user experience, but it was ignored by the existing solutions. Therefore, this work proposes to extend the ORCSK problem into Skyline Optimal Routes with Collective Spatial Keyword (Sky-ORCSK) by considering both distance and stop hardness. Specifically, we first propose the IG-Sky algorithm from the spatial keyword search perspective by extending the IG-Tree. Then we propose the DA-Sky algorithm from the path enumeration perspective by extending our previous DA-CSK. Furthermore, five optimization strategies are proposed to improve efficiency by pruning the search space. Extensive experimental evaluations on real-world datasets demonstrate the algorithms’ efficacy and reliability, marking a significant step forward in refined route planning for modern urban environments.

Lane-level traffic prediction is crucial for refined smart city applications, yet the scarcity and quality issues of datasets hinder its development. To overcome these challenges, this study introduces a novel M ulti- c hannel g raph-structured V ariational A uto E ncoder model, McgVAE. This model integrates road-level information to provide a global perspective for lane prediction and performs integrated tasks through three interconnected channels: the road-level channel ensures accurate prediction of road traffic states and communicates closely with the data quality channel to share historical and predicted road information; the data quality channel leverages road-level information to identify and correct missing and noisy data; and finally, the lane channel uses the aforementioned information for lane-level traffic prediction. After extensive experimental comparisons with multiple baseline models across three datasets, the McgVAE model demonstrated outstanding predictive performance and the ability to handle data missingness and noise

The prediction of stock prices is a highly sought-after topic in the data mining field. In recent decades, many promising methods have been proposed and widely adopted for stock price prediction. However, these methods have inherent limitations, such as low accuracy, lack of transparency, and failure to consider the interactions among stock factors. To address these issues, we propose a UNIversal and interpretable framework for enhancing Stock Price Prediction (abbreviated to UniSPP), which is capable of modeling the interactions among stock factors. UniSPP first builds a fully connected graph, where the nodes and edges are the stock factors and interactions between them, respectively. However, it is a non-trivial task to discover a proper feature interaction subgraph from a large space, especially in discrete graph modeling. Therefore, UniSPP proposes a novel idea to mine the real factor interactions by iteratively sampling subgraphs and optimizing the sampling controller. Empirical studies show that our framework can be incorporated with many popular forecasting models and can effectively discover the suitable factor interaction, which can significantly improve the prediction results of existing models.

With the popularization of mobile applications and the timely acquisition of fresh data, real-time clustering and its evolution analysis have become the primary operations for data processing and knowledge discovery. Such continuous queries on massive objects are computation-intensive tasks in dynamic scenarios. However, existing clustering techniques are incompetent to achieve decent performance when computation-intensive operations frequently occur in streaming scenarios, which is caused by two challenges: (i) uncertainty of the clustering frequency; (ii) unpredictable distribution evolution. Hence, it is critical to find a lightweight model that can cluster the high-speed dynamic instances while exploiting the evolution amid different clustering results. This paper focuses on the problem of real-time clustering on streaming data in computation-intensive and high-dynamics tasks, through a framework Ocean, consisting of the Online clustering algorithm and evolution analysis. Particularly, the framework conceives a flexible composite window to augment the knowledge mining, achieving a proper real-time response in various scenarios. The evolution analysis supports full life-cycle detection, improving the adaptability to dynamic concept drifts and multiple patterns. Inspired by the grid partition strategy, this framework adopts grid feature vectors to capture the significant changes in streaming data. Furthermore, we propose an optimization that removes sparse grids timely and performs the online clustering adaptively for space and time efficiency. It is proven to be effective both theoretically and experimentally. This strategy enables real-time clustering for dynamic streaming data without degrading the clustering quality or increasing the computation cost. Experiments on real datasets and synthetic datasets verify the accuracy and effectiveness of Ocean compared to the state-of-the-art approaches, as well as the superior ability to perform clustering in a real-time manner.

Sequential Recommendation (SR) has received increasing attention due to its ability to capture user dynamic preferences. Recently, Contrastive Learning (CL) provides an effective approach for sequential recommendation by learning invariance from different views of an input. However, most existing data or model augmentation methods may destroy semantic sequential interaction characteristics and often rely on the hand-crafted property of their contrastive view-generation strategies. In this paper, we propose a Meta-optimized Seq2Seq Generator and Contrastive Learning (Meta-SGCL) for sequential recommendation, which applies the meta-optimized two-step training strategy to adaptive generate contrastive views. Specifically, Meta-SGCL first introduces a simple yet effective augmentation method called Sequence-to-Sequence (Seq2Seq) generator, which treats the Variational AutoEncoders (VAE) as the view generator and can constitute contrastive views while preserving the original sequence's semantics. Next, the model employs a meta-optimized two-step training strategy, which aims to adaptively generate contrastive views without relying on manually designed view-generation techniques. Finally, we evaluate our proposed method Meta-SGCL using three public real-world datasets. Compared with the state-of-the-art methods, our experimental results demonstrate the effectiveness of our model and the code is available.11https.//anonymous.4open.science/status/Meta-SGCL-05B5

Graph Collaborative Filtering (GCF) is designed to leverage high-order connectivity in user-item graphs, thereby significantly enhancing recommendation performance. Recent advancements have seen the integration of contrastive learning into GCF as a strategy to mitigate the challenges of data sparsity. This approach involves creating contrastive views through augmentations, followed by the generation of self-supervised signals. These signals are produced by maximizing the mutual information between the contrastive views. While this method has proven effective, we argue that current CL-based GCF models are still limited to current augmentation techniques. Existing data augmentation or noise perturbation may destroy the structural and semantic features of the original data and node attribute information is not considered. To tackle the above limitations, we propose a Meta-optimized Structure and Semantic Contrastive Learning for Graph Collaborative Filtering, named Meta-SSCL, which utilizes graph structure information and semantic information contrastive learning for recommendation. Specifically, we first model the structural and node semantic information representations with LightGCN and vanilla attention mechanism, respectively. Then consider the structural and semantic information as two contrastive views for recommendation. Next, the meta-optimized two-step training strategy generates adaptive contrastive views. Finally, we fuse structural and semantic representations for recommendation. Extensive experiments on real-world datasets demonstrate that Meta-SSCL consistently outperforms state-of-the-art sequential recommendation methods. The code is available1.

The constantly increasing scale of graphs leads to higher costs in terms of data storage and computation. Consequently, there is a growing trend of outsourcing and analyzing graphs in clouds. As there is a concern that cloud servers may extract sensitive information from these graphs, the graphs being outsourced must be pre-anonymized, leading to increased space consumption and degraded graph query processing efficiency. Previous work has attempted to address this issue by outsourcing a compacted anonymized graph to the cloud. However, the solution typically focuses on a specific type of query, such as a subgraph query, and cannot adequately accommodate real-life scenarios where multiple applications often work concurrently on the same graph. In this paper, we propose a generic framework called FRESH to handle various graph queries efficiently within a single outsourced graph. To reduce the size of the outsourced graph, we developed a novel graph contraction scheme that transforms a big graph into a compact one while preserving graph privacy. To showcase the adaptability of classical graph query algorithms (e.g., subgraph query, triangle counting, and shortest distance query), we demonstrate their successful execution on the same compact graph created through our contraction scheme. We further extend our framework by incorporating optimizations that significantly improve query processing efficiency. Extensive experimental results demonstrate the superiority of FRESH over traditional techniques.

With the widespread application of intelligent transportation systems and navigation software, traffic prediction should be modeled in finer granularity to facilitate lane-changing guidance and congestion mitigation. However, existing studies divide the road network into continuous segments which assumes different lanes share the same spatio-temporal patterns. This paper proposes a novel lightweight, attention-based, fully convolutional model, named the Spatio-Temporal Attention- Based Convolutional network (ST-ABC), where lane segments are treated as graph nodes and dynamically models the adjacent spatial dependencies using local attention graph convolution. The attention-based dilated convolutions can process longer sequence periods in parallel, and a global attention layer allows individual nodes to be associated with the global context. By setting a target window, it can further reduce unnecessary computations and improve the prediction effect for the targeted area. Further-more, the ST-ABC model facilitates the simultaneous integration of spatio-temporal information and relational distance metrics among lane segments, enriching the granularity of multi-scaled spatial prediction. Empirical evaluations conducted on two real-world datasets substantiate the augmented efficacy of the STABC model in comparison to established models, with a marked prominence in long-term prediction scenarios.

Graph self-supervised learning aiming to learn the graph representation without much label information is an important tasks in data mining and machine learning since labeled graph data is scarce and expensive to obtain in the real world. Contrastive learning emerges as a promising solution. However, we show existing graph contrastive learning (GCL) models have a significant issue: they generate representations that collapse into a low-dimensional subspace, resulting in a loss of information and diversity. We believe this issue arises from the strong assumption in current GCL methods that all positive samples should be close and all negative samples should be far in the representation space. From a data engineering view, this assumption fails to deeply mine the graph data and oversimplifies the complexity and heterogeneity of graph data, leading to clustered and redundant representations. To address this issue, we propose GradGCL, a novel method that leverages intrinsic gradient information as an additional input signal to regularize GCL training. The gradient information reflects the optimization process of the representations with respect to the contrastive loss, providing a complementary perspective to the representations. Furthermore, we have designed a soft separation strategy that relaxes the hard separation strategy between positive and negative samples, allowing for more flexibility and diversity in the representation space. We have conducted extensive experiments on various graph-related tasks, using different types of contrastive losses, datasets, and model architectures. We demonstrate that gradients alone can learn graph information and achieve competitive results with representation-based GCL methods. We also show that GradGCL can enhance existing GCL models and prevent the issue of dimensional collapse.

Recently, graph contrastive learning proposes to learn node representations from the unlabeled graph to alleviate the heavy reliance on node labels in graph neural networks (GNNs). The core idea is to generate diverse positive views and negative views according to local subgraphs. Then, GNNs take these views as supervised signals and train the model by maximizing the similarity between positive view pairs of each node and minimizing the similarity between positive and negative views. Regardless of the fruitful progress, existing graph contrastive learning approaches still suffer from low-efficiency, insufficient-expressivity, and unpreserved-locality issues. First, they train GNNs by all nodes, reducing the efficiency due to similar and redundant nodes. Second, they only use limited operations (e.g., edge deletion and feature masking) to generate positive views, thereby restricting their expressivity. Third, they uniformly delete edges and mask node features and may modify important edges and features, thereby damaging the important locality information of nodes. In this paper, we propose an efficient and expressive contrastive learning framework for GNNs, namely E2GCL. Specifically, given a limited node budget, we select a set of representative nodes instead of all nodes to accelerate the GNNs training. Besides, we use three general operations (edge deletion, edge addition, and feature perturbation) to generate expressive and locality-preserved positive views based on edge and feature importance. Extensive experiments on various real-world datasets demonstrate the superior effectiveness and efficiency of our proposed E2GCL.

ID-based Recommender Systems (RecSys), where each item is assigned a unique identifier and subsequently converted into an embedding vector, have dominated the de-signing of RecSys. Though prevalent, such ID-based paradigm is not suitable for developing transferable RecSys and is also susceptible to the cold -start issue. In this paper, we unleash the boundaries of the ID- based paradigm and propose a Pure Multi-Modality based Recommender system (PMMRec), which relies solely on the multi-modal contents of the items (e.g., texts and images) and learns transition patterns general enough to transfer across domains and platforms. Specifically, we design a plug-and-play framework architecture consisting of multi-modal item encoders, a fusion module, and a user encoder. To align the cross-modal item representations, we propose a novel next-item enhanced cross-modal contrastive learning objective, which is equipped with both inter- and intra-modality negative samples and explicitly incorporates the transition patterns of user behaviors into the item encoders. To ensure the robustness of user representations, we propose a novel noised item detection objective and a robustness-aware contrastive learning objective, which work together to denoise user sequences in a self-supervised manner. PMMRec is designed to be loosely coupled, so after being pre-trained on the source data, each component can be transferred alone, or in conjunction with other components, allowing PMMRec to achieve versatility under both multi-modality and single-modality transfer learning settings. Extensive experiments on 4 sources and 10 target datasets demonstrate that PMMRec surpasses the state-of-the-art recommenders in both recommendation performance and transferability. Our code and dataset is available at: https://github.com/ICDE24IPMMRec.

Recently, continual learning (CL) has attracted much attention due to its widespread applications in the real world. Given a set of data sets sequentially, continual learning aims to achieve good performance on the new data sets while avoiding deterioration in performance on the old data sets. Despite the success, most CL models follow the supervised setting, which limits their potential in data scarcity cases. Thus, some pioneering works study unsupervised CL (UCL) to discuss what CL tricks suit the unsupervised setting. However, their advancements lack in-depth analysis of the characteristics of UCL, especially the lack of attention to the use of old data. We identify that using old data sets is essential for improving the UCL model performance while existing works ignore them. Unfortunately, given a limited data storage budget, it is a nontrivial task to select representative data and effectively replay them without label assistance. To further improve the UCL performance, we present a new method in this paper, named Effective Data Selection and Replay (EDSR) for UCL. Specifi-cally, we analyze that entropy can be an effective data selection metric, where representative data usually exhibit the highest entropy in the representation space. Then, to balance the model stability for old data and the plasticity for new data, we adopt a strategy of replaying those stored representative data with a noise-enhanced knowledge distillation process. The empirical study demonstrates the outstanding performance of EDSR on benchmark computer vision data sets. Especially, EDSR shows strong resistance to forgetting old data knowledge while maintaining high accuracy. The implementation is publicly available at https://github.com/LeeJarvis996/edsr_project/tree/main/EDSR.

The Constrained Shortest Path (CSP) problem seeks to identify the shortest path between two vertices in a road network while adhering to a specific constraint on another criterion. Solving the CSP problem frequently entails navigating the two-criteria skyline path problem, which incurs a substantial computational expense in large road networks. The primary challenge lies in handling a vast quantity of partial skyline paths, which often hinders index-based solutions from accurately determining the skyline paths. This paper introduces a-FHL, a practical approximation method designed to circumvent the costly skyline path search and hasten computation on skyline path indexing. a-FHL uses tree decomposition to hierarchically assign approximation ratios, thereby facilitating effective pruning within the labelling index. Moreover, we devise various strategies to allocate approximation ratios and an efficient approximation concatenation method to respond to the approximate CSP queries via the a-FHL index. Our method culminates in swift index construction and efficient query response. Comprehensive exper-iments conducted on real-world road networks substantiate the superiority of our approach over contemporary solutions

We devise a neural network-based temporal-textual framework that generates subgraphs with highly correlated authors from short-text contents. Our approach computes the relevance score (edge weight) between authors by considering a portmanteau of contents and concepts. It then employs a stack-wise graph-cutting algorithm to extract communities of related authors. Experimental results show that our multi-aspect vector space model can gain higher performance than other knowledge-centered competitors in linking short-text authors.

We devise a neural network-based temporal-textual framework that generates subgraphs with highly correlated authors from short-text contents. Our approach computes the relevance score (edge weight) between authors by considering a portmanteau of contents and concepts. It then employs a stack-wise graph-cutting algorithm to extract communities of related authors. Experimental results show that our multi-aspect vector space model can gain higher performance than other knowledge-centered competitors in linking short-text authors.

Addressing the challenge of matching queries with the right experts amid temporal-textual inconsistencies, we present a novel approach that combines an attention-based text embedding model with a continuous-time module. This method effectively maps queries to relevant experts by analyzing concept-oriented vectors and user behavior, demonstrating significant effectiveness on StackOverflow and Yahoo datasets.

Recently, graph neural networks (GNNs) have shown its unprecedented success in many graph-related tasks. However, GNNs face the label scarcity issue as other neural networks do. Thus, recent efforts try to pre-train GNNs on a large-scale unlabeled graph and adapt the knowledge from the unlabeled graph to the target downstream task. The adaptation is generally achieved by fine-tuning the pre-trained GNNs with a limited number of labeled data. However, current GNNs pre-training works focus more on how to better pre-train a GNN, but ignore the importance of fine-tuning to better leverage the transferred knowledge. Only a few works start to investigate a better fine-tuning strategy for pre-trained GNNs. But their designs either have strong assumptions or overlook the data-aware issue behind various downstream domains. To further boost pre-trained GNNs, we propose to search to fine-tune pre-trained GNNs for graph-level tasks (S2PGNN), which can adaptively design a suitable fine-tuning framework for the given pre-trained GNN and downstream data. Unfortunately, it is a non-trivial task to achieve this goal due to two technical challenges. First is the hardness of fine-tuning space design since there lack a systematic and unified exploration in existing literature. Second is the enormous computational overhead required for discovering suitable fine-tuning strategies from the discrete space. To tackle these challenges, S2PGNN first carefully summarizes a search space of fine-tuning strategies that is suitable for GNNs, which is expressive enough to enable powerful strategies to be searched. Then, S2PGNN integrates an efficient search algorithm to solve the computationally expensive search problem from a discrete and large space. The empirical studies show that S2PGNN can be implemented on the top of 10 famous pre-trained GNNs and consistently improve their performance by 9 % to 17 %. Our code is publicly available at https://github.com/zwangeo/icde2024.

Route planning and navigation systems have played an increasingly important role in our society and have a growing impact on transportation systems. The current system takes the traffic prediction as input and optimizes the routes individually. However, such a paradigm could generate congestion and deteriorate traffic conditions because the routing algorithms are not aware of their results' influence on the traffic flow. Therefore, in this paper, we identify this flaw in the current paradigm and propose a route data management system to evaluate the influence of the routing results and help improve future downstream tasks. Specifically, we first formulate traffic evaluation as a clear traffic-aware network time calibration problem and propose a simulation-based method to evaluate hundreds of thousands of routes efficiently. To support route updates on the evaluation results, we propose an RR-Index to support high throughput of route insertion, deletion, and temporal update. After that, we propose several techniques like influence terminate condition, propagation merge and ordering, and parallel processing to make it efficient enough to work in real life. Evaluations on real-world road networks verify the necessity, effectiveness, and efficiency of our methods.

Trust plays an essential role in an individual's decision-making. Traditional trust prediction models rely on pairwise correlations to infer potential relationships between users. However, in the real world, interactions between users are usually complicated rather than pairwise only. Hypergraphs offer a flexible approach to modeling these complex high-order correlations (not just pairwise connections), since hypergraphs can leverage hyperedeges to link more than two nodes. However, most hypergraph-based methods are generic and cannot be well applied to the trust prediction task. In this paper, we propose an Adaptive Hypergraph Network for Trust Prediction (AHNTP), a novel approach that improves trust prediction accuracy by using higher-order correlations. AHNTP utilizes Motif-based PageRank to capture high-order social influence information. In addition, it constructs hypergroups from both node-level and structure-level attributes to incorporate complex correlation information. Furthermore, AHNTP leverages adaptive hypergraph Graph Convolutional Network (GCN) layers and multilayer perceptrons (MLPs) to generate comprehensive user embeddings, facilitating trust relationship prediction. To enhance model generalization and robustness, we introduce a novel supervised contrastive learning loss for optimization. Extensive experiments demonstrate the superiority of our model over the state-of-the-art approaches in terms of trust prediction accuracy.

Owing to the nature of privacy protection, feder-ated recommender systems (FedRecs) have garnered increasing interest in the realm of on-device recommender systems. However, most existing FedRecs only allow participating clients to collaboratively train a recommendation model of the same public parameter size. Training a model of the same size for all clients can lead to suboptimal performance since clients possess varying resources. For example, clients with limited training data may prefer to train a smaller recommendation model to avoid excessive data consumption, while clients with sufficient data would benefit from a larger model to achieve higher recommendation accuracy. To address the above challenge, this paper introduces HeteFedRec, a novel FedRec framework that enables the assignment of personalized model sizes to partici-pants. Specifically, we present a heterogeneous recommendation model aggregation strategy, including a unified dual-task learning mechanism and a dimensional decorrelation regularization, to allow knowledge aggregation among recommender models of different sizes. Additionally, a relation-based ensemble knowledge distillation method is proposed to effectively distil knowledge from heterogeneous item embeddings. Extensive experiments conducted on three real-world recommendation datasets demonstrate the effectiveness and efficiency of HeteFedRec in training federated recommender systems under heterogeneous settings.

Extracting entities and relations from text is a significant task of information extraction. Existing extraction models often straightforwardly produce their confident prediction results without any reconsideration or double-checking, resulting in avoidable mistakes and sub-optimal performance. In this paper, we propose a novel coarse-to-fine extraction framework, which first extracts high-potential relations as well as entities via knowledge distillation, and then rechecks the predictions via handcrafted natural language inference (NLI) task in a fine-grained manner. Specifically, based on the knowledge distillation mechanism, we train multiple teacher models iteratively through an adaptive loss function for making one teacher concentrate more on the data that others are incompetent for. Then, these complementary teacher models are utilized to provide valuable soft-label information for training a considerate student model, enabling it to generate reliable preliminary predictions. Further, these generated potential relations and entities are formulated as hypotheses, together with the original sentences as premises, serving as the input for an NLI model. Considering the linguistic diversity of relational expression, we automatically generate various semantic templates for hypotheses through an$\mathcal{N}$-gram mining strategy. Moreover, due to the existence of multi-fact sentences, a relation-guided Gaussian attention is designed to reduce the gap between the single-relation hypothesis and the multi-relation premise. To implement efficient training, we also develop several ways to generate high-quality negative samples, which help the NLI model learn to identify errors. Experimental results show that the proposed method is effective and outperforms other strong baselines on public benchmarks.

In this paper, we revisit the problem of the current routing system in terms of prediction scalability and routing result optimality. Specifically, the current traffic prediction models are not suitable for large urban networks due to the incomplete information of traffic conditions. Besides, existing routing systems can only plan the routes based on the past traffic conditions and struggle to update the optimal route for vehicles in real-time. As a result, the actual route taken by vehicles is different from the ground-truth optimal path. Therefore, we propose a Just-In-Time Predictive Route Planning framework to tackle these two problems. Firstly, we propose a Travel Time Constrained Top-$k^{n}$Shortest Path algorithm which pre-computes a set of candidate paths with several switch points. This empowers vehicles to continuously have the opportunity to switch to better paths taking into account real-time traffic condition changes. Moreover, we present a query-driven prediction paradigm with ellipse-based searching space estimation, along with an efficient multi-queries handling mechanism. This not only allows for targeted traffic prediction by prioritizing regions with valuable yet outdated traffic information, but also provides optimal results for multiple queries based on real-time traffic evolution. Evaluations on two real-life road networks demonstrate the effectiveness and efficiency of our framework and methods.

Deep reinforcement learning (RL) has emerged as a promising approach for portfolio management due to its ability to make sequential decisions. However, applying RL techniques to this domain is still challenging due to the non-stationary nature of financial markets. Existing RL-based solutions fail to consider the intrinsic causes behind this non-stationary, which primarily stem from the involvement of diverse traders with distinct investment horizons and their varied investment strategies. In this paper, we tackle the non-stationary problem by examining its intrinsic causes and propose cross-insight trader, a novel two-step RL-based approach that integrates multiple trading policies with different investment horizons to adapt to the changing market conditions. In the first step, we learn multiple horizon-specific policies by providing each policy with tailored information specific to its investment horizon. This allows each policy to recognize dynamic patterns within its respective horizon and make insightful pre-decisions. In the second step, we learn a cross-insight policy to make the final trade decision by considering the investment pre-decisions made by multiple horizon-specific policies in the first step. To enable effective learning of two types of policies, our approach employs a centralized critic to evaluate the actions performed by both horizon-specific and cross-insight policies. By incorporating multiple insights from different investment horizons into the decision-making process, our approach enhances its adaptability to changing market conditions. Experimental results conducted on three stock markets demonstrate the superiority of our framework.

Shortest path computation is a fundamental operation of many applications in small-world networks, and shortest path index has been extensively studied to achieve high query efficiency. However, small-world networks evolve continuously in real life, and their graph size expands rapidly, necessitating the investigation of efficient shortest path index maintenance and construction for large dynamic graphs. In this paper, we adopt the Core-Tree index, which has exceptional scalability while preserving high query efficiency, as the underlying shortest path index, and put forward efficient algorithms to maintain and construct it for large dynamic small-world networks. Specifically, we first propose update propagation mechanisms for our Dynamic Core-Tree (DCT) algorithm, based on which the global tree index strategy is designed for efficient query processing. Moreover, for the core index, we propose a Propagation-based Dynamic PLL incorporating coarse update and refined update phases to ensure correct and efficient index maintenance. To enhance update efficiency and scalability for the core index, we also propose novel Parallel Canonical 2-hop Labeling (PCL) and Batch PCL (BPCL) to efficiently generate minimal canonical labels and pruning point records. Experimental studies on large real-world datasets demonstrate the superiority of our methods over the state-of-the-art in terms of indexing, updating, and scalability.

In this paper, we address the challenges of data augmentation in Multi-Modal Knowledge Graphs (MMKGs), a relatively under-explored area. We propose a novel diffusion-based generative model, the Simple Denoising Probabilistic Latent Diffusion Model (SimDiff). SimDiff is capable of handling different data modalities including the graph topology in a unified manner by the same diffusion model in the latent space. It enhances the utilization of multi-modal data and encourage the multi-modal fusion and reduces the dependency on limited training data. We validate our method in downstream Entity Alignment (EA) tasks in MMKGs, demonstrating that even when using only half of the seed entities in training, our methods can still achieve superior performance. This work contributes to the field by providing a new data generation or augmentation method for MMKGs, potentially paving the way for more effective use of MMKGs in various applications. Code is made available at https://github.com/ranlislz/SimDiff.

Graph neural networks (GNNs) have achieved great success on various graph tasks. However, recent studies have revealed that GNNs are vulnerable to injective attacks. Due to the openness of platforms, attackers can inject malicious nodes with carefully designed edges and node features, making GNNs misclassify the labels of target nodes. To resist such adversarial attacks, recent researchers propose GNN defenders. They assume that the attack patterns have been known, e.g., attackers tend to add edges between dissimilar nodes. Then, they remove edges between dissimilar nodes from attacked graphs, aiming to alleviate the negative impact of adversarial attacks. Nevertheless, on dynamic graphs, attackers can change their attack strategies at different times, making existing passive GNN defenders that are passively designed for specific attack patterns fail to resist attacks. In this paper, we propose a novel active GNN defender for dynamic graphs, namely ADGNN, which actively injects guardian nodes to protect target nodes from effective attacks. Specifically, we first formulate an active defense objective to design guardian node behaviors. This objective targets to disrupt the prediction of attackers and protect easily attacked nodes, thereby preventing attackers from generating effective attacks. Then, we propose a gradient-based algorithm with two acceleration techniques to optimize this objective. Extensive experiments on four real-world graph datasets demonstrate the effectiveness of our proposed defender and its capacity to enhance existing GNN defenders.

Sequential Recommendation (SR) methods play a crucial role in recommender systems, which aims to capture users' dynamic interest from their historical interactions. Recently, Contrastive Learning (CL), which has emerged as a successful method for sequential recommendation, utilizes various data augmentations to generate contrastive views to mine supervised signals from data to alleviate data sparsity issues. However, most existing sequential data augmentation methods may destroy semantic sequential interaction characteristics. Meanwhile, they often adopt random operations when generating contrastive views leading to suboptimal performance. To this end, in this paper, we propose a Learnable Model Augmentation Contrastive learning for sequential Recommendation (LMA4Rec). Specifically, LMA4Rec first takes the model-based augmentation method to generate constructive views. Then, LMA4Rec uses Learnable Bernoulli Dropout (LBD) to implement learnable model augmentation operations. Next, contrastive learning is used between the contrastive views to extract supervised signals. Furthermore, a novel multi-positive contrastive learning loss alleviates the supervised sparsity issue. Finally, experiments on public datasets show that our LMA4Rec method effectively improved sequential recommendation performance compared with the state-of-the-art baseline methods.

With an exponentially growing number of graphs from disparate repositories, there is a strong need to analyze a graph database containing an extensive collection of small- or medium-sized data graphs (eg chemical compounds). Although subgraph enumeration and subgraph mining have been proposed to bring insights into a graph database by a set of subgraph structures, they often end up with similar or homogenous topologies, which is undesirable in many graph applications. To address this limitation, we propose theTop-k Edge-Diversified Patterns Discovery problemto retrieve a set of subgraphs that cover the maximum number of edges in a database. To efficiently process such query, we present a generic and extensible framework called$\textsc {Ted}^+$which achieves a guaranteed approximation ratio to the optimal result. Three optimization strategies are further developed to improve the performance, and a lightweight version calledTedLiteis designed for even larger graph databases. Experimental studies on real-world datasets demonstrate the superiority of$\textsc {Ted}^+$to traditional techniques.

The protocols that satisfy Local Differential Privacy (LDP) enable untrusted third parties to collect aggregate information about a population without disclosing each user's privacy. In particular, each user locally encodes and perturbs his private data before sending it to the data collector, who aggregates and estimates the statistics about the population based on the collected perturbed values from individuals. Owing to their growing importance, LDP protocols have been widely studied and deployed in real-world scenarios (eg Chrome and Windows). However, as data poisoning attacks may be injected by attackers who introduce many fake users, the utility of the statistics is heavily poisoned. In this paper, we present a generic and extensible framework called LDPGuard to address the problem. LDPGuard provides effective defenses against data poisoning attacks to LDP protocols for frequency estimation, a basic query of most data analytics tasks. In particular, it first precisely estimates the percentage of fake users and then provides adversarial schemes to defend against particular data poisoning attacks. Experimental study on real-world and synthetic datasets demonstrates the superiority of LDPGuard compared to existing techniques.

The uniqueness of trajectory data for user re-identification has received unprecedented attention as the increasing popularity of location-based services boosts the excessive collection of daily trajectories with sufficient spatiotemporal coverage. Consequently, leveraging or releasing personally-sensitive trajectories without proper protection severely threatens individual privacy despite simply removing IDs. Trajectory privacy protection is never a trivial task due to the trade-off between privacy protection, utility preservation, and computational efficiency. Furthermore,recovery attack, one of the most threatening attacks specific to trajectory data, has not been well studied in the current literature. To tackle these challenges, we propose a frequency-based randomization model with a rigorous differential privacy guarantee for privacy-preserving trajectory data publishing. In particular, two randomized mechanisms are introduced for perturbing the local/global frequency distributions of a limited number of significantly essential locations in trajectories by injecting special Laplace noises. To reflect the perturbed distributions on the trajectory level without losing privacy guarantee or data utility, we formulate the trajectory modification tasks as kNN search problems and design two hierarchical indices with powerful pruning strategies and a novel search algorithm to support efficient modification. Extensive experiments on a real-world dataset verify the effectiveness of our approaches in resisting individual re-identification and recovery attacks simultaneously while still preserving desirable data utility. The efficient performance on large-scale data demonstrates the feasibility and scalability in practice.

Automation in road vehicles is an emerging technology that has developed rapidly over the last decade. There have been many inter-disciplinary challenges posed on existing transportation infrastructure by autonomous vehicles. In this paper, we conduct an algorithmic study on when and how an autonomous vehicle should change its lane, which is a fundamental problem in vehicle automation field and root cause of most ‘phantom’ traffic jams. We propose a prediction-and-decision framework, called Cheetah (Changelanesmartforautonomous vehicle), which aims to optimize the lane changing maneuvers of autonomous vehicle while minimizing its impact on surrounding vehicles. In the prediction phase, Cheetah learns the spatio-temporal dynamics from historical trajectories of surrounding vehicles with a deep model (GAS-LED model) and predict their corresponding actions in the near future. A global attention mechanism and state sharing strategy are also incorporated to achieve higher accuracy and better convergence efficiency. Then in the decision phase, Cheetah looks for optimal lane change maneuvers for the autonomous vehicle by taking into account a few factors such as speed, impact on other vehicles and safety issues. A tree-based adaptive beam search algorithm is designed to reduce the search space and improve accuracy. In order to make our framework applicable to more scenarios, we further propose an improved Cheetah (Cheetah+) framework that makes the autonomous vehicle adapt for exiting a road and meet the requirement for driving comfort. Extensive experiments offer evidence that the proposed framework can advance the state of the art in terms of effectiveness and efficiency.

Uncertainty is an essential consideration for time series forecasting tasks. In this work, we focus on quantifying the uncertainty of traffic forecasting from a unified perspective. We develop a novel traffic forecasting framework, namely Deep Spatio-Temporal Uncertainty Quantification (DeepSTUQ), which can estimate both aleatoric and epistemic uncertainty. Specifically, we first leverage a spatio-temporal model to model the complex spatio-temporal correlations of traffic data. Subsequently, two independent sub-neural networks maximizing the heterogeneous log-likelihood are developed to estimate aleatoric uncertainty. To estimate epistemic uncertainty, we combine the merits of variational inference and deep ensembling by integrating the Monte Carlo dropout and the Adaptive Weight Averaging re-training methods, respectively. Furthermore, to relax the Gaussianity assumption, mitigate overfitting, and improve horizon-wise uncertainty quantification performance, we define a new calibration method called Multi-horizon Conformal Calibration (MHCC). Finally, we provide a theoretical analysis of the proposed unified approach based on the PAC-Bayes theory. Extensive experiments are conducted on four public datasets, and the empirical results suggest that the proposed method outperforms state-of-the-art methods in terms of both point prediction and uncertainty quantification.

Embodied AI is one of the most popular studies in artificial intelligence and robotics, which can effectively improve the intelligence of real-world agents (i.e. robots) serving human beings. Scene knowledge is important for an agent to understand the surroundings and make correct decisions in the varied open world. Currently, knowledge base for embodied tasks is missing and most existing work use general knowledge base or pre-trained models to enhance the intelligence of an agent. For conventional knowledge base, it is sparse, insufficient in capacity and cost in data collection. For pre-trained models, they face the uncertainty of knowledge and hard maintenance. To overcome the challenges of scene knowledge, we propose a scene-driven multimodal knowledge graph (Scene-MMKG) construction method combining conventional knowledge engineering and large language models. A unified scene knowledge injection framework is introduced for knowledge representation. To evaluate the advantages of our proposed method, we instantiate Scene-MMKG considering typical indoor robotic functionalities (Manipulation andMobility), namedManipMob-MMKG. Comparisons in characteristics indicate our instantiated ManipMob-MMKG has broad superiority on data-collection efficiency and knowledge quality. Experimental results on typical embodied tasks show that knowledge-enhanced methods using our instantiated ManipMob-MMKG can improve the performance obviously without re-designing model structures complexly.

Locality-sensitive hashing (LSH) is a promising family of methods for the high-dimensional approximate nearest neighbor (ANN) search problem due to its sub-linear query time and strong theoretical guarantee. Existing LSH methods either suffer from large index sizes and hash boundary problems, or incur a linear cost for high-quality candidate identification. This dilemma is addressed in a novel method called DB-LSH proposed in this paper. It organizes the projected spaces with multi-dimensional indexes instead of fixed-width hash buckets, which significantly reduces space costs. High-quality candidates can be generated efficiently by dynamically constructing query-based hypercubic buckets with the required widths through index-based window queries. A novel incremental search strategy called DBI-LSH is also developed to further boost the query performance, which incrementally accesses the next best point for higher accuracy and efficiency. Considering the intermediate query information of each query, DBA-LSH is designed to adaptively tune termination conditions without scarifying the success probability. Our theoretical analysis proves that DB-LSH has a smaller query cost than the existing work while DBA-LSH and DBI-LSH have lower expected query costs than DB-LSH. An extensive range of experiments on real-world data show the superiority of our approaches over the state-of-the-art methods in both efficiency and accuracy.

Travel planning plays an increasingly important role in our society. The travel plans, which consist of the paths each vehicle is suggested to follow and its corresponding departure time, influence the traffic conditions naturally. However, existing travel planning algorithms cannot consider the planning results and their influences simultaneously, so traffic congestion could be created when many vehicles are directed to adopt similar travel plans. In this paper, we propose theGlobal Optimal Travel Planning (GOTP)problem that aims to minimize traffic congestion by continuously evaluating traffic conditions for a set of planning tasks. Achieving this global optimization goal is non-trivial because travel planning and traffic evaluation are time-consuming and interdependent. To break this dependency, we first propose aGOTPparadigm that interleaves travel planning and traffic evaluation for queries, where the planning consists of departure time planning and travel path planning. To implement the paradigm, we propose theserial modelthat optimizes travel plans one by one, followed by thebatch modelthat improves processing efficiency, and theiterative modelthat further optimizes planning quality. Extensive experiments on large real-world networks with synthetic and real workloads validate the effectiveness and efficiency of our methods.

Document-level Relation Extraction (RE) is a promising task aiming at identifying relations of multiple entity pairs in a document. Compared with the sentence-level counterpart, it has raised two significant challenges: a) In most cases, a relational fact can be adequately expressed via a small subset of sentences from the document, namely evidence. But the traditional method cannot model such strong semantic correlations between evidence sentences that collaborate to describe a specific relation; b) The data of this task is extremely long-tail in terms of too many NA instances and imbalanced relational types. Such data can mislead the tail prediction bias to the head categories in the RE model. In this paper, we present a novelEvidence reasoning andCurriculum learning method forDocRE(DRE-EC) to address these challenges. Particularly, we first formulate evidence extraction as a sequential decision problem through a crafted reinforcement learning mechanism with an efficient path searching strategy to reduce the action space. Providing the evidence for each entity pair as a customized-filtered document in advance helps infer the relations better. To address the long-tail issue, we further develop a hybrid curriculum learning method at the NA-level (NC) and relation-level (RC) with our customized difficulty measure score. In NC, the NA samples are scheduled in an easy-to-hard scheme and gradually added, resulting in the data distribution from ideal and balanced to real and unbalanced. In RC, the scheme is switched into hard-to-easy to enhance the hard and tail samples. In addition, we propose a new Equalization adaptive Focal Loss(EFLoss) that can adjust to the changing data distribution and focus more on the tail categories. We conduct various experiments on two document-level RE benchmarks and achieve a remarkable improvement over previous competitive baselines. Furthermore, we provide detailed analyses of the advantages and effectiveness of our method.

Recent years have witnessed a revolution in Spatial Crowdsourcing (SC), in which people with mobile connectivity can perform spatio-temporal tasks that involve traveling to specified locations. In this paper, we identify and study in depth a new multi-center-based task allocation problem in the context of SC, where multiple allocation centers exist. In particular, we aim to maximize the total number of the allocated tasks while minimizing the allocated task number difference. To solve the problem, we propose a two-phase framework, called Task Allocation with Geographic Partition, consisting of a geographic partition and a task allocation phase. The first phase divides the whole study area based on the allocation centers by using both a basic Voronoi diagram-based algorithm and an adaptive weighted Voronoi diagram-based algorithm. In the allocation phase, we utilize a Reinforcement Learning method to achieve the task allocation, where a graph neural network with the attention mechanism is used to learn the embeddings of allocation centers, delivery points, and workers. To further improve the efficiency, we propose an early stopping optimization strategy for the adaptive weighted Voronoi diagram-based algorithm in the geographic partition phase and give a distance-constrained graph pruning strategy for the Reinforcement Learning method in the task allocation phase. Extensive experiments give insight into the effectiveness and efficiency of the proposed solutions.

Spatial trajectory prediction is a fundamental problem for diverse location-based applications. However, existing methods fall short in learning and generalization, and cannot sufficiently capture users’ spatiotemporal preferences, especially for cold-start users. Moreover, these methods do not explicitly consider the diversity of moving patterns among users and trajectories, i.e., the learning difficulty of different user and trajectory samples, thus hindering the improvement of prediction accuracy. To solve these problems, we propose a novel Curriculum and Contrastive Learning Enhanced Meta-Learner (CCML) that transfers knowledge from users with rich data to cold-start users. Specifically, a Contrastive-based Trajectory Predictor (CTP) is designed as the base model, which utilizes contrastive learning technique on both user-level and trajectory-level, aiming to facilitate a more profound understanding and differentiation of the varied travel behaviors and preferences exhibited by individuals. Meanwhile, CCML also incorporates the curriculum learning and the hard sample mining strategies. It simultaneously considers the learning difficulty of both user and trajectory samples, and presents the learning tasks by an easy-to-hard curriculum. By learning more challenging combinations of user and trajectory samples in each meta-learning iteration, the meta-learner can converge to a better status. Extensive experiments on two real-world datasets demonstrate the superiority of our models.

Making accurate and safe clinical decisions for patients has long been a challenging task. With the proliferation of electronic health records and the rapid advancement of technology, drug recommender systems have emerged as invaluable aids for healthcare professionals, offering precise and secure prescriptions. Among prevailing methods, the exploration of motifs, defined as substructures with specific biological functions, has largely been overlooked. Nevertheless, the substantial impact of the motifs on drug efficacy and patient diseases implies that a more extensive incorporation could potentially improve the recommender systems. In light of this, we introduceDEPOT, an innovative drug recommendation framework developed from a motif-aware perspective. In our approach, we employ chemical decomposition to partition drug molecules into semantic motif-trees and design a structure-aware graph transformer to capture motif collaboration. This innovative practice preserves the topology knowledge and facilitates perception of drug functionality. To delve into the dynamic correlation between motifs and disease progression, we conduct a meticulous investigation from two perspectives: repetition and exploration. This comprehensive analysis allows us to gain valuable insights into the drug turnover, with the former focusing on reusability and the latter on discovering new requirements. We further formulate a historical weighting strategy for drug-drug interaction (DDI) objective, enabling adaptive control over the trade-off between accuracy and safety criteria throughout the training process. Extensive experiments conducted on four data sets validate the effectiveness and robustness ofDEPOT.

Anomaly detection is one of the most significant tasks in multivariate time series analysis, while it remains challenging to model complex patterns for improving detection accuracy and to interpret the root causes of anomalies. However, existing studies either consider only the temporal dependencies, or simply reconstruct the original input for detection, both neglecting the hidden relationships among multivariate. We propose an adversarial graph neural network based anomaly detection model, called SGAT-AE, which consists of aSelf-learningGraphATtention network (SGAT), anAuto-Encoder (AE), and an adversarial training component. Specifically, SGAT is a prediction model that discovers the graph dependency relationships among multivariate and acts as a sample generator to confuse AE, while AE reconstructs the samples and acts as a discriminator that distinguishes a real sample from a generated one. A novel adversarial training between SGAT and AE is applied to amplify the errors of anomalies such that the prediction performance of SGAT is improved and the overfitting of AE is avoided. In addition, we aggregate the prediction error, the reconstruction error, and the adversarial error for anomaly detection, and develop a graph based anomaly interpretation method that locates the root causes from both local and global perspectives. Extensive experiments with five real-world data offer evidence that the proposed solution SGAT-AE is capable of achieving better performance when compared with the state-of-the-art proposals.

Shortest path computation is a basic operation for many graph-based applications and has been extensively studied. However, most existing works only consider the optimal path of a single criterion but ignore real-world situations involving multiple criteria. This paper investigates a new Multi-Criteria Shortest Paths (MCSPs) problem, aiming to compute the shortest paths of all criteria between a vertex pair. It is significant for real-world applications such as GPS navigation and social network analysis. Nevertheless, the rapid growth of graph size or memory-limited devices poses a memory-constraint challenge, making the adaptation of existing methods extremely time-consuming. To solve the memory-constraint MCSPs problem, we propose a generalSTOP & SHAREscheme to synchronize the search speeds of all criteria for sharing partition accesses. Two algorithms calledOHPandMHP, adopting the one-hop strategy and partition exhaustive strategy, respectively, are proposed for implementing our scheme. Moreover, we develop two optimized algorithms,BMHPandBMHPS, to improve query efficiency by combiningMHPwith the bidirectional technique and a novelin-partition shortcut optimization. We also investigatepartition-oriented I/O management. Experimental studies on large real-world graphs demonstrate the effectiveness of the proposed methods over the multi-pass adaptations of the existing methods.

Abstract With the widespread use of networked and geo-positioned mobile devices, e.g., smartphones, Spatial Crowdsourcing (SC), which refers to the assignment of location-based tasks to moving workers, is drawing increasing attention. One of the critical issues in SC is task assignment that allocates tasks to appropriate workers. We propose and study a novel SC problem, namely Coalition-based Task Assignment (CTA), where the spatial tasks (e.g., home improvement and furniture installation) may require more than one worker (forming a coalition) to cooperate to maximize the overall rewards of workers. We design a greedy and an equilibrium-based CTA approach. The greedy approach forms a set of worker coalitions greedily for performing tasks and uses an acceptance probability to identify high-value task assignments. In the equilibrium-based approach, workers form coalitions in sequence and update their strategies (i.e., selecting a best-response task), to maximize their own utility (i.e., the reward of the coalition they belong to) until a Nash equilibrium is reached. Since the equilibrium obtained is not unique and optimal in terms of total rewards, we further propose a simulated annealing scheme to find a better Nash equilibrium. To achieve fair task assignments, we optimize the framework to distribute rewards fairly among workers in a coalition based on their marginal contributions and give workers who arrive first at the SC platform highest priority. Extensive experiments demonstrate the efficiency and effectiveness of the proposed methods on real and synthetic data.

The pervasiveness of GPS-enabled devices and wireless communication technologies results in a proliferation of traffic data in intelligent transportation systems, where traffic prediction is often essential to enable reliability and safety. Many recent studies target traffic prediction using deep learning techniques. They model spatio-temporal dependencies among traffic states by deep learning and achieve good overall performance. However, existing studies ignore the bias on traffic prediction models, which refers to non-uniformed performance distribution across road segments, especially the significantly poor prediction results on certain road segments. To solve this issue, we propose a framework named spatio-temporal mixture-of-experts (ST-MoE) that aims to eliminate the bias on traffic prediction. In general, we refer to any traffic prediction model as the based model, and adopt the proposed ST-MoE framework as a plug-in to debias. ST-MoE uses stacked convolution-based networks to learn spatio-temporal representations of individual patterns of road segments and then adaptively assigns appropriate expert layers (sub-networks) to different patterns through a spatio-temporal gating network. To this end, the patterns can be distinguished, and biased performance among road segments can be eliminated by experts tailored for specific patterns, which also further improves the overall prediction accuracy of the base model. Extensive experimental results on various base models and real-world datasets prove the effectiveness of ST-MoE.

Traffic prediction has drawn increasing attention due to its essential role in smart city applications. To achieve precise predictions, a large number of approaches have been proposed to model spatial dependencies and temporal dynamics. Despite their superior performance, most existing studies focus datasets that are usually in large geographic scales, e.g., citywide, while ignoring the results on specific regions. However, in many scenarios, for example, route planning on time-dependent road networks, only small regions are of interest. We name the task of answering forecasting requests from any query region of interest (ROI) as ROI-demand traffic prediction (RTP). In this paper, we make a primary observation that existing methods fail to jointly achieve effectiveness and efficiency for RTP. To address this issue, a novel model-agnostic framework based on pre-Training, Querying and fine-Tuning, named TQT, is proposed, which first customizes input data given an ROI, and then makes fast adaptation from pre-trained traffic prediction backbone models by fine-tuning. We evaluate TQT on two real-world traffic datasets, performing both flow and speed prediction tasks. Extensive experiment results demonstrate the effectiveness and efficiency of the proposed method.

Sequential recommendation (SR) aims to model user preferences by capturing behavior patterns from their item historical interaction data. Most existing methods model user preference in the time domain, omitting the fact that users’ behaviors are also influenced by various frequency patterns that are difficult to separate in the entangled chronological items. However, few attempts have been made to train SR in the frequency domain, and it is still unclear how to use the frequency components to learn an appropriate representation for the user. To solve this problem, we shift the viewpoint to the frequency domain and propose a novel Contrastive Enhanced SLIde Filter MixEr for Sequential Recommendation, named SLIME4Rec. Specifically, we design a frequency ramp structure to allow the learnable filter slide on the frequency spectrums across different layers to capture different frequency patterns. Moreover, a Dynamic Frequency Selection (DFS) and a Static Frequency Split (SFS) module are proposed to replace the self-attention module for effectively extracting frequency information in two ways. DFS is used to select helpful frequency components dynamically, and SFS is combined with the dynamic frequency selection module to provide a more fine-grained frequency division. Finally, contrastive learning is utilized to improve the quality of user embedding learned from the frequency domain. Extensive experiments conducted on five widely used benchmark datasets demonstrate our proposed model performs significantly better than the state-of-the-art approaches. Our code is available at https://github.com/sudaada/SLIME4Rec.

As more detailed POI (Point of Interest) information has been incorporated into road network, routing has evolved from finding paths from one place to another, to satisfying users’ needs (keywords) along the trip. However, the existing solutions either only support one keyword per POI, or require a fixed visiting order, or only provide one option to choose from. Therefore, we study the top-k Optimal Routes with Collective Spatial Keywords (k-ORCSK) problem, which is the most general keyword-aware routing problem that supports multiple keywords, arbitrary orders, and top-k results. To solve this problem, we apply an enumeration framework and reduce the complexity by contracting non POI-related vertices and taking the keywords into account. After that, we propose a best-first path expansion method DA-CSK based on deviation to convert the enumeration paradigm from the distance-oriented to the keyword-oriented. Finally, several optimization techniques are provided to further improve the query efficiency. Extensive experiments conducted on multiple real-life road networks show that our method can provide higher quality results more efficiently.

Map matching is a problem to align recorded location data to a digital map. It has been well studied to map GPS data collected from vehicles to paths in a road network. The problem of Cellular Trajectory Map-Matching (CTMM) is a new problem that deals with trajectories of cellular-based positioning data. It has a wide range of applications, for example, for telecommunication companies to understand and predict traffic information based on telecom tokens obtained from vehicles. CTMM is a significantly more challenging task that faces much lower data precision and higher positioning errors. While Hidden Markov Model (HMM) based methods can achieve satisfactory results for GPS-based map matching, we show that they cannot be directly applied to the CTMM problem. In this paper, we aim at reducing the impact of positioning errors by incorporating knowledge obtained by neural networks into learned probabilities. A multi-relational graph learning method is developed to generate meaningful embedding, with multi-relational useful information fully preserved in a shared space. An attentive neural network is then designed as the learner for observation probability, incorporating the knowledge of the dynamic correlation between roads and cell towers under varying trajectory contexts. A transition probability learner is used to capture implicit deep features for enhanced transition probability modeling. Finally, the learned observation and transition probabilities are seamlessly integrated into HMM to guide more accurate path-finding. Extensive experiments on two large-scale cellular datasets reveal that our approach achieves high accuracy and robustness on CTMM.

Route planning plays an increasingly important role in our society, and the routing results, which are the paths that vehicles actually travel in a road network, which influence the traffic condition naturally. However, the existing routing algorithms cannot consider the routing results and their influence simultaneously, so traffic congestion could be created when many vehicles are directed to follow similar routes. In this paper, we propose the Global Routing Optimization problem that aims to minimize traffic congestion by continuously evaluating traffic conditions for a set of routing tasks. It is non-trivial to achieve this global optimization goal, as routing and traffic condition evaluation is both time-consuming and interdependent. To break this dependency, we propose a global routing optimization paradigm that can evaluate the routing results’ influence on the traffic condition, and then plan the routes accordingly. To implement it, we first propose a serial model to optimize the next route, followed by a batch model to improve processing efficiency. After that, an iterative model is proposed to further optimize route qualities. Extensive experiments on large real-world networks with synthetic and real workloads validate the effectiveness and efficiency of our methods.

Computing the shortest path distance between two vertices in a road network is a building block in numerous applications. To do so efficiently, the state-of-the-art proposals adopt a tree decomposition process with heuristic strategies to build 2-hop label indexes. However, these indexes suffer from large space overheads caused by either tree imbalance or a large tree height. Independently of this, reinforcement learning has recently show impressive performance at sequential decision making in spatial data management tasks. We observe that tree decomposition is naturally a sequential decision making problem that decides which vertex to process at each step. In this paper, we propose a reinforcement learning based tree decomposition (RLTD) approach that reduces the space overhead significantly. We model tree decomposition as a Markov Decision Process, exploiting features of both the network topological structure and the tree structure. We further optimize the tree decomposition process by taking the network density into account, which yields a great generalization of the model on large road networks. Extensive experiments with real-world data offer insights into the performance of the proposals, showing that they are able to reduce the space overhead by about 51% and achieve on average about 14% speedup for queries with almost the same preprocessing time when compared with the state-of-the-art proposals.

Approximate nearest neighbor (ANN) search in high-dimensional space plays an essential role in a variety of real-world applications. A well-known solution to ANN search, inverted file product quantization (IVFPQ) adopts inverted files to avoid exhaustive examination and compresses vectors using product quantization to reduce the space overhead. However, existing implementations use the same fixed probing cardinality (i.e., the number of cells to probe) setting for all queries, which leads to too many or too few cell examinations, thus increasing the average query latency or reducing the recall. To achieve a better trade-off between latency and accuracy, we enable probing cardinality estimation for high-dimensional ANN search by using deep learning techniques. We develop HBK-means, a hierarchical balanced clustering algorithm that reduces the data distribution imbalance of cells to enable a better estimation. Next, we develop PCE-Net, an encoder-decoder based neural network for estimating query-dependent minimum probing cardinality. In addition, we introduce two query optimization strategies: lower bound sorting based pruning (LBS-Pruning) and early termination (ET), to further reduce query latency. Extensive experiments with real-world data offer evidence that the proposed solution is capable of achieving better performance than IVFPQ and its variants.

Test2SQL, a natural language interface to database querying, has seen considerable improvement, in part due to advances in deep learning. However, despite recent improvement, existing Text2SQL proposals allow only input in the form of complete questions. This leaves behind users who struggle to formulate complete questions, e.g., because they lack database expertise or are unfamiliar with the underlying database schema. To address this shortcoming, we study the novel problem of Text2SQL Auto-Completion (TSAC) that extends Text2SQL to also take partial or incomplete questions as input. Specifically, the TSAC problem is to predict the complete, executable SQL query. To solve the problem, we propose a novel Relation-aware Historical Bridging Network (RHB-Net) that consists of a relation-aware union encoder and an extraction-generation sensitive decoder. RHB-Net models relations between questions and database schemas and predicts the ambiguous intents expressed in partial queries. We also propose two optimization strategies: historical query bridging that fuses historical database queries, and a dynamic context construction that prevents repeated generation of the same SQL elements. Extensive experiments with real-world data offer evidence that RHB-Net is capable of outperforming baseline algorithms.

Entity alignment (EA) aims to identify equivalent entities between knowledge graphs (KGs), which is a key technique to improve the coverage of existing KGs. Current EA models largely ignore the importance of time information contained in KGs and treat relational facts or attribute values of entities as time-invariant. However, real-world entities could evolve over time, making the knowledge of the aligned entities very different in multiple KGs. This may cause incorrect matching between KGs if such entity dynamics is ignored. In this paper, we propose a time-aware entity alignment (TEA) model that discovers the entity evolving behaviour by exploring the time contexts in KGs and aggregates various contextual information to make the alignment decision. In particular, we address two main challenges in the TEA model: 1) How to identify highly-correlated temporal facts; 2) How to capture entity dynamics and incorporate it to learn a more informative entity representation for the alignment task. Experiments on real-world datasets1 verify the superiority of our TEA model over state-of-the-art entity aligners.

Learning fair and transferable representations of users that can be used for a wide spectrum of downstream tasks (specifically, machine learning models) has great potential in fairness-aware Web services. Existing studies focus on debiasing w.r.t. a small scale of (one or a handful of) fixed pre-defined sensitive attributes. However, in real practice, downstream data users can be interested in various protected groups and these are usually not known as prior. This requires the learned representations to be fair w.r.t. all possible sensitive attributes. We name this task universal fair representation learning, in which an exponential number of sensitive attributes need to be dealt with, bringing the challenges of unreasonable computational cost and un-guaranteed fairness constraints. To address these problems, we propose a controllable universal fair representation learning (CUFRL) method. An effective bound is first derived via the lens of mutual information to guarantee parity of the universal set of sensitive attributes while maintaining the accuracy of downstream tasks. We also theoretically establish that the number of sensitive attributes that need to be processed can be reduced from exponential to linear. Experiments on two public real-world datasets demonstrate CUFRL can achieve significantly better accuracy-fairness trade-off compared with baseline approaches.

With an exponentially growing number of graphs from disparate repositories, there is a strong need to analyze a graph database containing an extensive collection of small- or medium-sized data graphs (e.g., chemical compounds). Although subgraph enumeration and subgraph mining have been proposed to bring insights into a graph database by a set of subgraph structures, they often end up with similar or homogenous topologies, which is undesirable in many graph applications. To address this limitation, we propose the Top-k Edge-Diversified Patterns Discovery problem to retrieve a set of subgraphs that cover the maximum number of edges in a database. To efficiently process such query, we present a generic and extensible framework called Ted which achieves a guaranteed approximation ratio to the optimal result. Two optimization strategies are further developed to improve the performance. Experimental studies on real-world datasets demonstrate the superiority of Ted to traditional techniques.

Designing a space-efficient data structure to answer membership queries while ensuring high accuracy and real-time response is a challenging task in the field of stream processing. Many techniques have been developed to answer these queries in a sliding windows manner. However, assuming the user will conduct the query with the presupposed window size is not always practical. In this paper, we introduce a novel data structure called Learned Cuckoo Filter (LCF). It can provide satisfactory results for the approximate membership query on data streams, regardless of the user-defined query windows. LCF operates by adaptively maintaining cuckoo filters with the assistance of a well-trained oracle that learned the frequency feature of the data within the stream. To further enhance memory utilization, we develop a compact version of LCF (denoted by LCF_C), which selectively removes redundant information to reduce space consumption without compromising query accuracy. Furthermore, we conduct a thorough theoretical analysis of query accuracy and provide detailed guidelines for optimal parameter selection (denoted by LCF_O). Extensive experimental studies on synthetic and real-world datasets demonstrate the superiority of the proposed methods in terms of both space consumption and accuracy. Compared to the state-of-the-art algorithms, LCF_O can reduce up to 61% of space cost at the same error level, and achieve up to 12× improved accuracy with the same space cost.

Visual Graph Query Interfaces (VQIs) empower non-programmers to query graph data by constructing visual queries intuitively. Devising efficient technologies in Graph Query Engines (GQEs) for interactive search and exploration has also been studied for years. However, these two vibrant scientific fields are traditionally independent of each other, causing a vast barrier for users who wish to explore the full-stack operations of graph querying. In this demonstration, we propose a novel VQI system built upon Neo4j called VisualNeo that facilities an efficient subgraph query in large graph databases. VisualNeo inherits several advanced features from recent advanced VQIs, which include the data-driven gui design and canned pattern generation. Additionally, it embodies a database manager module in order that users can connect to generic Neo4j databases. It performs query processing through the Neo4j driver and provides an aesthetic query result exploration.

Entity resolution (ER) approaches typically consist of a blocker and a matcher. They share the same goal and cooperate in different roles: the blocker first quickly removes obvious non-matches, and the matcher subsequently determines whether the remaining pairs refer to the same real-world entity. Despite the state-of-the-art performance achieved by deep learning methods in ER, these techniques often rely on a large amount of labeled data for training, which can be challenging or costly to obtain. Thus, there is a need to develop effective ER systems under low-resource settings. In this work, we propose an end-to-end iterative Co-learning framework for ER, aimed at jointly training the blocker and the matcher by leveraging their cooperative relationship. In particular, we let the blocker and the matcher share their learned knowledge with each other via iteratively updated pseudo labels, which broaden the supervision signals. To mitigate the impact of noise in pseudo labels, we develop optimization techniques from three aspects: label generation, label selection and model training. Through extensive experiments on benchmark datasets, we demonstrate that our proposed framework outperforms baselines by an average of 9.13--51.55%. Furthermore, our analysis confirms that our framework achieves mutual benefits between the blocker and the matcher.

The approximate nearest neighbor (ANN) search in high-dimensional spaces is a fundamental but computationally very expensive problem. Many methods have been designed for solving the ANN problem, such as LSH-based methods and graph-based methods. The LSH-based methods can be costly to reach high query quality due to the hash-boundary issues, while the graph-based methods can achieve better query performance by greedy expansion in an approximate proximity graph (APG). However, the construction cost of these APGs can be one or two orders of magnitude higher than that for building hash-based indexes. In addition, they fail short in incrementally maintaining APGs as the underlying dataset evolves. In this paper, we propose a novel approach named LSH-APG to build APGs and facilitate fast ANN search using a lightweight LSH framework. LSH-APG builds an APG via consecutively inserting points based on their nearest neighbor relationship with an efficient and accurate LSH-based search strategy. A high-quality entry point selection technique and an LSH-based pruning condition are developed to accelerate index construction and query processing by reducing the number of points to be accessed during the search. LSH-APG supports fast maintenance of APGs in lieu of building them from scratch as dataset evolves. Its maintenance cost and query cost for a point is proven to be less affected by dataset cardinality. Extensive experiments on real-world and synthetic datasets demonstrate that LSH-APG incurs significantly less construction cost but achieves better query performance than existing graph-based methods.

Maximum inner product search (MIPS) in high-dimensional spaces has wide applications but is computationally expensive due to the curse of dimensionality. Existing studies employ asymmetric transformations that reduce the MIPS problem to a nearest neighbor search (NNS) problem, which can be solved using locality-sensitive hashing (LSH). However, these studies usually maintain multiple hash tables and locally examine them one by one, which may cause additional costs on probing unnecessary points. In addition, LSH is applied without taking into account the properties of the inner product. In this paper, we develop a fast search framework FARGO for MIPS on large-scale, high-dimensional data. We propose a global multi-probing (GMP) strategy that exploits the properties of the inner product to globally examine high quality candidates. In addition, we develop two optimization techniques. First, different with existing transformations that introduce either distortion errors or data distribution imbalances, we design a novel transformation, called random XBOX transformation, that avoids the negative effects of data distribution imbalances. Second, we propose a global adaptive early termination condition that finds results quickly and offers theoretical guarantees. We conduct extensive experiments with real-world data that offer evidence that FARGO is capable of outperforming existing proposals in terms of both accuracy and efficiency.

Growing demands for the efficient processing of extreme-scale time series workloads call for more capable time series database management systems (TSDBMS). Specifically, to maintain consistency and durability of transaction processing, systems employ write-ahead logging (WAL) whereby transactions are committed only after the related log entries are flushed to disk. However, when faced with massive I/O, this becomes a throughput bottleneck. Recent advances in byte-addressable Non-Volatile Memory (NVM) provide opportunities to improve logging performance by persisting logs to NVM instead. Existing studies typically track complex transaction dependencies and use barrier instructions of NVM to ensure log ordering. In contrast, few studies consider the heavy-tailed characteristics of time series workloads, where most transactions are independent of each other. We propose DecLog, a decentralized NVM-based logging system that enables concurrent logging of TSDBMS transactions. Specifically, we propose data-driven log sequence numbering and relaxed ordering strategies to track transaction dependencies and resolve serialization issues. We also propose a parallel logging method to persist logs to NVM after being compressed and aligned. An experimental study on the YCSB-TS benchmark offers insight into the performance properties of DecLog, showing that it improves throughput by up to 4.6× while offering lower recovery time in comparison to the open source TSDBMS Beringei.

Sequential recommendation has been a widely popular topic of recommender systems. Existing works have contributed to enhancing the prediction ability of sequential recommendation systems based on various methods, such as recurrent networks and self-attention mechanisms. However, they fail to discover and distinguish various relationships between items, which could be underlying factors which motivate user behaviors. In this article, we propose an Edge-Enhanced Global Disentangled Graph Neural Network (EGD-GNN) model to capture the relation information between items for global item representation and local user intention learning. At the global level, we build a global-link graph over all sequences to model item relationships. Then a channel-aware disentangled learning layer is designed to decompose edge information into different channels, which can be aggregated to represent the target item from its neighbors. At the local level, we apply a variational auto-encoder framework to learn user intention over the current sequence. We evaluate our proposed method on three real-world datasets. Experimental results show that our model can get a crucial improvement over state-of-the-art baselines and is able to distinguish item features.

An Attributed Dynamic Graph (ADG) contains multiple dynamic attributes associated with each edge in the graph, where people usually can specify multiple constraints in the attributes to illustrate their requirements, such as the total cost, the total travel time and the stopover interval of a flight between two cities. This inspires the Multi-Constrained Temporal Path (MCTP) discovery in ADGs, which is a challenging NP-Complete problem. The existing methods adopt Reinforcement Learning (RL) and Monte Carlo Tree Search (MCTS) in MCTP discovery. However, they require a certain degree of discovery experience to obtain better results, which can lead to the expensive cost of query time and storage space, and thus are not applicable in real-time applications. This motivates us to develop a new Adaptive Monte Carlo Tree Search algorithm (A-MCTS). A-MCTS dynamically adjusts the priority of historical records that are used in MCTS to improve the performance and reduce the size of required discovery experience. The experimental results on ten real-world dynamic graphs demonstrate that our proposed A-MCTS outperforms the state-of-the-art methods in terms of both efficiency and effectiveness.

Semantic relation prediction aims to mine the implicit relationships between objects in heterogeneous graphs, which consist of different types of objects and different types of links. In real-world scenarios, new semantic relations constantly emerge and they typically appear with only a few labeled data. Since a variety of semantic relations exist in multiple heterogeneous graphs, the transferable knowledge can be mined from some existing semantic relations to help predict the new semantic relations with few labeled data. This inspires a novel problem of few-shot semantic relation prediction across heterogeneous graphs. However, the existing methods cannot solve this problem because they not only require a large number of labeled samples as input, but also focus on a single graph with a fixed heterogeneity. Targeting this novel and challenging problem, in this paper, we propose a Meta-learning based Graph neural network for Semantic relation prediction, named MetaGS. First, MetaGS decomposes the graph structure between objects into multiple normalized subgraphs, then adopts a two-view graph neural network to capture local heterogeneous information and global structure information of these subgraphs. Second, MetaGS aggregates the information of these subgraphs with a hyper-prototypical network, which can learn from existing semantic relations and adapt to new semantic relations. Third, using the well-initialized two-view graph neural network and hyper-prototypical network, MetaGS can effectively learn new semantic relations from different graphs while overcoming the limitation of few labeled data. Extensive experiments on three real-world datasets have demonstrated the superior performance of MetaGS over the state-of-the-art methods.

Sequential recommendation, which aims to recommend next item that the user will likely interact in a near future, has become essential in various Internet applications. Existing methods usually consider the transition patterns between items, but ignore the transition patterns between features of items. We argue that only the item-level sequences cannot reveal the full sequential patterns, while explicit and implicit feature-level sequences can help extract the full sequential patterns. Meanwhile, the item-level sequential recommendation also suffers from limited supervised signal issues. In this article, we propose a novel model Feature-level Deeper Self-Attention Network with Contrastive Learning (FDSA-CL) for sequential recommendation. Specifically, FDSA-CL first integrates various heterogeneous features of items into feature-level sequences with different weights through a vanilla attention mechanism. After that, FDSA-CL applies separated self-attention blocks on item-level sequences and feature-level sequences, respectively, to model item transition patterns and feature transition patterns. Moreover, we propose contrastive learning and item feature recommendation tasks to capture the embedding commonality and further utilize the beneficial interaction among the two levels, so as to alleviate the sparsity of the supervised signal and extract the most critical information. Finally, we jointly optimize the above tasks. We evaluate the proposed model using two real-world datasets and experimental results show that our model significantly outperforms the state-of-the-art approaches.

Trajectory data has become ubiquitous nowadays, which can benefit various real-world applications such as traffic management and location-based services. However, trajectories may disclose highly sensitive information of an individual including mobility patterns, personal profiles and gazetteers, social relationships, etc, making it indispensable to consider privacy protection when releasing trajectory data. Ensuring privacy on trajectories demands more than hiding single locations, since trajectories are intrinsically sparse and high-dimensional, and require to protect multi-scale correlations. To this end, extensive research has been conducted to design effective techniques for privacy-preserving trajectory data publishing. Furthermore, protecting privacy requires carefully balance two metrics: privacy and utility. In other words, it needs to protect as much privacy as possible and meanwhile guarantee the usefulness of the released trajectories for data analysis. In this survey, we provide a comprehensive study and a systematic summarization of existing protection models, privacy and utility metrics for trajectories developed in the literature. We also conduct extensive experiments on two real-life public trajectory datasets to evaluate the performance of several representative privacy protection models, demonstrate the trade-off between privacy and utility, and guide the choice of the right privacy model for trajectory publishing given certain privacy and utility desiderata.

Distant supervision is an efficient way to generate large-scale training data for relation extraction without human efforts. However, the accompanying challenges have been plaguing the advance of the extractor: (1) the automatically annotated labels for training data contain much noisy data; (2) the annotations, based on bag-level (cluster of sentences) instead of sentence-level (single sentence), are too coarse to train an accurate extractor; (3) hetergeneous sentences are hard for a denoising model to capture the underlying commonness among valid relational expressions. To address these issues, we bulid a novel sentence representation and craft reinforcement learning to select the expressive sentence for each relation mentioned in a bag. More specifically, we introduce entity-free sentence pattern incorporated with attentive type information. Furthermore, multiple interactions between entity-specific and entity-free representation are proposed to generate complementary sentence features (for challenge 3). Then we design a fine-grained reward function, and model the sentence selection process as an auction where different relations for a bag need to compete together to achieve the possession of a specific sentence based on its expressiveness(for challenge 1 and 2). The experimental results on two public datasets demonstrate the superiority of our model for distantly supervised relation extraction.

Finding the most suitable individual to answer a question using brief content has important usages, including the community of question answering systems and online recommender frameworks. However, one must tackle challenges: Disregarding the indispensable noise in short text contents, authors usually answer the input query with mismatched words that can negatively influence the textual relevance. Moreover, many vocabularies imply various alterations. Finally, not every expert is eager to answer an input query given the time constraint, named the reluctance dilemma. To overcome the challenges, we devise a novel embedding approach that constructs context-aware vectors. We then extract the knowledge domains out of the online contextual content. While we track user textual-temporal behavioral patterns via an infinite continuous-time module, we recommend a set of experts pertinent to the given query and willingly provide the response during the expected time. Experimental results on two real-world datasets ofStackOverflowandYahooshow that our online time-sensitive value-wise transformer can achieve higher effectiveness and efficiency versus other trending rivals in online expert recommendation systems. In addition, we empirically experience that Fourier transformers can automatically infer multi-aspect base signals and overpass manual discrete-time models in obtaining time-specific user profiles.

Graph Pattern based Node Matching(GPNM) is to find all the matches of the nodes in a data graph$G_D$based on a given pattern graph$G_P$. GPNM has become increasingly important in many applications, e.g., group finding and expert recommendation. In real scenarios, both$G_P$and$G_D$are updated frequently. However, the existing GPNM methods either need to perform a new GPNM procedure from scratch to deliver the node matching results based on the updated$G_P$and$G_D$or incrementally perform the GPNM procedure for each of the updates, leading to low efficiency. Although the elimination relations between updates and partitions of data graphs are considered in the state-of-the-art method, it still suffers from low efficiency as only the labels of nodes are considered in the partitions. Therefore, there is a pressing need for a new method to efficiently deliver the node matching results on the updated graphs. In this paper, we propose a new Partition-aware GPNM algorithm, called P-GPNM, where we propose two new partition methods, i.e.,connection-based partitionanddensity-based partition. In these two methods, P-GPNM considers the dense connections between partitions and the inner connections inside a single partition, respectively. The experimental results on five real-world social graphs demonstrate that our proposed P-GPNM is much more efficient than the state-of-the-art GPNM methods.

Indexing is an effective way to support efficient query processing in large databases. Recently the concept oflearned index, which replaces or complements traditional index structures with machine learning models, has been actively explored to reduce storage and search costs. However, accurate and efficient similarity query processing in high-dimensional metric spaces remains to be an open challenge. In this paper, we propose a novel indexing approach called LIMS that uses data clustering, pivot-based data transformation techniques and learned indexes to support efficient similarity query processing in metric spaces. In LIMS, the underlying data is partitioned into clusters such that each cluster follows a relatively uniform data distribution. Data redistribution is achieved by utilizing a small number of pivots for each cluster. Similar data are mapped into compact regions and the mapped values are totally ordinal. Machine learning models are developed to approximate the position of each data record on disk. Efficient algorithms are designed for processing range queries and nearest neighbor queries based on LIMS, and for index maintenance with dynamic updates. Extensive experiments on real-world and synthetic datasets demonstrate the superiority of LIMS compared with traditional indexes and state-of-the-art learned indexes.

Dynamic graphs refer to graphs whose structure dynamically changes over time. Despite the benefits of learning vertex representations (i.e., embeddings) for dynamic graphs, existing works merely view a dynamic graph as a sequence of changes within the vertex connections, neglecting the crucial asynchronous nature of such dynamics where the evolution of each local structure starts at different times and lasts for various durations. To maintain asynchronous structural evolutions within the graph, we innovatively formulate dynamic graphs as temporal edge sequences associated with joining time of vertices (ToV) and timespan of edges (ToE). Then, a time-aware Transformer is proposed to embed vertices’ dynamic connections and ToEs into the learned vertex representations. Meanwhile, we treat each edge sequence as a whole and embed its ToV of the first vertex to further encode the time-sensitive information. Extensive evaluations on several datasets show that our approach outperforms the state-of-the-art in a wide range of graph mining tasks. At the same time, it is very efficient and scalable for embedding large-scale dynamic graphs.

Shortest path computation is a fundamental operation in many application domains and is especially challenging in frequently evolving small-world networks (i.e., graphs in which many nodes can be reached from every other node by a small number of hops). Index-based methods, especially ones based on 2-hop labeling are often used for high query efficiency. However, the evolvements of small-world networks in many realistic scenarios pose the challenge of efficient maintenance of the shortest path index. In this work, we adopt the state-of-the-artParallel Shortest-distance Labeling (PSL)as the underlying 2-hop labeling construction method, and design algorithms to support its efficient update given edge weight changes (increase and decrease). Specifically, we focus on weightedPSL (WPSL)and propose a propagation-based update mechanism for both synchronous and asynchronous propagation. We also identify thecurse of pruning powerin the edge weight increase case, and solve it with a balance between index size and effectiveness. Followed by, we extend the asynchronous propagation method toPruned Landmark Labeling (PLL)for faster index maintenance and query processing with a smaller index size. Finally, we further optimize the index performance by reducing the index size through graph contraction and accelerating the index update through parallelized mix index update. Our experimental results on real-life and synthetic networks demonstrate the superiority of our algorithms over the relevant baselines on index maintenance.

In Spatial crowdsourcing, mobile users perform spatio-temporal tasks that involve travel to specified locations. Spatial crowdsourcing (SC) is enabled by SC platforms that support mobile worker recruitment and retention, as well as task assignment, which is essential to maximize profits that are accrued from serving task requests. Specifically, how to best achieve task assignment in a cost-effective manner while contending with spatio-temporal constraints is a key challenge in SC. To address this challenge, we formalize and study a novel Profit-driven Task Assignment problem. We first establish a task reward pricing model that takes into account the temporal constraints (i.e., expected completion time and deadline) of tasks. Then we adopt an optimal algorithm based on tree decomposition to achieve an optimal task assignment and propose greedy algorithms based on Random Tuning Optimization to improve the computational efficiency. To balance effectiveness and efficiency, we also provide a heuristic task assignment algorithm based on Ant Colony Optimization that assigns tasks by simulating behavior of ant colonies foraging for food. Finally, we conduct extensive experiments using real and synthetic data, offering detailed insight into effectiveness and efficiency of the proposed methods.

Abstract In this paper, we study the Time-Dependent k Nearest Neighbor (TD- k NN) query on moving objects that aims to return k objects arriving at the query location with the least traveling cost departing at a given time t . Although the k NN query on moving objects has been widely studied in the scenario of the static road network, the TD- k NN query tends to be more complicated and challenging because under the time-dependent road network, the cost of each edge is measured by a cost function rather than a fixed distance value. To tackle such difficulty, we adopt the framework of GLAD and develop an advanced index structure to support efficient fastest travel cost query on time-dependent road network. In particular, we propose the Time-Dependent H2H (TD-H2H) index, which pre-computes the aggregated weight functions between each node to some specific nodes in the decomposition tree derived from the road network. Additionally, we establish a grid index on moving objects for candidate object retrieval and location update. To further accelerate the TD- k NN query, two pruning strategies are proposed in our solution. Apart from that, we extend our framework to tackle the time-dependent approachable k NN (TD-A k NN) query on moving objects targeting for the application of taxi-hailing service, where the moving object might have been occupied. Extensive experiments with different parameter settings on real-world road network show that our solutions for both TD- k NN and TD-A k NN queries are superior to the competitors in orders of magnitude.

Entity alignment is a crucial task in knowledge graph fusion. However, most entity alignment approaches have the scalability problem. Recent methods address this issue by dividing large KGs into small blocks for embedding and alignment learning in each. However, such a partitioning and learning process results in an excessive loss of structure and alignment. Therefore, in this work, we propose a scalable GNN-based entity alignment approach to reduce the structure and alignment loss from three perspectives. First, we propose a centrality-based subgraph generation algorithm to recall some landmark entities serving as the bridges between different subgraphs. Second, we introduce self-supervised entity reconstruction to recover entity representations from incomplete neighborhood subgraphs, and design cross-subgraph negative sampling to incorporate entities from other subgraphs in alignment learning. Third, during the inference process, we merge the embeddings of subgraphs to make a single space for alignment search. Experimental results on the benchmark OpenEA dataset and the proposed large DBpedia1M dataset verify the effectiveness of our approach.

With the popularity of GPS-enabled devices, a huge amount of trajectory data has been continuously collected and a variety of location-based services have been developed that greatly benefit our daily life. However, the released trajectories also bring severe concern on personal privacy, and several recent studies have demonstrated the existence of personally-identifying information in spatial trajectories. Trajectory anonymization is nontrivial due to the trade-off between privacy protection and utility preservation. Furthermore, recovery attack has not been well studied in the current literature. To tackle these issues, we propose a frequency-based randomization model with a rigorous differential privacy guarantee for trajectory data publishing. In particular, we introduce two randomized mechanisms to perturb the local/global frequency distributions of significantly important locations in trajectories by injecting Laplace noise. We design a hierarchical indexing along with a novel search algorithm to support efficient trajectory modification, ensuring the modified trajectories satisfy the perturbed distributions without compromising privacy guarantee or data utility. Extensive experiments on a real-world trajectory dataset verify the effectiveness of our approaches in resisting individual re-identification and recovery attacks, and meanwhile preserving desirable data utility as well as the feasibility in practice.

Among many solutions to the high-dimensional approximate nearest neighbor (ANN) search problem, locality sensitive hashing (LSH) is known for its sub-linear query time and robust theoretical guarantee on query accuracy. Traditional LSH methods can generate a small number of candidates quickly from hash tables but suffer from large index sizes and hash boundary problems. Recent studies to address these issues often incur extra overhead to identify eligible candidates or remove false positives, making query time no longer sub-linear. To address this dilemma, in this paper we propose a novel LSH scheme called DB-LSH which supports efficient ANN search for large high-dimensional datasets. It organizes the projected spaces with multi-dimensional indexes rather than using fixed-width hash buckets. Our approach can significantly reduce the space cost by avoiding the need to maintain many hash tables for different bucket sizes. During the query phase of DB-LSH, a small number of high-quality candidates can be generated efficiently by dynamically constructing query-based hypercubic buckets with the required widths through index-based window queries. For a dataset of$n$d-dimensional points with approximation ratio$c$, our rigorous theoretical analysis shows that DB-LSH achieves a smaller query cost$O(n^{\rho}d\log n)$, where$\rho^{\ast}$is bounded by$1/c^{\alpha}$versus a bound of$1/c$in the existing work. An extensive range of experiments on real-world data demonstrate the superiority of DB-LSH over state-of-the-art methods on both efficiency and accuracy.

The string similarity search is core functionality in a range of applications, including data cleaning, near-duplicate object detection, and data integration. We study the problem of threshold similarity search with the edit distance, where given a set of strings, a threshold$k$, and a query string$q$, we aim to find all strings in the set whose edit distances to$q$are no larger than$k$. Extensive studies have been proposed for the threshold similarity search problem with the edit distance. However, they suffer from a huge space consumption issue when achieving only an acceptable efficiency, especially for long strings. In this paper, we propose a simple yet small index, called minIL, to eliminate this issue. First, we adopt a minhash family to capture pivot characters and to construct sketch representations for strings. Second, we develop a multi-level inverted index to search sketches with a low space consumption. Finally, we apply a novel learned index technique on top of the index that further improves the query efficiency. Extensive experiments on real-world datasets offer insight into the performance of our method and show that it substantially reduces the index size, and is capable of outperforming the baseline approaches.

Computing shortest-path distances in road networks is core functionality in a range of applications. To enable the efficient computation of such distance queries, existing proposals frequently apply 2-hop labeling that constructs a label for each vertex and enables the computation of a query by performing only a linear scan of labels. However, few proposals take into account the spatio-temporal characteristics of query workloads. We observe that real-world workloads exhibit (1) spatial skew, meaning that only a small subset of vertices are queried frequently, and (2) temporal locality, meaning that adjacent time intervals have similar query distributions. We propose a Workload-aware Core-Forest label index (WCF) to exploit spatial skew in workloads. In addition, we develop a Reinforcement Learning based Time Interval Partitioning (RL-TIP) algorithm that exploits temporal locality to partition workloads to achieve further performance improvements. Extensive experiments with real-world data offer insights into the performance of the proposals, showing that they achieve 62% speedup on average for query processing with less preprocessing time and space overhead when compared with the state-of-the-art proposals.

Trajectory prediction is a fundamental problem for a wide spectrum of location-based applications. Existing methods can achieve inspiring results in predicting personal frequent routes conditioned on massive historical data. However, trajectory estimation may involve cold-start routes or users due to the data sparsity problem, which severely limits the performance of spatial trajectory prediction. Although meta-learning models can alleviate the cold-start problem, they simply utilize the same initialization for all tasks and thus cannot fit each user well due to users' varying travel preferences. To this end, we propose an adaptive meta-optimized model called MetaPTP for personalized spatial trajectory prediction. Specifically, it adopts a soft-clustering based method to guide the network initialization in a finer granularity, so that shared knowledge can be better transferred across users with similar travel preferences. Besides, towards model fine-tuning, an effective trajectory sampling method is introduced to generate meaningful support set, which simultaneously considers user preference and spatial trace similarities to provide task-related information for model adaptation. In addition, we design a weight generator to adaptively assign reasonable weights to trajectories in support set to avoid sub-optimal results which will occur when fine-tuning the initial network with the same weight for trajectories with different user preferences and spatial distributions. Finally, extensive experiments on two real-world datasets demonstrate the superiority of our model.

Entity alignment is a crucial step in integrating knowledge graphs (KGs) from multiple sources. Previous attempts at entity alignment have explored different KG structures, such as neighborhood-based and path-based contexts, to learn entity embeddings, but they are limited in capturing the multi-context features. Moreover, most approaches directly utilize the embedding similarity to determine entity alignment without considering the global interaction among entities and relations. In this work, we propose an Informed Multi-context Entity Alignment (IMEA) model to address these issues. In particular, we introduce Transformer to flexibly capture the relation, path, and neighborhood contexts, and design holistic reasoning to estimate alignment probabilities based on both embedding similarity and the relation/entity functionality. The alignment evidence obtained from holistic reasoning is further injected back into the Transformer via the proposed soft label editing to inform embedding learning. Experimental results on several benchmark datasets demonstrate the superiority of our IMEA model compared with existing state-of-the-art entity alignment methods.

Exploratory search is a search paradigm that plays a vital role in databases, data mining, and information retrieval to assist users to get familiar with the underlying databases. It supports iterative query formulation to explore the data space. Despite its growing importance, exploratory search on graph-structured data has not received adequate attention in the literature. In this paper, we demonstrate a novel system called Vincent that facilitates an efficient exploratory subgraph search in a graph database containing a large collection of small or medium-sized graphs. By automatically generating the content for panels in GUI and diversified patterns from databases and providing a visual result explorer, Vincent supports data-driven visual query formulation, incremental subgraph processing, and efficient query result summarization.

Multi-Constraint Shortest Path ( MCSP ) generalizes the classic shortest path from single to multiple criteria such that more personalized needs can be satisfied. However, MCSP query is essentially a high-dimensional skyline problem and thus time-consuming to answer. Although the current Forest Hop Labeling (FHL) index can answer MCSP efficiently, it takes a long time to construct and lacks the flexibility to handle arbitrary criteria combinations. In this paper, we propose a skyline-cube-based FHL index that can handle the flexible MCSP efficiently. Firstly, we analyze the relation between low and high-dimensional skyline paths theoretically and use a cube to organize them hierarchically. After that, we propose methods to derive the high-dimensional path from the lower ones, which can adapt to the flexible scenario naturally and reduce the expensive high dimensional path concatenation. Then we introduce efficient methods for both single and multi-hop cube concatenations and propose pruning methods to further alleviate the computation. Finally, we improve the FHL structure with lower height for faster construction and query. Experiments on real-life road networks demonstrate the superiority of our method over the state-of-the-art.

Route planning is ubiquitous and has a profound impact on our daily life. However, the existing path algorithms tend to produce similar paths between similar OD (Origin-Destination) pairs because they optimize query results without considering their influence on the whole network, which further introduces congestions. Therefore, we investigate the problem of diversifying the top-k paths between an OD pair such that their similarities are under a threshold while their total length is minimal. However, the current solutions all depend on the expensive graph traversal which is too slow to apply in practice. Therefore, we first propose an edge deviation and concatenation-based method to avoid the expensive graph search in path enumeration. After that, we dive into the path relations and propose a path similarity computation method with constant complexity, and propose a pruning technique to improve efficiency. Finally, we provide the completeness and efficiency-oriented solutions to further accelerate the query answering. Evaluations on the real-life road networks demonstrate the effectiveness and efficiency of our algorithm over the state-of-the-art.

Online ride-hailing platforms have reduced significantly the amounts of the time that taxis are idle and that passengers spend on waiting. As a key component of these platforms, the fleet management problem can be naturally modeled as a Markov Decision Process, which enables us to use the deep reinforcement learning. However, existing studies are proposed based on simplified problem settings that fail to model the complicated supply-dynamics and restrict the performance in the real traffic environment. In this article, we propose a supply-demand-aware deep reinforcement learning algorithm for taxi dispatching, where we use a deep Q-network with action sampling policy, called AS-DQN, to learn an optimal dispatching policy. Furthermore, we utilize a dueling network architecture, called AS-DDQN, to improve the performance of AS-DQN. Extensive experiments on real-world datasets offer insight into the performance of our model and show that it is capable of outperforming the baseline approaches.

Map inference algorithm aims to construct a digital map from other data sources automatically. Due to the labour intensity of traditional map creation and the frequent road change nowadays, map inference is deemed to be a promising solution to automatic map construction and update. However, existing map inference from GPS trajectories suffers from low GPS data quality, which makes the quality of the constructed map unsatisfactory. In this paper, we study the existing map inference algorithms using GPS trajectories. Different from previous surveys, we (1) include the most recent solutions and propose a new categorisation of method; (2) study how different types of GPS errors affect the quality of inference results; (3) evaluate the existing map inference quality measures regarding their ability to identify map quality issues. To achieve these goals, we conduct a comprehensive experimental study on several representative algorithms using both real-world datasets and synthetic datasets, which are generated from our proposed synthetic trajectory generator and artificial map generator. Overall, our study provides insightful observations regarding (1) which inference method performs better in each working scenario, (2) the general data quality requirements for map inference, (3) the direction of future works for quantitative map quality measures.

With the explosion of GPS-enabled smartphones and social media platforms, geo-social networks are increasing as tools for businesses to promote their products or services. Influence maximization, which aims to maximize the expected spread of influence in the networks, has drawn increasing attention. However, most recent work tries to study influence maximization by only considering geographic distance, while ignoring the influence of users’ spatio-temporal behavior on information propagation or location promotion, which can often lead to poor results. To relieve this problem, we propose a Similarity-aware Influence Maximization (SIM) model to efficiently maximize the influence spread by taking the effect of users’ spatio-temporal behavior into account, which is more reasonable to describe the real information propagation. We first calculate the similarity between users according to their historical check-ins, and then we propose a Propagation to Consumption (PTC) model to capture both online and offline behaviors of users. Finally, we propose two greedy algorithms to efficiently maximize the influence spread. The extensive experiments over real datasets demonstrate the efficiency and effectiveness of the proposed algorithms.

Trajectory-based spatiotemporal entity linking is to match the same moving object in different datasets based on their movement traces. It is a fundamental step to support spatiotemporal data integration and analysis. In this paper, we study the problem of spatiotemporal entity linking using effective and concise signatures extracted from their trajectories. This linking problem is formalized as a$k$-nearest neighbor ($k$-NN) query on the signatures. Four representation strategies (sequential, temporal, spatial, and spatiotemporal) and two quantitative criteria (commonality and unicity) are investigated for signature construction. A simple yet effective dimension reduction strategy is developed together with a novel indexing structure called the WR-tree to speed up the search. A number of optimization methods are proposed to improve the accuracy and robustness of the linking. Our extensive experiments on real-world datasets verify the superiority of our approach over the state-of-the-art solutions in terms of both accuracy and efficiency.

Finding the fastest path in the time-dependent road network is time consuming because its problem complexity is$\Omega (T(|V|\log |V|+|E|))$, where$T$is the size of the result's time-dependent function,$|V|$and$|E|$are the number of vertices and edges. There are three kinds of fastest path problems:SSFP (Single-Staring Time Fastest Path)that has a fixed departure time,ISFP (Interval-Staring Time Fastest Path)that selects the best departure time from an interval, andFPP (Fastest Path Profile)that returns the travel time of the entire time domain. In this paper, we aim to answer these three queries in time-dependent road network faster by extending the2-hop labelingapproach, which is fast in answering shortest distance query in the static graph. However, it is hard to construct index forSSFPandISFPbecause there are$|\mathcal {T}|$and$|\mathcal {T}|^2$possible time points and intervals, where$\mathcal {T}$is the time domain. Therefore, we first propose thetime-dependent hop-labelingforFPP, then provide the specific optimizations forSSFPandISFPquery answering. Moreover, it is both time and space consuming to build an index in a large time-dependent graph, so we partition road network into smaller sub-graphs and build indexes within and between the partitions. Furthermore, we propose an online approximation techniqueAT-Dijkstraand abottom-upcompression method to further reduce the label size, save construction time and speedup query answering. Experiments on real world road network show that our approach outperforms the state-of-art fastest path index approaches and can speed up the query answering by hundreds of times.

One-class collaborative filtering (OCCF) problems are ubiquitous in real-world recommendation systems, such as news recommendation, but suffer from data sparsity and lack of negative items. To address the challenge, the state-of-the-art algorithm assigns uninteracted items with smaller weights of being negative and performs low-rank approximation over the user-item interaction matrix. However, the prior ratings are usually suggested to be zero but may not be well-defined. To avert the direct utilization of prior ratings for uninteracted items, we propose a novel ranking-based implicit regularizer by hypothesizing that users’ preference scores for uninteracted items should not deviate a lot from each other. The regularizer is then used in a ranking-based OCCF framework to penalize large differences of preference scores between uninteracted items. To efficiently optimize model parameters in this framework, we develop the scalable alternating least square algorithm and coordinate descent algorithm, whose time complexity is linearly proportional to the data size. Finally, we extensively evaluate the proposed algorithms on six public real-world datasets. The results show that the proposed regularizer significantly improves the recommendation quality of ranking-based OCCF algorithms, such as BPRMF and RankALS. Moreover, the ranking-based framework with the proposed regularizer outperforms the state-of-the-art recommendation algorithms for implicit feedback.

Massive trajectory data stem from the prevalence of equipment-supporting GPS and wireless communication technology. Especially, activity trajectory from Location-based Social Network (LBSN) endows traditional trajectory data with additional user semantic activities, e.g., visiting work/home/entertainment places. Measuring the similarity between activity trajectories is to compare their proximity in multiple dimensions such as time, location, and semantics. In this way, we can mine implicit user preference and apply it to route planning, POI recommendation or any other online tasks. The key challenge of comparing activity trajectories (i.e., computing their similarity) lies in two aspects. One is the uneven sampling rate in both time and space. The other is the discrepancy of individual activities. Previous effort alleviates the issue of uneven sampling rate via trajectory complements, which is limited to spatial-temporal information. In this paper, we propose to learn a representation for one activity trajectory by jointly considering the spatio-temporal characteristics and the activity semantics. The similarity of two trajectories is computed by weighting individual trajectory points and contextual features with multi-level attention mechanisms. In specific, we propose a point-level and feature-level attention mechanism to adaptively select critical elements and contextual factors for learning trajectory representation. Our proposed approach, called At2vec, demonstrates better performance than existing baselines in extensive experimental evaluation on real trajectory databases.

Linking authors of short-text contents has important usages in many applications, including Named Entity Recognition (NER) and human community detection. However, certain challenges lie ahead. First, the input short-text contents are noisy, ambiguous, and do not follow the grammatical rules. Second, traditional text mining methods fail to effectively extract concepts through words and phrases. Third, the textual contents are temporally skewed, which can affect the semantic understanding by multiple time facets. Finally, using knowledge-bases can make the results biased to the content of the external database and deviate the meaning from the input short text corpus. To overcome these challenges, we devise a neural network-based temporal-textual framework that generates the subgraphs with highly correlated authors from short-text contents. Our approach, on the one hand, computes the relevance score (edge weight) between the authors through considering a portmanteau of contents and concepts, and on the other hand, employs a stack-wise graph cutting algorithm to extract the communities of the related authors. Experimental results show that compared to other knowledge-centered competitors, our multi-aspect vector space model can achieve a higher performance in linking short-text authors. In addition, given the author linking task, the more comprehensive the dataset is, the higher the significance of the extracted concepts will be.

It has been an important task for recommender systems to suggest satisfying activities to a group of users in peoples daily social life. The major challenge in this task is how to aggregate personal preferences of group members to infer the decision of a group. In this paper, we propose a novel end-to-end group recommender system named CAGR (short for Centrality-Aware Group Recommender), which takes the Bipartite Graph Embedding Model (BGEM), the self-attention mechanism and Graph Convolutional Networks (GCNs) as basic building blocks to learn group and user representations in a unified way. Specifically, we first extend BGEM to model group-item interactions, and then in order to overcome the sparsity of the interaction data generated by occasional groups, we propose a self-attentive mechanism to represent groups based on the group members. To further alleviate the group data sparsity problem, we propose two model optimization approaches to exploit an and integrate the user-item interaction data. To overcome the sparsity issue of user-item interaction data, we extend GCNs to leverage the social network to enhance user representation learning. We create two large-scale benchmark datasets and conduct extensive experiments on them. The experimental results show the superiority of our proposed CAGR.

Shortest path query in road network is pervasive in various location-based services nowadays. As the business expands, the scalability issue becomes severer and more servers are deployed to cope with it. Moreover, as the traffic condition keeps changing over time, the existing index-based approaches can hardly adapt to the real-life dynamic environment. Therefore, batch shortest path algorithms have been proposed recently to answer a set of queries together using shareable computation. Besides, they can also work in a highly dynamic environment as no index is needed. However, the existing batch algorithms either assume the batch queries are finely decomposed or just process them without differentiation, resulting in poor query efficiency. In this work, we assume the traffic condition is stable over a short period and treat the issued queries within that period as a stream of query sets. Specifically, we first propose three query set decomposition methods to cluster one query set into multiple query subsets:Zigzagthat considers the1-Nshared computation;Co-Clusteringthat considers the source and target's spatial locality; andSearch-Space-Awarethat further incorporates search space estimation. After that, we propose two batch algorithms that take advantage of the previously decomposed query sets for efficient query answering:R2Rthat finds a set of approximate shortest paths from one region to another with bounded error; andLocal Cachethat improves the existingGlobal Cachewith higher cache hit ratio. Finally, we design three efficient stream processing methods for intra-batch shared computation. The experiments on a large real-world query sets verify the effectiveness and efficiency of our decomposition methods compared with the state-of-the-art batch algorithms.

Next Point-of-Interest (POI) recommendation which is of great value to both users and POI holders is a challenging task since complex sequential patterns and rich contexts are contained in extremely sparse user check-in data. Recently proposed embedding techniques have shown promising results in alleviating the data sparsity issue by modeling context information, and Recurrent Neural Network (RNN) has been proved effective in the sequential prediction. However, existing next POI recommendation approaches train the embedding and network model separately, which cannot fully leverage rich contexts. In this paper, we propose a novel unified neural network framework, named NeuNext, which leverages POI context prediction to assist next POI recommendation by joint learning. Specifically, the Spatio-Temporal Gated Network (STGN) is proposed to model personalized sequential patterns for users’ long and short term preferences in the next POI recommendation. In the POI context prediction, rich contexts on POI sides are used to construct graph, and enforce the smoothness among neighboring POIs. Finally, we jointly train the POI context prediction and the next POI recommendation to fully leverage labeled and unlabeled data. Extensive experiments on real-world datasets show that our method outperforms other approaches for next POI recommendation in terms of Accuracy and MAP.

With the ubiquity of smart devices, Spatial Crowdsourcing (SC) has emerged as a new transformative platform that engages mobile users to perform spatio-temporal tasks by physically traveling to specified locations. Thus, various SC techniques have been studied for performance optimization, among which one of the major challenges is how to assign workers the tasks that they are really interested in and willing to perform. In this paper, we propose a novel preference-aware spatial task assignment system based on workers’ temporal preferences, which consists of two components:History-based Context-aware Tensor Decomposition (HCTD) for workers’ temporal preferences modelingandpreference-aware task assignment. We model workers’ preferences with a three-dimension tensor (worker-task-time). Supplementing the missing entries of the tensor through HCTD with the assistant of historical data and other two context matrices, we recover workers’ preferences for different categories of tasks in different time slots. Several preference-aware individual task assignment algorithms are then devised, aiming to maximize the total number of task assignments at every time instance, in which we give higher priorities to the workers who are more interested in the tasks. In order to make our proposed framework applicable to more scenarios, we further optimize the original framework by proposing strategies to allow each task to be assigned to a group of workers such that the task can be completed by these workers simultaneously, wherein workers’ tolerable waiting time, consensus, and tasks’ rewards are taken into consideration. We conduct extensive experiments using a real dataset, verifying the practicability of our proposed methods.

Abstract The appetite for effective use of information assets has been steadily rising in both public and private sector organisations. However, whether the information is used for social good or commercial gain, there is a growing recognition of the complex socio-technical challenges associated with balancing the diverse demands of regulatory compliance and data privacy, social expectations and ethical use, business process agility and value creation, and scarcity of data science talent. In this vision paper, we present a series of case studies that highlight these interconnected challenges, across a range of application areas. We use the insights from the case studies to introduce Information Resilience, as a scaffold within which the competing requirements of responsible and agile approaches to information use can be positioned. The aim of this paper is to develop and present a manifesto for Information Resilience that can serve as a reference for future research and development in relevant areas of responsible data management.

The development of existing extractive summarization models for long-form document summarization is hindered by two factors: 1) the computation of the summarization model will dramatically increase due to the sheer size of the input long document; 2) the discourse structural information in the long-form document has not been fully exploited. To address the two deficiencies, we propose HEROES, a novel extractive summarization model for summarizing long-form documents with rich discourse structural information. In particular, the HEROES model consists of two modules: 1) a content ranking module that ranks and selects salient sections and sentences to compose a short digest that empowers complex summarization models and serves as its input; 2) an extractive summarization module based on a heterogeneous graph with nodes from different discourse levels and elaborately designed edge connections to reflect the discourse hierarchy of the document and restrain the semantic drifts across section boundaries. Experimental results on benchmark datasets show that HEROES can achieve significantly better performance compared with various strong baselines.

Crowdsensing Data Trading (CDT), through which a platform can aggregate some data collected by a group of mobile users with sensing devices (a.k.a., data sellers) and sell the corresponding statistics to data consumers, has been recognized as a promising paradigm for large-scale data trading in recent years. It is critical to select sellers with high sensing qualities and maximize all trading participants' profits simultaneously. However, most existing CDT systems either assume that sellers' sensing qualities are known in advance or cannot realize concurrent profit maximization. In this paper, we propose a data trading mechanism based on Combinatorial Multi-Armed Bandit and three-stage Hierarchical Stackelberg game, called CMAB-HS, to tackle the problem of quality unknown seller selection and incentive strategy design. Our objective is to select a group of sellers to maximize the total sensing quality within time budget, and determine the optimal incentive strategy for each participant to maximize individual profit simultaneously. We theoretically prove that CMAB-HS achieves Stackelberg Equilibrium and a tight bound on regret. Additionally, we demonstrate its significant performances through extensive simulations on real data traces.

The Constrained Shortest Path (CSP) problem aims to find the shortest path between two nodes in a road network subject to a given constraint on another attribute. It is typically processed as a skyline path problem on the two attributes, resulting in very high computational cost which can be prohibitive for large road networks. The main bottleneck is to deal with a large amount of partial skyline paths, which further makes the existing index-based methods incapable to obtain the complete exact skyline paths. In this paper, we propose a novel skyline path concatenation approach to avoid the expensive skyline path search, which is then used to efficiently construct a 2-hop labeling index for the CSP queries. Specifically, a rectangle-based technique is designed to prune the concatenation space from multiple hops, and a constraint pruning method is used to further speed up the CSP query processing. To further scale up to larger networks, we propose a novel forest hop labeling that constructs labels from different partitions in parallel. Our approach is the first method that can achieve both accuracy and efficiency for CSP query answering. Extensive experiments on real-life road networks demonstrate that our method outperforms the state-of-the-art CSP solutions by several orders of magnitude.

Shortest path computation is a fundamental operation in small-world networks and index-based methods, especially 2-hop labeling, are commonly applied which have achieved high query efficiency. However, small-world networks keep evolving in real life, making it indispensable to study the maintenance of shortest path index. In this work, we adopt the state-of-the-art Parallel Shortest-distance Labeling (PSL) as the underlying 2-hop labeling construction method, and design algorithms to support efficient update of the index given edge weight change (increase and decrease) in the network. Specifically, we focus on weighted PSL (WPSL) and propose the update propagation mechanism for both synchronous propagation and asynchronous propagation. We then identify the curse of pruning power generated for the propagation under edge weight increase, and solve this problem with a balance between index size and effectiveness. Finally, we extend the proposed asynchronous propagation method to Pruned Landmark Labeling (PLL) for faster index maintenance and query processing with smaller index size. Our experimental results on real-life and synthetic networks demonstrate the superiority of our algorithms on index maintenance.

Shortest path finding is the building block of various applications in road networks and the index-based algorithms, especially hub labeling, can boost the query performance dramatically. However, the traffic condition keeps changing in real life, making the pre-computed index unable to answer the query correctly. In this work, we adopt the state-of-the-art tree decomposition-based hub labeling as the underlying index, and design efficient algorithms to incrementally maintain the index. Specifically, we first analyze the structural stability of the index in dynamic road networks which enables us to concentrate on label value maintenance. We then introduce the minimum weight property and minimum distance property to guarantee the index correctness without graph traversal. Moreover, we propose the star-centric paradigm for tracing index change and design various pruning techniques to further accelerate the index maintenance. Finally, we extend our algorithms to batch mode for shared computation, extend to structural maintenance for full types of update, and generalize to all kinds of TDHL. Our experimental results validate the superiority of our proposals over existing solutions on both index maintenance and query processing.

With the fast-paced development of mobile networks and the widespread usage of mobile devices, Spatial Crowdsourcing (SC), which refers to assigning location-based tasks to moving workers, has drawn increasing attention in recent years. One of the critical issues in SC is task assignment that allocates tasks to appropriate workers. In this paper, we propose a novel SC problem, namely Coalition-based Task Assignment (CTA), where the spatial tasks (e.g., house removals, furniture installation) may require more than one workers (forming a coalition) to cooperate in order to maximize the overall rewards of workers. To tackle the CTA problem, we design both greedy method and equilibrium-based method. In particular, the greedy method aims to form a set of worker coalitions greedily to perform the tasks, in which we introduce an acceptance possibility to find the high-value task assignments. In the equilibrium-based algorithm, workers form coalitions in sequence and update their strategy (i.e., selecting a best-response task) at their turn, in order to maximize their own utility (i.e., reward of the coalition they stay in) until Nash equilibrium is reached. Since the equilibrium point obtained by the best-response approach is not unique and optimal in terms of total rewards, we further propose a simulated annealing scheme to find a better Nash equilibrium. The extensive experiments demonstrate the efficiency and effectiveness of the proposed methods on both real and synthetic datasets.

Sequential recommendation has become an attractive topic in recommender systems. Existing sequential recommendation methods, including the methods based on the state-of-the-art self-attention mechanism, usually employ deterministic neural networks to represent user preferences as fixed-points in the latent feature spaces. However, the fixed-point vector lacks the ability to capture the uncertainty and dynamics of user preferences that are prevalent in recommender systems. In this paper, we propose a new Variational Self-Attention Network (VSAN), which introduces a variational autoencoder (VAE) into the self-attention network to capture latent user preferences. Specifically, we represent the obtained self-attention vector as density via variational inference, whose variance well characterizes the uncertainty of user preferences. Furthermore, we employ self-attention networks to learn the inference process and generative process of VAE, which well captures long-range and local dependencies. Finally, we evaluate our proposed method VSAN with two public real-world datasets. Our experimental results show the effectiveness of our model compared to the state-of-the-art approaches.

Trajectory similarity computation is a fundamental component in a variety of real-world applications, such as ridesharing, road planning, and transportation optimization. Recent advances in mobile devices have enabled an unprecedented increase in the amount of available trajectory data such that efficient query processing can no longer be supported by a single machine. As a result, means of performing distributed in-memory trajectory similarity search are called for. However, existing distributed proposals either suffer from computing resource waste or are unable to support the range of similarity measures that are being used. We propose a distributed in-memory management framework called REPOSE for processing top-k trajectory similarity queries on Spark. We develop a reference point trie (RP-Trie) index to organize trajectory data for local search. In addition, we design a novel heterogeneous global partitioning strategy to eliminate load imbalance in distributed settings. We report on extensive experiments with real-world data that offer insight into the performance of the solution, and show that the solution is capable of outperforming the state-of-the-art proposals.

Multivariate time series forecasting has been drawing increasing attention due to its prevalent applications. It has been commonly assumed that leveraging latent dependencies between pairs of variables can enhance prediction accuracy. However, most existing methods suffer from static variable relevance modeling and ignorance of correlation between temporal scales, thereby failing to fully retain the dynamic and periodic interdependencies among variables, which are vital for long- and short-term forecasting. In this paper, we propose METRO, a generic framework with multi-scale temporal graphs neural networks, which models the dynamic and cross-scale variable correlations simultaneously. By representing the multivariate time series as a series of temporal graphs, both intra- and inter-step correlations can be well preserved via message-passing and node embedding update. To enable information propagation across temporal scales, we design a novel sampling strategy to align specific steps between higher and lower scales and fuse the cross-scale information efficiently. Moreover, we provide a modular interpretation of existing GNN-based time series forecasting works as specific instances under our framework. Extensive experiments conducted on four benchmark datasets demonstrate the effectiveness and efficiency of our approach. METRO has been successfully deployed onto the time series analytics platform of Huawei Cloud, where a one-month online test demonstrated that up to 20% relative improvement over state-of-the-art models w.r.t. RSE can be achieved.

Shortest path computation is a building block of various network applications. Since real-life networks evolve as time passes, the Dynamic Shortest Path (DSP) problem has drawn lots of attention in recent years. However, as DSP has many factors related to network topology, update patterns, and query characteristics, existing works only test their algorithms on limited situations without sufficient comparisons with other approaches. Thus, it is still hard to choose the most suitable method in practice. To this end, we first identify the determinant dimensions and constraint dimensions of the DSP problem and create a complete problem space to cover all possible situations. Then we evaluate the state-of-the-art DSP methods under the same implementation standard and test them systematically under a set of synthetic dynamic networks. Furthermore, we propose the concept of dynamic degree to classify the dynamic environments and use throughput to evaluate their performance. These results can serve as a guideline to find the best solution for each situation during system implementation and also identify research opportunities. Finally, we validate our findings on real-life dynamic networks.

Many navigation applications take natural language speech as input, which avoids users typing in words and thus improves traffic safety. However, navigation applications often fail to understand a user's free-form description of a route. In addition, they only support input of a specific source or destination, which does not enable users to specify additional route requirements. We propose a SpeakNav framework that enables users to describe intended routes via speech and then recommends appropriate routes. Specifically, we propose a novel Route Template based Bidirectional Encoder Representation from Transformers (RT-BERT) model that supports the understanding of natural language route descriptions. The model enables extraction of information of intended POI keywords and related distances. Then we formalize a template-driven path query that uses the extracted information. To enable efficient query processing, we develop a hybrid label index for computing network distances between POIs, and we propose a branch-and-bound algorithm along with a pivot reverse B-tree (PB-tree) index. Experiments with real and synthetic data indicate that RT-BERT offers high accuracy and that the proposed algorithm is capable of outperforming baseline algorithms.

The join operations, including both equi and non-equi joins, are essential to the complex data analytics in the big data era. However, they are not inherently supported by existing DSPEs (Distributed Stream Processing Engines). The state-of-the-art join solutions on DSPEs rely on either complicated routing strategies or resource-inefficient processing structures, which are susceptible to dynamic workload, especially when the DSPEs face various join predicate operations and skewed data distribution. In this paper, we propose a new cost-effective stream join framework, named A-DSP (Adaptive Dimensional Space Processing), which enhances the adaptability of real-time join model and minimizes the resource used over the dynamic workloads. Our proposal includes: 1) a join model generation algorithm devised to adaptively switch between different join schemes so as to minimize the number of processing task required; 2) a load-balancing mechanism which maximizes the processing throughput; and 3) a lightweight algorithm designed for cutting down unnecessary migration cost. Extensive experiments are conducted to compare our proposal against state-of-the-art solutions on both benchmark and real-world workloads. The experimental results verify the effectiveness of our method, especially on reducing the operational cost under pay-as-you-go pricing scheme.

Data incompleteness is a common data quality problem in databases. Recent work proposes to retrieve missing string values from the World Wide Web for higher imputation recall, but on the other hand, takes the risk of introducing web noises into the imputation results. So far there lacks an effective way to control the quality of web-based data imputation, given the complexity of the quality model and lacking of enough ground truth data. In this article, an EM-based quality model is first built for web-based data imputation which investigates three key factors jointly, i.e., precision of web sources, correlation among web sources, and precision and recall of the employed extractors. However, the accuracy of the EM-based quality model could be harmed when the EM (Expectation Maximization) assumption that “the majority agree on the truth” does not hold in some cases. To solve this problem, we introduce crowd intervention to help improve the quality model. While a straightforward but expensive way is to let the crowd to identify all these undesirable cases and provide the right imputation values for these blanks, a most crowd-economic way is to select a small set of blanks for crowd-based imputation, whose results could help to adjust the EM-based quality model towards a better one. To achieve this, an adaptive blank selection strategy is proposed to select a sequence of blanks for crowd-based imputation. Also, we work on finding a proper time to stop further crowd intervention for the balance of crowd efficiency and quality improvement. Our experiments performed on three real world and one simulated data collections prove that the proposed quality model can effectively help improve the quality of the web-based imputation results by more than 15 percent, while our crowd cost saving strategy saves more than 75 percent crowd cost.

The intelligent transportation systems, e.g., DiDi and Uber, have served as essential travel tools for customers, which foster plenty of studies for the location-based queries on road network. In particular, given a set O of objects and a query point q on a road network, the k Nearest Neighbor (kNN) query returns the k nearest objects in O with the shortest road network distance to q. In literature, most existing solutions for kNN queries tend to reduce the query time, indexing storage, or throughput of the kNN queries while overlooking the correctness of the queries caused by query-query and update-query conflicts. In our work, we propose a grid-based framework on conflict-aware kNN queries on moving objects which aims to optimize system throughput while guaranteeing query correctness. In particular, we first propose efficient index structures and new query algorithms that significantly improve the throughput. We further present novel scheduling algorithms that aim to avoid conflicts and improve the system throughput. Moreover, we devise approximate solutions that provide a controllable trade-off between the conflict of kNN queries and system throughput. Finally, we propose a cost-based dispatching strategy to assign the kNN results to the corresponding queries. Extensive experiments on real-world data demonstrate the effectiveness and efficiency of our proposed solutions over alternatives.

Semi-supervised cluster ensemble usually introduces a small amount of supervision in the first stage of cluster ensemble, i.e., ensemble generation, by performing many runs of semi-supervised clustering algorithms. However, it is neither efficient in terms of computational complexity, nor flexible in a dynamic learning environment where limited supervision changes over time. In this article we propose a new framework which generates base partitions in an unsupervised manner and attributes different weights to each cluster of the base partitions. The weighting scheme considers both the internal validation measures of clustering and the degrees of satisfaction of pairwise constraints. A weighted co-association matrix based consensus approach is then applied to achieve a final partition. To handle high-dimensional data, we generate base partitions using k-means with both random sampling and random subspace techniques. The new framework retains a high accuracy, and is efficient since it avoids performing semi-supervised clustering in ensemble generation and the complexity of the weighting scheme is independent of the number of instances in a dynamic environment. It is more adaptive than the traditional approach because it does not require rerunning semi-supervised clustering algorithms when the limited supervision changes. Empirical results on 12 datasets demonstrate that it is also more robust to noisy constraints.

Graph Pattern based Node Matching (GPNM) has been proposed to find all the matches of the nodes in a data graph GD based on a given pattern graph GP. GPNM has been increasingly adopted in many applications such as group finding and expert recommendation, in which data graphs are frequently updated overtime. Moreover, many typical pattern graphs frequently and repeatedly appear in users' queries in a short period of time, e.g., social graph searches on Facebook. To deliver a GPNM result in such applications, the existing GPNM methods have to perform an incremental GPNM procedure for each of the updates in the data graph, which is computationally expensive. To address this problem, in this paper, we first analyze the elimination relationships between multiple updates in GD and the hierarchical structure between these elimination relationships. Then, we generate an Elimination Hierarchy Tree (EH-Tree) to index the elimination relationships and propose an EH-Tree based GPNM method, called EHGPNM, considering the elimination relationships between multiple updates in GD. EH-GPNM first delivers the GPNM result of an initial query, and then delivers the GPNM result of a subsequent query, based on the initial GPNM result and the multiple updates of GD that occur between those two queries. The experimental results on five real-world social graphs demonstrate that our proposed EH-GPNM is much more efficient than the state-of-the-art GPNM methods.

Recently accumulated massive amounts of geo-tagged photos provide an excellent opportunity to understand human behaviors and can be used for personalized tour recommendation. However, no existing work has considered the visual content information in these photos for tour recommendation. We believe the visual features of photos provide valuable information on measuring user / Point-of-Interest (POI) similarities, which is challenging due to data sparsity. To this end, in this paper, we propose a visual feature enhanced tour recommender system, named ‘Photo2Trip’, to utilize the visual contents and collaborative filtering models for recommendation. Specifically, we propose a Visual-enhanced Probabilistic Matrix Factorization model (VPMF), which integrates visual features into the collaborative filtering model, to learn user interests by leveraging the historical travel records. We then extend VPMF to End-to-End training framework to incorporate users (POIs) latent factors into the learning process of the visual content of photos, which generalizes the applicability of the proposed VPMF framework in tour recommendation. Extensive empirical studies verify that our proposed visual-enhanced personalized tour recommendation method outperforms other benchmark methods in terms of recommendation accuracy. The results also show that visual features are effective in alleviating the data sparsity and cold start problems on personalized tour recommendation.

Route reconstruction targets at recovering the actual routes of objects moving on an underlying road network from their times-tamped position measurements. This fundamental pre-processing step to many location-based applications has been extensively studied for GPS data, which are object-centric and relatively densely sampled data. In this paper, we investigate the problem of route reconstruction using data collected from road-side Bluetooth scanners. In many cities, Bluetooth scanners are installed in road networks for monitoring the movement of Bluetooth-enabled devices. To address new challenges caused by such reader-centric Bluetooth data including spatial and temporal distortion, a new route reconstruction framework is proposed to transform Bluetooth readings through a family of distortion suppression strategies such that the transformed data can work well with the Hidden Markov model (HMM) map-matching approach. Extensive experiments are conducted to evaluate different transformation strategies with real-world datasets. The experimental results show that when the algorithm uses the baseline or the proposed transformation strategies, the map matching F1 score can be increased by up to 10% depending on the severity of distortion.

Shortest path query is a fundamental operation in various location-based services (LBS) and most of them process queries on the server-side. As the business expands, scalability becomes a severe issue. Instead of simply deploying more servers to cope with the quickly increasing query number, batch shortest path algorithms have been proposed recently to answer a set of queries together using shareable computation. Besides, they can also work in a highly dynamic environment as no index is needed. However, the existing batch algorithms either assume the batch queries are finely decomposed or just process them without differentiation, resulting in poor query efficiency. In this paper, we aim to improve the performance of batch shortest path algorithms by revisiting the problem of query clustering. Specifically, we first propose three query decomposition methods to cluster queries: Zigzag that considers the 1-N shared computation; Search-Space Estimation that further incorporates search space estimation; and Co-Clustering that considers the source and target's spatial locality. After that, we propose two batch algorithms that take advantage of the previously decomposed query sets for efficient query answering: Local Cache that improves the existing Global Cache with higher cache hit ratio, and R2R that finds a set of approximate shortest paths from one region to another with bounded error. Experiments on a large real-world query sets verify the effectiveness and efficiency of our decomposition methods compared with the state-of-the-art batch algorithms.

With the rapid development of mobile networks and the widespread usage of mobile devices, spatial crowdsourcing, which refers to assigning location-based tasks to moving workers, has drawn increasing attention. One of the major issues in spatial crowdsourcing is task assignment, which allocates tasks to appropriate workers. However, existing works generally assume the static offline scenarios, where the spatio-temporal information of all the workers and tasks is determined and known a priori. Ignorance of the dynamic spatio-temporal distributions of workers and tasks can often lead to poor assignment results. In this work we study a novel spatial crowdsourcing problem, namely Predictive Task Assignment (PTA), which aims to maximize the number of assigned tasks by taking into account both current and future workers/tasks that enter the system dynamically with location unknown in advance. We propose a two-phase data-driven framework. The prediction phase hybrids different learning models to predict the locations and routes of future workers and designs a graph embedding approach to estimate the distribution of future tasks. In the assignment component, we propose both greedy algorithm for large-scale applications and optimal algorithm with graph partition based decomposition. Extensive experiments on two real datasets demonstrate the effectiveness of our framework.

In various web applications like targeted advertising and recommender systems, the available categorical features (e.g., product type) are often of great importance but sparse. As a widely adopted solution, models based on Factorization Machines (FMs) are capable of modelling high-order interactions among features for effective sparse predictive analytics. As the volume of web-scale data grows exponentially over time, sparse predictive analytics inevitably involves dynamic and sequential features. However, existing FM-based models assume no temporal orders in the data, and are unable to capture the sequential dependencies or patterns within the dynamic features, impeding the performance and adaptivity of these methods. Hence, in this paper, we propose a novel Sequence-Aware Factorization Machine (SeqFM) for temporal predictive analytics, which models feature interactions by fully investigating the effect of sequential dependencies. As static features (e.g., user gender) and dynamic features (e.g., user interacted items) express different semantics, we innovatively devise a multi-view self-attention scheme that separately models the effect of static features, dynamic features and the mutual interactions between static and dynamic features in three different views. In SeqFM, we further map the learned representations of feature interactions to the desired output with a shared residual network. To showcase the versatility and generalizability of SeqFM, we test SeqFM in three popular application scenarios for FM-based models, namely ranking, classification and regression tasks. Extensive experimental results on six large-scale datasets demonstrate the superior effectiveness and efficiency of SeqFM.

Graph Pattern based Node Matching (GPNM) is to find all the matches of the nodes in a data graph GDbased on a given pattern graph GP. GPNM has become increasingly important in many applications, e.g., group finding and expert recommendation. In real scenarios, both GPand GDare updated frequently. However, the existing GPNM methods either need to perform a new GPNM procedure from scratch to deliver the node matching results based on the updated GPand GDor incrementally perform the GPNM procedure for each of the updates, leading to low efficiency. Therefore, there is a pressing need for a new method to efficiently deliver the node matching results on the updated graphs. In this paper, we first analyze and detect the elimination relationships between the updates. Then, we construct an Elimination Hierarchy Tree (EH-Tree) to index these elimination relationships. In order to speed up the GPNM process, we propose a graph partition method and then propose a new updates-aware GPNM method, called UA-GPNM, considering the single-graph elimination relationships among the updates in a single graph of GPor GD, and also the cross-graph elimination relationships between the updates in GPand the updates in GD. UA-GPNM first delivers the GPNM result of an initial query, and then delivers the GPNM result of a subsequent query, based on the initial GPNM result and the multiple updates that occur between two queries. The experimental results on five real-world social graphs demonstrate that our proposed UA-GPNM is much more efficient than the state-of-the-art GPNM methods.

The set similarity join (SSJ) is core functionality in a range of applications, including data cleaning, near-duplicate object detection, and data integration. Threshold-based SSJ queries return all pairs of sets with similarity no smaller than a given threshold. As results, and their utility, are very sensitive to the choice of threshold value, it is a problem that it is difficult to choose such an appropriate value. Doing so requires prior knowledge of the data, which users often do not have. To avoid this problem, we propose a solution to the top-k overlap set similarity join (TkOSSJ) that returns k pairs of sets with the highest overlap similarities. The state-of-the-art solution disregards the effect of the so-called step size, which is the number of elements accessed in each iteration of the algorithm. This affects its performance negatively. To address this issue, we first propose an algorithm that uses a fixed step size, thus taking advantage of the benefits of a large step size, and then we present an adaptive step size algorithm that is capable of automatically adjusting the step size, thus reducing redundant computations. An extensive empirical study offers insight into the new algorithms and indicates that they are capable of outperforming the state-of-the-art method on real, large-scale data sets.

Visual aesthetics of products plays an important role in the decision process when purchasing appearance-first products, e.g., clothes. Indeed, user’s aesthetic preference, which serves as a personality trait and a basic requirement, is domain independent and could be used as a bridge between domains for knowledge transfer. However, existing work has rarely considered the aesthetic information in product images for cross-domain recommendation. To this end, in this paper, we propose a new deep Aesthetic Cross-Domain Networks (ACDN), in which parameters characterizing personal aesthetic preferences are shared across networks to transfer knowledge between domains. Specifically, we first leverage an aesthetic network to extract aesthetic features. Then, we integrate these features into a cross-domain network to transfer users’ domain independent aesthetic preferences. Moreover, network cross-connections are introduced to enable dual knowledge transfer across domains. Finally, the experimental results on real-world datasets show that our proposed model ACDN outperforms benchmark methods in terms of recommendation accuracy.

Abstract With the pervasiveness of GPS-enabled smart devices and increased wireless communication technologies, spatial crowdsourcing (SC) has drawn increasing attention in assigning location-sensitive tasks to moving workers. In real-world scenarios, for the complex tasks, SC is more likely to assign each task to more than one worker, called group task assignment (GTA), for the reason that an individual worker cannot complete the task well by herself. It is a challenging issue to assign worker groups the tasks that they are interested in and willing to perform. In this paper, we propose a novel framework for group task assignment based on worker groups’ preferences, which includes two components: social impact-based preference modeling (SIPM) and preference-aware group task assignment (PGTA). SIPM employs a bipartite graph embedding model and the attention mechanism to learn the social impact-based preferences of different worker groups on different task categories. PGTA utilizes an optimal task assignment algorithm based on the tree decomposition technique to maximize the overall task assignments, in which we give higher priorities to the worker groups showing more interests in the tasks. We further optimize the original framework by proposing strategies to improve the effectiveness of group task assignment, wherein a deep learning method and the group consensus are taken into consideration. Extensive empirical studies verify that the proposed techniques and optimization strategies can settle the problem nicely.

The pervasiveness of GPS-enabled devices and wireless communication technologies results in massive trajectory data, incurring expensive cost for storage, transmission, and query processing. To relieve this problem, in this paper we propose a novel framework for compressing trajectory data, REST (Reference-based Spatio-temporal trajectory compression), by which a raw trajectory is represented by concatenation of a series of historical (sub-)trajectories (called reference trajectories) that form the compressed trajectory within a given spatio-temporal deviation threshold. In order to construct a reference trajectory set that can most benefit the subsequent compression, we propose three kinds of techniques to select reference trajectories wisely from a large dataset such that the resulting reference set is more compact yet covering most footprints of trajectories in the area of interest. To address the computational issue caused by the large number of combinations of reference trajectories that may exist for resembling a given trajectory, we propose efficient greedy algorithms that run in the blink of an eye and dynamic programming algorithms that can achieve the optimal compression ratio. Compared to existing work on trajectory compression, our framework has few assumptions about data such as moving within a road network or moving with constant direction and speed, and better compression performance with fairly small spatio-temporal loss. In addition, by indexing the reference trajectories directly with an in-memory R-tree and building connections to the raw trajectories with inverted index, we develop an extremely efficient algorithm that can answer spatio-temporal range queries over trajectories in their compressed form. Extensive experiments on a real taxi trajectory dataset demonstrate the superiority of our framework over existing representative approaches in terms of both compression ratio and efficiency.

Video recommendation has become an essential way of helping people explore the massive videos and discover the ones that may be of interest to them. In the existing video recommender systems, the models make the recommendations based on the user-video interactions and single specific content features. When the specific content features are unavailable, the performance of the existing models will seriously deteriorate. Inspired by the fact that rich contents (e.g., text, audio, motion, and so on) exist in videos, in this paper, we explore how to use these rich contents to overcome the limitations caused by the unavailability of the specific ones. Specifically, we propose a novel general framework that incorporates arbitrary single content feature with user-video interactions, named as collaborative embedding regression (CER) model, to make effective video recommendation in both in-matrix and out-of-matrix scenarios. Our extensive experiments on two real-world large-scale datasets show that CER beats the existing recommender models with any single content feature and is more time efficient. In addition, we propose a priority-based late fusion (PRI) method to gain the benefit brought by the integrating the multiple content features. The corresponding experiment shows that PRI brings real performance improvement to the baseline and outperforms the existing fusion methods.

In this paper, we study a new type of spatial crowdsourcing, namely competitive detour tasking, where workers can make detours from their original travel paths to perform multiple tasks, and each worker is allowed to compete for preferred tasks by strategically claiming his/her detour costs. The objective is to make suitable task assignment by maximizing the social welfare of crowdsourcing systems and protecting workers' private sensitive information. We first model the task assignment problem as a reverse auction process. We formalize the winning bid selection of reverse auction as an n-to-one weighted bipartite graph matching problem with multiple 0-1 knapsack constraints. Since this problem is NP-hard, we design an approximation algorithm to select winning bids and determine corresponding payments. Based on this, a Secure Reverse Auction (SRA) protocol is proposed for this novel spatial crowdsourcing. We analyze the approximation performance of the proposed protocol and prove that it has some desired properties, including truthfulness, individual rationality, computational efficiency, and security. To the best of our knowledge, this is the first theoretically provable secure auction protocol for spatial crowdsourcing systems. In addition, we also conduct extensive simulations on a real trace to verify the performance of the proposed protocol.

With the proliferation of GPS-enabled smart devices and increased availability of wireless network, spatial crowdsourcing (SC) has been recently proposed as a framework to automatically request workers (i.e., smart device carriers) to perform location-sensitive tasks (e.g., taking scenic photos, reporting events). In this paper, we study a destination-aware task assignment problem that concerns the optimal strategy of assigning each task to proper worker such that the total number of completed tasks can be maximized whilst all workers can reach their destinations before deadlines after performing assigned tasks. Finding the global optimal assignment turns out to be an intractable problem since it does not imply optimal assignment for individual worker. Observing that the task assignment dependency only exists amongst subsets of workers, we utilize tree-decomposition technique to separate workers into independent clusters and develop an efficient depth-first search algorithm with progressive bounds to prune non-promising assignments. In order to make our proposed framework applicable to more scenarios, we further optimize the original framework by proposing strategies to reduce the overall travel cost and allow each task to be assigned to multiple workers. Extensive empirical studies verify that the proposed technique and optimization strategies perform effectively and settle the problem nicely.

With the proliferation of geo-textual objects on the web, extensive efforts have been devoted to improving the efficiency of top-k spatial keyword queries in different settings. However, comparatively much less work has been reported on enhancing the quality and usability of such queries. In this context, we propose means of enhancing the usability of a top-k group spatial keyword query, where a group of users aim to find k objects that contain given query keywords and are nearest to the users. Specifically, when users receive the result of such a query, they may find that one or more objects that they expect to be in the result are in fact missing, and they may wonder why. To address this situation, we develop a so-called why-notquery that is able to minimally modifythe original query into a query that returns the expected, but missing, objects, in addition to other objects. Specifically, we formalize the why-not query in relation to the top-k group spatial keyword query, called the Why-not Group Spatial Keyword Query (WGSK) that is able to provide a group of users with a more satisfactory query result. We propose a three-phase framework for efficiently computing the WGSK. The first phase substantially reduces the search space for the subsequent phases by retrieving a set of objects that may affect the ranking of the user-expected objects. The second phase provides an incremental sampling algorithm that generates candidate weightings of more promising queries. The third phase determines the penalty of each refined query and returns the querywith minimal penalty, i.e., the minimally modified query. Extensive experiments with real and synthetic data offer evidence that the proposed solution excels over baselines with respect to both effectiveness and efficiency.

Distant supervision is an efficient way to generate large-scale training data for relation extraction without human efforts. However, a coin has two sides. The automatically annotated labels for training data are problematic, which can be summarized as multi-instance multi-label problem and coarse-grained (bag-level) supervised signal. To address these problems, we propose two reasonable assumptions and craft reinforcement learning to capture the expressive sentence for each relation mentioned in a bag. More specifically, we extend the original expressed-at-least-once assumption to multi-label level, and introduce a novel express-at-most-one assumption. Besides, we design a fine-grained reward function, and model the sentence selection process as an auction where different relations for a bag need to compete together to achieve the possession of a specific sentence based on its expressiveness. In this way, our model can be dynamically self-adapted, and eventually implements the accurate one-to-one mapping from a relation label to its chosen expressive sentence, which serves as training instances for the extractor. The experimental results on a public dataset demonstrate that our model constantly and substantially outperforms current state-of-the-art methods for relation extraction.

Route scheduling on time-dependent road network is slow due to its problem complexity of Ω(T(|V|log |V|+|E|)), where T is the size of the result's time-dependent function, |V| is the number of vertices and |E| is the number of edges. To make things worse, T grows larger as the route becomes longer or the query time interval becomes bigger, especially for a fastest path profile query whose time interval is 24 hours. In this paper, we aim to answer the fastest path profile query on time-dependent road network faster by extending the 2-hop labeling approach, which is fast in answering shortest distance query on the static graph. However, building an index on a time-dependent graph is both time and space consuming, so currently only online-search approach exist. Apparently, its query answering power is limited by the online searching. To solve this problem, we first propose the time-dependent hop on large road network by partitioning it into smaller sub-graphs. The index is built within and between the partitions, and is retrieved from disk during query answering with the help of sampling. Moreover, we propose an online approximation technique AT-Dijkstra and a bottom-up compression method to further reduce the label size, save construction time and speedup query answering. Experiments on real world road network show that our approach outperforms the state-of-art fastest path index approaches and can speed up the query answering by hundreds of times.

Given a set O of objects and a query point q on a road network, the k Nearest Neighbor (kNN) query returns the k nearest objects in O with the shortest road network distance to q. These kNN queries find many applications in location-based services, e.g., ride-hailing services, where each taxi is regarded as an object. In such applications, objects are constantly moving such that even for the same query point, the correct answer of a kNN query may vary with time. Ideally, the returned answer should be adequately correct with respect to the moving object set. However, in literature, all existing solutions for kNN queries mainly focus on reducing the query time, indexing storage, or throughput of the kNN queries with little focus on their correctness. Motivated by this, we propose a framework on correctness-aware kNN queries which aim to optimize system throughput while guaranteeing query correctness on moving objects. We formally define the serializable-kNN query that ensures the correctness of the query answer when considering moving objects and dependencies of different queries. We propose several techniques to optimize the throughput of serializable-kNN queries: firstly, we propose efficient index structures and new query algorithms that significantly improve the throughput; we further present novel scheduling algorithms that aim to avoid conflicts and improve the system throughput. Moreover, we devise approximate solutions that provide a controllable trade-off between the correctness of kNN queries and system throughput. Extensive experiments on real-world data demonstrate the effectiveness and efficiency of our proposed solutions over alternatives.

The prevalent adoption of GPS-enabled devices has witnessed an explosion of various location-based services which produce a huge amount of trajectories monitoring an individual's movement. This triggers an interesting question: is movement history sufficiently representative and distinctive to identify an individual? In this work, we study the problem of moving object linking based on their historical traces. However, it is non-trivial to extract effective patterns from moving history and meanwhile conduct object linking efficiently. To this end, we propose four representation strategies (sequential, temporal, spatial, and spatiotemporal) and two quantitative criteria (commonality and unicity) to construct the personalised signature from the historical trace. Moreover, we formalise the problem of moving object linking as a k-nearest neighbour (k-NN) search on the collection of signatures, and aim to improve efficiency considering the high dimensionality of signatures and the large cardinality of the candidate object set. A simple but effective dimension reduction strategy is introduced in this work, which empirically outperforms existing algorithms including PCA and LSH. We propose a novel indexing structure, Weighted R-tree (WR-tree), and two pruning methods to further speed up k-NN search by combining weight and spatial information contained in the signature. Our extensive experimental results on a real world dataset verify the superiority of our proposals, in terms of both accuracy and efficiency, over state-of-the-art approaches.

In this demonstration, we present an end-to-end web-aided data imputation prototype system named WebPut. WebPut consults the Web for imputing the missing values in a local database when the traditional inferring-based imputation method has difficulties in getting the right answers. Specifically, WebPut investigates the interaction between the local inferring-based imputation methods and the web-based retrieving methods and shows that retrieving a small number of selected missing values can greatly improve the imputation recall of the inferring-based methods. Besides, WebPut also incorporates a crowd intervention component that can get advice from humans in case that the web-based imputation methods may have difficulties in making the right decisions. We demonstrate, step by step, how WebPut fills an incomplete table with each of its components.

Location-aware services have become widely available on a variety of devices. The resulting fusion of spatio-textual data enables the kind of top-k query that takes into account both location proximity and text relevance. Considering both the misspellings in user input and the data quality issues of spatiotextual databases, it is necessary to support error-tolerant spatial keyword search for end-users. Existing studies mainly focused on set-based textual relevance, but they cannot find reasonable results when the input tokens are not exactly matched with those from records in the database. In this paper, we propose a novel framework to solve the problem of top-k location-aware similarity search with fuzzy token matching. We propose a hierarchical index HGR-Tree to capture signatures of both spatial and textual relevance. Based on such an index structure, we devise a best-first search algorithm to preferentially access nodes of HGR-Tree with more similar objects while those with dissimilar ones can be pruned. We further devise an incremental search strategy to reduce the overhead brought by supporting fuzzy token matching. Experimental results on real world POI datasets show that our framework outperforms state-of-the-art methods by one to two orders of magnitude.

As social animals, attending group activities is an indispensable part in people's daily social life, and it is an important task for recommender systems to suggest satisfying activities to a group of users. The major challenge in this task is how to aggregate personal preferences of group members to infer the decision of a group. Conventional group recommendation methods applied a predefined strategy for preference aggregation. However, these static strategies are too simple to model the real and complex process of group decision-making, especially for occasional groups which are formed ad-hoc. Moreover, group members should have non-uniform influences or weights in a group, and the weight of a user can be varied in different groups. Therefore, an ideal group recommender system should be able to accurately learn not only users' personal preferences but also the preference aggregation strategy from data. In this paper, we propose a novel group recommender system, namely SIGR (short for "Social Influence-based Group Recommender"), which takes an attention mechanism and a bipartite graph embedding model BGEM as building blocks. Specifically, we adopt an attention mechanism to learn each user's social influence and adapt their social influences to different groups and develop a novel deep social influence learning framework to exploit and integrate users' global and local social network structure information to further improve the estimation of users' social influences. BGEM is extended to model group-item interactions. In order to overcome the limitation and sparsity of the interaction data generated by occasional groups, we propose two model optimization approaches to seamlessly integrate the user-item interaction data. We create two large-scale benchmark datasets and conduct extensive experiments on them. The experimental results show the superiority of our proposed SIGR by comparing with state-of-the-art group recommender models.

With the proliferation of geo-textual objects on the web, extensive efforts have been devoted to improving the efficiency of top-k spatial keyword queries in different settings. However, comparatively much less work has been reported on enhancing the quality and usability of such queries. In this context, we propose means of enhancing the usability of a top-k group spatial keyword query, where a group of users aim to find k objects that contain given query keywords and are nearest to the users. Specifically, when users receive the result of such a query, they may find that one or more objects that they expect to be in the result are in fact missing, and they may wonder why. To address this situation, we develop a so-called why-not query that is able to minimally modify the original query into a query that returns the expected, but missing, objects, in addition to other objects. Specifically, we formalize the why-not query in relation to the top-k group spatial keyword query, called the Why-not Group Spatial Keyword Query (WGSK) that is able to provide a group of users with a more satisfactory query result. We propose a three-phase framework for efficiently computing he WGSK. Extensive experiments with real and synthetic data offer evidence that the proposed solution excels over baselines with respect to both effectiveness and efficiency.

Finding the shortest path from one place to another is an essential operation for various location-based services (LBS), and most of the computations run on the server side. However, as the business grows, the service providers are facing an increasing swarm of path requests submitted during a short time period. The most straightforward solution is deploying more servers, while the operation cost increases at the same time. Therefore, in this work, we aim to improve the efficiency algorithmically by answering a large set of shortest path queries in a batch and reusing sharable computations. Specifically, we first propose the petal A*-1N algorithm to process 1-N shortest path queries by batch without repeated computation. Then we introduce several decomposition methods to cluster the start/target set and answer the whole query set with zigzag scheduling methods to further reduce the total running time. Extensive evaluations on both synthetic and real-world data verify the superiority of our algorithm compared with state-of-the-art methods.

The recent art in relation extraction is distant supervision which generates training data by heuristically aligning a knowledge base with free texts and thus avoids human labelling. However, the concerned relation mentions often use the bag-of-words representation, which ignores inner correlations between features located in different dimensions and makes relation extraction less effective. To capture the complex characteristics of relation expression and tighten the correlated features, we attempt to discover and utilise informative correlations between features by the following four phases: 1) formulating semantic similarities between lexical features using the embedding method; 2) constructing generative relation for lexical features with different sizes of side windows; 3) computing correlation scores between syntactic features through a kernel-based method; and 4) conducting a distillation process for the obtained correlated feature pairs and integrating informative pairs with existing relation extraction models. The extensive experiments demonstrate that our method can effectively discover correlation information and improve the performance of state-of-the-art relation extraction methods.

The sequential recommendation, which models sequential behavioral patterns among users for the recommendation, plays a critical role in recommender systems. However, the state-of-the-art Recurrent Neural Networks (RNN) solutions rarely consider the non-linear feature interactions and non-monotone short-term sequential patterns, which are essential for user behavior modeling in sparse sequence data. In this paper, we propose a novel Recurrent Convolutional Neural Network model (RCNN). It not only utilizes the recurrent architecture of RNN to capture complex long-term dependencies, but also leverages the convolutional operation of Convolutional Neural Network (CNN) model to extract short-term sequential patterns among recurrent hidden states. Specifically, we first generate a hidden state at each time step with the recurrent layer. Then the recent hidden states are regarded as an “image”, and RCNN searches non-linear feature interactions and non-monotone local patterns via intra-step horizontal and inter-step vertical convolutional filters, respectively. Moreover, the output of convolutional filters and the hidden state are concatenated and fed into a fully-connected layer to generate the recommendation. Finally, we evaluate the proposed model using four real-world datasets from various application scenarios. The experimental results show that our model RCNN significantly outperforms the state-of-the-art approaches on sequential recommendation.

In many surveillance applications, capture devices are set on fixed locations to track entities, leading to valuable spatio-temporal trajectories. However, sometimes the IDs of the entities in these trajectories are incorrectly identified due to various reasons (e.g., illumination conditions and partial occlusion). Since very often the movements of the entities are constrained by certain restrictions imposed by the application (e.g., vehicles must move along the given road network), we consider how to repair the erroneous IDs using transition graphs derived from such restrictions. Roughly speaking, the occurrence of erroneous IDs can cause a valid trajectory to be broken into trajectory fragments that violate some movement constraints imposed by the transition graph, and we aim to repair them by rewriting the IDs and merging the fragments. This problem is practically challenging since it is not easy to judge which IDs in the dataset are correct, and also there may be multiple candidates as the correct value for a single error. We formulate the repair process as an optimization problem and propose a two-phase repair paradigm, which includes candidate repair generation and compatible repair selection, to maximize the quality improvement estimated by a designed objective function. Though both phases are intractable, we propose effective algorithms to solve them through exploiting the locality and sparsity of trajectories. We further devise an index structure, as well as a pruning method to make the repair process more efficient. Experiments on both real and synthetic datasets demonstrate the effectiveness and efficiency of the proposed methods. © 2018 Copyright held by the owner/author(s)

Sources of complementary information are connected when we link the user accounts belonging to the same user across different domains or devices. The expanded information promotes the development of a wide range of applications, such as cross-domain prediction, cross-domain recommendation, and advertisement. Due to the great significance of user account linkage, there are increasing research works on this study. With the widespread popularization of GPS-enabled mobile devices, linking user accounts with location data has become an important and promising research topic. Being different from most existing studies in this domain that only focus on the effectiveness, we propose novel approaches to improve both effectiveness and efficiency of user account linkage. In this paper, a kernel density estimation (KDE) based method has been proposed to improve the accuracy by alleviating the data sparsity problem in measuring users' similarities. To improve the efficiency, we develop a grid-based structure to organize location data to prune the search space. The extensive experiments conducted on two real-world datasets demonstrate the superiority of the proposed approach in terms of both effectiveness and efficiency compared with the state-of-art methods.

Crowdsourcing has been widely established as a means to enable human computation at large-scale, in particular for tasks that require manual labelling of large sets of data items. Answers obtained from heterogeneous crowd workers are aggregated to obtain a robust result. However, existing methods for answer aggregation are designed for \\emph{discrete} tasks, where answers are given as a single label per item. In this paper, we consider \\emph{partial-agreement} tasks that are common in many applications such as image tagging and document annotation, where items are assigned sets of labels. Going beyond the state-of-the-art, we propose a novel Bayesian nonparametric model to aggregate the partial-agreement answers in a generic way. This model enables us to compute the consensus of partially-sound and partially-complete worker answers, while taking into account mutual relations in labels and different answer sets. An evaluation of our method using real-world datasets reveals that it consistently outperforms the state-of-the-art in terms of precision, recall, and scalability.

Graph Pattern based Node Matching (GPNM) is to find all the matches of the nodes in a data graph GD based on a given pattern graph GP. GPNM has become increasingly important in many applications, e.g., group finding and expert recommendation. In real scenarios, both GP and GD are updated frequently. However, the existing GPNM methods need to perform a new GPNM procedure from scratch to deliver the node matching results based on the updated GP and updated GD, which consumes much time. Therefore, there is a pressing need for a novel method to efficiently deliver the node matching results. In this paper, we propose a novel INCremental GPNM method called INC-GPNM, where we first build up indices to incrementally maintain the shortest path length range between different label types in GD, and then identify the affected parts of GD in GPNM including nodes and edges w.r.t. the updates of GP and GD. Moreover, based on the index structure and our novel search strategies, INC-GPNM can efficiently deliver node matching results taking the updates of GP and GD as input, and can greatly save the query processing time with improved time complexity. The extensive experiments on five real-world social graphs demonstrate that our method greatly outperforms the state-of-the-art GPNM method in efficiency.

With the prevalent trend of combining online and offline interactions among users in event-based social networks (EBSNs), event recommendation has become an essential means to help people discover new interesting events to attend. However, existing literatures on event recommendations ignore the social attribute of events: people prefer to attend events with their friends or family rather than alone. Therefore, we propose a new recommendation paradigm: joint event-partner recommendation that focuses on recommending event-partner pairs to users. In this paper, we focus on the new problem of joint event-partner recommendation in EBSNs, which is extremely challenging due to the intrinsic cold-start property of events, the complex decision-making process for choosing event-partner pairs and the huge prediction space of event-partner combinations. We propose a generic graph-based embedding model (GEM) to collectively embed all the observed relations among users, events, locations, time and text content in a shared low-dimension space, which is able to leverage the correlation between events and their associated content and contextual information to address the cold-start issue effectively. To accelerate the convergence of GEM and improve its modeling accuracy, an adaptive noise sampler is developed to generate adversarial negative samples in the model optimization. Besides, to speed up the online recommendation, we propose a novel space transformation method to project each event-partner pair to one point in a new space and then develop effective space pruning and efficient online recommendation techniques. We conduct comprehensive experiments on our created real benchmark datasets, and the experimental results demonstrate the superiority of our proposals in terms of recommendation effectiveness, efficiency and scalability

With the advances in geo-positioning technologies and location-based services, it is nowadays quite common for road networks to have textual contents on the vertices. Previous work on identifying an optimal route that covers a sequence of query keywords has been studied in recent years. However, in many practical scenarios, an optimal route might not always be desirable. Therefore, in this paper, we investigate the problem of clue-based route search (CRS), which allows a user to provide clues on keywords and spatial relationships. First, we propose a greedy algorithm and a dynamic programming algorithm as baselines. To improve efficiency, we develop a branch-and-bound algorithm that prunes unnecessary vertices in query processing. In order to quickly locate candidate, we propose an AB-tree that stores both the distance and keyword information in tree structure. To further reduce the index size, we construct a PB-tree by utilizing the virtue of 2-hop label index to pinpoint the candidate. Extensive experiments are conducted and verify the superiority of our algorithms and index structures.

As a common strategy in sales-supply chains, the prediction of sales volume offers precious information for companies to achieve a healthy balance between supply and demand. In practice, the sales prediction task is formulated as a time series prediction problem which aims to predict the future sales volume for different products with the observation of various influential factors (e.g., brand, season, discount, etc.) and corresponding historical sales records. However, with the development of contemporary commercial markets, the dynamic interaction between influential factors with different semantic meanings becomes more subtle, causing challenges in fully capturing dependencies among these variables. Besides, though seeking similar trends from the history benefits the accuracy for the prediction of upcoming sales, existing methods hardly suit sales prediction tasks because the trends in sales time series are more irregular and complex. Hence, we gain insights from the encoder-decoder recurrent neural network (RNN) structure, and propose a novel framework named TADA to carry out trend alignment with dualattention, multi-task RNNs for sales prediction. In TADA, we innovatively divide the influential factors into internal feature and external feature, which are jointly modelled by a multi-task RNN encoder. In the decoding stage, TADA utilizes two attention mechanisms to compensate for the unknown states of influential factors in the future and adaptively align the upcoming trend with relevant historical trends to ensure precise sales prediction. Experimental results on two real-world datasets comprehensively show the superiority of TADA in sales prediction tasks against other state-of-the-art competitors.

Given a pair of Origin-Destination (OD) locations, the set of trajectories passing from the original to destination, usually possesses the nature to reflect different traveling patterns between OD. In general, the higher diversity these trajectories have, the more various traveling behaviors and greater robustness of the connectivity can be revealed, which highly raises the value of transportation analysis towards the corresponding OD pair. Therefore, in this paper, we introduce a comprehensive and rational measure for trajectory diversity, on top of which we propose a novel query, Top-k Diversified Search (TkDS), that aims to find a set of k OD pairs among all the given OD pairs such that the trajectories traversing in-between have the highest diversity. Owing to the intrinsic characteristics of trajectory data, the computational cost for diversity is considerably high. Thus we present an efficient bounding algorithm with early termination to filter the candidates that are impossible to contribute the result. Finally, we demonstrate some case studies for trajectory diversity on real world dataset and give a comprehensive performance evaluation on the Top-k Diversified Search.

An alarm is raised due to a defect in a transportation system. Given a graph over which the alarms propagate, we aim to exploit a set of subgraphs with highly correlated nodes (or entities). The edge weight between each pair of entities can be computed using the temporal dynamics of the propagation process. We retrieve the top k edge weights and each group of connected entities can consequently form a tightly coupled subgraph. However, numerous challenges abound. First, the textual contents associated with the alarms of the same type differ during the propagation process. Hence, in the lack of textual data, the temporal information can only be employed to compute the correlation weights. Second, in many scenarios, the same alarm does not propagate. Third, given a pair of entities, the propagation can occur in both directions. Most of the prior work only consider the time-window and assume that the propagation between a pair of entities occurs sequentially. But, the propagation process should be inferred using miscellaneous temporal features. Therefore, we devise a generative approach that, on the one hand, utilizes infinite temporal latent factors (e.g. hour, day, and etc.) to compute the correlation weights, and on the other hand, analyzes how an alarm in one entity can cause a set of alarms in another. We also conduct an extensive set of experiments to compare the performance of the subgraph mining methods. The results show that our unified framework can effectively exploit the tightly coupled subgraphs.

Measuring the similarity (or distance) between trajectories of moving objects is a common procedure taken by most trajectory data-driven applications. One of the biggest challenges of trajectory distances measurement is that the distance needs to be carefully defined in order to reflect the true underlying similarity. This is due to the fact that trajectories are essentially non-uniform sequential data with variable length, attached with both spatial and temporal attributes, which may or may not be considered for similarity measures. Therefore, tens of similarity measures for trajectory data have been proposed; every technique claim an advantage over the others in a different aspect. Hence, it's difficult for users to choose the best-suited technique, as well as the appropriate parameter values, since each technique has distinct performance and characteristics depending on various factors. In this paper, we develop an application that allows to evaluate several techniques in different aspects (accuracy, sensitivity to trajectory features, performance, etc.). We believe that this tool will be able to serve as a practical guideline for both researchers and developers. While researchers can use our tool to assess existing or new techniques, developers can reuse its components to reduce the development complexity.

With the rapid development of location-based social networks (LBSNs), spatial item recommendation has become an important way of helping users discover interesting locations to increase their engagement with location-based services. The availability of spatial, temporal, and social information in LBSNs offers an unprecedented opportunity to enhance the spatial item recommendation. Many previous works studied spatial and social influences on spatial item recommendation in LBSNs. Due to the strong correlations between a user’s check-in time and the corresponding check-in location, which include the sequential influence and temporal cyclic effect, it is essential for spatial item recommender system to exploit the temporal effect to improve the recommendation accuracy. Leveraging temporal information in spatial item recommendation is, however, very challenging, considering (1) when integrating sequential influences, users’ check-in data in LBSNs has a low sampling rate in both space and time, which renders existing location prediction techniques on GPS trajectories ineffective, and the prediction space is extremely large, with millions of distinct locations as the next prediction target, which impedes the application of classical Markov chain models; (2) there are various temporal cyclic patterns (i.e., daily, weekly, and monthly) in LBSNs, but existing work is limited to one specific pattern; and (3) there is no existing framework that unifies users’ personal interests, temporal cyclic patterns, and the sequential influence of recently visited locations in a principled manner. In light of the above challenges, we propose a Temporal Personalized Model ( TPM ), which introduces a novel latent variable topic-region to model and fuse sequential influence, cyclic patterns with personal interests in the latent and exponential space. The advantages of modeling the temporal effect at the topic-region level include a significantly reduced prediction space, an effective alleviation of data sparsity, and a direct expression of the semantic meaning of users’ spatial activities. Moreover, we introduce two methods to model the effect of various cyclic patterns. The first method is a time indexing scheme that encodes the effect of various cyclic patterns into a binary code. However, the indexing scheme faces the data sparsity problem in each time slice. To deal with this data sparsity problem, the second method slices the time according to each cyclic pattern separately and explores these patterns in a joint additive model. Furthermore, we design an asymmetric Locality Sensitive Hashing (ALSH) technique to speed up the online top- k recommendation process by extending the traditional LSH. We evaluate the performance of TPM on two real datasets and one large-scale synthetic dataset. The performance of TPM in recommending cold-start items is also evaluated. The results demonstrate a significant improvement in TPM’s ability to recommend spatial items, in terms of both effectiveness and efficiency, compared with the state-of-the-art methods.

Crowdsourcing has been widely established as a means to enable human computation at large-scale, in particular for tasks that require manual labelling of large sets of data items. Answers obtained from heterogeneous crowd workers are aggregated to obtain a robust result. However, existing methods for answer aggregation are designed for discrete tasks, where answers are given as a single label per item. In this paper, we consider-partial-agreement-tasks that are common in many applications such as image tagging and document annotation, where items are assigned sets of labels. Common approaches for the aggregation of partial-agreement answers either (i) reduce the problem to several instances of an aggregation problem for discrete tasks or (ii) consider each label independently. Going beyond the state-of-the-art, we propose a novel Bayesian nonparametric model to aggregate the partial-agreement answers in a generic way. This model enables us to compute the consensus of partially-sound and partially-complete worker answers, while taking into account mutual relationships in labels and different answer sets. We also show how this model is instantiated for incremental learning, incorporating new answers from crowd workers as they arrive. An evaluation of our method using real-world datasets reveals that it consistently outperforms the state-of-the-art in terms of precision, recall, and robustness against faulty workers and data sparsity.

Semantic drift is a common problem in iterative information extraction. Previous approaches for minimizing semantic drift may incur substantial loss in recall. We observe that most semantic drifts are introduced by a small number of questionable extractions in the earlier rounds of iterations. These extractions subsequently introduce a large number of questionable results, which lead to the semantic drift phenomenon. We call these questionable extractions Drifting Points (DPs). If erroneous extractions are the “symptoms” of semantic drift, then DPs are the “causes” of semantic drift. In this paper, we propose a method to minimize semantic drift by identifying the DPs and removing the effect introduced by the DPs. We use isA (concept-instance) extraction as an example to describe our approach in cleaning information extraction errors caused by semantic drift, but we perform experiments on different relation extraction processes on three large real data extraction collections. The experimental results show that our DP cleaning method enables us to clean around 90 percent incorrect instances or patterns with about 90 percent precision, which outperforms the previous approaches we compare with.

Graph Pattern Matching (GPM) has been used in lots of areas, like biology, medical science, and physics. With the advent of Online Social Networks (OSNs), recently, GPM has been playing a significant role in social network analysis, which has been widely used in, for example, finding experts, social community mining, and social position detection. Given a query which contains a pattern graph GQand a data graph GD, a GPM algorithm finds those subgraphs, GM, that match GQin GD. However, the existing GPM methods do not consider the multiple end-to-end constraints of the social contexts, like social relationships, social trust, and social positions on edges in GQ, which are commonly found in various applications, such as crowdsourcing travel, social network based ecommerce, and study group selection, etc. In this paper, we first conceptually extend Bounded Simulation to Multi-Constrained Simulation (MCS), and propose a novel NP-Complete Multi-Constrained Graph Pattern Matching (MC-GPM) problem. Then, to address the efficiency issue in large-scale MC-GPM, we propose a new concept called Strong Social Component (SSC), consisting of participants with strong social connections. We also propose an approach to identifying SSCs, and propose a novel index method and a graph compression method for SSC. Moreover, we devise a multithreading heuristic algorithm, called M-HAMC, to bidirectionally search the MC-GPM results in parallel without decompressing graphs. An extensive empirical study over five real-world large-scale social graphs has demonstrated the effectiveness and efficiency of our approach.

Cross-device and cross-domain user linkage have been attracting a lot of attention recently. An important branch of the study is to achieve user linkage with spatio-temporal data generated by the ubiquitous GPS-enabled devices. The main task in this problem is twofold, i.e., how to extract the representative features of a user; how to measure the similarities between users with the extracted features. To tackle the problem, we propose a novel model STUL (Spatio-Temporal User Linkage) that consists of the following two components. 1) Extract users - spatial features with a density based clustering method, and extract the users - temporal features with the Gaussian Mixture Model. To link user pairs more precisely, we assign different weights to the extracted features, by lightening the common features and highlighting the discriminative features. 2) Propose novel approaches to measure the similarities between users based on the extracted features, and return the pair-wise users with similarity scores higher than a predefined threshold. We have conducted extensive experiments on three real-world datasets, and the results demonstrate the superiority of our proposed STUL over the state-of-the-art methods.

Schema Matching (SM) and Record Matching (RM) are two necessary steps in integrating multiple relational tables of different schemas, where SM unifies the schemas and RM detects records referring to the same real-world entity. The two processes have been thoroughly studied separately, but few attention has been paid to the interaction of SM and RM. In this work we find that, even alternating them in a simple manner, SM and RM can benefit from each other to reach a better integration performance (i.e., in terms of precision and recall). Therefore, combining SM and RM is a promising solution for improving data integration.

With the rapid prevalence of smart mobile devices and the dramatic proliferation of mobile applications (Apps), App recommendation becomes an emergent task that will benefit different stockholders of mobile App ecosystems. Unlike traditional items, Apps have privileges to access a user's sensitive resources (e.g., contacts, messages and locations) which may lead to security risk or privacy leak. Thus, users' choosing of Apps are influenced by not only their personal interests but also their privacy preferences. Moreover, user privacy preferences vary with App categories. In this paper, we propose a mobile sparse additive generative model (Mobi-SAGE) to recommend Apps by considering both user interests and category-aware user privacy preferences. We collected a real-world dataset from 360 App store - the biggest Android App platform in China, and conduct extensive experiments on it. The experimental results show that our Mobi-SAGE consistently and significantly outperforms the state-of-the-art approaches, which implies the importance of exploiting category-aware user privacy preferences.

On time-dependent graphs, fastest path query is an important problem and has been well studied. It focuses on minimizing the total travel time (waiting time + on-road time) but does not allow waiting on any intermediate vertex if the FIFO property is applied. However, in practice, waiting on a vertex can reduce the time spent on the road (for example, resuming traveling after a traffic jam). In this paper, we study how to find a path with the minimal on-road time on time-dependent graphs by allowing waiting on some predefined parking vertices. The existing works are based on the following fact: the arrival time of a vertex v is determined by the arrival time of its in-neighbor u , which does not hold in our scenario since we also consider the waiting time on u if u allows waiting. Thus, determining the waiting time on each parking vertex to achieve the minimal on-road time becomes a big challenge, which further breaks FIFO property. To cope with this challenging problem, we propose two efficient algorithms using minimum on-road travel cost function to answer the query. The evaluations on multiple real-world time-dependent graphs show that the proposed algorithms are more accurate and efficient than the extensions of existing algorithms. In addition, the results further indicate, if the parking facilities are enabled in the route scheduling algorithms, the on-road time will reduce significantly compared to the fastest path algorithms.

Along with the proliferation of online digital map and location-based service, very large POI (point of interest) databases have been constructed where a record corresponds to a POI with information including name, category, address, geographical location and other features. A basic spatial query in POI database is POI retrieval. In many scenarios, a user cannot provide enough information to pinpoint the POI except some clue. For example, a user wants to identify a caf é in a city visited many years ago. SHe cannot remember the name and address but she still recalls that "the caf é is about 200 meters away from a restaurant; and turning left at the restaurant there is a bakery 500 meters away, etc.". Intuitively, the clue, even partial and approximate, describes the spatio-textual context around the targeted POI. Motivated by this observation, this work investigates clue-based spatio-textual query which allows user providing clue, i.e., some nearby POIs and the spatial relationships between them, in POI retrieval. The objective is to retrieve k POIs from a POI database with the highest spatio-textual context similarities against the clue. This work has deliberately designed data-quality-tolerant spatio-textual context similarity metric to cope with various data quality problems in both the clue and the POI database. Through crossing valuation, the query accuracy is further enhanced by ensemble method. Also, this work has developed an index called roll-out-star R-tree (RSR-tree) to dramatically improve the query processing efficiency. The extensive tests on data sets from the real world have verified the superiority of our methods in all aspects.

With the rapid development of location-based social networks (LBSNs), spatial item recommendation has become an important mobile application, especially when users travel away from home. However, this type of recommendation is very challenging compared to traditional recommender systems. A user may visit only a limited number of spatial items, leading to a very sparse user-item matrix. This matrix becomes even sparser when the user travels to a distant place, as most of the items visited by a user are usually located within a short distance from the user’s home. Moreover, user interests and behavior patterns may vary dramatically across different time and geographical regions. In light of this, we propose ST-SAGE, a spatial-temporal sparse additive generative model for spatial item recommendation in this article. ST-SAGE considers both personal interests of the users and the preferences of the crowd in the target region at the given time by exploiting both the co-occurrence patterns and content of spatial items. To further alleviate the data-sparsity issue, ST-SAGE exploits the geographical correlation by smoothing the crowd’s preferences over a well-designed spatial index structure called the spatial pyramid . To speed up the training process of ST-SAGE, we implement a parallel version of the model inference algorithm on the GraphLab framework. We conduct extensive experiments; the experimental results clearly demonstrate that ST-SAGE outperforms the state-of-the-art recommender systems in terms of recommendation effectiveness, model training efficiency, and online recommendation efficiency.

Schema Matching (SM) and Record Matching (RM) are two necessary steps in integrating multiple relational tables of different schemas, where SM unifies the schemas and RM detects records referring to the same real-world entity. The two processes have been thoroughly studied separately, but few attention has been paid to the interaction of SM and RM. In this work, we find that, even alternating them in a simple manner, SM and RM can benefit from each other to reach a better integration performance (i.e., in terms of precision and recall). Therefore, combining SM and RM is a promising solution for improving data integration. To this end, we define novel matching rules for SM and RM, respectively, that is, every SM decision is made based on intermediate RM results, and vice versa, such that SM and RM can be performed alternately. The quality of integration is guaranteed by a Matching Likelihood Estimation model and the control of semantic drift, which prevent the effect of mismatch magnification. To reduce the computational cost, we design an index structure based on q-grams and a greedy search algorithm that can reduce around 90 percent overhead of the interaction. Extensive experiments on three data collections show that the combination and interaction between SM and RM significantly outperforms previous works that conduct SM and RM separately.

Understanding short texts is crucial to many applications, but challenges abound. First, short texts do not always observe the syntax of a written language. As a result, traditional natural language processing tools, ranging from part-of-speech tagging to dependency parsing, cannot be easily applied. Second, short texts usually do not contain sufficient statistical signals to support many state-of-the-art approaches for text mining such as topic modeling. Third, short texts are more ambiguous and noisy, and are generated in an enormous volume, which further increases the difficulty to handle them. We argue that semantic knowledge is required in order to better understand short texts. In this work, we build a prototype system for short text understanding which exploits semantic knowledge provided by a well-known knowledgebase and automatically harvested from a web corpus. Our knowledge-intensive approaches disrupt traditional methods for tasks such as text segmentation, part-of-speech tagging, and concept labeling, in the sense that we focus on semantics in all these tasks. We conduct a comprehensive performance evaluation on real-life data. The results show that semantic knowledge is indispensable for short text understanding, and our knowledge-intensive approaches are both effective and efficient in discovering semantics of short texts.

Point-of-interest (POI) recommendation has become an important way to help people discover attractive and interesting places, especially when they travel out of town. However, the extreme sparsity of user-POI matrix and cold-start issues severely hinder the performance of collaborative filtering-based methods. Moreover, user preferences may vary dramatically with respect to the geographical regions due to different urban compositions and cultures. To address these challenges, we stand on recent advances in deep learning and propose a Spatial-Aware Hierarchical Collaborative Deep Learning model (SH-CDL). The model jointly performs deep representation learning for POIs from heterogeneous features and hierarchically additive representation learning for spatial-aware personal preferences. To combat data sparsity in spatial-aware user preference modeling, both the collective preferences of the public in a given target region and the personal preferences of the user in adjacent regions are exploited in the form of social regularization and spatial smoothing. To deal with the multimodal heterogeneous features of the POIs, we introduce a late feature fusion strategy into our SH-CDL model. The extensive experimental analysis shows that our proposed model outperforms the state-of-the-art recommendation models, especially in out-of-town and cold-start recommendation scenarios.

With the advances in geo-positioning technologies and location-based services, it is nowadays quite common for road networks to have textual contents on the vertices. Previous work on identifying an optimal route that covers a sequence of query keywords has been studied in recent years. However, in many practical scenarios, an optimal route might not always be desirable. For example, a personalized route query is issued by providing some clues that describe the spatial context between PoIs along the route, where the result can be far from the optimal one. Therefore, in this paper, we investigate the problem of clue-based route search (CRS), which allows a user to provide clues on keywords and spatial relationships. First, we propose a greedy algorithm and a dynamic programming algorithm as baselines. To improve efficiency, we develop a branch-and-bound algorithm that prunes unnecessary vertices in query processing. In order to quickly locate candidate, we propose an AB-tree that stores both the distance and keyword information in tree structure. To further reduce the index size, we construct a PB-tree by utilizing the virtue of 2-hop label index to pinpoint the candidate. Extensive experiments are conducted and verify the superiority of our algorithms and index structures.

Data imputation aims at filling in missing attribute values in databases. Existing imputation approaches to nonquantitive string data can be roughly put into two categories: (1) inferring-based approaches [2], and (2) retrieving-based approaches [1]. Specifically, the inferring-based approaches find substitutes or estimations for the missing ones from the complete part of the data set. However, they typically fall short in filling in unique missing attribute values which do not exist in the complete part of the data set [1]. The retrieving-based approaches resort to external resources for help by formulating proper web search queries to retrieve web pages containing the missing values from the Web, and then extracting the missing values from the retrieved web pages [1]. This webbased retrieving approach reaches a high imputation precision and recall, but on the other hand, issues a large number of web search queries, which brings a large overhead [1].

With the rapid development of location-based social networks (LBSNs), spatial item recommendation has become an important way of helping users discover interesting locations to increase their engagement with location-based services. Although human movement exhibits sequential patterns in LBSNs, most current studies on spatial item recommendations do not consider the sequential influence of locations. Leveraging sequential patterns in spatial item recommendation is, however, very challenging, considering 1) users' check-in data in LBSNs has a low sampling rate in both space and time, which renders existing prediction techniques on GPS trajectories ineffective; 2) the prediction space is extremely large, with millions of distinct locations as the next prediction target, which impedes the application of classical Markov chain models; and 3) there is no existing framework that unifies users' personal interests and the sequential influence in a principled manner. In light of the above challenges, we propose a sequential personalized spatial item recommendation framework (SPORE) which introduces a novel latent variable topic-region to model and fuse sequential influence with personal interests in the latent and exponential space. The advantages of modeling the sequential effect at the topic-region level include a significantly reduced prediction space, an effective alleviation of data sparsity and a direct expression of the semantic meaning of users' spatial activities. Furthermore, we design an asymmetric Locality Sensitive Hashing (ALSH) technique to speed up the online top-k recommendation process by extending the traditional LSH. We evaluate the performance of SPORE on two real datasets and one large-scale synthetic dataset. The results demonstrate a significant improvement in SPORE's ability to recommend spatial items, in terms of both effectiveness and efficiency, compared with the state-of-the-art methods.

Social community detection is a growing field of interest in the area of social network applications, and many approaches have been developed, including graph partitioning, latent space model, block model and spectral clustering. Most existing work purely focuses on network structure information which is, however, often sparse, noisy and lack of interpretability. To improve the accuracy and interpretability of community discovery, we propose to infer users' social communities by incorporating their spatiotemporal data and semantic information. Technically, we propose a unified probabilistic generative model, User-Community-Geo-Topic (UCGT), to simulate the generative process of communities as a result of network proximities, spatiotemporal co-occurrences and semantic similarity. With a well-designed multi-component model structure and a parallel inference implementation to leverage the power of multicores and clusters, our UCGT model is expressive while remaining efficient and scalable to growing large-scale geo-social networking data. We deploy UCGT to two application scenarios of user behavior predictions: check-in prediction and social interaction prediction. Extensive experiments on two large-scale geo-social networking datasets show that UCGT achieves better performance than existing state-of-the-art comparison methods.

It is nowadays quite common for road networks to have textual contents on the vertices, which describe auxiliary information (e.g., business, traffic, etc.) associated with the vertex. In such road networks, which are modelled as weighted undirected graphs, each vertex is associated with one or more keywords, and each edge is assigned with a weight, which can be its physical length or travelling time. In this paper, we study the problem of keyword-aware continuous k nearest neighbour (KCkNN) search on road networks, which computes the k nearest vertices that contain the query keywords issued by a moving object and maintains the results continuously as the object is moving on the road network. Reducing the query processing costs in terms of computation and communication has attracted considerable attention in the database community with interesting techniques proposed. This paper proposes a framework, called a Labelling AppRoach for Continuous kNN query (LARC), on road networks to cope with KCkNN query efficiently. First we build a pivot-based reverse label index and a keyword-based pivot tree index to improve the efficiency of keyword-aware k nearest neighbour (KkNN) search by avoiding massive network traversals and sequential probe of keywords. To reduce the frequency of unnecessary result updates, we develop the concepts of dominance interval and region on road network, which share the similar intuition with safe region for processing continuous queries in Euclidean space but are more complicated and thus require more dedicated design. For high frequency keywords, we resolve the dominance interval when the query results changed. In addition, a path-based dominance updating approach is proposed to compute the dominance region efficiently when the query keywords are of low frequency. We conduct extensive experiments by comparing our algorithms with the state-of-the-art methods on real data sets. The empirical observations have verified the superiority of our proposed solution in all aspects of index size, communication cost and computation time.

Route recommendation is one of the most widely used location-based services nowadays, as it is vital for nice-driving experience and smooth public traffic. Given a pair of user-specified origin and destination, a route recommendation service aims to provide users with the routes of the best travelling experience according to given criteria. However, even the routes recommended by the big-thumb service providers can deviate significantly from the ones travelled by experienced drivers, which motivates the previous research that leverages crowds’ knowledge to improve the recommendation quality. Since route recommendation is normally an online task, low-latency response to drivers’ queries is required in this kind of systems. Unfortunately, latency of crowdsourced systems is usually high, because they need to generate tasks and wait for workers’ feedbacks before answering queries. To address this issue, we extend our previous system—CrowdPlanner—by proposing some strategies to reuse existing answers (truths) to deal with newly coming queries more efficiently. A prototype system has been deployed to many voluntary mobile clients and extensive tests on real-scenario queries have shown the superiority of our system in comparison with the results given by map services and popular route-mining algorithms.

Semantic tags of points of interest (POIs) are a crucial prerequisite for location search, recommendation services, and data cleaning. However, most POIs in location-based social networks (LBSNs) are either tag-missing or tag-incomplete. This article aims to develop semantic annotation techniques to automatically infer tags for POIs. We first analyze two LBSN datasets and observe that there are two types of tags, category-related ones and sentimental ones, which have unique characteristics. Category-related tags are hierarchical, whereas sentimental ones are category-aware. All existing related work has adopted classification methods to predict high-level category-related tags in the hierarchy, but they cannot apply to infer either low-level category tags or sentimental ones. In light of this, we propose a latent-class probabilistic generative model, namely the spatial-temporal topic model (STM), to infer personal interests, the temporal and spatial patterns of topics/semantics embedded in users’ check-in activities, the interdependence between category-topic and sentiment-topic, and the correlation between sentimental tags and rating scores from users’ check-in and rating behaviors. Then, this learned knowledge is utilized to automatically annotate all POIs with both category-related and sentimental tags in a unified way. We conduct extensive experiments to evaluate the performance of the proposed STM on a real large-scale dataset. The experimental results show the superiority of our proposed STM, and we also observe that the real challenge of inferring category-related tags for POIs lies in the low-level ones of the hierarchy and that the challenge of predicting sentimental tags are those with neutral ratings.

With the explosion of smartphones and social network services, location-based social networks (LBSNs) are increasingly seen as tools for businesses (e.g., restaurants and hotels) to promote their products and services. In this article, we investigate the key techniques that can help businesses promote their locations by advertising wisely through the underlying LBSNs. In order to maximize the benefit of location promotion, we formalize it as an influence maximization problem in an LBSN, i.e., given a target location and an LBSN, a set of k users (called seeds) should be advertised initially such that they can successfully propagate and attract many other users to visit the target location. Existing studies have proposed different ways to calculate the information propagation probability, that is, how likely it is that a user may influence another, in the setting of a static social network. However, it is more challenging to derive the propagation probability in an LBSN since it is heavily affected by the target location and the user mobility, both of which are dynamic and query dependent. This article proposes two user mobility models, namely the Gaussian-based and distance-based mobility models, to capture the check-in behavior of individual LBSN users, based on which location-aware propagation probabilities can be derived. Extensive experiments based on two real LBSN datasets have demonstrated the superior effectiveness of our proposals compared with existing static models of propagation probabilities to truly reflect the information propagation in LBSNs.

The study of urban networks reveals that the accessibility of important city objects for the vehicle traffic and pedestrians is significantly correlated to the popularity, micro-criminality, micro-economic vitality, and social liveability of the city, and is always the chief factor in regulating the growth and expansion of the city. The accessibility between different components of an urban structure are frequently measured along the streets and routes considered as edges of a planar graph, while the traffic ultimate destination points and street junctions are treated as vertices. For estimation of the accessibility of destination vertex$j$from vertex$i$through urban networks, in particular, the random walks are used to calculate the expected distance a random walker starting from$i$makes before$j$is visited (known asaccess time). The state-of-the-art of access time computation is costly in large planar graphs since it involves matrix operation over entire graph. The time complexity is$O(n^{2.376})$where$n$is the number of vertices in the planar graph. To enable efficient access time query answering in large planar graphs, this work proposes the first access time oracle which is based on the proposed access time decomposition and reconstruction scheme. The oracle is a hierarchical data structure with deliberate design on the relationships between different hierarchical levels. The storage requirement of the proposed oracle is$O(n^{\frac{4}{3}}\log \log n)$and the access time query response time is$O(n^{\frac{2}{3}})$. The extensive tests on a number of large real-world road networks (with up to about 2 million vertices) have verified the superiority of the proposed oracle.

The problem we aim to address is the optimization of cost management for executing multiple continuous queries on data streams, where each query is defined by several filters, each of which monitors certain status of the data stream. Specially, the filter can be shared by different queries and expensive to evaluate. The conventional objective for such a problem is to minimize the overall execution cost to solve all queries, by planning the order of filter evaluation in shared strategy. However, in the streaming scenario, the characteristics of data items may change in process, which can bring some uncertainty to the outcome of individual filter evaluation, and affect the plan of query execution as well as the overall execution cost. In our work, considering the influence of the uncertain variation of data characteristics, we propose a framework to deal with the dynamic adjustment of filter ordering for query execution on data stream, and focus on the issues of cost management. By incrementally monitoring and analyzing the results of filter evaluation, our proposed approach can be effectively adaptive to the varied stream behavior and adjust the optimal ordering of filter evaluation, so as to optimize the execution cost. In order to achieve satisfactory performance and efficiency, we also discuss the trade-off between the adaptivity of our framework and the overhead incurred by filter adaption. The experimental results on synthetic and two real data sets (traffic and multimedia) show that our framework can effectively reduce and balance the overall query execution cost and keep high adaptivity in streaming scenario.

Point-of-Interest recommendation is an essential means to help people discover attractive locations, especially when people travel out of town or to unfamiliar regions. While a growing line of research has focused on modeling user geographical preferences for POI recommendation, they ignore the phenomenon of user interest drift across geographical regions, i.e., users tend to have different interests when they travel in different regions, which discounts the recommendation quality of existing methods, especially for out-of-town users. In this paper, we propose a latent class probabilistic generative model Spatial-Temporal LDA (ST-LDA) to learn region-dependent personal interests according to the contents of their checked-in POIs at each region. As the users' check-in records left in the out-of-town regions are extremely sparse, ST-LDA incorporates the crowd's preferences by considering the public's visiting behaviors at the target region. To further alleviate the issue of data sparsity, a social-spatial collective inference framework is built on ST-LDA to enhance the inference of region-dependent personal interests by effectively exploiting the social and spatial correlation information. Besides, based on ST-LDA, we design an effective attribute pruning (AP) algorithm to overcome the curse of dimensionality and support fast online recommendation for large-scale POI data. Extensive experiments have been conducted to evaluate the performance of our ST-LDA model on two real-world and large-scale datasets. The experimental results demonstrate the superiority of ST-LDA and AP, compared with the state-of-the-art competing methods, by making more effective and efficient mobile recommendations.

Point-of-Interest (POI) recommendation has become an important means to help people discover attractive and interesting places, especially when users travel out of town. However, the extreme sparsity of a user-POI matrix creates a severe challenge. To cope with this challenge, we propose a unified probabilistic generative model, the Topic-Region Model (TRM) , to simultaneously discover the semantic, temporal, and spatial patterns of users’ check-in activities, and to model their joint effect on users’ decision making for selection of POIs to visit. To demonstrate the applicability and flexibility of TRM, we investigate how it supports two recommendation scenarios in a unified way, that is, hometown recommendation and out-of-town recommendation. TRM effectively overcomes data sparsity by the complementarity and mutual enhancement of the diverse information associated with users’ check-in activities (e.g., check-in content, time, and location) in the processes of discovering heterogeneous patterns and producing recommendations. To support real-time POI recommendations, we further extend the TRM model to an online learning model, TRM-Online, to track changing user interests and speed up the model training. In addition, based on the learned model, we propose a clustering-based branch and bound algorithm (CBB) to prune the POI search space and facilitate fast retrieval of the top- k recommendations. We conduct extensive experiments to evaluate the performance of our proposals on two real-world datasets, including recommendation effectiveness, overcoming the cold-start problem, recommendation efficiency, and model-training efficiency. The experimental results demonstrate the superiority of our TRM models, especially TRM-Online, compared with state-of-the-art competitive methods, by making more effective and efficient mobile recommendations. In addition, we study the importance of each type of pattern in the two recommendation scenarios, respectively, and find that exploiting temporal patterns is most important for the hometown recommendation scenario, while the semantic patterns play a dominant role in improving the recommendation effectiveness for out-of-town users.

Point-of-Interest (POI) recommendation has become an important means to help people discover attractive and interesting locations, especially when users travel out of town. However, extreme sparsity of user-POI matrix creates a severe challenge. To cope with this challenge, a growing line of research has exploited the temporal effect, geographical-social influence, content effect and word-of-mouth effect. However, current research lacks an integrated analysis of the joint effect of the above factors to deal with the issue of data-sparsity, especially in the out-of-town recommendation scenario which has been ignored by most existing work.

Spatial trajectory data is widely available today. Over a sustained period of time, trajectory data has been collected from numerous GPS devices, smartphones, sensors and social media applications. Daily increases of real-time trajectory data have also been phenomenal in recent years. More and more new applications have emerged to derive business values from both trajectory data warehouses and real-time trajectory data. Due to their very large volumes, their nature of streaming, their highly variable levels of data quality, as well as many possible links with other types of data, making sense of spatial trajectory data becomes one of the crucial areas for big data analytics. In this paper we will present a review of the extensive work in spatiotemporal data management and trajectory mining, and discuss new challenges and new opportunities in the context of new applications, focusing on recent advances in trajectory data management and trajectory mining from their foundations to high performance processing with modern computing infrastructure.

Understanding short texts is crucial to many applications, but challenges abound. First, short texts do not always observe the syntax of a written language. As a result, traditional natural language processing methods cannot be easily applied. Second, short texts usually do not contain sufficient statistical signals to support many state-of-the-art approaches for text processing such as topic modeling. Third, short texts are usually more ambiguous. We argue that knowledge is needed in order to better understand short texts. In this work, we use lexical-semantic knowledge provided by a well-known semantic network for short text understanding. Our knowledge-intensive approach disrupts traditional methods for tasks such as text segmentation, part-of-speech tagging, and concept labeling, in the sense that we focus on semantics in all these tasks. We conduct a comprehensive performance evaluation on real-life data. The results show that knowledge is indispensable for short text understanding, and our knowledge-intensive approaches are effective in harvesting semantics of short texts.

Outsourcing database to clouds is a scalable and cost-effective way for large scale data storage, management, and query processing. Trajectory data contain rich spatio-temporal relationships and reveal many forms of individual sensitive information (e.g., home address, health condition), which necessitate them to be encrypted before being outsourced for privacy concerns. However, efficient query processing over encrypted trajectory data is a very challenging task. Though some achievements have been reported very recently for simple queries (e.g., SQL queries, kNN queries) on encrypted data, there is rather limited progress on secure evaluation of trajectory queries because they are more complex and need special treatment. In this paper, we focus on secure trajectory similarity computation that is the cornerstone of secure trajectory query processing. More specifically, we propose an efficient solution to securely compute the similarity between two encrypted trajectories, which reveals nothing about the trajectories, but the final result. We theoretically prove that our solution is secure against the semi-honest adversaries model as all the intermediate information in our protocols can be simulated in polynomial time. Finally we empirically study the efficiency of the proposed method, which demonstrates the feasibility of our solution.

Graph Pattern Matching (GPM) plays a significant role in social network analysis, which has been widely used in, for example, experts finding, social community mining and social position detection. Given a pattern graph GQand a data graph GD, a GPM algorithm finds those subgraphs, GM, that match GQin GD. However, the existing GPM methods do not consider the multiple constraints on edges in GQ, which are commonly exist in various applications such as, crowdsourcing travel, social network based e-commerce and study group selection, etc. In this paper, we first conceptually extend Bounded Simulation to Multi-Constrained Simulation (MCS), and propose a novel NP-Complete Multi-Constrained Graph Pattern Matching (MC-GPM) problem. Then, to address the efficiency issue in large-scale MC-GPM, we propose a new concept called Strong Social Component (SSC), consisting of participants with strong social connections. We also propose an approach to identify SSCs, and propose a novel index method and a graph compression method for SSC. Moreover, we devise a heuristic algorithm to identify MC-GPM results effectively and efficiently without decompressing graphs. An extensive empirical study on five real-world large-scale social graphs has demonstrated the effectiveness, efficiency and scalability of our approach.

Due to the prevalence of GPS-enabled devices and wireless communication technology, spatial trajectories that describe the movement history of moving objects are being generated and accumulated at an unprecedented pace. However, a raw trajectory in the form of sequence of timestamped locations does not make much sense for humans without semantic representation. In this work we aim to facilitate human's understanding of a raw trajectory by automatically generating a short text to describe it. By formulating this task as the problem of adaptive trajectory segmentation and feature selection, we propose a partition-and-summarization framework. In the partition phase, we first define a set of features for each trajectory segment and then derive an optimal partition with the aim to make the segments within each partition as homogeneous as possible in terms of their features. In the summarization phase, for each partition we select the most interesting features by comparing against the common behaviours of historical trajectories on the same route and generate short text description for these features. For empirical study, we apply our solution to a real trajectory dataset and have found that the generated text can effectively reflect the important parts in a trajectory.

Conventional top-k spatial keyword queries require users to explicitly specify their preferences between spatial proximity and keyword relevance. In this work we investigate how to eliminate this requirement by enhancing the conventional queries with interaction, resulting in Interactive Top-k Spatial Keyword (ITkSK) query. Having confirmed the feasibility by theoretical analysis, we propose a three-phase solution focusing on both effectiveness and efficiency. The first phase substantially narrows down the search space for subsequent phases by efficiently retrieving a set of geo-textual k-skyband objects as the initial candidates. In the second phase three practical strategies for selecting a subset of candidates are developed with the aim of maximizing the expected benefit for learning user preferences at each round of interaction. Finally we discuss how to determine the termination condition automatically and estimate the preference based on the user's feedback. Empirical study based on real PoI datasets verifies our theoretical observation that the quality of top-k results in spatial keyword queries can be greatly improved through only a few rounds of interactions.

Driven by the advances in location positioning techniques and the popularity of location sharing services, semantic enriched trajectory data have become unprecedentedly available. While finding relevant Point-of-Interest (POIs) based on users' locations and query keywords has been extensively studied in the past years, it is largely untouched to explore the keyword queries in the context of semantic trajectory database. In this paper, we study the problem of approximate keyword search in massive semantic trajectories. Given a set of query keywords, an approximate keyword query of semantic trajectory (AKQST) returns k trajectories that contain the most relevant keywords to the query and yield the least travel effort in the meantime. The main difference between AKQST and conventional spatial keyword queries is that there is no query location in AKQST, which means the search area cannot be localized. To capture the travel effort in the context of query keywords, a novel utility function, called spatio-textual utility function, is first defined. Then we develop a hybrid index structure called GiKi to organize the trajectories hierarchically, which enables pruning the search space by spatial and textual similarity simultaneously. Finally an efficient search algorithm and fast evaluation of the minimum value of spatio-textual utility function are proposed. The results of our empirical studies based on real check-in datasets demonstrate that our proposed index and algorithms can achieve good scalability.

With the rapid development of location-based social networks (LBSNs), spatial item recommendation has become an important means to help people discover attractive and interesting venues and events, especially when users travel out of town. However, this recommendation is very challenging compared to the traditional recommender systems. A user can visit only a limited number of spatial items, leading to a very sparse user-item matrix. Most of the items visited by a user are located within a short distance from where he/she lives, which makes it hard to recommend items when the user travels to a far away place. Moreover, user interests and behavior patterns may vary dramatically across different geographical regions. In light of this, we propose Geo-SAGE, a geographical sparse additive generative model for spatial item recommendation in this paper. Geo-SAGE considers both user personal interests and the preference of the crowd in the target region, by exploiting both the co-occurrence pattern of spatial items and the content of spatial items. To further alleviate the data sparsity issue, Geo-SAGE exploits the geographical correlation by smoothing the crowd's preferences over a well-designed spatial index structure called spatial pyramid. We conduct extensive experiments and the experimental results clearly demonstrate our Geo-SAGE model outperforms the state-of-the-art.

With the explosion of smartphones and social network services, location-based social networks (LBSNs) are increasingly seen as tools for businesses (e.g., restaurants, hotels) to promote their products and services. In this paper, we investigate the key techniques that can help businesses promote their locations by advertising wisely through the underlying LBSNs. In order to maximize the benefit of location promotion, we formalize it as an influence maximization problem in an LBSN, i.e., given a target location and an LBSN, which a set of k users (called seeds) should be advertised initially such that they can successfully propagate and attract most other users to visit the target location. Existing studies have proposed different ways to calculate the information propagation probability, that is how likely a user may influence another, in the settings of static social network. However, it is more challenging to derive the propagation probability in an LBSN since it is heavily affected by the target location and the user mobility, both of which are dynamic and query dependent. This paper proposes two user mobility models, namely Gaussian-based and distance-based mobility models, to capture the check-in behavior of individual LBSN user, based on which location-aware propagation probabilities can be derived respectively. Extensive experiments based on two real LBSN datasets have demonstrated the superior effectiveness of our proposals than existing static models of propagation probabilities to truly reflect the information propagation in LBSNs.

Nowadays microblogging sites, such as Twitter and Chinese Sina Weibo, have established themselves as an invaluable information source, which provides a huge collection of manually-generated tweets with broad range of topics from daily life to breaking news. Entity linking is indispensable for understanding and maintaining such information, which in turn facilitates many real-world applications such as tweet clustering and classification, personalized microblog search, and so forth. However, tweets are short, informal and error-prone, rendering traditional approaches for entity linking in documents largely inapplicable. Recent work addresses this problem by utilising information from other tweets and linking entities in a batch manner. Nevertheless, the high computational complexity makes this approach infeasible for real-time applications given the high arrival rate of tweets. In this paper, we propose an efficient solution to link entities in tweets by analyzing their social and temporal context. Our proposed framework takes into consideration three features, namely entity popularity, entity recency, and user interest information embedded in social interactions to assist the entity linking task. Effective indexing structures along with incremental algorithms have also been developed to reduce the computation and maintenance costs of our approach. Experimental results based on real tweet datasets verify the effectiveness and efficiency of our proposals.

An increasing amount of motion history data, which is called trajectory, is being collected from different sources such as GPS-enabled mobile devices, surveillance cameras and social networks. However it is hard to store and manage trajectory data in traditional database systems, since its variable lengths and asynchronous sampling rates do not fit disk-based and tuple-oriented structures, which are the fundamental structures of traditional database systems. We implement a novel trajectory storage system that is motivated by the success of column store and recent development of in-memory based databases. In this storage design, we try to explore the potential opportunities, which can boost the performance of query processing for trajectory data. To achieve this, we partition the trajectories into frames as column-oriented storage in order to store the sample points of a moving object, which are aligned by the time interval, within the main memory. Furthermore, the frames can be highly compressed and well structured to increase the memory utilization ratio and reduce the CPU-cache missing. It is also easier for parallelizing data processing on the multi-core server since the frames are mutually independent.

Web Harvesting enables the enrichment of incomplete data sets by retrieving required information from the Web. However, the ambiguity of instances may greatly decrease the quality of the harvested data, given that any instance in the local data set may become ambiguous when attempting to identify it on the Web. Although plenty of disambiguation methods have been proposed to deal with the ambiguity problems in various settings, none of them are able to handle the instance ambiguity problem in Web Harvesting. In this paper, we propose to do instance disambiguation in Web Harvesting with a novel disambiguation method inspired by the idea of collaborative identity recognition. In particular, we expect to find some common properties in forms of latent shared attribute values among instances in the list, such that these shared attribute values can differentiate instances within the list against those ambiguous ones on the Web. Our extensive experimental evaluation illustrates the utility of collaborative disambiguation for a popular Web Harvesting application, and shows that it substantially improves the accuracy of the harvested data.

The rapid growth of location-based services provide the potential to understand people's mobility pattern at an unprecedented level, which can also enable food-service industry to accurately predict consumer's dining behavior. In this paper, by leveraging users' historical dining pattern, socio-demographic characteristics and restaurants' attributes, we aim at generating the top-K restaurants for a user's next dining. Compared to previous studies in location prediction which mainly focus on regular mobility patterns, we present a novelty-seeking based dining recommender system, termed NDRS, in consideration of both exploration and exploitation. First, we apply a Conditional Random Field (CRF) with additional constraints to infer users' novelty-seeking statuses by considering both spatial-temporal-historical features and users' socio-demographic characteristics. On the one hand, when a user is predicted to be novelty-seeking, by incorporating the influence of restaurants' contextual factors such as price and service quality, we propose a context-aware collaborative filtering method to recommend restaurants she has never visited before. On the other hand, when a user is predicted to be not novelty-seeking, we then present a Hidden Markov Model (HMM) considering the temporal regularity to recommend the previously visited restaurants. To evaluate the performance of each component as well as the whole system, we conduct extensive experiments, with a large dataset we have collected covering the concerned dining related check-ins, users' demographics, and restaurants' attributes. The results reveal that our system is effective for dining recommendation.

Driven by the dominance of the relational model, the requirements of modern applications, and the veracity of data, we revisit the fundamental notion of a key in relational databases with NULLs. In SQL database systems primary key columns are NOT NULL by default. NULL columns may occur in unique constraints which only guarantee uniqueness for tuples which do not feature null markers in any of the columns involved, and therefore serve a different function than primary keys. We investigate the notions of possible and certain keys, which are keys that hold in some or all possible worlds that can originate from an SQL table, respectively. Possible keys coincide with the unique constraint of SQL, and thus provide a semantics for their syntactic definition in the SQL standard. Certain keys extend primary keys to include NULL columns, and thus form a sufficient and necessary condition to identify tuples uniquely, while primary keys are only sufficient for that purpose. In addition to basic characterization, axiomatization, and simple discovery approaches for possible and certain keys, we investigate the existence and construction of Armstrong tables, and describe an indexing scheme for enforcing certain keys. Our experiments show that certain keys with NULLs do occur in real-world databases, and that related computational problems can be solved efficiently. Certain keys are therefore semantically well-founded and able to maintain data quality in the form of Codd's entity integrity rule while handling the requirements of modern applications, that is, higher volumes of incomplete data from different formats.

It is common that the objects in a spatial database (e.g., restaurants/hotels) are associated with keyword(s) to indicate their businesses/services/features. An interesting problem known as Closest Keywords search is to query objects, called keyword cover, which together cover a set of query keywords and have the minimum inter-objects distance. In recent years, we observe the increasing availability and importance of keyword rating in object evaluation for the better decision making. This motivates us to investigate a generic version of Closest Keywords search called Best Keyword Cover which considers inter-objects distance as well as the keyword rating of objects. The baseline algorithm is inspired by the methods of Closest Keywords search which is based on exhaustively combining objects from different query keywords to generate candidate keyword covers. When the number of query keywords increases, the performance of the baseline algorithm drops dramatically as a result of massive candidate keyword covers generated. To attack this drawback, this work proposes a much more scalable algorithm called keyword nearest neighbor expansion (keyword-NNE). Compared to the baseline algorithm, keyword-NNE algorithm significantly reduces the number of candidate keyword covers generated. The in-depth analysis and extensive experiments on real data sets have justified the superiority of our keyword-NNE algorithm.

The papers in this special section were presented a the 29th International Conference on Data Engineering was held in Brisbane, QLD, Australia, on April 8-11, 2013.

Data imputation aims at filling in missing attribute values in databases. Most existing imputation methods to string attribute values are inferring-based approaches, which usually fail to reach a high imputation recall by just inferring missing values from the complete part of the data set. Recently, some retrieving-based methods are proposed to retrieve missing values from external resources such as the World Wide Web, which tend to reach a much higher imputation recall, but inevitably bring a large overhead by issuing a large number of search queries. In this paper, we investigate the interaction between the inferring-based methods and the retrieving-based methods. We show that retrieving a small number of selected missing values can greatly improve the imputation recall of the inferring-based methods. With this intuition, we propose an inTeractive Retrieving-Inferring data imPutation approach (TRIP), which performs retrieving and inferring alternately in filling in missing attribute values in a data set. To ensure the high recall at the minimum cost, TRIP faces a challenge of selecting the least number of missing values for retrieving to maximize the number of inferable values. Our proposed solution is able to identify an optimal retrieving-inferring scheduling scheme in deterministic data imputation, and the optimality of the generated scheme is theoretically analyzed with proofs. We also analyze with an example that the optimal scheme is not feasible to be achieved in τ-constrained stochastic data imputation (τ-SDI), but still, our proposed solution identifies an expected-optimal scheme in τ-SDI. Extensive experiments on four data collections show that TRIP retrieves on average 20 percent missing values and achieves the same high recall that was reached by the retrieving-based approach.

Social media provides valuable resources to analyze user behaviors and capture user preferences. This article focuses on analyzing user behaviors in social media systems and designing a latent class statistical mixture model, named temporal context-aware mixture model (TCAM), to account for the intentions and preferences behind user behaviors. Based on the observation that the behaviors of a user in social media systems are generally influenced by intrinsic interest as well as the temporal context (e.g., the public's attention at that time), TCAM simultaneously models the topics related to users' intrinsic interests and the topics related to temporal context and then combines the influences from the two factors to model user behaviors in a unified way. Considering that users' interests are not always stable and may change over time, we extend TCAM to a dynamic temporal context-aware mixture model (DTCAM) to capture users' changing interests. To alleviate the problem of data sparsity, we exploit the social and temporal correlation information by integrating a social-temporal regularization framework into the DTCAM model. To further improve the performance of our proposed models (TCAM and DTCAM), an item-weighting scheme is proposed to enable them to favor items that better represent topics related to user interests and topics related to temporal context, respectively. Based on our proposed models, we design a temporal context-aware recommender system (TCARS). To speed up the process of producing the top- k recommendations from large-scale social media data, we develop an efficient query-processing technique to support TCARS. Extensive experiments have been conducted to evaluate the performance of our models on four real-world datasets crawled from different social media sites. The experimental results demonstrate the superiority of our models, compared with the state-of-the-art competitor methods, by modeling user behaviors more precisely and making more effective and efficient recommendations.

The last decade has witnessed the prevalence of sensor and GPS technologies that produce a high volume of trajectory data representing the motion history of moving objects. However some characteristics of trajectories such as variable lengths and asynchronous sampling rates make it difficult to fit into traditional database systems that are disk-based and tuple-oriented. Motivated by the success of column store and recent development of in-memory databases, we try to explore the potential opportunities of boosting the performance of trajectory data processing by designing a novel trajectory storage within main memory. In contrast to most existing trajectory indexing methods that keep consecutive samples of the same trajectory in the same disk page, we partition the database into frames in which the positions of all moving objects at the same time instant are stored together and aligned in main memory. We found this column-wise storage to be surprisingly well suited for in-memory computing since most frames can be stored in highly compressed form, which is pivotal for increasing the memory throughput and reducing CPU-cache miss. The independence between frames also makes them natural working units when parallelizing data processing on a multi-core environment. Lastly we run a variety of common trajectory queries on both real and synthetic datasets in order to demonstrate advantages and study the limitations of our proposed storage.

Semantic drift is a common problem in iterative information extraction. Previous approaches for minimizing semantic drift may incur substantial loss in recall. We observe that most semantic drifts are introduced by a small number of questionable extractions in the earlier rounds of iterations. These extractions subsequently introduce a large number of questionable results, which lead to the semantic drift phenomenon. We call these questionable extractions Drifting Points (DPs). If erroneous extractions are the "symptoms" of semantic drift, then DPs are the "causes" of semantic drift. In this paper, we propose a method to minimize semantic drift by identifying the DPs and removing the effect introduced by the DPs. We use isA (concept-instance) extraction as an example to demonstrate the effectiveness of our approach in cleaning information extraction errors caused by semantic drift. We perform experiments on a isA relation iterative extraction, where 90.5 million of isA pairs are automatically extracted from 1.6 billion web documents with a low precision. The experimental results show our DP cleaning method enables us to clean more than 90% incorrect instances with 95% precision, which outperforms the previous approaches we compare with. As a result, our method greatly improves the prevision of this large isA data set from less than 50% to over 90%.

As travel is taking more significant part in our life, route recommendation service becomes a big business and attracts many major players in IT industry. Given a pair of user-specified origin and destination, a route recommendation service aims to provide users with the routes of best travelling experience according to criteria, such as travelling distance, travelling time, traffic condition, etc. However, previous research shows that even the routes recommended by the big-thumb service providers can deviate significantly from the routes travelled by experienced drivers. It means travellers' preferences on route selection are influenced by many latent and dynamic factors that are hard to model exactly with pre-defined formulas. In this work we approach this challenging problem with a very different perspective- leveraging crowds' knowledge to improve the recommendation quality. In this light, CrowdPlanner - a novel crowd-based route recommendation system has been developed, which requests human workers to evaluate candidate routes recommended by different sources and methods, and determine the best route based on their feedbacks. In this paper, we particularly focus on two important issues that affect system performance significantly: (1) how to efficiently generate tasks which are simple to answer but possess sufficient information to derive user-preferred routes; and (2) how to quickly identify a set of appropriate domain experts to answer the questions timely and accurately. Specifically, the task generation component in our system generates a series of informative and concise questions with optimized ordering for a given candidate route set so that workers feel comfortable and easy to answer. In addition, the worker selection component utilizes a set of selection criteria and an efficient algorithm to find the most eligible workers to answer the questions with high accuracy. A prototype system has been deployed to many voluntary mobile clients and extensive tests on real-scenario queries have shown the superiority of CrowdPlanner in comparison with the results given by map services and popular route mining algorithms.

Route recommendation service has become a big business in industry since traveling is now an important part of our daily life. We can travel to unknown places by simply typing in our destination and then following recommendation service's guidance, that a pleasant trip desires them to provide a good route. However, previous research shows that even the routes recommended by the big-thumb service providers can deviate significantly from the routes travelled by experienced drivers since the many latent factors affect drivers' preferences and it is hard for a single route recommendation algorithm to model all of them. In this demo we will present the CrowPlanner system to leverage crowds' knowledge to improve the recommendation quality. It requests human workers to evaluate candidates routes recommended by different sources and methods, and determines the best route based on the feedbacks of these workers. In this demo, we first introduce the core component of our system for smart question generation, and then show several real route recommendation cases and the feedback of users.

Recently, with the advent of location-based social networking services (LBSNs), travel planning and location-aware information recommendation based on LBSNs have attracted much research attention. In this paper, we study the impact of social relations hidden in LBSNs, i.e., The social influence of friends. We propose a new social influence-based user recommender framework (SIR) to discover the potential value from reliable users (i.e., Close friends and travel experts). Explicitly, our SIR framework is able to infer influential users from an LBSN. We claim to capture the interactions among virtual communities, physical mobility activities and time effects to infer the social influence between user pairs. Furthermore, we intend to model the propagation of influence using diffusion-based mechanism. Moreover, we have designed a dynamic fusion framework to integrate the features mined into a united follow probability score. Finally, our SIR framework provides personalized top-k user recommendations for individuals. To evaluate the recommendation results, we have conducted extensive experiments on real datasets (i.e., The Go Walla dataset). The experimental results show that the performance of our SIR framework is better than the state-of the-art user recommendation mechanisms in terms of accuracy and reliability.

In this demo paper we present Orange, a system prototype for objective-aware range query refinement. Orange essentially refines a range query to meet a pre-specified cardinality constraint while taking into account the (dis)similarity between the initial query and its corresponding refined version. To achieve this goal, Orange employes the novel scheme SAQR for efficient similarity-aware query refinement. The main idea underlying SAQR is to utilize the pre-defined constraints on cardinality and similarity in order to bound the search space and quickly find a refined query, which meets the user's expectations. We showcase Orange in a web-based application which aims to guide planners in allocating service zones for police patrol units using real and historical dataset of crime incidents.

The efficiency of spatial query processing is crucial for many applications such as location-based services. In spatial networks, queries like k-NN queries are all based on network distance evaluation. Classic solutions for these queries rely on network expansion and are not efficient enough for large networks. Some approaches have improved the query efficiency but brought considerable space cost for index. To address these problems, we propose a hierarchical graph partitioning based index named Partition Tree. It organizes the vertices of a spatial network into a hierarchy through a series of graph partitioning processes. Meanwhile precomputed distances are associated with this hierarchy to facilitate efficient query processing. Inspired by the observation that queries are usually invoked around objects of interest, we propose a query-oriented optimization on top of the Partition Tree. It uses a cost model to evaluate the influence of the object distribution and partitioning topology on the query efficiency. Then a cost-efficient graph partitioning method is developed based on this cost model. Experimental results on real datasets demonstrate that our proposed index and algorithms have superior performance over the state-of-the-art approaches and are scalable to large spatial networks.

Understanding the dynamics of human daily mobility patterns is essential for the management and planning of urban facilities and services. Travel smart cards, which record users' public transporting histories, capture rich information of users' mobility pattern. This provides the opportunity to discover valuable knowledge from these transaction records. In recent years, research on measuring user similarity for behavior analysis has attracted a lot of attention in applications such as recommendation systems, crowd behavior analysis applications, and numerous data mining tasks. In this paper, our goal is to estimate the similarity between users' travel patterns according to their travel smart card data. The core of our proposal is a novel user similarity measurement, namely, Travel Spatial-Temporal Similarity (TST), which measures the spatial range and temporal similarity between users. Moreover, we also propose a hybrid index structure, which integrates inverted files and cluster-based partitioning, to allow for efficient retrieval of the top-K most similar users. Through experimental evaluation, our proposed approach is shown to deliver scalable performance.

Widely adoption of GPS-enabled devices generates large amounts of trajectories every day. The raw trajectory data describes the movement history of moving objects by a sequence of < longitude, latitude, time-stamp > triples, which are nonintuitive for human to perceive the prominent features of the trajectory, such as where and how the moving object travels. In this demo, we present the STMaker system to help users make sense of individual trajectories. Given a trajectory, STMaker can automatically extract the significant semantic behavior of the trajectory, and summarize the behavior by a short human-readable text. In this paper, we first introduce the phrases of generating trajectory summarizations, and then show several real trajectory summarization cases.

Many pattern analysis and data mining problems have witnessed high-dimensional data represented by a large number of features, which are often redundant and noisy. Feature selection is one main technique for dimensionality reduction that involves identifying a subset of the most useful features. In this paper, a novel unsupervised feature selection algorithm, named clustering-guided sparse structural learning (CGSSL), is proposed by integrating cluster analysis and sparse structural analysis into a joint framework and experimentally evaluated. Nonnegative spectral clustering is developed to learn more accurate cluster labels of the input samples, which guide feature selection simultaneously. Meanwhile, the cluster labels are also predicted by exploiting the hidden structure shared by different features, which can uncover feature correlations to make the results more reliable. Row-wise sparse models are leveraged to make the proposed model suitable for feature selection. To optimize the proposed formulation, we propose an efficient iterative algorithm. Finally, extensive experiments are conducted on 12 diverse benchmarks, including face data, handwritten digit data, document data, and biomedical data. The encouraging experimental results in comparison with several representative algorithms and the theoretical analysis demonstrate the efficiency and effectiveness of the proposed algorithm for feature selection.

We identify Relation Completion (RC) as one recurring problem that is central to the success of novel big data applications such as Entity Reconstruction and Data Enrichment.Given a semantic relation R, RC attempts at linking entity pairs between two entity lists under the relation R. To accomplish the RC goals, we propose to formulate search queries for each query entity α based on some auxiliary information, so that to detect its target entity β from the set of retrieved documents.For instance, a Pattern-based method (PaRE) uses extracted patterns as the auxiliary information in formulating search queries.However, high-quality patterns may decrease the probability of finding suitable target entities.As an alternative, we propose CoRE method that uses context terms learned surrounding the expression of a relation as the auxiliary information in formulating queries.The experimental results based on several real-world web data collections demonstrate that CoRE reaches a much higher accuracy than PaRE for the purpose of RC.

This paper investigates the problem of efficiently computing responsibility for lineages of conjunctive queries with inequalities on databases. We classify the lineages of a class of queries with inequalities, called IQ queries, into path and composite lineages. We first compile path lineages into lineage graphs and transform lineage graphs into matrices. Then we reduce the problem of computing responsibility for path lineages to the shortest path problem, which can be solved by the dynamic programming algorithm in PTIME. We further prove composite lineages can be decomposed into path lineages for computing responsibility. Thus, our first main result shows it is in PTIME to compute responsibility for lineages of IQ queries. We generalize the previous results on dichotomy of responsibility analysis for lineages of conjunctive queries with equalities, now in the presence of inequalities. After decomposing composite lineages into path lineages, the data population needed for computing responsibility decreases more than one order of magnitude. Thus, our algorithm can efficiently compute responsibility for composite lineages. In order to compute responsibility for lineages in general, we introduce a greedy algorithm, consisting of a reduction to the set cover problem. Finally, we demonstrate the benefits of the proposed algorithms with extensive experimental results.

The increasing pervasiveness of location-acquisition technologies has enabled collection of huge amount of trajectories for almost any kind of moving objects. Discovering useful patterns from their movement behaviors can convey valuable knowledge to a variety of critical applications. In this light, we propose a novel concept, called gathering, which is a trajectory pattern modeling various group incidents such as celebrations, parades, protests, traffic jams and so on. A key observation is that these incidents typically involve large congregations of individuals, which form durable and stable areas with high density. In this work, we first develop a set of novel techniques to tackle the challenge of efficient discovery of gathering patterns on archived trajectory dataset. Afterwards, since trajectory databases are inherently dynamic in many real-world scenarios such as traffic monitoring, fleet management and battlefield surveillance, we further propose an online discovery solution by applying a series of optimization schemes, which can keep track of gathering patterns while new trajectory data arrive. Finally, the effectiveness of the proposed concepts and the efficiency of the approaches are validated by extensive experiments based on a real taxicab trajectory dataset.

Due to the prevalence of GPS-enabled devices and wireless communications technologies, spatial trajectories that describe the movement history of moving objects are being generated and accumulated at an unprecedented pace. Trajectory data in a database are intrinsically heterogeneous, as they represent discrete approximations of original continuous paths derived using different sampling strategies and different sampling rates. Such heterogeneity can have a negative impact on the effectiveness of trajectory similarity measures, which are the basis of many crucial trajectory processing tasks. In this paper, we pioneer a systematic approach to trajectory calibration that is a process to transform a heterogeneous trajectory dataset to one with (almost) unified sampling strategies. Specifically, we propose an anchor-based calibration system that aligns trajectories to a set of anchor points, which are fixed locations independent of trajectory data. After examining four different types of anchor points for the purpose of building a stable reference system, we propose a geometry-based calibration approach that considers the spatial relationship between anchor points and trajectories. Then a more advanced model-based calibration method is presented, which exploits the power of machine learning techniques to train inference models from historical trajectory data to improve calibration effectiveness. Finally, we conduct extensive experiments using real trajectory datasets to demonstrate the effectiveness and efficiency of the proposed calibration system.

A search task represents an atomic information need of a user in web search. Tasks consist of queries and their reformulations, and identifying tasks is important for search engines since they provide valuable information for determining user satisfaction with search results, predicting user search intent, and suggesting queries to the user. Traditional approaches to identifying tasks exploit either temporal or lexical features of queries. However, many query refinements are topical, which means that a query and its refinements may not be similar on the lexical level. Furthermore, multiple tasks in the same search session may interleave, which means we cannot simply order the searches by their timestamps and divide the session into multiple tasks. Thus, in order to identify tasks correctly, we need to be able to compare two queries at the semantic level. In this paper, we use a knowledgebase known as Probase to infer the conceptual meanings of queries, and automatically identify the topical query refinements in the tasks. Experimental results on real search log data demonstrate that Probase can indeed help estimate the topical affinity between queries, and thus enable us to merge queries that are topically related but dissimilar at the lexical level.

In this paper, we propose a new type of Dictionary-based Entity Recognition Problem, named Approximate Membership Localization (AML). The popular Approximate Membership Extraction (AME) provides a full coverage to the true matched substrings from a given document, but many redundancies cause a low efficiency of the AME process and deteriorate the performance of real-world applications using the extracted substrings. The AML problem targets at locating nonoverlapped substrings which is a better approximation to the true matched substrings without generating overlapped redundancies. In order to perform AML efficiently, we propose the optimized algorithm P-Prune that prunes a large part of overlapped redundant matched substrings before generating them. Our study using several real-word data sets demonstrates the efficiency of P-Prune over a baseline method. We also study the AML in application to a proposed web-based join framework scenario which is a search-based approach joining two tables using dictionary-based entity recognition from web documents. The results not only prove the advantage of AML over AME, but also demonstrate the effectiveness of our search-based approach.

Data clustering is one of the fundamental research problems in data mining and machine learning. Most of the existing clustering methods, for example, normalized cut and (k)-means, have been suffering from the fact that their optimization processes normally lead to an NP-hard problem due to the discretization of the elements in the cluster indicator matrix. A practical way to cope with this problem is to relax this constraint to allow the elements to be continuous values. The eigenvalue decomposition can be applied to generate a continuous solution, which has to be further discretized. However, the continuous solution is probably mixing-signed. This result may cause it deviate severely from the true solution, which should be naturally nonnegative. In this paper, we propose a novel clustering algorithm, i.e., discriminative nonnegative spectral clustering, to explicitly impose an additional nonnegative constraint on the cluster indicator matrix to seek for a more interpretable solution. Moreover, we show an effective regularization term which is able to not only provide more useful discriminative information but also learn a mapping function to predict cluster labels for the out-of-sample test data. Extensive experiments on various data sets illustrate the superiority of our proposal compared to the state-of-the-art clustering algorithms.

Provenance information is vital in many application areas as it helps explain data lineage and derivation. However, storing fine-grained provenance information can be expensive. In this paper, we present a framework for storing provenance information relating to data derived via database queries. In particular, we first propose a provenance tree data structure which matches the query structure and thereby presents a possibility to avoid redundant storage of information regarding the derivation process. Then we investigate two approaches for reducing storage costs. The first approach utilizes two ingenious rules to achieve reduction on provenance trees. The second one is a dynamic programming solution, which provides a way of optimizing the selection of query tree nodes where provenance information should be stored. The optimization algorithm runs in polynomial time in the query size and is linear in the size of the provenance information, thus enabling provenance tracking and optimization without incurring large overheads. Experiments show that our approaches guarantee significantly lower storage costs than existing approaches.

Piecewise Linear Representation (PLR) has been a widely used method for approximating data streams in the form of compact line segments. The buffer-based approach to PLR enables a semi-global approximation which relies on the aggregated processing of batches of streamed data so that to adjust and improve the approximation results. However, one challenge towards applying the buffer-based approach is allocating the necessary memory resources for stream buffering. This challenge is further complicated in a multi-stream environment where multiple data streams are competing for the available memory resources, especially in resource-constrained systems such as sensors and mobile devices.

Given a directed graph G, a reachability query (u, v) asks whether there exists a path from a node u to a node v in G. The existing studies support reachability queries using indexing techniques, where both the graph and the index are required to reside in main memory. However, they cannot handle reachability queries on massive graphs, when the graph and the index cannot be entirely held in memory because of the high I/O cost. In this paper, we focus on how to minimize the I/O cost when answering reachability queries on massive graphs that cannot reside entirely in memory. First, we propose a new Yes-Label scheme, as a complement of the No-Label used in GRAIL [23], to reduce the number of intermediate results generated. Second, we show how to minimize the number of I/Os using a heap-on-disk data structure when traversing a graph. We also propose new methods to partition the heap-on-disk, in order to ensure that only sequential I/Os are performed. Third, we analyze our approaches and show how to extend our approaches to answer multiple reachability queries effectively. Finally, we conducted extensive performance studies on both large synthetic and large real graphs, and confirm the efficiency of our approaches.

The increasing availability of GPS-embedded mobile devices has given rise to a new spectrum of location-based services, which have accumulated a huge collection of location trajectories. In practice, a large portion of these trajectories are of low-sampling-rate. For instance, the time interval between consecutive GPS points of some trajectories can be several minutes or even hours. With such a low sampling rate, most details of their movement are lost, which makes them difficult to process effectively. In this work, we investigate how to reduce the uncertainty in such kind of trajectories. Specifically, given a low-sampling-rate trajectory, we aim to infer its possible routes. The methodology adopted in our work is to take full advantage of the rich information extracted from the historical trajectories. We propose a systematic solution, History based Route Inference System (HRIS), which covers a series of novel algorithms that can derive the travel pattern from historical data and incorporate it into the route inference process. To validate the effectiveness of the system, we apply our solution to the map-matching problem which is an important application scenario of this work, and conduct extensive experiments on a real taxi trajectory dataset. The experiment results demonstrate that HRIS can achieve higher accuracy than the existing map-matching algorithms for low-sampling-rate trajectories.

Estimating the global data distribution in Peer-to-Peer (P2P) networks is an important issue and has yet to be well addressed. It can benefit many P2P applications, such as load balancing analysis, query processing, and data mining. Inspired by the inversion method for random variate generation, in this paper we present a novel model named distribution-free data density estimation for dynamic ring-based P2P networks to achieve high estimation accuracy with low estimation cost regardless of distribution models of the underlying data. It generates random samples for any arbitrary distribution by sampling the global cumulative distribution function and is free from sampling bias. In P2P networks, the key idea for distribution-free estimation is to sample a small subset of peers for estimating the global data distribution over the data domain. Algorithms on computing and sampling the global cumulative distribution function based on which global data distribution is estimated are introduced with detailed theoretical analysis. Our extensive performance study confirms the effectiveness and efficiency of our methods in ring-based P2P networks.

Given a data point set D, a query point set Q, and an integer k, the Group Nearest Group (GNG) query finds a subset ω (|ω| ≤ k)of points from Dsuch that the total distance from all points in Q to the nearest point in ω is not greater than any other subset ω' (|ω'| ≤ k) of points in D. GNG query is a partition-based clustering problem which can be found in many real applications and is NP-hard. In this paper, Exhaustive Hierarchical Combination (EHC) algorithm and Subset Hierarchial Refinement (SHR) algorithm are developed for GNG query processing. While EHC is capable to provide the optimal solution for k = 2, SHR is an efficient approximate approach that combines database techniques with local search heuristic. The processing focus of our approaches is on minimizing the access and evaluation of subsets of cardinality k in D since the number of such subsets is exponentially greater than |D|. To do that, the hierarchical blocks of data points at high level are used to find an intermediate solution and then refined by following the guided search direction at low level so as to prune irrelevant subsets. The comprehensive experiments on both real and synthetic data sets demonstrate the superiority of SHR in terms of efficiency and quality.

With the rapidly increasing availability of uncertain data in many important applications such as location-based services, sensor monitoring, and biological information management systems, uncertainty-aware query processing has received a significant amount of research effort from the database community in recent years. In this paper, we investigate a new type of query in the context of uncertain databases, namely uncertain top-k influential sites query (UTkIS query for short), which can be applied in a wide range of application areas such as marketing analysis and mobile services. Since it is not so straightforward to precisely define the semantics of top-k query with uncertain data, in this paper we introduce a novel and more intuitive formulation of the query on the basis of expected rank semantics. To address the efficiency issue caused by possible worlds exploration, we propose effective pruning rules and a divide-and-conquer paradigm such that the number of candidates as well as the number of possible worlds to be considered can be significantly reduced. Finally, we conduct extensive experiments on real data sets to verify the effectiveness and efficiency of the new methods proposed in this paper.

Shortest path query is one of the most fundamental queries in spatial network databases. There exist algorithms that can process shortest path queries in real time. However, many complex applications require more than just the calculation of a single shortest path. For example, one of the common ways to determine the importance (or price) of a vertex or an edge in spatial network is to use Vickrey pricing, which intuitively values the vertex v (or edge e ) based on how much harder for travelling from the sources to the destinations without using v (or e ). In such cases, the alternative shortest paths without using v (or e ) are required. In this article, we propose using a precomputation based approach for both single pair alternative shortest path and all pairs shortest paths processing. To compute the alternative shortest path between a source and a destination efficiently, a naïive way is to precompute and store all alternative shortest paths between every pair of vertices avoiding every possible vertex (or edge), which requires O ( n 4 ) space. Currently, the state of the art approach for reducing the storage cost is to choose a subset of the vertices as center points, and only store the single-source alternative shortest paths from those center points. Such approach has the space complexity of O ( n 2 log n ). We propose a storage scheme termed iSPQF , which utilizes shortest path quadtrees by observing the relationships between each avoiding vertex and its corresponding alternative shortest paths. We have reduced the space complexity from the naïive O ( n 4 ) (or the state of the art O ( n 4 log n )) to O (min( γ, L ) n 1.5 ) with comparable query performance of O ( K ), where K is the number of vertices in the returned paths, L is the diameter of the spatial network, and γ is a value that depends on the structure of the spatial network, which is empirically estimated to be 40 for real road networks. Experiments on real road networks have shown that the space cost of the proposed iSPQF is scalable, and both the algorithms based on iSPQF are efficient.

The problem of monitoring the correlations of discrete streams is to continuously monitor the temporal correlations among massive discrete streams. A temporal correlation of two streams is defined as a tracking behavior, i.e., the most recent pattern of one stream is very similar to a historical pattern of another stream. The challenge is that both the tracking stream and the tracked stream are evolving, which causes the frequent updates of the correlation-ships. The straightforward way of monitoring correlations by brute-force subsequence matching will be very expensive for massive streams. We propose techniques that are able to significantly reduce the number of expensive subsequence matching calls, by continuously pruning and refining the correlated streams. Extensive experiments on the streaming trajectories show the significant performance improvement achieved by the proposed algorithms.

In a pilot application based on web search engine called Web-based Relation Completion (WebRC), we propose to join two columns of entities linked by a predefined relation by mining knowledge from the web through a web search engine. To achieve this, a novel retrieval task Relation Query Expansion (RelQE) is modelled: given an entity (query), the task is to retrieve documents containing entities in predefined relation to the given one. Solving this problem entails expanding the query before submitting it to a web search engine to ensure that mostly documents containing the linked entity are returned in the top K search results. In this paper, we propose a novel Learning-based Relevance Feedback (LRF) approach to solve this retrieval task. Expansion terms are learned from training pairs of entities linked by the predefined relation and applied to new entity-queries to find entities linked by the same relation. After describing the approach, we present experimental results on real-world web data collections, which show that the LRF approach always improves the precision of top-ranked search results to up to 8.6 times the baseline. Using LRF, WebRC also shows performances way above the baseline.

Trajectories representing the motion of moving objects are typically obtained via location sampling, e.g. using GPS or road-side sensors, at discrete time-instants. In-between consecutive samples, nothing is known about the whereabouts of a given moving object. Various models have been proposed (e.g., sheared cylinders; spacetime prisms) to represent the uncertainty of the moving objects both in unconstrained Euclidian space, as well as road networks. In this paper, we focus on representing the uncertainty of the objects moving along road networks as time-dependent probability distribution functions, assuming availability of a maximal speed on each road segment. For these settings, we introduce a novel indexing mechanism -- UTH (Uncertain Trajectories Hierarchy), based upon which efficient algorithms for processing spatio-temporal range queries are proposed. We also present experimental results that demonstrate the benefits of our proposed methodologies.

In this paper, we propose and investigate a novel spatial query called Reverse Path Nearest Neighbor (R-PNN) search to find the most accessible locations in road networks. Given a trajectory data-set and a list of location candidates specified by users, if a location o is the Path Nearest Neighbor (PNN) of k trajectories, the influence-factor of o is defined as k and the R-PNN query returns the location with the highest influence-factor. The R-PNN query is an extension of the conventional Reverse Nearest Neighbor (RNN) search. It can be found in many important applications such as urban planning, facility allocation, traffic monitoring, etc. To answer the R-PNN query efficiently, an effective trajectory data pre-processing technique is conducted in the first place. We cluster the trajectories into several groups according to their distribution. Based on the grouped trajectory data, a two-phase solution is applied. First, we specify a tight search range over the trajectory and location data-sets. The efficiency study reveals that our approach defines the minimum search area. Second, a series of optimization techniques are adopted to search the exact PNN for trajectories in the candidate set. By combining the PNN query results, we can retrieve the most accessible locations. The complexity analysis shows that our solution is optimal in terms of time cost. The performance of the proposed R-PNN query processing is verified by extensive experiments based on real and synthetic trajectory data in road networks.

The booming industry of location-based services has accumulated a huge collection of users' location trajectories of driving, cycling, hiking, etc. In this work, we investigate the problem of discovering the Most Popular Route (MPR) between two locations by observing the traveling behaviors of many previous users. This new query is beneficial to travelers who are asking directions or planning a trip in an unfamiliar city/area, as historical traveling experiences can reveal how people usually choose routes between locations. To achieve this goal, we firstly develop a Coherence Expanding algorithm to retrieve a transfer network from raw trajectories, for indicating all the possible movements between locations. After that, the Absorbing Markov Chain model is applied to derive a reasonable transfer probability for each transfer node in the network, which is subsequently used as the popularity indicator in the search phase. Finally, we propose a Maximum Probability Product algorithm to discover the MPR from a transfer network based on the popularity indicators in a breadth-first manner, and we illustrate the results and performance of the algorithm by extensive experiments.

Multimedia similarity search has been playing a critical role in many novel applications. Typically, multimedia objects are described by high-dimensional feature vectors (or points) which are organized in databases for retrieval. Although many high-dimensional indexing methods have been proposed to facilitate the search process, efficient retrieval over large, sparse and extremely high-dimensional databases remains challenging due to the continuous increases in data size and feature dimensionality. In this paper, we propose the first framework for Data Co-Reduction (DCR) on both data size and feature dimensionality. By utilizing recently developed co-clustering methods, DCR simultaneously reduces both size and dimensionality of the original data into a compact subspace, where lower bounds of the actual distances in the original space can be efficiently established to achieve fast and lossless similarity search in the filter-and refine approach. Particularly, DCR considers the duality between size and dimensionality, and achieves the optimal coreduction which generates the least number of candidates for actual distance computations. We conduct an extensive experimental study on large and real-life multimedia datasets, with dimensionality ranging from 432 to 1936. Our results demonstrate that DCR outperforms existing methods significantly for lossless retrieval, especially in the presence of extremely high dimensionality.

The skyline of a set of multi-dimensional points (tuples) consists of those points for which no clearly better point exists in the given set, using component-wise comparison on domains of interest. Skyline queries, i.e., queries that involve computation of a skyline, can be computationally expensive, so it is natural to consider parallelized approaches which make good use of multiple processors. We approach this problem by using hyperplane projections to obtain useful partitions of the data set for parallel processing. These partitions not only ensure small local skyline sets, but enable efficient merging of results as well. Our experiments show that our method consistently outperforms similar approaches for parallel skyline computation, regardless of data distribution, and provides insights on the impacts of different optimization strategies.

With the increasing amount of text data stored in relational databases, there is a demand for RDBMS to support keyword queries over text data. As a search result is often assembled from multiple relational tables, traditional IR-style ranking and query evaluation methods cannot be applied directly. In this paper, we study the effectiveness and the efficiency issues of answering top-k keyword query in relational database systems. We propose a new ranking formula by adapting existing IR techniques based on a natural notion of virtual document. We also propose several efficient query processing methods for the new ranking method. We have conducted extensive experiments on large-scale real databases using two popular RDBMSs. The experimental results demonstrate significant improvement to the alternative approaches in terms of retrieval effectiveness and efficiency.

Given a set of lists, where items of each list are sorted by the ascending order of their values, the objective of this paper is to figure out the common items that appear in all of the lists efficiently. This problem is sometimes known as common items extraction from sorted lists. To solve this problem, one common approach is to scan all items of all lists sequentially in parallel until one of the lists is exhausted. However, we observe that if the overlap of items across all lists is not high, such sequential access approach can be significantly improved. In this paper, we propose two algorithms, MergeSkip and MergeESkip, to solve this problem by taking the idea of skipping as many items of lists as possible. As a result, a large number of comparisons among items can be saved, and hence the efficiency can be improved. We conduct extensive analysis of our proposed algorithms on one real dataset and two synthetic datasets with different data distributions. We report all our findings in this paper.

Online video steam data is surging to an unprecedented level. Massive video publishing and sharing impose heavy demands on continuous video near-duplicate detection for many novel video applications. This paper presents an accurate and accelerated system for video near-duplicate detection over continuous video streams. We propose to transform a high-dimensional video stream into a one-dimensional Video Trend Stream (VTS) to monitor the continuous luminance changes of consecutive frames, based on which video similarity is derived. In order to do fast comparison and effective early pruning, a compact auxiliary signature named CutSig is proposed to approximate the video structure. CutSig explores cut distribution feature of the video structure and contributes to filter candidates quickly. To scan along a video stream in a rapid way, shot cuts with local maximum AI (average information) in a query video are used as reference cuts, and a skipping approach based on reference cut alignment is embedded for efficient acceleration. Extensive experimental results on detecting diverse near-duplicates in real video streams show the effectiveness and efficiency of our method.

In this paper, we propose a search-based approach to join two tables in the absence of clean join attributes. Non-structured documents from the web are used to express the correlations between a given query and a reference list. To implement this approach, a major challenge we meet is how to efficiently determine the number of times and the locations of each clean reference from the reference list that is approximately mentioned in the retrieved documents. We formalize the Approximate Membership Localization (AML) problem and propose an efficient partial pruning algorithm to solve it. A study using real-word data sets demonstrates the effectiveness of our search-based approach, and the efficiency of our AML algorithm.

Trajectory search has long been an attractive and challenging topic which blooms various interesting applications in spatial-temporal databases. In this work, we study a new problem of searching trajectories by locations, in which context the query is only a small set of locations with or without an order specified, while the target is to find the k Best-Connected Trajectories (k-BCT) from a database such that the k-BCT best connect the designated locations geographically. Different from the conventional trajectory search that looks for similar trajectories w.r.t. shape or other criteria by using a sample query trajectory, we focus on the goodness of connection provided by a trajectory to the specified query locations. This new query can benefit users in many novel applications such as trip planning.

We investigate the problem of creating and analyzing samples of relational databases to find relationships between string-valued attributes. Our focus is on identifying attribute pairs whose value sets overlap, a pre-condition for typical joins over such attributes. However, real-world data sets are often 'dirty', especially when integrating data from different sources. To deal with this issue, we propose new similarity measures between sets of strings, which not only consider set based similarity, but also similarity between strings instances. To make the measures effective, we develop efficient algorithms for distributed sample creation and similarity computation. Test results show that for dirty data our measures are more accurate for measuring value overlap than existing sample-based methods, but we also observe that there is a clear tradeoff between accuracy and speed. This motivates a two-stage filtering approach, with both measures operating on the same samples.

The K-Nearest Neighbor search (kNN) problem has been investigated extensively in the past due to its broad range of applications. In this paper we study this problem in the context of fuzzy objects that have indeterministic boundaries. Fuzzy objects play an important role in many areas, such as biomedical image databases and GIS. Existing research on fuzzy objects mainly focuses on modelling basic fuzzy object types and operations, leaving the processing of more advanced queries such as kNN query untouched. In this paper, we propose two new kinds of kNN queries for fuzzy objects, Ad-hoc kNN query (AKNN) and Range kNN query (RKNN), to find the k nearest objects qualifying at a probability threshold or within a probability range. For efficient AKNN query processing, we optimize the basic best-first search algorithm by deriving more accurate approximations for the distance function between fuzzy objects and the query object. To improve the performance of RKNN search, effective pruning rules are developed to significantly reduce the search space and further speed up the candidate refinement process. The efficiency of our proposed algorithms as well as the optimization techniques are verified with an extensive set of experiments using both synthetic and real datasets.

Entity resolution (ER) is a problem that arises in many areas. In most of cases, it represents a task that multiple entities from different sources require to be identified if they refer to the same or different objects because there are not unique identifiers associated with them. In this paper, we propose a model using web pages identification to identify entities and merge those entities refer to one object together. We use a classical name disambiguation problem as case study and examine our model on a subset of digital library records as the first stage of our work. The favorable results indicated that our proposed approach is highly effective. © 2010 Copyright is held by the author/owner(s).

Duplicates in data streams may often be observed by the projection on a subspace and/or multiple recordings of objects. Without the uniqueness assumption on observed data elements, many conventional aggregates computation problems need to be further investigated due to their duplication-sensitive nature. In this paper, we present novel, space-efficient, one-scan algorithms to continuously maintain duplicate-insensitive order sketches so that rank-based queries can be approximately processed with a relative rank error guarantee \epsilon in the presence of data duplicates. Besides the space efficiency, the proposed algorithms are time-efficient and highly accurate. Moreover, our techniques may be immediately applied to the heavy hitter problem against distinct elements and to the existing fault-tolerant distributed communication techniques. A comprehensive performance study demonstrates that our algorithms can support real-time computation against high-speed data streams.

Efficiently and effectively identifying similar videos is an important and nontrivial problem in content-based video retrieval. This paper proposes a subspace symbolization approach, namely SUDS, for content-based retrieval on very large video databases. The novelty of SUDS is that it explores the data distribution in subspaces to build a visual dictionary with which the videos are processed by deriving the string matching techniques with two-step data simplification. Specifically, we first propose an adaptive approach, called VLP, to extract a series of dominant subspaces of variable lengths from the whole visual feature space without the constraint of dimension consecutiveness. A stable visual dictionary is built by clustering the video keyframes over each dominant subspace. A compact video representation model is developed by transforming each keyframe into a word that is a series of symbols in the dominant subspaces, and further each video into a series of words. Then, we present an innovative similarity measure called CVE, which adopts a complementary information compensation scheme based on the visual features and sequence context of videos. Finally, an efficient two-layered index strategy with a number of query optimizations is proposed to facilitate video retrieval. The experimental results demonstrate the high effectiveness and efficiency of SUDS.

Recently, video search reranking has been an effective mechanism to improve the initial text-based ranking list by incorporating visual consistency among the result videos. While existing methods attempt to rerank all the individual result videos, they suffer from several drawbacks. In this article, we propose a new video reranking paradigm called cluster-based video reranking (CVR). The idea is to first construct a video near-duplicate graph representing the visual similarity relationship among videos, followed by identifying the near-duplicate clusters from the video near-duplicate graph, then ranking the obtained near-duplicate clusters based on cluster properties and intercluster links, and finally for each ranked cluster, a representative video is selected and returned. Compared to existing methods, the new CVR ranks clusters and exhibits several advantages, including superior reranking by utilizing more reliable cluster properties, fast reranking on a small number of clusters, diverse and representative results. Particularly, we formulate the near-duplicate cluster identification as a novel maximally cohesive subgraph mining problem. By leveraging the designed cluster scoring properties indicating the cluster's importance and quality, random walk is applied over the near-duplicate cluster graph to rank clusters. An extensive evaluation study proves the novelty and superiority of our proposals over existing methods.

Mobile devices have become indispensable in daily life, and hence how to take advantage of these portable and powerful facilities to share resources and information begins to emerge as an interesting problem. In this paper, we investigate the problem of information retrieval in a mobile peer-to-peer network. The prevailing approach to information retrieval is to apply flooding methods because of its quick response and easy maintenance. Obviously, this kind of approach wastes a huge amount of communication bandwidth which greatly affects the availability of the network, and the battery power which significantly shortens the serving time of mobile devices in the network. To tackle this problem, we propose a novel approach by mimicking different human behaviors of social networks, which takes advantages of Intelligence Accuracy (IA) mechanism that evaluates the distance from a node to certain resources in the network. Extensive experimental results show the efficiency and effectiveness of our approach as well as its scalability in a volatile environment.

To explore the benefit of advertising instant and location-aware commercials that can not be effectively promoted by traditional medium like TV program and Internet, we propose in this paper a solution for disseminating instant advertisements to users within the area of interest through a mobile peer-to-peer network. This is a new application scenario, and we devise an opportunistic gossiping model for advertisement propagation with spatial and temporal constraints. As bandwidth and computational resources are limited in a wireless environment, two optimization mechanisms utilizing distance and velocity information are provided for reducing redundant advertising messages. User interest is also considered as another critical factor in adjusting the advertisement propagation model, and we adopt the FM algorithm to achieve efficient counting of distinct users' interests. Finally, we study the performance of our solution through simulation in NS-2. Compared with the naive flooding method, our approach achieves high quality delivery rate while reducing the number of messages by nearly an order of magnitude.

Video search has become a compelling research topic in recent years, due to the proliferation of online video uploading/sharing sites and the exponential explosion of video data. In this demonstration, we showcase a Web-based integrated platform which performs online detection of near-duplicate occurrences over continuous video streams, as well as retrieval of near-duplicate clips from segmented video collections. In particular, our method to detect relevant subsequences in a streaming video is characterized by a novel one-dimensional distance trajectory capturing the changes of consecutive frames. Such a trajectory is further represented by a sequence of compact signatures. An effective similarity measure is devised to compare the trajectory with multiple query videos. This system shows a number of new features compared with our previous prototype.

A common approach to performing keyword search over relational databases is to find the minimum Steiner trees in database graphs. These methods, however, are rather expensive as the minimum Steiner tree problem is known to be NP-hard. Further, these methods cannot benefit from DBMS capabilities. We propose a new concept called Compact Steiner Tree (CSTree), which can be used to approximate the Steiner tree problem for answering top-k keyword queries efficiently. We propose a structure-aware index, together with an effective ranking mechanism for fast, progressive and accurate retrieval of top-k highest ranked CSTrees. The proposed techniques can be implemented using a standard RDBMS to benefit from its indexing and query processing capability. The experimental results show that our method achieves high search efficiency and result quality comparing to existing state-of-the-art approaches.

We propose a subspace symbolization approach, namely SUDS, for content-based search on very large video databases. The novelty of SUDS is that it explores the data distribution in subspaces to build a visual dictionary. With this dictionary, the video data are processed using string matching techniques with two-step data simplification. A compact video representation model is developed by transforming each keyframe into a word that is a series of symbols in the dominant subspaces. Then, we present an innovative similarity measure called ED, which draws from the concept of the edit distance on strings to conduct video matching. The experimental results demonstrate the high effectiveness of SUDS with optimal parameters.

This paper addresses the problem of monitoring the k nearest neighbors to a dynamically changing path in road networks. Given a destination where a user is going to, this new query returns the k-NN with respect to the shortest path connecting the destination and the user's current location, and thus provides a list of nearest candidates for reference by considering the whole coming journey. We name this query the k-Path Nearest Neighbor query (k-PNN). As the user is moving and may not always follow the shortest path, the query path keeps changing. The challenge of monitoring the k-PNN for an arbitrarily moving user is to dynamically determine the update locations and then refresh the k-PNN efficiently. We propose a three-phase Best-first Network Expansion (BNE) algorithm for monitoring the k-PNN and the corresponding shortest path. In the searching phase, the BNE finds the shortest path to the destination, during which a candidate set that guarantees to include the k-PNN is generated at the same time. Then in the verification phase, a heuristic algorithm runs for examining candidates' exact distances to the query path, and it achieves significant reduction in the number of visited nodes. The monitoring phase deals with computing update locations as well as refreshing the k-PNN in different user movements. Since determining the network distance is a costly process, an expansion tree and the candidate set are carefully maintained by the BNE algorithm, which can provide efficient update on the shortest path and the k-PNN results. Finally, we conduct extensive experiments on real road networks and show that our methods achieve satisfactory performance.

Floating Car Data (FCD) provides an economic complement to infrastructure-based traffic monitoring systems. Based on our previous MOIR platform [5], we use FCD as the data source for large-scale real-time traffic monitoring. This new function brings a challenge of efficiently handling of streaming data from a very large number of moving objects. Server overload problems can occur when a system fails to process data and queries in real-tme, which can lead to critical issues such as unbounded delay accumulation, lost monitoring accuracy or lack of spontaneity. These problems can be addressed by adopting suitable load dropping decisions. In this work, we demonstrate several load shedding techniques, focusing on decision-making based on data attributes. With the end results being quantified and visualized using real data for a large city, this proof-of-concept system provides a convincing way of validating our ideas.

With the growing demand for visual information of rich content, effective and efficient manipulations of large video databases are increasingly desired. Many investigations have been made on content-based video retrieval. However, despite the importance, video subsequence identification, which is to find the similar content to a short query clip from a long video sequence, has not been well addressed. This paper presents a graph transformation and matching approach to this problem, with extension to identify the occurrence of potentially different ordering or length due to content editing. With a novel batch query algorithm to retrieve similar frames, the mapping relationship between the query and database video is first represented by a bipartite graph. The densely matched parts along the long sequence are then extracted, followed by a filter-and-refine search strategy to prune some irrelevant subsequences. During the filtering stage, maximum size matching is deployed for each subgraph constructed by the query and candidate subsequence to obtain a smaller set of candidates. During the refinement stage, sub-maximum similarity matching is devised to identify the subsequence with the highest aggregate score from all candidates, according to a robust video similarity model that incorporates visual content, temporal order, and frame alignment information. The performance studies conducted on a long video recording of 50 hours validate that our approach is promising in terms of both search accuracy and speed.

Recently, video clips have become very popular online. The massive influx of video clips has created an urgent need for video search engines to facilitate retrieving relevant clips. Different from traditional long videos, a video clip is a short video often expressing a moment of significance. Due to the high complexity of video data, efficient video clip search from large databases turns out to be very challenging. We propose a novel video clip representation model called the Bounded Coordinate System (BCS), which is the first single representative capturing the dominating content and content—changing trends of a video clip. It summarizes a video clip by a coordinate system, where each of its coordinate axes is identified by principal component analysis (PCA) and bounded by the range of data projections along the axis. The similarity measure of BCS considers the operations of translation, rotation, and scaling for coordinate system matching. Particularly, rotation and scaling reflect the difference of content tendencies. Compared with the quadratic time complexity of existing methods, the time complexity of measuring BCS similarity is linear. The compact video representation together with its linear similarity measure makes real-time search from video clip collections feasible. To further improve the retrieval efficiency for large video databases, a two-dimensional transformation method called Bidistance Transformation (BDT) is introduced to utilize a pair of optimal reference points with respect to bidirectional axes in BCS. Our extensive performance study on a large database of more than 30,000 video clips demonstrates that BCS achieves very high search accuracy according to human judgment. This indicates that content tendencies are important in determining the meanings of video clips and confirms that BCS can capture the inherent moment of video clip to some extent that better resembles human perception. In addition, BDT outperforms existing indexing methods greatly. Integration of the BCS model and BDT indexing can achieve real-time search from large video clip databases.

Existing prediction methods in moving objects databases cannot forecast locations accurately if the query time is far away from the current time. Even for near future prediction, most techniques assume the trajectory of an object's movements can be represented by some mathematical formulas of motion functions based on its recent movements. However, an object's movements are more complicated than what the mathematical formulas can represent. Prediction based on an object's trajectory patterns is a powerful way and has been investigated by several work. But their main interest is how to discover the patterns. In this paper, we present a novel prediction approach, namely The Hybrid Prediction Model, which estimates an object's future locations based on its pattern information as well as existing motion functions using the object's recent movements. Specifically, an object's trajectory patterns which have ad-hoc forms for prediction are discovered and then indexed by a novel access method for efficient query processing. In addition, two query processing techniques that can provide accurate results for both near and distant time predictive queries are presented. Our extensive experiments demonstrate that proposed techniques are more accurate and efficient than existing forecasting schemes.

We introduce a convoy query that retrieves all convoys from historical trajectories, each of which consists of a set of objects that travelled closely during a certain time period. Convoy query is useful for many applications such as carpooling and traffic jam analysis, however, limited work has been done in the database community. This study proposes three efficient methods for discovering convoys. The main novelty of our methods is to approximate original trajectories by using line simplification methods and perform the discovery process over the simplified trajectories with bounded errors. Our experimental results confirm the effectiveness and efficiency of our methods.

MOIR is a Web-based prototype to support a number of novel applications with network-constrained moving object management. Technical aspects of MOIR range from data acquisition and trajectory smoothing, trajectory data management and query processing, movement predications, and location based Web page recommendation. The demo is in the context of detailed digital road maps with 38,0000 road segments and 55,000 road intersection points, and real spatiotemporal data of over ten thousand taxis in Beijing.

As mobile devices with positioning capabilities continue to proliferate, data management for so-called trajectory databases that capture the historical movements of populations of moving objects becomes important. This paper considers the querying of such databases for convoys, a convoy being a group of objects that have traveled together for some time. More specifically, this paper formalizes the concept of a convoy query using density-based notions, in order to capture groups of arbitrary extents and shapes. Convoy discovery is relevant for real-life applications in throughput planning of trucks and carpooling of vehicles. Although there has been extensive research on trajectories in the literature, none of this can be applied to retrieve correctly exact convoy result sets. Motivated by this, we develop three efficient algorithms for convoy discovery that adopt the well-known filter-refinement framework. In the filter step, we apply line-simplification techniques on the trajectories and establish distance bounds between the simplified trajectories. This permits efficient convoy discovery over the simplified trajectories without missing any actual convoys. In the refinement step, the candidate convoys are further processed to obtain the actual convoys. Our comprehensive empirical study offers insight into the properties of the paper's proposals and demonstrates that the proposals are effective and efficient on real-world trajectory data.

Searching relevant visual information based on content features in large databases is an interesting and changeling topic that has drawn lots of attention from both the research community and industry. This paper gives an overview of our investigations on effective and efficient video similarity search. We briefly introduce some novel techniques developed for two specific tasks studied in this PhD project: video retrieval in a large collection of segmented video clips, and video subsequence identification from a long unsegmented stream. The proposed methods for processing these two types of similarity queries have shown encouraging performance and are being incorporated into our prototype system of video search named UQLIPS, which has demonstrated some marketing potentials for commercialisation.

Similarity search for 3D structure data sets is fundamental to many database applications such as molecular biology, image registration, and computer-aided design. Identifying the common 3D subtructures between two objects is an important research problem. However, it is well known that computing structural similarity is very expensive due to the high exponential time complexity of structure similarity measures. As the structure databases keep growing rapidly, real-time search from large-structure databases becomes problematic. In this paper, we present a novel statistical model, that is, the multiresolution Localized Co-Occurrence Model (LCM), to approximately measure the similarity between the two point-based 3D structures in linear time complexity for fast retrieval. LCM could capture both distribution characteristics and spatial structure of 3D data by localizing the point co-occurrence relationship within a predefined neighborhood system. As a step further, a novel structure query processing method called the incremental and Bounded search (iBound) is also proposed to speed up the search process. iBound avoids a large amount of expensive computation at higher resolution LCMs. By superposing two LCMs, their largest common substructure can also be found quickly. Finally, our experiment results prove the effectiveness and efficiency of our methods.

Skyline query processing has been investigated extensively in recent years, mostly for only one query reference point. An example of a single-source skyline query is to find hotels which are cheap and close to the beach (an absolute query), or close to a user-given location (a relatively query). A multi-source skyline query considers several query points at the same time (e.g., to find hotels which are cheap and close to the University, the Botanic Garden and the China Town). In this paper, we consider the problem of efficient multi-source skyline query processing in road networks. It is not only the first effort to consider multi-source skyline query in road networks but also the first effort to process the relative skyline queries where the network distance between two locations needs to be computed on-the-fly. Three different query processing algorithms are proposed and evaluated in this paper. The Lower Bound Constraint algorithm (LBC) is proven to be an instance optimal algorithm. Extensive experiments using large real road network datasets demonstrate that LBC is four times more efficient than a straightforward algorithm.

To retrieve similar database videos to a query clip, each video is typically represented by a sequence of high-dimensional feature vectors. Given a query video containing m feature vectors, an independent nearest neighbor (NN) search for each feature vector is often first performed. Completing all the NN searches, an overall similarity is then computed, i.e., a single video retrieval usually involves the searches for m times. Since normally nearby feature vectors in a video are similar, a large number of expensive random disk accesses are expected to repeatedly occur, which crucially affects the overall query performance. Batch nearest neighbor (BNN) search is stated as a single operation that performs a batch of individual NN searches. This paper presents a novel approach to efficient high-dimensional BNN search called dynamic query ordering (DQO) for advanced optimizations in both I/O and CPU cost. Observing the overlapped candidates (or search space) of a pervious query may help to further reduce the candidate sets of succeeding queries, DQO aims to progressively find a query order such that the common candidates among queries are fully utilized to maximally reduce the total number of candidates. Modelling the candidate set relationship by a candidate overlapping graph (COG), DQO iteratively selects the next query to be executed based on its estimated pruning power to the rest of queries with the dynamically updated COG. The extensive experiments show its significance.

In this paper, we investigated the problem of approximately processing rank queries against distinct data elements in a data stream with the presence of duplicated data elements. Novel space and time efficient techniques are developed for continuously maintaining order statistics so that rank queries can be answered with a relative error guarantee. This is the first work providing the space and time efficient data stream techniques to process approximate rank queries with relative error guarantees against distinct data elements.

Dimensionality reduction plays an important role in efficient similarity search, which is often based on k-nearest neighbor (k-NN) queries over a high-dimensional feature space. In this paper, we introduce a novel type of k-NN query, namely conditional k-NN (ck-NN), which considers dimension-specific constraint in addition to the inter-point distances. However, existing dimensionality reduction methods are not applicable to this new type of queries. We propose a novel Mean-Std (standard deviation) guided Dimensionality Reduction (MSDR) to support a pruning based efficient ck-NN query processing strategy. Our preliminary experimental results on 3D protein structure data demonstrate that the MSDR method is promising.

With the increasing amount of text data stored in relational databases, there is a demand for RDBMS to support keyword queries over text data. As a search result is often assembled from multiple relational tables, traditional IR-style ranking and query evaluation methods cannot be applied directly.

A k-NN query finds the k nearest-neighbors of a given point from a point database. When it is sufficient to measure object distance using the Euclidian distance, the key to efficient k-NN query processing is to fetch and check the distances of a minimum number of points from the database. For many applications, such as vehicle movement along road networks or rover and animal movement along terrain surfaces, the distance is only meaningful when it is along a valid movement path. For this type of k-NN queries, the focus of efficient query processing is to minimize the cost of computing distances using the environment data (such as the road network data and the terrain data), which can be several orders of magnitude larger than that of the point data. Efficient processing of k-NN queries based on the Euclidian distance or the road network distance has been investigated extensively in the past. In this paper, we investigate the problem of surface k-NN query processing, where the distance is calculated from the shortest path along a terrain surface. This problem is very challenging, as the terrain data can be very large and the computational cost of finding shortest paths is very high. We propose an efficient solution based on multiresolution terrain models. Our approach eliminates the need of costly process of finding shortest paths by ranking objects using estimated lower and upper bounds of distance on multiresolution terrain models.

Quantile computation has many applications including data mining and financial data analysis. It has been shown that an /spl epsi/-approximate summary can be maintained so that, given a quantile query (/spl phi/,/spl epsi/), the data item at rank /spl lceil//spl phi/N/spl rceil/ may be approximately obtained within the rank error precision /spl epsi/N over all N data items in a data stream or in a sliding window. However, scalable online processing of massive continuous quantile queries with different /spl phi/ and /spl epsi/ poses a new challenge because the summary is continuously updated with new arrivals of data items. In this paper, first we aim to dramatically reduce the number of distinct query results by grouping a set of different queries into a cluster so that they can be processed virtually as a single query while the precision requirements from users can be retained. Second, we aim to minimize the total query processing costs. Efficient algorithms are developed to minimize the total number of times for reprocessing clusters and to produce the minimum number of clusters, respectively. The techniques are extended to maintain near-optimal clustering when queries are registered and removed in an arbitrary fashion against whole data streams or sliding windows. In addition to theoretical analysis, our performance study indicates that the proposed techniques are indeed scalable with respect to the number of input queries as well as the number of items and the item arrival rate in a data stream.

Multiresolution Triangular Mesh (MTM) models are widely used to improve the performance of large terrain visualization by replacing the original model with a simplified one. MTM models, which consist of both original and simplified data, are commonly stored in spatial database systems due to their size. The relatively slow access speed of disks makes data retrieval the bottleneck of such terrain visualization systems. Existing spatial access methods proposed to address this problem rely on main-memory MTM models, which leads to significant overhead during query processing. In this paper, we approach the problem from a new perspective and propose a novel MTM called direct mesh that is designed specifically for secondary storage. It supports available indexing methods natively and requires no modification to MTM structure. Experiment results, which are based on two real-world data sets, show an average performance improvement of 5-10 times over the existing methods.

Summarizing topological relations is fundamental to many spatial applications including spatial query optimization. In this article, we present several novel techniques to effectively construct cell density based spatial histograms for range (window) summarizations restricted to the four most important level-two topological relations: contains, contained, overlap, and disjoint. We first present a novel framework to construct a multiscale Euler histogram in 2D space with the guarantee of the exact summarization results for aligned windows in constant time. To minimize the storage space in such a multiscale Euler histogram, an approximate algorithm with the approximate ratio 19/12 is presented, while the problem is shown NP-hard generally. To conform to a limited storage space where a multiscale histogram may be allowed to have only k Euler histograms, an effective algorithm is presented to construct multiscale histograms to achieve high accuracy in approximately summarizing aligned windows. Then, we present a new approximate algorithm to query an Euler histogram that cannot guarantee the exact answers; it runs in constant time. We also investigate the problem of nonaligned windows and the problem of effectively partitioning the data space to support nonaligned window queries. Finally, we extend our techniques to 3D space. Our extensive experiments against both synthetic and real world datasets demonstrate that the approximate multiscale histogram techniques may improve the accuracy of the existing techniques by several orders of magnitude while retaining the cost efficiency, and the exact multiscale histogram technique requires only a storage space linearly proportional to the number of cells for many popular real datasets.

With rapid advances in video processing technologies and ever fast increments in network bandwidth, the popularity of video content publishing and sharing has made similarity search an indispensable operation to retrieve videos of user interests. The video similarity is usually measured by the percentage of similar frames shared by two video sequences, and each frame is typically represented as a high-dimensional feature vector. Unfortunately, high complexity of video content has posed the following major challenges for fast retrieval: (a) effective and compact video representations, (b) efficient similarity measurements, and (c) efficient indexing on the compact representations. In this paper, we propose a number of methods to achieve fast similarity search for very large video database. First, each video sequence is summarized into a small number of clusters, each of which contains similar frames and is represented by a novel compact model called Video Triplet (ViTri). ViTri models a cluster as a tightly bounded hypersphere described by its position, radius, and density. The ViTri similarity is measured by the volume of intersection between two hyperspheres multiplying the minimal density, i.e., the estimated number of similar frames shared by two clusters. The total number of similar frames is then estimated to derive the overall similarity between two video sequences. Hence the time complexity of video similarity measure can be reduced greatly. To further reduce the number of similarity computations on ViTris, we introduce a new one dimensional transformation technique which rotates and shifts the original axis system using PCA in such a way that the original inter-distance between two high-dimensional vectors can be maximally retained after mapping. An efficient B+-tree is then built on the transformed one dimensional values of ViTris' positions. Such a transformation enables B+-tree to achieve its optimal performance by quickly filtering a large portion of non-similar ViTris. Our extensive experiments on real large video datasets prove the effectiveness of our proposals that outperform existing methods significantly.