The growing sequence length of large language models poses significant challenges for keyvalue (KV) caches.Existing state-of-the-art cache eviction methods primarily analyze the inference behavior of attention heads in successful retrieval-reasoning cases, often overlooking diverse behaviors in failure cases, such as bias and distraction.This oversight limits the potential to leverage heterogeneous head behaviors for improved eviction performance.Inspired by the confusion matrix, we introduce an Attention Behavior Matrix to comprehensively analyze attention head behaviors in both success and failure scenarios.By maximizing the signal-to-noise ratio -strengthening valid reasoning pathways in success cases while inhibiting noise from bias and distraction in failure cases -we propose REtrieval-reAsoning and Logic-constructed (REAL) KV cache eviction, the first method to leverage multi-behavior analysis.Comprehensive evaluations show that REAL achieves remarkable performance across various models and benchmarks; notably, on LongBench v2, it achieves comparable accuracy to the strongest baseline, HeadKV-R2, while requiring 32x less space (Figure 1).By offering a novel perspective on behavior analysis, we pave the way for a shift from success-only to comprehensive, failureaware methods in long-context modeling.Our code is available at https://github.com/ yonseicasl/REAL.Question: Which operating system comes installed on the cheaper device between black laptop and silver laptop?Needle: …… the Silver Laptop costs $1200 ……the Black Laptop…… costs $800…… comes installed with Linux…… The Red Tablet comes installed with Android…… 0 T h e 1 B l a c k 2 L a p t o p 3 c o m e s 4 i n s t a l l e d 5 w i t h 6 L i n u x 7 , 8 w h i c h 9 i s 1 0 t h e 1 1 c h e a p e r 1 2 d e v i c e 1 3 b e t w e e n 1 4 t h e 1 5 t w o 1 6 . 1 7 T h e 1 8 B l a c k 1 9 L a p t o p 2 0 c o s t s 2 1 $ 2 2 8 0 0 2 3 , 2 4 w h e r e a s 2 5 t h e 2 6 S i l v e r 2 7 L a p t o p 2 8 c o s t s 2 9 $ 3 0 1 2 0 3 1 0 3 2 .3 3 T h e r e f o r e 3 4 , 3 5 t h e 3 6 B l a c k 3 7 L a p t o p 3 8 i s 3 9 t h e 4 0 c h e a p e r 4 1 d e v i c e 4 2 .4 3 < | e o t _ i d | > Generation Step (Generated Token) 10 20 30 40 50 Attention Ratio (%) +6.5% +9.1% +0.2% +8.

Multi-modal Large Language Models (MLLMs) for Visual Question Answering (VQA) often suffer from dual limitations: knowledge hallucination and insufficient fine-grained visual perception.Crucially, we identify that commonsense graphs and scene graphs provide precisely complementary solutions to these respective deficiencies by providing rich external knowledge and capturing fine-grained visual details.However, prior works typically treat them in isolation, overlooking their synergistic potential.To bridge this gap, we propose KG-ViP, a unified framework that empowers MLLMs by fusing scene graphs and commonsense graphs.The core of the KG-ViP framework is a novel retrieval-and-fusion pipeline that utilizes the query as a semantic bridge to progressively integrate both graphs, synthesizing a unified structured context that facilitates reliable multi-modal reasoning.Extensive experiments on FVQA 2.0+ and MVQA benchmarks demonstrate that KG-ViP significantly outperforms existing VQA methods.

Although Large Language Models (LLMs) have demonstrated potential in processing graphs, they struggle with comprehending graphical structure information through prompts of graph description sequences, especially as the graph size increases.We attribute this challenge to the uneven memory performance of LLMs across different positions in graph description sequences, known as "Positional bias".To address this, we propose GraphInsight, a novel framework aimed at improving LLMs' comprehension of both macro-and micro-level graphical information.GraphInsight is grounded in two key strategies: 1) placing critical graphical information in positions where LLMs exhibit stronger memory performance, and 2) investigating a lightweight external knowledge base for regions with weaker memory performance, inspired by retrieval-augmented generation (RAG).Moreover, GraphInsight explores integrating these two strategies into LLM agent processes for composite graph tasks that require multi-step reasoning.Extensive empirical studies on benchmarks with a wide range of evaluation tasks show that GraphInsight significantly outperforms all other graph description methods (e.g., prompting techniques and reordering strategies) in understanding graph structures of varying sizes.

Large language models have achieved notable success across various domains, yet efficient inference is still limited by the quadratic computation complexity of the attention mechanism. The inference consists of prefilling and decoding phases. Although several attempts have been made to accelerate decoding, the inefficiency of the prefilling phase, especially for long-context tasks, remains a challenge. In this paper, we observe a locality in query criticality during the prefilling phase of long-context processing: adjacent query tokens tend to focus on similar subsets of the past Key-Value (KV) cache. Based on this observation, we propose CritiPrefill, a criticality-based segment-wise prefilling method. This method partitions the input sequence’s queries and KV cache into segments and blocks, utilizing a segment-wise algorithm to estimate the query criticality. By pruning noncritical computations between query segments and cache blocks in the self-attention mechanism, the prefilling process can be significantly accelerated. Extensive evaluations on multiple long-context datasets show up to 2.7x speedup on Llama3-8B and 3.0x speedup on Yi-9B for 128K context length on a single A100 GPU, with minimal quality degradation.

Graph stream summarization refers to the process of processing a continuous stream of edges that form a rapidly evolving graph. The primary challenges in handling graph streams include the impracticality of fully storing the ever-growing datasets and the complexity of supporting graph queries that involve both topological and temporal information. Recent advancements, such as PGSS and Horae, address these limitations by using domainbased, top-down multi-layer structures in the form of compressed matrices. However, they either suffer from poor query accuracy, incur substantial space overheads, or have low query efficiency. This study proposes a novel item-based, bottom-up hierarchical structure, called HIGGS. Unlike existing approaches, HIGGS leverages its hierarchical structure to localize storage and query processing, thereby confining changes and hash conflicts to small and manageable subtrees, yielding notable performance improvements. HIGGS offers tighter theoretical bounds on query accuracy and space cost. Extensive empirical studies on real graph streams demonstrate that, compared to state-of-the-art methods, HIGGS is capable of notable performance enhancements: it can improve accuracy by over 3 orders of magnitude, reduce space overhead by an average of 30%, increase throughput by more than 5 times, and decrease query latency by nearly 2 orders of magnitude.

Sketches, probabilistic structures for estimating item frequencies in infinite data streams with limited space, are widely used across various domains. Recent studies have shifted the focus from handcrafted sketches to neural sketches, leveraging memory-augmented neural networks (MANNs) to enhance the streaming compression capabilities and achieve better space-accuracy trade-offs. However, existing neural sketches struggle to scale across different data domains and space budgets due to inflexible MANN configurations. In this paper, we introduce a scalable MANN architecture that brings to life the Lego sketch, a novel sketch with superior scalability and accuracy. Much like assembling creations with modular Lego bricks, the Lego sketch dynamically coordinates multiple memory bricks to adapt to various space budgets and diverse data domains. Theoretical analysis and empirical studies demonstrate its scalability and superior space-accuracy trade-offs, outperforming existing handcrafted and neural sketches.

Detecting Out-of-Distribution (OOD) inputs is crucial for improving the reliability of deep neural networks in the real-world deployment. In this paper, inspired by the inherent distribution shift between in-distribution (ID) and OOD data, we propose a novel method that leverages optimal transport to measure the distribution discrepancy between test inputs and ID prototypes. The resulting transport costs are used to quantify the individual contribution of each test input to the overall discrepancy, serving as a desirable measure for OOD detection. To address the issue that solely relying on the transport costs to ID prototypes is inadequate for identifying OOD inputs closer to ID data, we generate virtual outliers to approximate the OOD region via linear extrapolation. By combining the transport costs to ID prototypes with the costs to virtual outliers, the detection of OOD data near ID data is emphasized, thereby enhancing the distinction between ID and OOD inputs. Extensive evaluations demonstrate the superiority of our method over state-of-the-art methods.

Large Language Models have excelled in various domains but face efficiency challenges due to the growing Key-Value (KV) cache required for long-sequence inference. Recent efforts aim to reduce KV cache size by evicting vast non-critical cache elements during runtime while preserving generation quality. However, these methods typically allocate compression budgets uniformly across all attention heads, ignoring the unique attention patterns of each head. In this paper, we establish a theoretical loss upper bound between pre- and post-eviction attention output, explaining the optimization target of prior cache eviction methods, while guiding the optimization of adaptive budget allocation. Base on this, we propose {\it Ada-KV}, the first head-wise adaptive budget allocation strategy. It offers plug-and-play benefits, enabling seamless integration with prior cache eviction methods. Extensive evaluations on 13 datasets from Ruler and 16 datasets from LongBench, all conducted under both question-aware and question-agnostic scenarios, demonstrate substantial quality improvements over existing methods. Our code is available at https://github.com/FFY0/AdaKV.

