Graph data has become increasingly important in the AI and big data era. However, graph data analysis raises privacy concerns since it often originates from individual users. As a privacy regulation, the right to be forgotten has been established to allow users to erase their data hosted by a third party. When users request to delete their information from the original graph, the deletion must be synchronized to analysis results, like graph statistics or pre-trained AI models. In existing works, much effort has been made to fulfill the right to be forgotten for complicated graph learning models. In this work, we aim at a fundamental query — graph summarization, which serves as a building block for many graph analysis tasks. Since in summarization, when data removal requests are received, re-summarizing the graph from scratch can be costly, we present a novel approach to graph summarization regarding potential deletion requests. Inspired by machine unlearning, we define this problem as graph unsummarization which has three goals: efficiency, forgetting quality, and utility. Towards these goals, we propose SUGPT, a graph summarization and unsummarization method based on matrix partition and trie. The essence of SUGPT is to identify similarities between vertices by embedding matrix partitions into a trie structure, to accelerate summary updating upon deletion requests. We prove the forgetting quality of SUGPT theoretically and our extensive experiments demonstrate that SUGPT balances well in efficiency and utility in graph analysis.

Graph neural network-based recommenders employ the aggregation paradigms to learn node representation from higher-order neighboring nodes within the graph. However, these simple aggregation paradigms may perform poorly when mitigating noise impacts and capturing complex user preferences. To address it, some studies have attempted to enhance representation through contrastive augmentation across different views. Despite some effectiveness, the simple-view contrasts are still suboptimal with some unresolved challenges: (1) the influence of multivariate noise in interaction data, (2) knowledge biases introduced by irrelevant connections, and (3) user’s multiple interests. In this work, we propose a novel method named Diffusion-Based Relation Augmentation for Knowledge-aware Recommendation (DRAR) to overcome the above challenges. First, we alleviate the impact of interaction noise by injecting uncertainty and generating preference distributions with a diffusion-based module. Next, we design a relation augmentation module to effectively capture user neighborhood-level and context-level enhanced representations to alleviate the knowledge bias of irrelevant connections. Furthermore, we design a collaborative alignment module that enhances the model’s robustness by aligning user representation views at different stages. Extensive experiments on three benchmark datasets consistently demonstrate the superiority of our model over the state-of-the-art approaches. Our model demonstrates average improvements of 6.78% in Recall and 7.38% in NDCG across all datasets.

To protect privacy for data-collection-based services, local differential privacy (LDP) is widely adopted due to its rigorous theoretical bound on privacy loss.However, mistakes in complex theoretical analysis or subtle implementation errors may undermine its practical guarantee.To address this, auditing is crucial to confirm that LDP protocols truly protect user data.However, existing auditing methods, though, mainly target machine learning and federated learning tasks based on centralized differentially privacy (DP), with limited attention to LDP.Moreover, the few studies on LDP auditing focus solely on simple frequency estimation task for discrete data, leaving correlated key-value data -which requires both discrete frequency estimation for keys and continuous mean estimation for values -unexplored.To bridge this gap, we propose KV-Auditor, a framework for auditing LDP-based key-value estimation mechanisms by estimating their empirical privacy lower bounds.Rather than traditional LDP auditing methods that relies on binary output predictions, KV-Auditor estimates this lower bound by analyzing unbounded output distributions, supporting continuous data.Specifically, we classify state-of-the-art LDP key-value mechanisms into interactive and non-interactive types.For non-interactive mechanisms, we propose horizontal KV-Auditor for small domains with sufficient samples and vertical KV-Auditor for large domains with limited samples.For interactive mechanisms, we design a segmentation strategy to capture incremental privacy leakage across iterations.Finally, we perform extensive experiments to validate the effectiveness of our approach, offering insights for optimizing LDP-based key-value estimators. CCS Concepts• Security and privacy →

As a fundamental operation of location-based services, shortest path querying is widely adopted in real-time applications. Regrettably, most prior works overlook the impact of traffic-flow on shortest path querying. Taking traffic-flow into account is essential for finding a more convenient path through the Flow-Aware Shortest Path Querying (FSPQ). FSPQ faces the following challenges: (1) index restriction, existing indexes are only constructed by the relative spatial distance, if we leverage the traffic-flow to build the index, we can reduce the index size and improve its query efficiency. (2) maintenance latency, the traffic-flow and edges' weights undergo high-frequency changes with different traffic conditions, meaning that our index must be able to support high-frequency updates. To end this, we propose a novel Flow-Aware Hierarchical Labeling Index (FAHL) in this paper. In the index construction aspect, we propose a degree-flow joint ordering method to obtain the joint vertex ordering, and then build the index on it. In this way, FAHL can not only perceive both spatial distance and traffic-flow information but also reduce the index overhead during the query. In the index maintenance aspect, we propose Improved Structure Update (ISU) and Index Label Update (ILU) algorithms to support the index updating when high-frequency flow$\backslash$weight changes. Moreover, a flow priority shortest path search algorithm with pruning query bounds is proposed to speed up the query processing. Extensive experiments demonstrate that our proposed method achieves 33.1% speedup on average for the flow-aware shortest path querying compared to the state-of-the-art methods.

We propose the concept of Intra-Query Runtime Elasticity (IQRE) for cloud-native data analysis. IQRE enables a cloud-native OLAP engine to dynamically adjust a query's Degree of Parallelism (DOP) during execution. This capability allows users to utilize cloud computing resources more cost-effectively. We present Accordion, the first IQRE query engine. Accordion can adjust the parallelism of a query at any point during query execution without pausing data processing. It features a user-friendly interface and an auto-tuner backed by a "what-if" service to allow users to adjust the DOP according to their query latency constraints. The design of Accordion follows the execution model in Presto, an open-source distributed SQL query engine developed at Meta. We present the implementation of Accordion and demonstrate its ease of use, showcasing how it enables users to minimize compute resource consumption while meeting their query time constraints.

