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.

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.

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.

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.

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.

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.

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.

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.