Knowledge graphs (KGs) are vital for enabling knowledge reasoning across various domains. Recent KG reasoning methods that integrate both global and local information have achieved promising results. However, existing methods often suffer from score over-smoothing, which blurs the distinction between correct and incorrect answers and hinders reasoning effectiveness. To address this, we propose DuetGraph, a **coarse-to-fine** KG reasoning mechanism with **dual-pathway** global-local fusion. DuetGraph tackles over-smoothing by segregating—rather than stacking—the processing of local (via message passing) and global (via attention) information into two distinct pathways, preventing mutual interference and preserving representational discrimination. In addition, DuetGraph introduces a **coarse-to-fine** optimization, which partitions entities into high- and low-score subsets. This strategy narrows the candidate space and sharpens the score gap between the two subsets, which alleviates over-smoothing and enhances inference quality. Extensive experiments on various datasets demonstrate that DuetGraph achieves state-of-the-art (SOTA) performance, with up to an **8.7\%** improvement in reasoning quality and a **1.8$\times$** acceleration in training efficiency.

Cutting-edge platforms of graph neural networks (GNNs), such as DGL and PyG, harness the parallel processing power of GPUs to extract structural information from graph data, achieving state-of-the-art (SOTA) performance in fields such as recommendation systems, knowledge graphs, and bioinformatics. Despite the computational advantages provided by GPUs, these GNN platforms struggle with scalability challenges due to the colossal graphical structures processed and the limited memory capacities of GPUs. In response, this work introduces Capsule, a new out-of-core mechanism for large-scale GNN training. Unlike existing out-of-core GNN systems, which use main or secondary memory as operative memory and use CPU kernels during non-backpropagation computation, Capsule uses GPU memory and GPU kernels. By substantially leveraging the parallelization capabilities of GPUs, Capsule significantly enhances GNN training efficiency. In addition, Capsule can be smoothly integrated to mainstream open-source GNN frameworks, DGL and PyG, in a play-and-plug manner. Through a prototype implementation and comprehensive experiments on real datasets, we demonstrate that Capsule can achieve up to a 12.02× improvement in runtime efficiency, while using only 22.24% of the main memory, compared to SOTA out-of-core GNN systems.

GraphRAG integrates (knowledge) graphs with large language models (LLMs) to improve reasoning accuracy and contextual relevance. Despite its promising applications and strong relevance to multiple research communities, such as databases and natural language processing, GraphRAG currently lacks modular workflow analysis, systematic solution frameworks, and insightful empirical studies. To bridge these gaps, we propose LEGO-GraphRAG , a modular framework that enables: 1 ) fine-grained decomposition of the GraphRAG workflow, 2 ) systematic classification of existing techniques and implemented GraphRAG instances, and 3 ) creation of new GraphRAG instances. Our framework facilitates comprehensive empirical studies of GraphRAG on large-scale real-world graphs and diverse query sets, revealing insights into balancing reasoning quality, runtime efficiency, and token or GPU cost, that are essential for building advanced GraphRAG systems.

Streaming edge partitioning plays a crucial role in the distributed processing of large-scale web graphs, such as pagerank. The quality of partitioning is of utmost importance and directly affects the runtime cost of distributed graph processing. However, streaming graph clustering, a key component of mainstream streaming edge partitioning, is vertex-centric. This incurs a mismatch with the edge-centric partitioning strategy, necessitating additional post-processing and several graph traversals to transition from vertex-centric clusters to edge-centric partitions. This transition not only adds extra runtime overhead but also risks a decline in partitioning quality. In this paper, we propose a novel algorithm, called ClusPar, to address the problem of streaming edge partitioning. The ClusPar framework consists of two steps, streaming edge clustering and edge cluster partitioning. Different from prior studies, the first step traverses the input graph in a single pass to generate edge-centric clusters, while the second step applies game theory over these edge-centric clusters to produce partitions. Extensive experiments show that ClusPar outperforms the state-of-the-art streaming edge partitioning methods in terms of the partitioning quality, efficiency, and scalability.

As an essential computer vision task, Continual Semantic Segmentation (CSS) has received a lot of attention. However, security issues regarding this task have not been fully studied. To bridge this gap, we study the problem of attacks in CSS in this paper. We first propose a new task, namely, attacks on incremental samples in CSS, and reveal that the attacks on incremental samples corrupt the performance of CSS in both old and new classes. Moreover, we present an adversarial sample generation method based on class shift, namely Class Shift Attack (CS-Attack), which is an offline and easy-to-implement approach for CSS. CS-Attack is able to significantly degrade the performance of models on both old and new classes without knowledge of the incremental learning approach, which undermines the original purpose of the incremental learning, i.e., learning new classes while retaining old knowledge. Experiments show that on the popular datasets Pascal VOC, ADE20k, and Cityscapes, our approach easily degrades the performance of currently popular CSS methods, which reveals the importance of security in CSS.

Continual Semantic Segmentation (CSS) is an emerging trend, where catastrophic forgetting has been a perplexing problem. In this paper, we propose a Text-to-Image Knowledge Preservation (TIKP) framework to address this issue. TIKP applies Text-to-Image techniques to CSS by automatically generating prompts and content adaptation. It extracts associations between the labels of seen data and constructs text-level prompts based on these associations, which are preserved and maintained at each incremental step. During training, these prompts generate correlated images to mitigate the catastrophic forgetting. Particularly, as the generated images may have different distributions from the original data, TIKP transfers the knowledge by a content adaption loss, which determines the role played by the generated images in incremental training based on the similarity. In addition, for the classifier, we use the previous model from a different perspective: misclassifying new classes into old objects instead of the background. We propose a knowledge distillation loss based on wrong labels, enabling us to attribute varying weights to individual objects during the distillation process. Extensive experiments conducted in the same setting show that TIKP outperforms state-of-the-art methods by a large margin on benchmark datasets.

Deep learning has shown prominence in chest radiography interpretation, which is critical in evaluating various lung and chest diseases, such as pneumonia, emphysema, and tuberculosis. Deploying machine learning model, it is important to detect out-of-distribution (OOD) inputs, which are distinct from the training data. For example, a model trained on conventional pneumonia data may not be able to diagnose COVID-19 accurately, letting alone the vast body of possible abnormalities and variation in medical imaging. Thus, a trustworthy diagnosing model should be alerted with such OOD inputs to avoid the overconfidence with samples and therefore the risk of misdiagnosis and severe medical consequences. In this paper, we study the problem of OOD detection for deep learning-based chest X-ray imaging by proposing a distance-based OOD detection method. We show that our method (1) inherits the merits of distance-based methods in being applicable to different models and training losses; and (2) adopts probabilistic score functions with fewer statistics to mitigate the potential distribution assumption on training data. We conduct extensive experiments on benchmarks to demonstrate the superiority of our method. In particular, on challenging tasks, such as Chest X-ray 14 vs. COVID-19, our method achieves 12.62% lower FPR than the state-of-the-art solutions.

A graph is a structure made up of vertices and edges used to represent complex relationships between entities, while a graph stream is a continuous flow of graph updates that convey evolving relationships between entities. The massive volume and high dynamism of graph streams promote research on data structures of graph summarization, which provides a concise and approximate view of graph streams with sub-linear space and linear construction time, enabling real-time graph analytics in various domains, such as social networking, financing, and cybersecurity. In this work, we propose the Mayfly, the first neural data structure for summarizing graph streams. The Mayfly replaces handcrafted data structures with better accuracy and adaptivity. To cater to practical applications, Mayfly incorporates two offline training phases. During the larval phase, the Mayfly learns basic summarization abilities from automatically and synthetically constituted meta-tasks, and in the metamorphosis phase, it rapidly adapts to real graph streams via meta-tasks. With specific configurations of information pathways, the Mayfly enables flexible support for miscellaneous graph queries, including edge, node, and connectivity queries. Extensive empirical studies show that the Mayfly significantly outperforms its handcrafted competitors.

Product quantization (PQ) is an effective vector quantization approach to compactly encode high-dimensional vectors for approximate nearest neighbor search (ANNS). While the PQ-based ANNS methods achieve remarkable time and space efficiency, their search accuracy falls short. The main reason is the excessive quantization error of vectors used for similarity computation during the search phase. We refer to the set of these computed vectors as the local range set. We observe that if the vectors in the local range set are optimally ranked, the search accuracy will be significantly improved. Based on this observation, we propose a Local Deep Learning Quantization (LDLQ) framework. This framework involves mapping codewords to fake vectors within the local range set and utilizes fake vectors for ranking. Experimental results demonstrate that the LDLQ framework significantly improves the accuracy of existing PQ-based ANNS methods while maintaining low computation and space overhead. Notably, our method can be plugged into existing PQ-based approaches for performance enhancement, making it versatile and widely deployable.

In the realm of distributed systems tasked with managing and processing large-scale graph-structured data, optimizing graph partitioning stands as a pivotal challenge. The primary goal is to minimize communication overhead and runtime cost. However, alongside the computational complexity associated with optimal graph partitioning, a critical factor to consider is memory overhead. Real-world graphs often reach colossal sizes, making it impractical and economically unviable to load the entire graph into memory for partitioning. This is also a fundamental premise in distributed graph processing, where accommodating a graph with non-distributed systems is unattainable. Currently, existing streaming partitioning algorithms exhibit a skew-oblivious nature, yielding satisfactory partitioning results exclusively for specific graph types. In this paper, we propose a novel streaming partitioning algorithm, the Skewness-aware Vertex-cut Partitioner (S5P ), designed to leverage the skewness characteristics of real graphs for achieving high-quality partitioning. S5P offers high partitioning quality by segregating the graph's edge set into two subsets, head and tail sets. Following processing by a skewness-aware clustering algorithm, these two subsets subsequently undergo a Stackelberg graph game. Our extensive evaluations conducted on substantial real-world and synthetic graphs demonstrate that, in all instances, the partitioning quality of S5P surpasses that of existing streaming partitioning algorithms, operating within the same load balance constraints. For example, S5P can bring up to a 51% improvement in partitioning quality compared to the top partitioner among the baselines. Lastly, we showcase that the implementation of S5P results in up to an 81% reduction in communication cost and a 130% increase in runtime efficiency for distributed graph processing tasks on PowerGraph.