Cloud databases empower users to leverage vast computing resources for efficient data analysis. However, achieving cost-effective utilization of these resources remains a challenge. Users often struggle to balance computing resource allocation with their temporal and financial constraints. To address this, we propose the concept of Intra-Query Runtime Elasticity (IQRE), which allows a cloud-native OLAP engine to dynamically adjust the query Degree of Parallelism (DOP) during query execution. We introduce Accordion, the first IQRE engine. Accordion features a friendly user interface for parallelism adjustments. It includes an auto-tuner that supports both manual and automatic DOP tuning during query execution. In this demonstration, we present Accordion's architecture and provide attendees with hands-on experience, allowing them to execute queries and adjust query parallelism during query execution based on their time or cost budgets.

The mainstream approach of GNN-based recommendation aggregates high-order ID information associated with the node in the user-item graph. The aggregation pattern using ID as signal has two disadvantages: lack of textual semantics and the impact of interaction noise. These disadvantages pose a threat to effectively learn user preferences, especially in capturing intricate user-item semantic relationships. Although large language models (LLMs) allow the integration of rich textual information into recommenders and have had groundbreaking applications in recommender systems, current works need to bridge the gap between different representation spaces. This is because LLM-based methods align the representations of GNN-based models only by using text embedding of LLM, leading to unsatisfactory results. To address this challenge, we propose a denoising alignment framework with LLMs for GNN-based recommenders (DALR) , which aims to align structural representation with textual representation and mitigate the effects of noise. Specifically, we propose a modeling framework that integrates the representation of graph structure with textual information from LLMs to capture intricate user-item interactions. We also suggest an alignment paradigm to enhance representation performance by aligning semantic signals from LLMs and structural features from GNN models. Additionally, we introduce a contrastive learning scheme to relieve the impact of noise and improve model performance. Extensive experiments on public datasets demonstrate that our model consistently outperforms the state-of-the-art methods. DALR achieves improvements ranging from 2.82% to 12.20% in Recall@5 and from 1.04% to 3.48% in NDCG@5 compared to the strongest baseline model, using the Steam dataset as an example.

As a fundamental technology in intelligent transportation systems (ITS), accurate traffic flow prediction has emerged as a critical challenge in real-time applications. How to fully utilize the traffic data, and capture the spatial temporal correlation are keys to improve the model's prediction ability. Numerous neural networks have been proposed to address this issue. However, most of these existing methods have the following two problems: 1) Lack of byroads information. Meaning that the existing methods do not consider the byroads in real-life traffic environments; 2) Lack of potential learning ability. Meaning that the existing methods suffer the non-similar forgetting and hard to gain the multi-hop correlation. To overcome these problems, we propose a novel Spatial Temporal Byroad-Aware Graph Convolution Network (ByGCN) in this paper. ByGCN consists of byroad identification and spatial temporal learning modules. In the first module, we design spatial temporal decoupling and graph diffusion blocks to identify the byroads and reconstruct them into the flow data. In the second module, with the help of spatial temporal attention and GCN, our module can capture the complex spatial temporal correlation. Experiments on four real-world traffic datasets demonstrate that ByGCN outperforms the state-of-the-art methods.

With the development of astronomical facilities, large-scale time series data observed by these facilities is being collected. Analyzing anomalies in these astronomical observations is crucial for uncovering potential celestial events and physical phenomena, thus advancing the scientific research process. However, existing time series anomaly detection methods fall short in tackling the unique characteristics of astronomical observations where each star is inherently independent but interfered by random concurrent noise, resulting in a high rate of false alarms. To overcome the challenges, we propose AERO, a novel two-stage framework tailored for unsupervised anomaly detection in astronomical observations. In the first stage, we employ a Transformer-based encoder-decoder architecture to learn the normal temporal patterns on each variate (i.e., star) in alignment with the characteristic of variate independence. In the second stage, we enhance the graph neural network with a window-wise graph structure learning to tackle the occurrence of concurrent noise characterized by spatial and temporal randomness. In this way, AERO is not only capable of distinguishing normal temporal patterns from potential anomalies but also effectively differentiating concurrent noise, thus decreasing the number of false alarms. We conducted extensive experiments on three synthetic datasets and three real-world datasets. The results demonstrate that AERO outperforms the compared baselines. Notably, compared to the state-of-the-art model, AERO improves the F1-score by up to 8.76% and 2.63% on synthetic and real-world datasets respectively.

The recent surge in learned index algorithms, along-side traditional indexes, has greatly diversified indexing options to support query processing in databases. Despite the rapid expansion of learned indexes, there remains a significant gap in tools for index algorithm selection. Traditional research on index selection has largely focused on recommending which columns to index, as the choice between algorithms like B+tree or hash index was once straightforward. This was managed through basic rules or experiential judgment, given the historically limited options. However, this approach is inadequate today, due to the growing diversity and complexity of index algorithms. In this paper, we introduce a Learned INDex Algorithm Selector, LINDAS. Taking a learned approach, LINDAS uniquely focuses on automatically selecting the most suitable index algorithm for a specific column, that satisfies diverse performance objectives in a wide range of applications. We explore the design space of LINDAS, employing a carefully designed featurization approach to capture both data-and workload-specific characteristics with attention mechanisms, as well as the meta-features of index algorithms. Two variants of LINDAS are designed to cater to diverse scenarios and adapt readily to new datasets, workloads, and emerging index algorithms. Comprehensive evaluations of LINDAS across various datasets and workloads demonstrate its effectiveness and superiority compared to applicable baselines.

Answering range queries in the context of Local Differential Privacy (LDP) is a widely studied problem in Online Analytical Processing (OLAP). Existing LDP solutions all assume a uniform data distribution within each domain partition, which may not align with real-world scenarios where data distribution is varied, resulting in inaccurate estimates. To address this problem, we introduce PriPL-Tree, a novel data structure that combines hierarchical tree structures with piecewise linear (PL) functions to answer range queries for arbitrary distributions. PriPL-Tree precisely models the underlying data distribution with a few line segments, leading to more accurate results for range queries. Furthermore, we extend it to multi-dimensional cases with novel data-aware adaptive grids. These grids leverage the insights from marginal distributions obtained through PriPL-Trees to partition the grids adaptively, adapting the density of underlying distributions. Our extensive experiments on both real and synthetic datasets demonstrate the effectiveness and superiority of PriPL-Tree over state-of-the-art solutions in answering range queries across arbitrary data distributions.

Collecting and analyzing users' set-valued data with privacy-preserving is a common scenario in real life. However, the existing solutions in LDP are not efficient enough, where users perturbing their data locally introduces a large amount of noise. The shuffle model, which adds a shuffler in LDP to shuffle all perturbed values, can amplify privacy, then improve utility. Inspired by this, we study the frequency estimation and top-$k$frequent item estimation of set-valued data in the shuffle model. To solve the challenges of different item quantities of users and further improve the utility, we combine sampling and shuffling together, and propose theEncoding, Padding, Sampling, and Shufflingframework, i.e., EPS$^{2}$. Based on this framework, we propose three protocols for frequency estimation in different application scenarios, then assemble them into multi-phase protocols for the top-$k$frequent item estimation. Theoretically, we identify all three protocols gain dual privacy amplification from sampling and shuffling. And by setting the size of users' set to 1, we can extend this amplified bound to the single-valued frequency estimation scenario, producing a tighter privacy bound than existing works. Finally, we perform experiments on both synthetic and real-world datasets to demonstrate the effectiveness of our protocols.

The meteoric rise of cross-silo Federated Learning (FL) is due to its ability to mitigate data breaches during collaborative training. To further provide rigorous privacy protection with consideration of the varying privacy requirements across different clients, a privacy-enhanced line of work on personalized differentially private federated learning (PDP-FL) has been proposed. However, the existing solution for PDP-FL [20] assumes the raw privacy budgets of all clients should be collected by the server. These values are then directly utilized to improve the model utility via facilitating the privacy preferences partitioning (i.e., partitioning all clients into multiple privacy groups). It is however non-realistic because the raw privacy budgets can be quite informative and sensitive.

A shortest distance query is a fundamental operation of various real-time response applications in time-dependent road networks. Unfortunately, existing methods (e.g., G-treelike, 2-hop labeling-like) are prohibitively expensive in terms of space/time. To this end, we propose a novel Double Hierarchical Labeling (DHL) index, which consists of a Hierarchical Graph Partition (HGP) tree and a hierarchical border labeling list. For HGP-tree, we first use a hierarchical graph partitioning to split the entire road network into hierarchical subgraphs and then index these subgraphs by a balanced tree. To preserve all connectivity information between border vertices of subgraphs, a Time-based Distance Inverted File (TDIF) is constructed for each leaf node of the HGP-tree. For the hierarchical labeling list, we construct it only for border vertices and use it to speed up query processing. Moreover, a label propagation update is proposed to manage label updating when weights change. Finally, we propose a phase-aware search algorithm for different search situations between given query vertices to guarantee query efficiency. Extensive experiments are conducted to demonstrate the superiority of the proposed proposals on query processing and index maintenance.

As modern applications generate data at an unprecedented speed and often require the querying/analysis of data spanning a large duration, it is crucial to develop indexing techniques that cater to larger-than-memory databases, where data reside on heterogeneous storage devices (such as memory and disk), and support fast data insertion and query processing. In this paper, we propose FILM, a F ully learned I ndex for L arger-than- M emory databases. FILM is a learned tree structure that uses simple approximation models to index data spanning different storage devices. Compared with existing techniques for larger-than-memory databases, such as anti-caching, FILM allows for more efficient query processing at significantly lower main-memory overhead. FILM is also designed to effectively address one of the bottlenecks in existing methods for indexing larger-than-memory databases that is caused by data swapping between memory and disk. More specifically, updating the LRU (for Least Recently Used) structure employed by existing methods for cold data identification (determining the data to be evicted to disk when the available memory runs out) often incurs significant delay to query processing. FILM takes a drastically different approach by proposing an adaptive LRU structure and piggybacking its update onto query processing with minimal overhead. We thoroughly study the performance of FILM and its components on a variety of datasets and workloads, and the experimental results demonstrate its superiority in improving query processing performance and reducing index storage overhead (by orders of magnitudes) compared with applicable baselines.

Local differential privacy (LDP) is an emerging technique for privacy-preserving data collection without a trusted collector. Despite its strong privacy guarantee, LDP cannot be easily applied to real-world graph analysis tasks such as community detection and centrality analysis due to its high implementation complexity and low data utility. In this paper, we address these two issues by presenting LF-GDPR, the first LDP-enabled graph metric estimation framework for graph analysis. It collects two atomic graph metrics—the adjacency bit vector and node degree—from each node locally. LF-GDPR simplifies the job of implementing LDP-related steps (e.g., local perturbation, aggregation and calibration) for a graph metric estimation task by providing either a complete or a parameterized algorithm for each step. To address low data utility of LDP, it optimally allocates privacy budget between the two atomic metrics during data collection. To demonstrate the usage of LF-GDPR, we show use cases on two common graph analysis tasks, namely, clustering coefficient estimation and community detection. The privacy and utility achieved by LF-GDPR are verified through theoretical analysis and extensive experimental results.

Federated Learning (FL) is a promising framework for multiple clients to learn a joint model without directly sharing the data. In addition to high utility of the joint model, rigorous privacy protection of the data and communication efficiency are important design goals. Many existing efforts achieve rigorous privacy by ensuring differential privacy for intermediate model parameters, however, they assume a uniform privacy parameter for all the clients. In practice, different clients may have different privacy requirements due to varying policies or preferences. In this paper, we focus on explicitly modeling and leveraging the heterogeneous privacy requirements of different clients and study how to optimize utility for the joint model while minimizing communication cost. As differentially private perturbations affect the model utility, a natural idea is to make better use of information submitted by the clients with higher privacy budgets (referred to as "public" clients, and the opposite as "private" clients). The challenge is how to use such information without biasing the joint model. We propose P rojected F ederated A veraging (PFA), which extracts the top singular subspace of the model updates submitted by "public" clients and utilizes them to project the model updates of "private" clients before aggregating them. We then propose communication-efficient PFA+, which allows "private" clients to upload projected model updates instead of original ones. Our experiments verify the utility boost of both algorithms compared to the baseline methods, whereby PFA+ achieves over 99% uplink communication reduction for "private" clients.