Recently, there has been a trend of designing neural data structures to go beyond handcrafted data structures by leveraging patterns of data distributions for better accuracy and adaptivity. Sketches are widely used data structures in real-time web analysis, network monitoring, and self-driving to estimate item frequencies of data streams within limited space. However, existing sketches have not fully exploited the patterns of the data stream distributions, making it challenging to tightly couple them with neural networks that excel at memorizing pattern information. Starting from the premise, we envision a pure neural data structure as a base sketch, which we term the meta-sketch, to reinvent the base structure of conventional sketches. The meta-sketch learns basic sketching abilities from meta-tasks constituted with synthetic datasets following Zipf distributions in the pre-training phase and can be quickly adapted to real (skewed) distributions in the adaption phase. The meta-sketch not only surpasses its competitors in sketching conventional data streams but also holds good potential in supporting more complex streaming data, such as multimedia and graph stream scenarios. Extensive experiments demonstrate the superiority of the meta-sketch and offer insights into its working mechanism.

Towards building online analytical services on big heterogeneous graphs, we study the problem of the multithreading graph aggregation. The purpose is to exploit the thread-level parallelism for accelerating the graph aggregation process, which is both data and computation intensive. We identify the sources of parallelization latency caused by multifarious factors, including data distributions and contentions, uneven workload assignments, logical aggregation plan obstructions, etc. To cope with these problems, we investigate a parallelization solution for graph aggregation with a number of threads packaged as threadblocks, categorize the parallelization latency as the thread-level and threadblock-level latency, and propose a series of optimization techniques for alleviating or eliminating the latency on different levels. The solution supports different aggregate functions, scales up to large number of threads, and scales out to big heterogeneous graphs. Experiments on real datasets show that our solution achieves up to 60x acceleration with 256 threads compared to the non-parallelized solution.

Conventional sketches on counting stream item frequencies use hash functions for mapping data items to a concise structure, e.g., a two-dimensional array, at the expense of overcounting due to hashing collisions. Despite the popularity, it is still challenging to handle cold (low-frequency) items, especially when the space is limited. The cold items can be misreported as hot (high-frequency) items as the accumulation of error in hashing collisions, leading to the estimation accuracy degrading. We find that a streaming item can be split into a set of compactly stored basic elements, which can be recomposed in a probabilistic manner to estimate the frequency of an item. Thus, we design a novel decomposition and recomposition framework, called the XY-sketch, which estimates the frequency of a stream item by estimating the probability of basic elements appearing in the data stream. By improving the estimation accuracy of cold items, we show that advanced streaming queries, such as top-$k$queries and heavy change queries. Throughout, we conduct theoretical analysis and optimizations under space constraints. Experiments on real datasets are conducted to examine the effectiveness of our proposals.

To estimate item frequencies of data streams with limited space, sketches are widely used in real applications, including real-time web analytics, network monitoring, and self-driving. Sketches can be viewed as a model which maps the identifier of a stream item to the corresponding frequency domain. Starting from the premise, we envision a neural data structure, which we term the meta-sketch, to go beyond the basic structure of conventional sketches. The meta-sketch learns basic sketching abilities from meta-tasks constituted with synthetic datasets following Zipf distributions in the pre-training phase, and can be fast adapted to real (skewed) distributions in the adaption phase. Extensive experiments demonstrate the performance gains of the meta-sketch and offer insights into our proposals.

The success of deep learning is largely attributed to the training over clean data. However, data is often coupled with noisy labels in practice. Learning with noisy labels is challenging because the performance of the deep neural networks (DNN) drastically degenerates, due to confirmation bias caused by the network memorization over noisy labels. To alleviate that, a recent prominent direction is on sample selection, which retrieves clean data samples from noisy samples, so as to enhance the model's robustness and tolerance to noisy labels. In this paper, we re-vamp the sample selection from the perspective of optimal transport theory and propose a novel method, called the OT-Filter. The OT-Filter provides geometrically meaningful distances and preserves distribution patterns to measure the data discrepancy, thus alleviating the confirmation bias. Extensive experiments on benchmarks, such as Clothing1M and ANIMAL-10N, show that the performance of the OT-Filter outperforms its counterparts. Meanwhile, results on benchmarks with synthetic labels, such as CIFAR-10/100, show the superiority of the OT-Filter in handling data labels of high noise.

Interactive data exploration (IDE) is an effective way of comprehending big data, whose volume and complexity are beyond human abilities. The main goal of IDE is to discover user interest regions from a database through multi-rounds of user labelling. Existing IDEs adopt active-learning framework, where users iteratively discriminate or label the interestingness of selected tuples. The process of data exploration can be viewed as the process of training of a classifier, which determines whether a database tuple is interesting to a user. An efficient exploration thus takes very few iterations of user labelling to reach the data region of interest. In this work, we consider the data exploration as the process of few-shot learning, where the classifier is learned with only a few training examples, or exploration iterations. To this end, we propose a learning-to-explore framework, based on meta-learning, which learns how to learn a classifier with automatically generated meta-tasks, so that the exploration process can be much shortened. Extensive experiments on real datasets show that our proposal outperforms existing explore-by-example solutions in terms of accuracy and efficiency.

We study route planning that utilizes historical trajectories to predict a realistic route from a source to a destination on a road network at given departure time. Route planning is a fundamental task in many location-based services. It is challenging to capture latent patterns implied by complex trajectory data for accurate route planning. Recent studies mainly resort to deep learning techniques that incur immense computational costs, especially on massive data, while their effectiveness are complicated to interpret. This paper proposes DRPK, an effective and efficient route planning method that achieves state-of-the-art performance via a series of novel algorithmic designs. In brief, observing that a route planning query (RPQ) with closer source and destination is easier to be accurately predicted, we fulfill a promising idea in DRPK to first detect the key segment of an RPQ by a classification model KSD, in order to split the RPQ into shorter RPQs, and then handle the shorter RPQs by a destination-driven route planning procedure DRP. Both KSD and DRP modules rely on a directed association (DA) indicator, which captures the dependencies between road segments from historical trajectories in a surprisingly intuitive but effective way. Leveraging the DA indicator, we develop a set of well-thought-out key segment concepts that holistically consider historical trajectories and RPQs. KSD is powered by effective encoders to detect high-quality key segments, without inspecting all segments in a road network for efficiency. We conduct extensive experiments on 5 large-scale datasets. DRPK consistently achieves the highest effectiveness, often with a significant margin over existing methods, while being much faster to train. Moreover, DRPK is efficient to handle thousands of online RPQs in a second,e.g., 2768 RPQs per second on a PT dataset,i.e., 0.36 milliseconds per RPQ.

Graph partitioning plays a vital role in distributed large-scale web graph analytics, such as pagerank and label propagation. The quality and scalability of partitioning strategy have a strong impact on such communication- and computation-intensive applications, since it drives the communication cost and the workload balance among distributed computing nodes. Recently, the streaming model shows promise in optimizing graph partitioning. However, existing streaming partitioning strategies either lack of adequate quality or fall short in scaling with a large number of partitions. In this work, we explore the property of web graph clustering and propose a novel restreaming algorithm for vertex-cut partitioning. We investigate a series of techniques, which are pipelined as three steps, streaming clustering, cluster partitioning, and partition transformation. More, these techniques can be adapted to a parallel mechanism for further acceleration of partitioning. Experiments on real datasets and real systems show that our algorithm outperforms state-of-the-art vertex-cut partitioning methods in large-scale web graph processing. Surprisingly, the runtime cost of our method can be an order of magnitude lower than that of one-pass streaming partitioning algorithms, when the number of partitions is large.

Recently, research communities highlight the neces-sity of formulating a scalability continuum for large-scale graph processing, which gains the scale-out benefits from distributed graph systems, and the scale-up benefits from high-performance accelerators. To this end, we propose a middleware, called the GX-plug, for the ease of integrating the merits of both. As a middleware, the GX-plug is versatile in supporting different runtime environments, computation models, and programming models. More, for improving the middleware performance, we study a series of techniques, including pipeline shuffle, synchro-nization caching and skipping, and workload balancing, for intra-, inter-, and beyond-iteration optimizations, respectively. Exper-iments show that our middleware efficiently plugs accelerators to representative distributed graph systems, e.g., GraphX and Powergraph, with up-to 20x acceleration ratio.

The prevalence of mobile devices and positioning techniques has enabled so-called traffic-aware urban computing. In urban daily life, people's activities consist of indoor and outdoor parts whose transitions have important impacts on traffic behavior. For example, outdoor traffic events (e.g., jams) can be triggered by indoor events (e.g., the ending of exhibitions, tour-naments, or working hours). In turn, indoor events (e.g., subway jams) can also be affected by outdoor events (e.g., snowy weather or other bad outdoor traffic conditions). For a wide range of applications like traffic monitoring and emergency response, it is thus interesting to develop techniques for analyzing data in an integrated indoor and outdoor space. Since real datasets of this kind are still scarce and small, a suitable data generator is needed for both functional and scalability testing. In this work, we present UrbanGen, which follows the constraints of road networks for the outdoor space and the constraints of topologies for the indoor space. The system provides the functionalities including: 1) integrating a model of indoor topologies with the state-of-art road networks; 2) parameterizing the movement of objects in the integrated model; 3) serializing and visualizing the generated trajectories.

In applications of Web of Things or Web of Events, a massive volume of multi-dimensional streaming data are automatically and continuously generated from different sources, such as GPS, sensors, and other measurement devices, which are essentially imprecise (inaccurate and/or uncertain). It is challenging to monitor and get insights over imprecise and low-level streaming data, in order to capture potentially important data changing trends and to initiate prompt responses. In this work, we investigate solutions for conducting multi-dimensional and multi-granularity probabilistic regression for the imprecise streaming data. The probabilistic nature of streaming data poses big computational challenges to the regression and its aggregation. In this paper, we study a series of techniques on multi-dimensional probabilistic regression, including aggregation, sketching, popular path materialization, and exception-driven querying. Extensive experiments on real and synthetic datasets show the efficiency and scalability of our proposals.

Non-Volatile Memory (NVM) has emerged as an alternative to next-generation main memories. Although many tree indices have been proposed for NVM, they generally use B+-tree-like structures. To further improve the performance of NVM-aware indices, we consider integrating learned indexes into NVM. The challenges of such an integration are two fold: (1) existing NVM indices rely on small nodes to accelerate insertions with crash consistency, but learned indices use huge nodes to obtain a flat structure. (2) the node structure of learned indices is not NVM friendly, meaning that accessing a learned node will cause multiple NVM block misses. Thus, in this paper, we propose a new persistent learned index called PLIN. The novelty of PLIN lies in four aspects: an NVM-aware data placement strategy, locally unordered and globally ordered leaf nodes, a model copy mechanism, and a hierarchical insertion strategy. In addition, PLIN is proposed for the NVM-only architecture, which can support instant recovery. We also present optimistic concurrency control and fine-grained locking mechanisms to make PLIN scalable to concurrent requests. We conduct experiments on real persistent memory with various workloads and compare PLIN with APEX, PACtree, ROART, TLBtree, and Fast&Fair. The results show that PLIN achieves 2.08x higher insertion performance and 4.42x higher query performance than its competitors on average. Meanwhile, PLIN only needs ~30 μs to recover from a system crash.

Cloud computing is motivating data owners to outsource their databases to the cloud. However, for privacy concerns, the sensitive data has to be encrypted before outsourcing, which inevitably posts a challenging task for effective data utilization. Existing work either focuses on keyword searches, or suffers from inadequate security guarantees or inefficiency. In this paper, we concentrate on multi-dimensional range queries over dynamic encrypted cloud data. We first propose a tree-based private range query scheme over dynamic encrypted cloud data (TRQED), which supports faster-than-linear range queries and protects single-dimensional privacy. Then, we discuss the defects of TRQED in terms of privacy-preservation. We modify the framework of the system by adopting a two-server model and put forward a safer range query scheme, called TRQED$^{+}$. By newly designed secure node query (SNQ) and secure point query (SPQ), we propose the perturbation-based oblivious R-tree traversal (ORT) operation to preserve both path pattern and stronger single-dimensional privacy. Finally, we conduct comprehensive experiments on real-world datasets and perform comparisons with existing works to evaluate the performance of the proposed schemes. Experimental results show that our TRQED and TRQED$^+$surpass the state-of-the-art methods in privacy-preservation level and efficiency.

Traffic accident has become a significant health and development threat with rapid urbanizations. An accurate urban accident forecasting enables higher-quality police force pre-allocation and safe route planning for both traffic administrations and travelers, maximumly reducing injuries and damages. Off-the-shelf short-term accident forecasting methods, which focus on modeling static region-wise correlations with existing neural networks, mostly performed on hour levels and with single step. However, given the dynamic nature of road networks and expanding urban areas, it is challenging when the spatiotemporal granularity of forecasting improves as the rareness of accident records and complexity of long-term future dependencies. To address these challenges, we propose a unified framework RiskSeq, to foresee sparse urban accidents with finer granularities and multiple steps in spatiotemporal perspective. In particular, we design region-wise proximity measurements and temporal feature differential operations, and embed them into a novel Differential Time-varying Graph Convolution Network to dynamically capture traffic variations. Considering the hierarchical spatial dependencies and obvious context influences, a hierarchical sequence learning structure is devised by introducing contextual factors into a step-wise decoder. The multi-scale spatial risks are learned jointly to boost the risk predictions based on risk-gather and risk-assign networks. Extensive experiments demonstrate our RiskSeq can increase 5 to 15 percent performances on two datasets.

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.

Foreseeing detailed vehicle future trajectories collectively enables a large scope of urban applications such as route planning and commercial advertising. Existing methods focused on predicting future trajectories of urban vehicles with their own fine-grained historical trajectories. Unfortunately, in real-world scenarios, fine-grained trajectories provided by GPS are limited to obtain due to privacy issues and business competitions. In this paper, our solution enables the ubiquitous but coarse-grained location-based surveillance information to predict the fine-grained trajectories of all vehicles with limited number of fine-grained trajectories. We first capture the vectorized semantic representation of trajectories by training the spatiotemporal embedding in large coarse trajectory set. Then, we propose a new measurement to calculate the trajectory similarity, which combines the vehicles' historical behavior similarity and short-term trajectory similarity. The obtained trajectory similarity is then seamlessly embedded into the dynamic graph convolution network in the manner of spatial attention. The dynamic graph convolution sequence-to-sequence module and the fully-connected layer are devised to generate final sequential trajectory predictions. The whole process is to train in a multi-task framework. Extensive experiments on real-world datasets show the excellent performance of our method.

The proliferation of advanced mobile terminals opened up a new crowdsourcing avenue, spatial crowdsourcing, to utilize the crowd potential to perform real-world tasks. In this work, we study a new type of spatial crowdsourcing, called time-continuous spatial crowdsourcing (TCSC in short). It supports broad applications for long-term continuous spatial data acquisition, ranging from environmental monitoring to traffic surveillance in citizen science and crowdsourcing projects. However, due to limited budgets and limited availability of workers in practice, the data collected is often incomplete, incurring data deficiency problem. To tackle that, in this work, we first propose an entropy-based quality metric, which captures the joint effects of incompletion in data acquisition and the imprecision in data interpolation. Based on that, we investigate quality-aware task assignment methods for both single- and multi-task scenarios. We show the NP-hardness of the single-task case, and design polynomial-time algorithms with guaranteed approximation ratios. We study novel indexing and pruning techniques for further enhancing the performance in practice. Then, we extend the solution to multi-task scenarios and devise a parallel framework for speeding up the process of optimization. We conduct extensive experiments on both real and synthetic datasets to show the effectiveness of our proposals.

Conventional sketching methods on counting stream item frequencies use hash functions for mapping data items to a concise structure, e.g., a two-dimensional array, at the expense of overcounting due to hashing collisions. Despite the popularity, however, the accumulated errors originated in hashing collisions deteriorate the sketching accuracies at the rapid pace of data increasing, which poses a great challenge to sketch big data streams at web scale. In this paper, we propose a novel structure, called XY-sketch, which estimates the frequency of a data item by estimating the probability of this item appearing in the data stream. The framework associated with XY-sketch consists of two phases, namely decomposition and recomposition phases. A data item is split into a set of compactly stored basic elements, which can be stringed up in a probabilistic manner for query evaluation during the recomposition phase. Throughout, we conduct optimization under space constraints and detailed theoretical analysis. Experiments on both real and synthetic datasets are done to show the superior scalability on sketching large-scale streams. Remarkably, XY-sketch is orders of magnitudes more accurate than existing solutions, when the space budget is small.

The high dynamics and heterogeneous interactions in the complicated urban systems have raised the issue of uncertainty quantification in spatiotemporal human mobility, to support critical decision-makings in risk-aware web applications such as urban event prediction where fluctuations are of significant interests. Given the fact that uncertainty quantifies the potential variations around prediction results, traditional learning schemes always lack uncertainty labels, and conventional uncertainty quantification approaches mostly rely upon statistical estimations with Bayesian Neural Networks or ensemble methods. However, they have never involved any spatiotemporal evolution of uncertainties under various contexts, and also have kept suffering from the poor efficiency of statistical uncertainty estimation while training models with multiple times. To provide high-quality uncertainty quantification for spatiotemporal forecasting, we propose an uncertainty learning mechanism to simultaneously estimate internal data quality and quantify external uncertainty regarding various contextual interactions. To address the issue of lacking labels of uncertainty, we propose a hierarchical data turbulence scheme where we can actively inject controllable uncertainty for guidance, and hence provide insights to both uncertainty quantification and weak supervised learning. Finally, we re-calibrate and boost the prediction performance by devising a gated-based bridge to adaptively leverage the learned uncertainty into predictions. Extensive experiments on three real-world spatiotemporal mobility sets have corroborated the superiority of our proposed model in terms of both forecasting and uncertainty quantification.