Local differential privacy (LDP) is an emerging technique for privacy-preserving data collection without a trusted collector. Despite its strong privacy guarantee, LDP cannot be easily applied to real-world graph analysis tasks such as community detection and centrality analysis due to its high implementation complexity and low data utility. In this paper, we address these two issues by presenting LF-GDPR, the first LDP-enabled graph metric estimation framework for graph analysis. It collects two atomic graph metrics - the adjacency bit vector and node degree - from each node locally. LF-GDPR simplifies the job of implementing LDP-related steps (e.g., local perturbation, aggregation and calibration) for a graph metric estimation task by providing either a complete or a parameterized algorithm for each step.

We present the design of and a demonstration for SciDetector, a system of scientific research for online analysis. SciDetector can efficiently online analyze scientific events on large-scale newly arriving data. In modern scientific research, especially astronomy survey, with the development of the observation infrastructure, Short-Timescale and Large Field-of-view (STLF) sky survey has been the major topic. However, existing scientific system focus on offline analysis of long-term historical data, not real-time analysis of large-scale scientific data. Using real data, we demonstrate how SciDetector processes the data and generate the scientific product.

Astronomy is well recognized as big data driven science. As the novel observation infrastructures are developed, the sky survey cycles have been shortened from a few days to a few seconds, causing data processing pressure to shift from offline to online. However, existing scientific databases focus on offline analysis of long-term historical data, not real-time and low latency analysis of large-scale newly arriving data.In this paper, a cloud based method is proposed to efficiently analyze scientific events on large-scale newly arriving data. The solution is implemented as a highly efficient system, namely Aserv. A set of compact data store and index structures are proposed to describe the proposed scientific events and a typical analysis pattern is formulized as a set of query operations. Domain aware filter, accuracy aware data partition, highly efficient index and frequently used statistical data designs are four key methods to optimize the performance of Aserv. Experimental results under the typical cloud environment show that the presented optimization mechanism can meet the low latency demand for both large data insertion and scientific event analysis. Aserv can insert 3.5 million rows of data within 3 seconds and perform the heaviest query on 6.7 billion rows of data also within 3 seconds. Furthermore, a performance model is given to help Aserv choose the right cloud resource setup to meet the guaranteed real-time performance requirement.

Sentiment analysis and opinion mining are significant and valuable for subject information extraction from the text. Word embedding that can map the words to low-dimensional vector representations has been widely used in natural language processing tasks. But the word embedding based on context such as Word2Vec and GloVe is lack of capturing the sentiment information. Most of existing sentiment analysis methods incorporate sentiment polarity (positive and negative) to improve the sentiment embedding for sentiment tasks. Instead of making a new word embedding model, we introduce the multi-emotion category (MEC) model to improve the pre-trained word vectors which aims to move target word vectors closer to the words from both similar semantics and similar emotions. The MEC model can give eight-dimensional vector for one word in emotion space that can capture more sentiment information than the binary polarity labels. In addition, the obvious advantage of the MEC model is that it can be fit for any pre-trained word embedding. The experimental results on several Chinese and English data sets show that this new model can improve the conventional word embedding and some existing sentiment embedding for sentiment classification.

Storm is a popular real-time processing system. However, our earlier experiment shows that the fixed configuration of Storm would lead to either significant resource waste or limited processing throughput. In this demonstration, we present AdaStorm, a system to dynamically adjust the Storm configuration according to current data stream properties. AdaStorm is designed to minimize the resource usage while still ensuring the same or even better real-time response. We will demonstrate that AdaStorm can achieve resource efficiency as well as data rate tolerance, compared to Storm system with fixed configuration. Video: https://youtu.be/YFPBFNdMbXM.

Distributed data stream management systems (DDSMS) are often used to analyze and process road network data streams. DDSMS are composed of upper layer relational query systems (RQS) and lower layer stream processing systems (SPS). DDSMS usually need to meet multiple query requests. This often converts RQS submitted by users into different quest tasks on SPS, and executes query plans on different nodes in parallel by partitioning stream according to the values of specific attributes or partitioning keys. However, executing multiple query plans can cause redundant and repetitive partitioning. This article presents the framework of data stream partitioning based on runtime correlation discovery. It combines the runtime positive-correlation partitioning (RPC-partitioning) and the clustering partitioning (Clu-partitioning). In the process of RPC-partitioning, we first use batching schemes to reduce the number of output buffers and then partition data streams using the correlation between different partitioning keys. In the process of Clu-partitioning, we re-partition data streams by clustering for skewed data. Experiments show that our method can reduce the network communication cost from 16% to 20% with two workloads of road network data streams and improve the throughput in DDSMS. It proves the effectiveness of our method, especially on reducing the operational cost in the cloud environment.

Distributed data stream management systems (DDSMS) are usually composed of upper layer relational query systems (RQS) and lower layer stream processing systems (SPS). When users submit new queries to RQS, a query planner needs to be converted into a directed acyclic graph (DAG) consisting of tasks which are running on SPS. Based on different query requests and data stream properties, SPS need to configure different deployments strategies. However, how to dynamically predict deployment configurations of SPS to ensure the processing throughput and low resource usage is a great challenge. This article presents OrientStream, a framework for automating characterization deployment in DDSMS using incremental machine learning techniques. By introducing the data-level, query plan-level, operator-level, and cluster-level's four-level feature extraction mechanism, we first use the different query workloads as training sets to predict the resource usage by DDSMS, and select the optimal resource configuration from candidate settings based on the current query requests and stream properties, then migrate the operator state by introducing dynamic reconfiguration. Finally, we validate our approach on the open source SPS-Storm. In view of the application scenarios with long monitoring cycle and non-frequent data fluctuation, experiments show that OrientStream can reduce CPU usage of 8-15 percent and memory usage of 38-48 percent, respectively.

Distributed data stream management systems (DDSMS) are usually composed of upper layer relational query systems (RQS) and lower layer stream processing systems (SPS). When users submit new queries to RQS, a query planner needs to be converted into a directed acyclic graph (DAG) consisting of tasks which are running on SPS. Based on different query requests and data stream properties, SPS need to configure different deployments strategies. However, how to dynamically predict deployment configurations of SPS to ensure the processing throughput and low resource usage is a great challenge. This article presents OrientStream, a framework for dynamic resource allocation in DDSMS using incremental machine learning techniques. By introducing the data-level, query plan-level, operator-level and cluster-level's four-level feature extraction mechanism, we firstly use the different query workloads as training sets to predict the resource usage of DDSMS and then select the optimal resource configuration from candidate settings based on the current query requests and stream properties. Finally, we validate our approach on the open source SPS--Storm. Experiments show that OrientStream can reduce CPU usage of 8%-15% and memory usage of 38%-48% respectively.

Histograms are the workhorse of data mining and analysis. This paper considers the problem of publishing histograms under differential privacy, one of the strongest privacy models. Existing differentially private histogram publication schemes have shown that clustering (or grouping) is a promising idea to improve the accuracy of sanitized histograms. However, none of them fully exploits the benefit of clustering. In this paper, we introduce a new clustering framework. It features a sophisticated evaluation of the trade-off between the approximation error due to clustering and the Laplace error due to Laplace noise injected, which is normally overlooked in prior work. In particular, we propose three clustering strategies with different orders of run-time complexities. We prove the superiority of our approach by theoretical utility comparisons with the competitors. Our extensive experiments over various standard real-life and synthetic datasets confirm that our technique consistently outperforms existing competitors.

The fifth ACM international workshop on cloud data management is held in San Francisco, California, USA on October 28, 2013 and co-located with the ACM 22nd Conference on Information and Knowledge Management (CIKM). The main objective of the workshop is to address the challenges of large scale data management based on the cloud computing infrastructure. The workshop brings together researchers and practitioners from cloud computing, distributed storage, query processing, parallel algorithms, data mining, and system analysis, all attendees share common research interests in maximizing performance, reducing cost of cloud data management and enlarging the scale of their endeavors. We have constructed an exciting program of four refereed papers and an invited keynote talk that will give participants a full dose of emerging research.

Online aggregation is a promising solution to achieving fast early responses for interactive ad-hoc queries that compute aggregates on massive data. To process large datasets on large-scale computing clusters, MapReduce has been introduced as a popular paradigm into many data analysis applications. However, typical MapReduce implementations are not well-suited to analytic tasks, since they are geared towards batch processing. With the increasing popularity of ad-hoc analytic query processing over enormous datasets, processing aggregate queries using MapReduce in an online fashion is therefore an emerging important application need. We present a MapReduce-based online aggregation system called COLA, which provides progressive approximate aggregate answers for both single table and multiple joined tables. COLA provides an online aggregation execution engine with novel sampling techniques to support incremental and continuous computing of aggregation, and minimize the waiting time before an acceptably precise estimate is available. In addition, user-friendly SQL queries are supported in COLA. Furthermore, COLA can implicitly convert non-OLA jobs into online version so that users don't have to write any special-purpose code to make estimates.

The Internet of Things (IOT) has been widely applied in many fields, while the IOT data are always large volume, update frequently and inherently multi-dimensional, these characteristics bring big challenges to the traditional DBMSs. The traditional DBMSs have rich functionality and can deal with multi-attributes access efficiently, they can not scale good enough to deal with large volume data and can not support high insert throughput. The cloud-based database systems have good scalability, but they don't support multi-dimensional access natively.In order to deal with the large volume of IOT data, we propose an update and query efficient index framework (UQE-Index) based on key-value store that can support high insert throughput and provide efficient multi-dimensional query simultaneously. We implemented a prototype based on HBase and did comprehensive experiments to test our solution's scalability and efficiency.

The fourth ACM international workshop on cloud data management is held in Maui, Hawaii, USA on October 29, 2012 and co-located with the ACM 21th Conference on Information and Knowledge Management (CIKM). The main objective of the workshop is to address the challenges of large scale data management based on the cloud computing infrastructure. The workshop brings together researchers and practitioners from cloud computing, distributed storage, query processing, parallel algorithms, data mining, and system analysis, all attendees share common research interests in maximizing performance, reducing cost of cloud data management and enlarging the scale of their endeavors. We have constructed an exciting program of seven refereed papers and four invited keynote talks that will give participants a full dose of emerging research.

Cloud-based data management systems are emerging as scalable, fault-tolerant, and efficient solutions to manage large volumes of data with cost effective infrastructures, and more and more data analysis applications are migrated to the cloud. As an attractive solution to provide a quick sketch of massive data before a long wait of the final accurate query result, online processing of aggregate queries in the cloud is of paramount importance. This problem is challenging to solve because of the large block based data organization and distributed processing mode in the cloud. In this paper, we present COLA, a system for Cloud Online Aggregation to provide progressive approximate answers for both single tables and joined multiple tables. We develop an online query processing algorithm for MapReduce to support incremental and continuous computing of aggregations on joins which minimizes the waiting time before an acceptable estimate is achieved. We formulate a statistical foundation that supports block-level sampling for single-table online aggregations and effective estimation of approximate results and confidence intervals of statistical significance. We also develop a two-phase stratified sampling method to support multi-table aggregations to improve the approximate query answers and speed up the convergence of confidence intervals. We implement COLA in Hadoop, and our experiments demonstrate that COLA can deliver reasonable precise online estimates within a time period two orders of magnitude shorter than that used to produce exact answers.