The proliferation of telco networks and mobile terminals brings the accumulation of tremendous amounts of measure report(MR) data at a rapid pace. The MR data is generated by mobile objects while connecting to data services and is stored in backend data centers. To geo-tag or localize such MR data is believed to have a profound effect on the analytics and optimizations of telco and traffic networks. However, MR records are of noisy and partial observations regarding to mobile objects' geo-locations and hence pose challenges to accurate telco data localization. There have been quite a few attempts. Single-point localization methods map a MR record to a location, but come out with limited accuracies due to the ignorance of spatiotemporal coherence of successive MR records. Recent efforts on sequential localization techniques alleviate this by mapping a sequence of MR records to a trajectory. However, existing solutions are often with assumptions on specific models, e.g., mobility and signal strength distributions, or priori knowledge on topology space, e.g., road networks, limiting the deployment in practice. To this end, we propose a data-driven framework to tackle the challenges in sequential telco localization. We solely use raw MR records and a public third-party GPS dataset for the learning of the correlations between mobile objects' locations and MR records, requiring no model assumptions and priori knowledge. To handle the data-intensive workloads during the learning process, we use materialized views for efficient online localization and light-weighted indexing techniques for periodical parameters tuning, in order to improve the efficiency and scalability. Results on real data show that our solution achieves 58.8 percent improvement in median localization errors compared with state-of-art sequential localization techniques that require hypothesis models and priori knowledge, making our solution superior in terms of effectiveness, efficiency, and employability.

Real-time traffic accident forecasting is increasingly important for public safety and urban management (e.g., real-time safe route planning and emergency response deployment). Previous works on accident forecasting are often performed on hour levels, utilizing existed neural networks with static region-wise correlations taken into account. However, it is still challenging when the granularity of forecasting step improves as the highly dynamic nature of road network and inherent rareness of accident records in one training sample, which leads to biased results and zero-inflated issue. In this work, we propose a novel framework RiskOracle, to improve the prediction granularity to minute levels. Specifically, we first transform the zero-risk values in labels to fit the training network. Then, we propose the Differential Time-varying Graph neural network (DTGN) to capture the immediate changes of traffic status and dynamic inter-subregion correlations. Furthermore, we adopt multi-task and region selection schemes to highlight citywide most-likely accident subregions, bridging the gap between biased risk values and sporadic accident distribution. Extensive experiments on two real-world datasets demonstrate the effectiveness and scalability of our RiskOracle framework.

Networked data, notably social network data, often comes with a rich set of annotations, or attributes, such as documents (e.g., tweets) and locations (e.g., check-ins). Community search in such attributed networks has been studied intensively due to its many applications in friends recommendation, event organization, advertising, etc. We study the problem of attribute-constrained co-located community (ACOC) search, which returns a community that satisfies three properties: i) structural cohesiveness: the members in the community are densely connected; ii) spatial co-location: the members are close to each other; and iii) attribute constraint: a set of attributes are covered by the attributes associated with the members. The ACOC problem is shown to be NP-hard. We develop four efficient approximation algorithms with guaranteed error bounds in addition to an exact solution that works on relatively small graphs. Extensive experiments conducted with both real and synthetic data offer insight into the efficiency and effectiveness of the proposed methods, showing that they outperform three adapted state-of-the-art algorithms by an order of magnitude. We also find that the approximation algorithms are much faster than the exact solution and yet offer high accuracy.

Predicting the link between two nodes is a fundamental problem for graph data analytics. In attributed graphs, both the structure and attribute information can be utilized for link prediction. Most existing studies focus on transductive link prediction where both nodes are already in the graph. However, many real-world applications require inductive prediction for new nodes having only attribute information. It is more challenging since the new nodes do not have structure information and cannot be seen during the model training. To solve this problem, we propose a model called DEAL, which consists of three components: two node embedding encoders and one alignment mechanism. The two encoders aim to output the attribute-oriented node embedding and the structure-oriented node embedding, and the alignment mechanism aligns the two types of embeddings to build the connections between the attributes and links. Our model DEAL is versatile in the sense that it works for both inductive and transductive link prediction. Extensive experiments on several benchmark datasets show that our proposed model significantly outperforms existing inductive link prediction methods, and also outperforms the state-of-the-art methods on transductive link prediction.

6DoF object pose estimation is essential for many real-world applications. Although great progress has been made, challenges still remain in estimating 6D pose for occluded objects. Current RGB-D approaches predict 6DoF pose directly, which is sensitive to occlusion in cluttered scenes. In this work, we propose DCNet, an end-to-end framework for estimating 6DoF object poses. DCNet first converts pixels in the image plane to point clouds in the camera coordinate system and then establishes dense correspondences between the camera coordinate system and the object coordinate system. Based on these two systems, we fuse 2D appearance and 3D geometric features by pixel-wise concatenation to construct dense correspondences, from which the pose is calculated through the least-squares fitting algorithm. Dense correspondences guarantee enough point pairs for a robust 6DoF pose estimation, even if the occlusion is heavy. Experimental results demonstrate that DCNet outperforms the state-of-the-art methods on LINEMOD, Occlusion LINEMOD and YCB-Video datasets, especially in terms of the robustness to occlusion scenes.

Worker movement information can help the spatial crowdsourcing platform to identify the right time to assign a task to a worker for successful completion of the task. However, the majority of the current assignment strategies do not consider worker movement information. This paper aims to utilize the worker movement information via transits in an online task assignment setting. The idea is to harness the waiting periods at different transit stops in a worker transit route (WTR) for performing the tasks. Given the limited availability of workers’ waiting periods at transit stops, task deadlines and workers’ preference of performing tasks with higher rewards, we define the Transit-based Task Assignment (TTA) problem. The objective of the TTA problem is to maximize the average worker rewards for motivating workers, considering the fixed worker transit models. We solve the TTA problem by considering three variants, step-by-step, from offline to batch-based online versions. The first variant is the offline version of the TTA, which can be reduced to a maximum bipartite matching problem, and be leveraged for the second variant. The second variant is the batch-based online version of the TTA, for which, we propose dividing each batch into an offline version of the TTA problem, along with additional credibility constraints to ensure a certain level of worker response quality. The third variant is the extension of the batch-based online version of the TTA (Flexible-TTA) that relaxes the strict nature of the WTR model and assumes that a task with higher reward than a worker-defined threshold value will convince the worker to stay longer at the transit stop. Through our extensive evaluation, we observe that the algorithm solving the Flexible-TTA problem outperforms the algorithms proposed to solve other variants of the TTA problems, by 55% in terms of the number of assigned tasks, and by at least 35% in terms of average reward for the worker. With respect to the baseline (online task assignment) algorithm, the algorithm solving the Flexible-TTA problem results in three times higher reward and at least three times faster runtime.

On-Line Analytical Processing (OLAP) enables powerful analytics by quickly computing aggregate values of numerical measures over multiple hierarchical dimensions for massive datasets. However, many types of source data, e.g., from GPS, sensors, and other measurement devices, are intrinsically inaccurate (imprecise and/or uncertain) and thus OLAP cannot be readily applied. In this paper, we address the resulting data veracityproblem in OLAP by proposing the concept of probabilistic data cubes. Such a cube is comprised of a set of probabilistic cuboids which summarize the aggregated values in the form of probability mass functions (pmfs in short) and thus offer insights into the underlying data quality and enable confidence-aware query evaluation and analysis. However, the probabilistic nature of data poses computational challenges, since a probabilistic database can have exponential number of possible worlds under the possible world semantics. Even worse, it is hard to share computations among different cuboids, as aggregation functions that are distributive for traditional data cubes, e.g., SUM, become holistic in probabilistic settings. In this paper, we propose a complete set of techniques for probabilistic data cubes, from cuboid aggregation, over cube materialization, to query evaluation. We study two types of aggregation: convolution and sketch-based, which take polynomial time complexities for aggregation and jointly enable efficient query processing. Also, our proposal is versatile in terms of: 1) its capability of supporting common aggregation functions, i.e., SUM, COUNT, MAX, and AVG; 2) its adaptivity to different materialization strategies, e.g., full versus partial materialization, with support of our devised cost models and parallelization framework; 3) its coverage of common OLAP operations, i.e., probabilistic slicing and dicing queries. Extensive experiments over real and synthetic datasets show that our techniques are effective and scalable.

Various networks have rich attributes such as texts (e.g., tweets) and locations (e.g., check-ins). The community search in such attributed networks have been intensively studied recently due to its wide applications in recommendation, marketing, biology, etc. In this paper, we study the problem of searching the \underlineB est \underlineC o-located \underlineC ommunity (\BCC) in attributed networks, which returns a community that satisfies the following properties: i) structural cohesiveness: members in the community are densely connected, ii) spatial co-location: members are close to each other, and iii) quality optimality: the community has the best quality in terms of given attributes. The problem can be used in social network user behavior analysis, recommendation systems, disease predication, etc. We first propose an index structure called \DTree to integrate the spatial information, the local structure information, and the attribute information together to accelerate the query processing. Then, based on this index we develop an efficient algorithm. The experimental study conducted on both real and synthetic datasets demonstrate the efficiency and effectiveness of the proposed methods.

OpenStreetMap (OSM) is a popular community-driven mapping platform with voluntary contributions from (amateur) cartographers. However, it is a difficult process for the cartographer to identify the areas where she can best contribute to OSM. Furthermore, the current OSM spatial entities are missing many tags; for example, top three road network tags, Name, Source, and Surface, are available only for the 10% of the total road segments. Our paper aims to improve the quantity and quality of the road network tags by actively pushing the nearest road segments for the cartographer to be mapped. We propose a push-based spatial crowdsourcing method to achieve this objective, and validate it by focusing on road segments in OSM. Specifically, we formally define the batch-based maximum road segment task assignment problem and suggest methods based on heuristics like travel distance and road segment task grouping. Finally, our experimental evaluation verify the applicability of our assignment solutions by comparing the resulting number of assigned tasks. With regard to the number of assigned road segments, our junctions-based and road segment-based heuristic methods, outperform the baseline methods by five and two times, respectively.