Privacy protection has recently received considerable attention in location-based services. A large number of location cloaking algorithms have been proposed for protecting the location privacy of mobile users. In this paper, we consider the scenario where different location-based query requests are continuously issued by mobile users while they are moving. We show that most of the existing k-anonymity location cloaking algorithms are concerned with snapshot user locations only and cannot effectively prevent location-dependent attacks when users' locations are continuously updated. Therefore, adopting both the location k-anonymity and cloaking granularity as privacy metrics, we propose a new incremental clique-based cloaking algorithm, called ICliqueCloak, to defend against location-dependent attacks. The main idea is to incrementally maintain maximal cliques needed for location cloaking in an undirected graph that takes into consideration the effect of continuous location updates. Thus, a qualified clique can be quickly identified and used to generate the cloaked region when a new request arrives. The efficiency and effectiveness of the proposed ICliqueCloak algorithm are validated by a series of carefully designed experiments. The experimental results also show that the price paid for defending against location-dependent attacks is small.

No abstract available.

The Web is the largest repository of information. Personal information is usually scattered on various pages of different websites. Search engines have made it easier to find personal information. An attacker may collect a user's scattered information together via search engines, and infer some privacy information. We call this kind of privacy attack Privacy Inference Attack via Search Engines.

Nowadays, due to the increasing user requirements of efficient and personalized services, a perfect travel plan is urgently needed. However, at present it is hard for people to make a personalized traveling plan. Most of them follow other people's general travel trajectory. So only after finishing their travel, do they know which scene is their favorite, which is not, and what is the perfect order of visits. In this research we propose a novel spatio-temporal sequence (STS) searching, which mainly includes two steps.

No abstract available.

Flash disks are being widely used as an important alternative to conventional magnetic disks, although accessed through the same interface by applications, their distinguished feature, i.e., different read and write cost in the aspects of time, makes it necessary to reconsider the design of existing replacement algorithms to leverage their performance potential. Different from existing flash-aware buffer replacement policies that focus on the asymmetry of read and write operations, we address the “discrepancy” of the asymmetry for different flash disks, which is the fact that exists for a long time, while has drawn little attention by researchers since most existing flash-aware buffer replacement polices are somewhat based on the assumption that the cost of read operation is neglectable compared with that of write operation. In fact, this is not true for current flash disks on the market. We propose an adaptive cost-aware replacement policy (ACR) that uses three cost-based heuristics to select the victim page, thus can fairly make trade off between clean pages (their content remain unchanged) and dirty pages (their content is modified), and hence, can work well for different type of flash disks of large discrepancy. Further, in ACR, buffer pages are divided into clean list and dirty list, the newly entered pages will not be inserted at the MRU position of either list, but at some position in the middle, thus the once-requested pages can be flushed out from the buffer quickly and the frequently-requested pages can stay in buffer for a longer time. Such mechanism makes ACR adaptive to workloads of different access patterns. The experimental results on different traces and flash disks show that ACR not only adaptively tunes itself to workloads of different access patterns, but also works well for different kind of flash disks compared with existing methods.

Solid State Drive (SSD), as new data storage media with low power consumption, high shock resistance and lightweight form, has been widely used in laptops during the past several years. The most attractive characteristic of SSD is its high random read speed because of no mechanical latency. However, poor random write performance becomes the bottle neck in wider applications. Random write is almost two orders of magnitude slower than both random read and sequential access. In our database prototype based on Oracle Berkeley DB (BDB), we propose to insert unmodified data into random write sequence in order to convert random writes into sequential writes, and then data sequence can be flushed at the speed of sequential write. Further, we optimize the write performance by reducing quantity of unmodified data to be inserted. In this demo, we visualize the progress and results when a write sequence is run on three database system. Besides this, we can select three kinds of benchmarks to run. After getting runtime of one benchmark on three database systems, we can replay their run progress in the same time. In this way, we can intuitively show the high performance of our database system.

Relocation in personal desktop resources is an interesting and promising research topic. This demonstration illustrates a new perspective in exploring desktop resources to help users re-find expected data resources more effectively. Different from existing works, our prototype OrientSpace has two features: automatically extract and maintain user tasks to support task-based exploration, and support vague search by exploiting associations between desktop resources.

Deep Web contents are accessed by queries submitted to Web databases and the returned data records are enwrapped in dynamically generated Web pages (they will be called deep Web pages in this paper). Extracting structured data from deep Web pages is a challenging problem due to the underlying intricate structures of such pages. Until now, a large number of techniques have been proposed to address this problem, but all of them have inherent limitations because they are Web-page-programming-language-dependent. As the popular two-dimensional media, the contents on Web pages are always displayed regularly for users to browse. This motivates us to seek a different way for deep Web data extraction to overcome the limitations of previous works by utilizing some interesting common visual features on the deep Web pages. In this paper, a novel vision-based approach that is Web-page-programming-language-independent is proposed. This approach primarily utilizes the visual features on the deep Web pages to implement deep Web data extraction, including data record extraction and data item extraction. We also propose a new evaluation measure revision to capture the amount of human effort needed to produce perfect extraction. Our experiments on a large set of Web databases show that the proposed vision-based approach is highly effective for deep Web data extraction.

Solid State Drive (SSD), emerging as new data storage media with high random read speed, has been widely used in laptops, desktops, and data servers to replace hard disk during the past few years. However, poor random write performance becomes the bottle neck in practice. In this paper, we propose to insert unmodified data into random write sequence in order to convert random writes into sequential writes, and thus data sequence can be flushed at the speed of sequential write. Further, we propose a clustering strategy to improve the performance by reducing quantity of unmodified data to read. After exploring the intrinsic parallelism of SSD, we also propose to flush write sequences with the help of the simultaneous program between planes and parallel program between devices for the first time. Comprehensive experiments show that our method outperform the existing random-write solution up to one order of magnitude improvement.