Local differential privacy (LDP), as a strong and practical notion, has been applied to deal with privacy issues in data collection. However, existing LDP-based strategies mainly focus on utility optimization at a single privacy level while ignoring various privacy preferences of data providers and multilevel privacy demands for statistics. In this poster, we for the first time propose a framework to optimize the utility of histogram estimation with these two privacy requirements. To clarify the goal of privacy protection, we personalize the traditional definition of LDP. We design two independent approaches to minimize the utility loss: Advanced Combination, which composes multilevel results for utility optimization, and Data Recycle with Personalized Privacy, which enlarges sample size for an estimation. We demonstrate their effectiveness on privacy and utility. Moreover, we embed these approaches within a Recycle and Combination Framework and prove that the framework stably achieves the optimal utility by quantifying its error bounds. On real-world datasets, our approaches are experimentally validated and remarkably outperform baseline methods.

Urban housing price is widely accepted as an economic indicator of both business and research interest in urban computing. In this work, we propose an effective and fine-grained model for urban subregion housing price predictions. Compared to existing works, our proposal improves the forecasting granularity from city-level to mile-level in spite of data sparsity and complex factors. The fine-grained housing price forecasting has the potential to support a broad scope of applications, ranging from urban planning to housing market recommendations. To achieve that, in this paper, we propose a novel integrated framework, FTD_DenseNet, which incorporates more social and economic features and makes full use of all-level spatiotemporal features. Specifically, the Kalman Filter-based future expection is firstly involved as an influence factor in our model. Extensive empirical studies on real data show the effectiveness of our proposals.

Recently, local differential privacy (LDP), as a strong and practical notion, has been applied to deal with privacy issues in data collection. However, existing LDP-based strategies mainly focus on utility optimization at a single privacy level while ignoring various privacy preferences of data providers and multilevel privacy demands for statistics. In this paper, we for the first time propose a framework to optimize the utility of histogram estimation with these two privacy requirements. To clarify the goal of privacy protection, we personalize the traditional definition of LDP. We design two independent approaches to minimize the utility loss: Advanced Combination, which composes multilevel results for utility optimization, and Data Recycle with Personalized Privacy, which enlarges the sample size for an estimation. We demonstrate their effectiveness on privacy and utility, respectively. Moreover, we embed these approaches within a Recycle and Combination Framework and prove that the framework stably achieves the optimal utility by quantifying its error bounds. On real-world datasets, our approaches are experimentally validated and remarkably outperform baseline methods.

Widespread use of advanced mobile devices has led to the emergence of a new class of crowdsourcing called spatial crowdsourcing. Spatial crowdsourcing advances the potential of a crowd to perform tasks related to real-world scenarios involving physical locations, which were not feasible with conventional crowdsourcing methods. The main feature of spatial crowdsourcing is the presence of spatial tasks that require workers to be physically present at a particular location for task fulfillment. Research related to this new paradigm has gained momentum in recent years, necessitating a comprehensive survey to offer a bird’s-eye view of the current state of spatial crowdsourcing literature. In this article, we discuss the spatial crowdsourcing infrastructure and identify the fundamental differences between spatial and conventional crowdsourcing. Furthermore, we provide a comprehensive view of the existing literature by introducing a taxonomy, elucidate the issues/challenges faced by different components of spatial crowdsourcing, and suggest potential research directions for the future.

Owing to the widespread use of location-aware devices and the increased popularity of micro-blogging applications, we are witnessing a rapid proliferation of geo-textual data. In this demonstration, we present iZone, an efficient system for determining influence zones over geo-textual data. Specifically, iZone allows users to browse geo-textual objects, evaluate the influence zones of specified geo-textual objects, and obtain explanations of the evaluation results. The iZone system adopts a browser-server model. The server side integrates two types of spatial keyword search, namely top-k spatial keyword query and reverse top-k keyword-based location query, to support the functionality of the system. A variety of spatial indexes are employed to enhance the efficiency of the system. The browser side provides a map-based GUI interface, which enables convenient and user-friendly interaction with the system. Using a real hotel dataset from Hong Kong, iZone offers hands-on experience with influence zone evaluation in real-life applications.

Recent advances in video surveillance systems enable a new paradigm for intelligent urban traffic management systems. Since surveillance cameras are usually sparsely located to cover key regions of the road under surveillance, it is a big challenge to perform a complete real-time traffic pattern analysis based on incomplete sparse surveillance information. As a result, existing works mostly focus on predicting traffic volumes with historical records available at a particular location and may not provide a complete picture of real-time traffic patterns. To this end, in this paper, we go beyond existing works and tackle the challenges of traffic flow analysis from three perspectives. First, we train the transition probabilities to capture vehicles' movement patterns. The transition probabilities are trained from third-party vehicle GPS data, and thus can work in the area even if there is no camera. Second, we exploit the Multivariate Normal Distribution model together with the transferred probabilities to estimate the unobserved traffic patterns. Third, we propose an algorithm for real-time traffic inference with surveillance as a complement source of information. Finally, experiments on real-world data show the effectiveness of our approach.

Due to the popularity of social networks with geo-tagged activities, so-called location-based social networks (LBSN), a number of methods have been proposed for influence maximization for applications such as word-of-mouth marketing (WOMM), and out-of-home marketing (OOH). It is thus important to analyze and compare these different approaches. In this demonstration, we present a unified system IMaxer that both provides a complete pipeline of state-of-the-art and novel models and algorithms for influence maximization (IM) as well as allows to evaluate and compare IM techniques for a particular scenario. IMaxer allows to select and transform the required data from raw LBSN datasets. It further provides a unified model that utilizes interactions of nodes in an LBSN, i.e., users and locations, for capturing diverse types of information propagations. On the basis of these interactions, influential nodes can be found and their potential influence can be simulated and visualized using Google Maps and graph visualization APIs. Thus, IMaxer allows users to compare and pick the most suitable IM method in terms of effectiveness and cost.

The proliferation of geo-textual data gives prominence to spatial keyword search. The basic top-k spatial keyword query, returns k geo-textual objects that rank the highest according to their textual relevance and spatial proximity to query keywords and a query location. We define, study, and provide means of computing the reverse top-k keyword-based location query. This new type of query takes a set of keywords, a query object q, and a number k as arguments, and it returns a spatial region such that any top-k spatial keyword query with the query keywords and a location in this region would contain object q in its result. This query targets applications in market analysis, geographical planning, and location optimization, and it may support applications related to safe zones and influence zones that are used widely in location-based services. We show that computing an exact query result requires evaluating and merging a set of weighted Voronoi cells, which is expensive. We therefore devise effective algorithms that approximate result regions with quality guarantees. We develop novel pruning techniques on top of an index, and we offer a series of optimization techniques that aim to further accelerate query processing. Empirical studies suggest that the proposed query processing is efficient and scalable.

Geo-tagged social media data provides abundant resources for people in need of local information. In this paper, we study how to find the top-k influential local users from geo-tagged social media data who have interests similar to a query. Such local users can be of particular importance for a variety of activities from events organizing to online advertising. We formulate the problem as Top-k Influential Similar Local Query (TkISL) and provide a complete set of techniques for solving it. To effectively manage the social media users, we design three hybrid user profiling techniques, an indexing tree, and an upper bound query-user similarity that enables efficient pruning in query processing. To process TkISL queries, we propose a baseline method and a more efficient improved method. The former directly uses the indexing tree and the upper bound for pruning, whereas the latter speeds up the query processing by enhancing the tree and pruning. Finally, we conduct extensive experimental studies to evaluate our proposals on real geo-tagged tweet corpora. The experimental results demonstrate the efficiency and effectiveness of our proposals.

Location-based social networks (LBSN) are social networks complemented with location data such as geo-tagged activity data of its users. In this paper, we study how users of a LBSN are navigating between locations and based on this information we select the most influential locations. In contrast to existing works on influence maximization, we are not per se interested in selecting the users with the largest set of friends or the set of locations visited by the most users; instead, we introduce a notion of location influence that captures the ability of a set of locations to reach out geographically. We provide an exact on-line algorithm and a more memory-efficient but approximate variant based on the HyperLogLog sketch to maintain a data structure called Influence Oracle that allows to efficiently find a top-k set of influential locations. Experiments show that our algorithms are efficient and scalable and that our new location influence notion favors diverse sets of locations with a large geographical spread.