Many users need to refer to content in existing files (pictures, tables, emails, web pages and etc.) when they write doc-uments(programs, presentations, proposals and etc.), and often need to revisit these referenced files for review, re-vision or reconfirmation. Therefore it is meaningful to dis-cover an approach to help users revisit these references effec-tively. Traditional approaches(file explorer, desktop search, and etc.) fail to work in this case. In this paper, we propose an efficient solution for this problem. We firstly define a new personal data relationship: Context-based Reference(CR), which is generated by user behaviors. We also propose ef-ficient methods to identify CR relationship and present a new type of query based on it: Context-based Query(C-Query), which helps users efficiently revisit personal docu-ments based on CR relationship. Our experiments validate the effectiveness and efficiency of our methods.

We study the problem of approximate membership extraction (AME), i.e., how to efficiently extract substrings in a text document that approximately match some strings in a given dictionary. This problem is important in a variety of applications such as named entity recognition and data cleaning. We solve this problem in two steps. In the first step, for each substring in the text, we filter away the strings in the dictionary that are very different from the substring. In the second step, each candidate string is verified to decide whether the substring should be extracted. We develop an incremental algorithm using signature-based inverted lists to minimize the duplicate list-scan operations of overlapping windows in the text. Our experimental study of the proposed algorithms on real and synthetic datasets showed that our solutions significantly outperform existing methods in the literature.

This is the first workshop in CIKM conference that addresses the challenge of large data management based on cloud computing infrastructure. This workshop will bring together researchers and practitioners in cloud computing and data-intensive system design, programming, parallel algorithms, data management, scientific applications, and information-based applications to maximize performance, minimize cost and improve the scale of their endeavors.

NAND Flash has become the most popular stable storage medium for embedded systems. As on-board storage capacity increases, the need for efficient indexing techniques arises. Such techniques are very challenging to design due to a combination of NAND Flash constraints (for example the block-erase-before-page-rewrite constraint and limited number of erase cycles) and embedded system constraints (for example tiny RAM and resource consumption predictability). Previous work adapted traditional indexing methods to cope with Flash constraints by deferring index updates using a log and batching them to decrease the number of rewrite operations in Flash memory. However, these methods were not designed with embedded system constraints in mind and do not address them. In this paper, we propose a new alternative for indexing Flash-resident data that specifically addresses the embedded context. This approach, called PBFilter, organizes the index structure in a purely sequential way. Key lookups are sped up thanks to two principles called Summarization and Partitioning. We instantiate these principles with data structures and algorithms based on Bloom Filters and show the effectiveness of this approach through a comprehensive performance study.

Privacy preservation has recently received considerable attention for location-based mobile services. Various location cloaking approaches have been proposed to protect the location privacy of mobile users. However, existing cloaking approaches are ill-suited for continuous queries. In view of the privacy disclosure and poor QoS (Quality of Service) under continuous query anonymization, in this paper, we propose a δp-privacy model and a δq-distortion model to balance the tradeoff between user privacy and QoS. Furthermore, two incremental utility-based cloaking algorithms --- bottom-up cloaking and hybrid cloaking, are proposed to anonymize continuous queries. Experimental results validate the efficiency and effectiveness of the proposed algorithms.

Location update strategy is one of the most important factors that affect the performance of moving objects databases. However, current motion vector based location tracking methods are designed for regular movements and are thus not suitable for transportation networks with changeful traffic conditions. To solve this problem, we propose a new location update mechanism, Adaptive Network-constrained moving object Location Update Mechanism (ANLUM), in this paper. In ANLUM, the moving object can switch between different location tracking policies according to difference traffic conditions, so that the overall performance can be improved. To evaluate the performance of the proposed method, an experimental system is implemented and the results show that ANLUM can effectively reduce the communication costs with location tracking accuracy guaranteed in traffic jammed transportation networks.

Privacy preservation has recently received considerable attention for location-based mobile services. In this paper, we present location-dependent attack resulting from continuous and dependent location updates and propose an incremental clique-based cloaking algorithm, called ICliqueCloak, to defend against location-dependent attack. The main idea is to incrementally maintain maximal cliques for location cloaking in an un-directed graph that takes into consideration the effect of continuous location updates.

NAND Flash has become the most popular persistent data storage medium for mobile and embedded devices. The hardware characteristics of NAND Flash (e.g. page granularity for read/write with a block-erase-before-rewrite constraint, limited number of erase cycles) preclude in-place updates. In this paper, we propose a new indexing scheme, called PBFilter, designed from the outset to exploit the peculiarities of NAND Flash.

Database outsourcing becomes increasingly attractive as ad-vances in network technologies eliminate the perceived per-formance difference between in-house databases and out-sourced databases, and price advantages of third-party data-base service providers continue to increase due to economy of scale. However, the potentially explosive growth of database outsourcing is hampered by security concerns, namely data privacy and query integrity of outsourced databases. While privacy issues of outsourced databases have been extensively studied, query integrity for outsourced databases has just started to draw attention from the database community. Currently, there still does not exist a solution that can pro-vide complete integrity. In particular, previous studies have not examined the mechanisms for providing freshness guar-antees, that is, the assurance that queries are executed again-st the most up-to-date data, instead of just some version of the data in the past. Providing a practical solution for fresh-ness guarantees is challenging because continuously moni-toring data’s up-to-dateness is expensive. In this paper, we perform a thorough study on how to add freshness guaran-tees over proposed schemes (including authenticated data structure-based and probabilistic-based approaches) to pro-vide integrity assurance. We implement our solutions and perform extensive experiments to quantify the cost. Our ex-periment results show that we can provide reasonable tight freshness guarantees without sacrificing much performance. 1.

Compared with traditional magnetic disks, flash memory has many advantages and has been used as external storage media for a wide spectrum of electronic devices (such as PDA, MP3, digital camera and mobile phone). As the capacity increases and price drops, it looks like a perfect alternative for magnetic disks. However, due to hardware limitations of flash memory, techniques including storage subsystem and indexing originally designed for magnetic disks can not run smoothly in a flash memory without any modification. In this paper we explore problems of indexing flash-resided data and present a new dynamical hash index for flash memory in two schemas. The analysis and experimental results validate the efficiency of our design.