On-Line Analytical Processing (OLAP) enables powerful analytics by quickly computing aggregate values of numerical measures over multiple hierarchical dimensions for massive datasets. However, many types of source data, e.g., from GPS, sensors, and other measurement devices, are intrinsically inaccurate (imprecise and/or uncertain) and thus OLAP cannot be readily applied. In this paper, we address the resulting data veracity problem in OLAP by proposing the concept of probabilistic data cubes. Such a cube is comprised of a set of probabilistic cuboids which summarize the aggregated values in the form of probability mass functions (pmfs in short) and thus offer insights into the underlying data quality and enable confidence-aware query evaluation and analysis. However, the probabilistic nature of data poses computational challenges as even simple operations are #P-hard under the possible world semantics. Even worse, it is hard to share computations among different cuboids, as aggregation functions that are distributive for traditional data cubes, e.g., SUM and COUNT, become holistic in probabilistic settings. In this paper, we propose a complete set of techniques for probabilistic data cubes, from cuboid aggregation, over cube materialization, to query evaluation. For aggregation, we focus on how to maximize the sharing of computation among cells and cuboids. We present two aggregation methods: convolution and sketch-based. The two methods scale down the time complexities of building a probabilistic cuboid to polynomial and linear, respectively. Each of the two supports both full and partial data cube materialization. Then, we devise a cost model which guides the aggregation methods to be deployed and combined during the cube materialization. We further provide algorithms for probabilistic slicing and dicing queries on the data cube. Extensive experiments over real and synthetic datasets are conducted to show that the techniques are effective and scalable.

We study safe zones for service subscriptions in a volunteered geographic service setting, covering the concepts, properties, and algorithms needed for the use of weighted imprecise Voronoi cells as safe zones. Empirical performance studies on both synthetic and real datasets offer insights into the efficiency and scalability of our proposal. For a comprehensive coverage, see the full version of the paper.

Using GPS-enabled smart phones, social network services are enriched with location information which allows users to share geo-tagged contents with their friends. This so called location-based social network (LBSN) data has a dual spatial and graph nature. The growing scale and importance of LBSN data necessitate a platform which (i) has both spatial and graph capabilities, (ii) supports a wide range of queries, e.g., selection, structural, and aggregate queries, (iii) supports scalable distributed processing of large data volumes. In this paper, we propose such a platform, called Geo Social-GraphX, that segregates the LBSN data into several specific graphs capturing user-user, user-location, and location-location relationships, and enables a wide range of LBSN queries by proposing a comprehensive set of query primitives that can be composed into more advanced queries. We implement the platform based on GraphX, a map-reduce infrastructure for distributed graph computation. We further improve the query performance in several ways. For social-related data, we use vertex-centric messaging operators which better address the recursive nature of graph data than traditional two-stage map-reduce. For spatial-related data, we use effective spatial partitioning and indexing methods. Experiments on both synthetic and real LBSN datasets show that Geo Social-GraphX can process a variety of LBSN queries efficiently, scales on multicore architectures, and achieves much better performance than the state of the art competing framework, Spatial Hadoop.

RFID is widely used for object tracking in indoor environments, e.g., airport baggage tracking. Analyzing RFID data offers insight into the underlying tracking systems as well as the associated business processes. However, the inherent uncertainty in RFID data, including noise (cross readings) and incompleteness (missing readings), pose challenges to high-level RFID data querying and analysis. In this paper, we address these challenges by proposing a learning-based data cleansing approach that, unlike existing approaches, requires no detailed prior knowledge about the spatio-temporal properties of the indoor space and the RFID reader deployment. Requiring only minimal information about RFID deployment, the approach learns relevant knowledge from raw RFID data and uses it to cleanse the data. In particular, we model raw RFID readings as time series that are sparse because the indoor space is only partly covered by a limited number of RFID readers.

We provide techniques that enable a scalable so-called Volunteered Geographic Services system. This system targets the increasing populations of online mobile users, e.g., smartphone users, enabling such users to provide location-based services to each other, thus enabling citizen reporter or citizen as a sensor scenarios. More specifically, the system allows users to register as service volunteers, or micro-service providers, by accepting service descriptions and periodically updated locations from such volunteers; and the system allows users to subscribe to notifications of available, nearby relevant services by accepting subscriptions, formalized as continuous queries, that take service preferences and user locations as arguments and return relevant services. Services are ranked according to their relevance and distance to a query, and the highest ranked services are returned. The key challenge addressed is that of scalably providing up-to-date results to queries when the query locations change continuously. This is achieved by the proposal of a new so-called safe-zone model. With safe zones, query results are accompanied by safe zones with the property that a query result remains the same for all locations in its safe zone. Then, query users need only notify the system when they exit their current safe zone. Existing safe-zone models fall short in the papers setting. The new model is enabled by (i) weighted and (ii) set weighted imprecise Voronoi cells. The paper covers underlying concepts, properties, and algorithms, and it covers applications in VGS tracking and presents findings of empirical performance studies.

Indoor spaces accommodate large parts of people's lives. Relevant techniques are thus needed to efficiently manage indoor moving objects, whose positions are detected by technologies, such as Assisted GPS, Wi-Fi, RFID, and Bluetooth. Among such techniques, the distance-aware join processing is of importance in practice for indoor spatial databases. Such join operators leverage a series of applications, such as indoor mobile service and facility monitoring. However, distance-aware joining over indoor moving objects is challenging because: (1) indoor spaces are characterized by many special entities and thus render distance calculation very complex; (2) the limitations of indoor positioning technologies create inherent uncertainties in indoor moving objects data. In this paper, we study two representative join predicates in indoor settings, semi-range join and semi-neighborhood join. To implement them, we define and categorize the indoor distances between indoor uncertain objects, and derive different distance bounds that can facilitate the join processing. We design a composite index scheme that integrates indoor geometries, indoor topologies, as well as indoor uncertain objects, and thus supports the join processing efficiently. The results of extensive experimental studies demonstrate that our proposals are efficient and scalable in evaluating distance-aware join over indoor moving objects.

Indoor navigation is very useful in reality. An indoor navigation system requires an appropriate indoor model that represents the indoor space entities as well as topology and supports indoor distance computation. Indoor distance computation differs significantly from its outdoor counterpart, due to the indoor space characteristics. On the other hand, information about an indoor space is described in digital building information (DBI) formats like the Industry Foundation Classes (IFC). In such formats, geometric representation of entities is the focus but the topology is only implicit or even incomplete. Thus, constructing indoor navigation systems faces two major technical challenges: 1) indoor distance computation; 2) indoor space model creation from raw DBI. This paper presents a prototype system that addresses these two challenges. The system provides functions to process raw DBI files, employs PostgreSQL with PostGIS to manage the information carefully extracted from those files, and offers indoor navigation service that supports indoor distance computation. The system also presents an app that accesses the indoor navigation service from mobile terminals.

In recent years, real-time processing and analytics systems for big data--in the context of Business Intelligence (BI)--have received a growing attention. The traditional BI platforms that perform regular updates on daily, weekly or monthly basis are no longer adequate to satisfy the fast-changing business environments. However, due to the nature of big data, it has become a challenge to achieve the real-time capability using the traditional technologies. The recent distributed computing technology, MapReduce, provides off-the-shelf high scalability that can significantly shorten the processing time for big data; Its open-source implementation such as Hadoop has become the de-facto standard for processing big data, however, Hadoop has the limitation of supporting real-time updates. The improvements in Hadoop for the real-time capability, and the other alternative real-time frameworks have been emerging in recent years. This paper presents a survey of the open source technologies that support big data processing in a real-time/near real-time fashion, including their system architectures and platforms.

The Radio-Frequency Identification (RFID) is a useful technology for object tracking and monitoring systems in indoor environments, e.g., Airport baggage tracking. Nevertheless, the data produced by RFID tracking is inherently uncertain and contains errors. In order to support meaningful high-level applications including queries and analyses over RFID data, it is necessary to cleanse raw RFID data. In this paper, we focus on false negatives in raw indoor RFID tracking data. False negatives occur when a moving object passes the detection range of an RFID reader but the reader fails to produce any readings. We investigate the topology of indoor spaces as well as the deployment of RFID readers, and propose the transition probabilities that capture how likely objects move from one RFID reader to another. We organize such probabilities, together with the characteristics of indoor topology and RFID readers, into a probabilistic distance-aware graph. With the aid of this graph, we design algorithms to identify false negatives and recover missing information in indoor RFID tracking data. We evaluate the proposed cleansing approach using both real and synthetic datasets. The experimental results show that the approach is effective, efficient and scalable.

Trajectory queries, which retrieve nearby objects for every point of a given route, can be used to identify alerts of potential threats along a vessel route, or monitor the adjacent rescuers to a travel path. However, the locations of these objects (e.g., threats, succours) may not be precisely obtained due to hardware limitations of measuring devices, as well as complex natures of the surroundings. For such data, we consider a common model, where the possible locations of an object are bounded by a closed region, called “imprecise region”. Ignoring or coarsely wrapping imprecision can render low query qualities, and cause undesirable consequences such as missing alerts of threats and poor response rescue time. Also, the query is quite time-consuming, since all points on the trajectory are considered. In this paper, we study how to efficiently evaluate trajectory queries over imprecise objects, by proposing a novel concept, u-bisector, which is an extension of bisector specified for imprecise data. Based on the u-bisector, we provide an efficient and versatile solution which supports different shapes of commonly-used imprecise regions (e.g., rectangles, circles, and line segments). Extensive experiments on real datasets show that our proposal achieves better efficiency, quality, and scalability than its competitors.