As a de facto standard for information representation and exchange over the Internet, XML has been used extensively in many applications. And XML query technology has attracted more and more attention in data management research community. Standard XML query languages, e.g. XPath and XQuery, use twig pattern as a basic unit to match relevant fragments from a given XML document. However, in most existing work, only simple containment relationships are involved in the twig pattern, which makes it infeasible in many cases. In this paper, we extend the original twig pattern to complex twig pattern (CTP), which may contain ordered relationship between query nodes. We give a detailed analysis of the hard nuts that prevent us from finding an efficient solution for CTP matching, and then propose a novel holistic join algorithm, LBHJ, to handle the CTP efficiently and effectively. We show in experimental results that LBHJ can largely reduce the size of intermediate results and thus improve the query performance significantly according to various metrics when processing CTP with ordered axes.

Advances in wireless sensor networks and positioning technologies enable traffic management (e.g. routing traffic) that uses real-time data monitored by GPS-enabled cars. Location management has become an enabling technology in such application. The location modeling and trajectory prediction of moving objects are the fundamental components of location management in mobile locationaware applications. In this paper, we model the road network and moving objects in a graph of cellular automata (GCA), which makes full use of the constraints of the network and the stochastic behavior of the traffic. A simulation-based method based on graphs of cellular automata is proposed to predict future trajectories. Our technique strongly differs from the linear prediction method, which has low prediction accuracy and requires frequent updates when applied to real traffic with velocity changes. The experiments, carried on two different datasets, show that the simulation-based prediction method provides higher accuracy than the linear prediction method.

Sequence-based XML indexing aims at avoiding expensive join operations in query processing. It transforms structured XML data into sequences so that a structured query can be answered holistically through subsequence matching. In this paper, we address the problem of query equivalence with respect to this transformation, and we introduce a performance-oriented principle for sequencing tree structures. With query equivalence, XML queries can be performed through subsequence matching without join operations, post-processing, or other special handling for problems such as false alarms. We identify a class of sequencing methods for this purpose, and we present a novel subsequence matching algorithm that observe query equivalence. Still, query equivalence is just a prerequisite for sequence-based XML indexing. Our goal is to find the best sequencing strategy with regard to the time and space complexity in indexing and querying XML data. To this end, we introduce a performance-oriented principle to guide the sequencing of tree structures. For any given XML data set, the principle finds an optimal sequencing strategy according to its schema and its data distribution. We present a novel method that realizes this principle. In our experiments, we show the advantages of sequence-based indexing over traditional XML indexing methods, and we compare several sequencing strategies and demonstrate the benefit of the performance-oriented sequencing principle.

Given a tree-pattern query, most XML indexing approaches decompose it into multiple sub-queries, and then join their results to provide the answer to the original query. Join operations have been identified as the most time-consuming component in XML query processing. XSeq is a powerful XML indexing infrastructure which makes tree patterns a first class citizen in XML query processing. Unlike most indexing methods that directly manipulate tree structures, XSeq builds its indexing infrastructure on a much simpler data model: sequences. That is, we represent both XML data and XML queries by structure-encoded sequences. We have shown that this new data representation preserves query equivalence, and more importantly, through subsequence matching, structured queries can be answered directly without resorting to expensive join operations. Moreover, the XSeq infrastructure unifies indices on both the content and the structure of XML documents, hence it achieves an additional performance advantage over methods indexing either just content or structure, or indexing them separately.

Recently, more research has been conducted on moving object databases (MOD). Typically, there are three kinds of data for dynamic attributes in MOD, i.e., historical, current and future. Although many index structures have been developed for the former two types of data, there is not much work to deal with the future data. In particular, the problem of index update has not been addressed with efficient methods. This paper proposes a novel spatio-temporal index based on PMR quadtree, which is called Future Trajectory Quadtree (FT-Quadtree). FT-Quadtree adopts a trajectory segment shared structure and depicts an efficient update algorithm. The performance studies have shown that FT-Quadtree has superiority to the traditional one in index maintenance.

We propose a novel schema-guided approach for wrapper maintenance, called SG-WRAM. SG-WRAP can generate a wrapper to extract data from an HTML document to produce an XML document conforming to the user-defined schema. Based on these observations, we fulfill the maintenance following four sequential steps. At first, syntactic features, data pattern and notation are obtained from the schema, previous rule and extracted results, and then they are used to recognize the data items. After that, they are grouped according to the given schema. Each group is an instance of the given schema. At last, the representative instances are selected to re-induce the extraction rule. We name these four steps as features discovery, item recovery, block configuration and wrapper reparation respectively. The system to be demonstrated is implemented in Java. We also consider the major algorithms used in SG-WRAM.

Although wrapper generation work has been reported in the literature, there seem no standard ways to evaluate the performance of such systems. We conducted a series of experiments to evaluate the usability, correctness and efficiency of SG-WRAP. The usability tests selected a number of users to use the system. The results indicated that, with minimal introduction of the system, DTD definition and structure of HTML pages, even naive users could quickly generate wrappers without much difficulty. For correctness, we adapted the precision and recall metrics in information retrieval to data extraction. The results show that, with the refining process, the system can generate wrappers with very high accuracy. Finally, the efficiency tests indicated that the wrapper generation process is fast enough even with large size Web pages.

Replication is one of the key technologies in promoting the performance of mobile database systems. In this paper, a novel mobile database replication scheme, the transaction-level result-set propagation (TLRSP) model, is put forward. A conflict detection and resolution strategy based on TLRSP is discussed in detail and its implementation algorithm is proposed. In the TLRSP model, mobile users are allowed to access local replicas of the database and to submit local transactions when the system is disconnected. The locally committed transactions are sent to a fixed database server for conflict reconciliation and result-set incorporation when the system is reconnected. The TLRSP model uses the incremental refreshing method to synchronize database replicas and to maintain the consistency of the replicated mobile database system.