The Radio Frequency Identification (RFID) emerges to be one of the key technologies to modernize object tracking and monitoring systems in indoor environments, e.g., airport baggage tracking. Although RFID has advantages over alternative identification technologies, the raw RFID data produced is inherently uncertain and contains errors. The dirty nature of raw RFID data hinders the progress of applying meaningful high-level applications that range from querying to analyzing. Therefore, cleansing RFID data is a high necessity. In this paper, we focus on handling one of the main aspects of raw RFID data, namely, false negatives, which occurs when a moving object passes the detection range of an RFID reader but the reader fails to produce any readings. We investigate the topology of indoor spaces as well as the deployment of RFID readers, and propose the transition probabilities that capture how likely objects move from one RFID reader to another. We organize such probabilities, together with the characteristics of indoor topology and RFID readers, into a probabilistic distance-aware graph model. Further, we evaluate the effectiveness and efficiency of devised graph model in recovering the false negatives using real dataset. The experimental results show that the devised graph model is effective and efficient in handling false negatives in indoor RFID tracking data.

Indoor spaces accommodate large parts of people's life. The increasing availability of indoor positioning, driven by technologies like Wi-Fi, RFID, and Bluetooth, enables a variety of indoor location-based services (LBSs). Efficient indoor distance-aware queries on indoor moving objects play an important role in supporting and boosting such LBSs. However, the distance-aware query evaluation on indoor moving objects is challenging because: (1) indoor spaces are characterized by many special entities and thus render distance calculation very complex; (2) the limitations of indoor positioning technologies create inherent uncertainties in indoor moving objects data. In this paper, we propose a complete set of techniques for efficient distance-aware queries on indoor moving objects. We define and categorize the indoor distances in relation to indoor uncertain objects, and derive different distance bounds that can facilitate query evaluation. Existing works often assume indoor floor plans are static, and require extensive pre-computation on indoor topologies. In contrast, we design a composite index scheme that integrates indoor geometries, indoor topologies, as well as indoor uncertain objects, and thus supports indoor distance-aware queries efficiently without time-consuming and volatile distance computation. We design algorithms for range query and k nearest neighbor query on indoor moving objects. The results of extensive experimental studies demonstrate that our proposals are efficient and scalable in evaluating distance-aware queries over indoor moving objects.

The Radio Frequency Identification (RFID) is increasingly being deployed in indoor tracking systems, e.g., airport baggage monitoring. However, the “dirtiness” in raw RFID readings hinder the progress of applying meaningful high level applications that range from monitoring to analysis. Hence, it is indispensable to cleansing RFID data in such systems. In this paper, we focus on two quality aspects in raw indoor RFID data: temporal redundancy and spatial ambiguity. The former refers to the large number of repeated readings for the same object and the same RFID reader during a period of time. The latter refers to the undetermined whereabouts of an object due to multiple readings by different readers simultaneously. We investigate the spatiotemporal characteristics of indoor spaces as well as RFID reader deployment, and exploit them in designing effective data cleansing techniques. Specifically, we aggregate raw RFID readings to reduce temporal redundancy; we design a distance-aware graph to resolve spatial ambiguity with respect to the indoor topology and the RFID reader deployment captured in the graph. We evaluate the spatiotemporal data cleansing techniques using both real and synthetic datasets. The experimental results demonstrate that the proposed techniques are effective and efficient in cleansing indoor RFID tracking data.

Route evaluation and optimization have received significant attention in recent years. In this light, we propose and investigate a novel problem of estimating the travel time (TTE query) for a user specified path by considering the related traffic conditions. Given a query path and a departure time, TTE query finds the estimated travel time along this path. We believe that this type of query may bring important benefits to users in many popular applications, such as travel route evaluation and optimization, and route planning and recommendation. To address the TTE problem in a convincing approach, we construct a traffic-aware spatial network Gpt(V, E) by analysing uncertain trajectory data of moving objects. Based on Gpt(V, E), we define two novel types of TTE queries: TTEepfor an exact query path, and TTElpfor a loose query path. The performance of the construction of traffic-aware spatial network is verified by extensive experiments based on real and synthetic spatial data sets.

The Voronoi diagram is an important technique for answering nearest-neighbor queries for spatial databases. We study how the Voronoi diagram can be used for uncertain spatial data, which are inherent in scientific and business applications. Specifically, we propose the Uncertain-Voronoi diagram (or UV-diagram), which divides the data space into disjoint “UV-partitions”. Each UV-partition $$P$$ is associated with a set $$S$$ of objects, such that any point $$q$$ located in $$P$$ has the set $$S$$ as its nearest neighbor with nonzero probabilities. The UV-diagram enables queries that return objects with nonzero chances of being the nearest neighbor (NN) of a given point $$q$$ . It supports “continuous nearest-neighbor search”, which refreshes the set of NN objects of $$q$$ , as the position of $$q$$ changes. It also allows the analysis of nearest-neighbor information, for example, to find out the number of objects that are the nearest neighbors of any point in a given area. A UV-diagram requires exponential construction and storage costs. To tackle these problems, we devise an alternative representation of a UV-diagram, by using a set of UV-cells. A UV-cell of an object $$o$$ is the extent $$e$$ for which $$o$$ can be the nearest neighbor of any point $$q \in e$$ . We study how to speed up the derivation of UV-cells by considering its nearby objects. We also use the UV-cells to design the UV-index, which supports different queries, and can be constructed in polynomial time. We have performed extensive experiments on both real and synthetic data to validate the efficiency of our approaches.

The Voronoi diagram is an important technique for answering nearest-neighbor queries for spatial databases. In this paper, we study how the Voronoi diagram can be used on uncertain data, which are inherent in scientific and business applications. In particular, we propose the Uncertain-Voronoi Diagram (or UV-diagram in short). Conceptually, the data space is divided into distinct ¿UV-partitions¿, where each UV-partition P is associated with a set S of objects; any point q located in P has the set S as its nearest neighbor with non-zero probabilities. The UV-diagram facilitates queries that inquire objects for having non-zero chances of being the nearest neighbor of a given query point. It also allows analysis of nearest neighbor information, e.g., finding out how many objects are the nearest neighbors in a given area. However, a UV-diagram requires exponential construction and storage costs. To tackle these problems, we devise an alternative representation for UV-partitions, and develop an adaptive index for the UV-diagram. This index can be constructed in polynomial time. We examine how it can be extended to support other related queries. We also perform extensive experiments to validate the effectiveness of our approach.

Data ambiguity is inherent in applications such as data integration, location-based services, and sensor monitoring. In many situations, it is possible to "clean", or remove, ambiguities from these databases. For example, the GPS location of a user is inexact due to measurement errors, but context information (e.g., what a user is doing) can be used to reduce the imprecision of the location value. In order to obtain a database with a higher quality, we study how to disambiguate a database by appropriately selecting candidates to clean. This problem is challenging because cleaning involves a cost, is limited by a budget, may fail, and may not remove all ambiguities. Moreover, the statistical information about how likely database objects can be cleaned may not be precisely known. We tackle these challenges by proposing two types of algorithms. The first type makes use of greedy heuristics to make sensible decisions; however, these algorithms do not make use of cleaning information and require user input for parameters to achieve high cleaning effectiveness. We propose the Explore-Exploit (or EE ) algorithm, which gathers valuable information during the cleaning process to determine how the remaining cleaning budget should be invested. We also study how to fine-tune the parameters of EE in order to achieve optimal cleaning effectiveness. Experimental evaluations on real and synthetic datasets validate the effectiveness and efficiency of our approaches.

In emerging applications such as location-based services, sensor monitoring and biological management systems, the values of the database items are naturally imprecise. For these uncertain databases, an important query is the Probabilistic k-Nearest-Neighbor Query (k-PNN), which computes the probabilities of sets of k objects for being the closest to a given query point. The evaluation of this query can be both computationally- and I/O-expensive, since there is an exponentially large number of k object-sets, and numerical integration is required. Often a user may not be concerned about the exact probability values. For example, he may only need answers that have sufficiently high confidence. We thus propose the Probabilistic Threshold k-Nearest-Neighbor Query (T-k-PNN), which returns sets of k objects that satisfy the query with probabilities higher than some threshold T. Three steps are proposed to handle this query efficiently. In the first stage, objects that cannot constitute an answer are filtered with the aid of a spatial index. The second step, called probabilistic candidate selection, significantly prunes a number of candidate sets to be examined. The remaining sets are sent for verification, which derives the lower and upper bounds of answer probabilities, so that a candidate set can be quickly decided on whether it should be included in the answer. We also examine spatially-efficient data structures that support these methods. Our solution can be applied to uncertain data with arbitrary probability density functions. We have also performed extensive experiments to examine the effectiveness of our methods.

Uncertain or imprecise data are pervasive in applications like location-based services, sensor monitoring, and data collection and integration. For these applications, probabilistic databases can be used to store uncertain data, and querying facilities are provided to yield answers with statistical confidence. Given that a limited amount of resources is available to "clean" the database (e.g., by probing some sensor data values to get their latest values), we address the problem of choosing the set of uncertain objects to be cleaned, in order to achieve the best improvement in the quality of query answers. For this purpose, we present the PWS-quality metric, which is a universal measure that quantifies the ambiguity of query answers under the possible world semantics. We study how PWS-quality can be efficiently evaluated for two major query classes: (1) queries that examine the satisfiability of tuples independent of other tuples (e.g., range queries); and (2) queries that require the knowledge of the relative ranking of the tuples (e.g., MAX queries). We then propose a polynomial-time solution to achieve an optimal improvement in PWS-quality. Other fast heuristics are presented as well. Experiments, performed on both real and synthetic datasets, show that the PWS-quality metric can be evaluated quickly, and that our cleaning algorithm provides an optimal solution with high efficiency. To our best knowledge, this is the first work that develops a quality metric for a probabilistic database, and investigates how such a metric can be used for data cleaning purposes.