Retrieval-Augmented Generation (RAG) systems can amplify political bias from underlying web corpora. To empirically demonstrate this amplification, we first analyze 16,254 documents from the C4 dataset and 24,300 LLM-generated responses, revealing significant left-leaning and supportive stance bias that can propagate strongly from retrieval to generation. To mitigate this amplification of political bias, we propose FAIR-RAG, an end-to-end framework integrating (1) multi-LLM persona-based annotation, (2) a vector database with political-stance metadata, and (3) a multi-stage fairness engine designed for each of the three stages in RAG systems. FAIR-RAG achieves Attention Weighted Rank Fairness of 97.51 (82.1% improvement) and Perspective Balance of 51.01/82.37 (average 5.6% improvement over state-of-the-art) while maintaining high output quality (Context Precision: 0.974/0.975, Faithfulness: 0.994/0.996). Ablation studies confirm that all three components must operate collaboratively for optimal bias mitigation. This work provides a foundational framework for developing trustworthy and equitable AI information systems. All source code and experimental scripts are publicly available at: https://github.com/bigbases/FAIR-RAG.

Search engine personalization, while enhancing user satisfaction, can lead to information disparities. Previous studies on this topic face limitations, such as the absence of context-aware data collection, superficial URL-level analysis, and human-dependent annotations. We propose FAIR-SE, a Framework for Analyzing Information dispaRities in Search Engines that addresses these challenges through AWS Lambda-based concurrent data collection and LLM-generated persona-based content analysis. We collected search results across four user contexts (Search History, Geo-location, Language Preference, and Access Environment) and analyzed them through four analytical perspectives (Political Leaning, Topic-specific Stance, Subjectivity, and Bias). Experiments conducted on two globally prominent search engines across nine controversial topics demonstrate the efficacy of FAIR-SE regarding benchmark accuracy, persona consistency, and ability to reflect real-world discourse patterns across diverse topics. Our statistical analysis identifies distinct search engine characteristics and demonstrates significant information disparities in our case studies examining regional disparities in search results. Our code and datasets are publicly available at: https://github.com/bigbases/FAIR-SE.

Graph representation learning (GRL) aims to map a graph into a low-dimensional vector space while preserving graph topology and node properties. This study proposes a novel GRL model, Multi-Level GRL (simply, ML-GRL), that recursively partitions input graphs by selecting the most appropriate community detection algorithm at each graph or partitioned subgraph. To preserve the relationship between subgraphs, ML-GRL incorporates global graphs that effectively maintain the overall topology. ML-GRL employs a prediction model, which is pre-trained using graph-based features and covers a wide range of graph distributions, to estimate GRL accuracy of each community detection algorithm without partitioning graphs or subgraphs and evaluating them. ML-GRL improves learning accuracy by selecting the most effective community detection algorithm while enhancing learning efficiency from parallel processing of partitioned subgraphs. Through extensive experiments with two different tasks, we demonstrate ML-GRL's superiority over the six representative GRL models in terms of both learning accuracy and efficiency. Specifically, ML-GRL not only improves the accuracy of existing GRL models by 3.68 ~ 47.59% for link prediction and 1.75 ~ 40.90% for node classification but also significantly reduces their running time by 9.63 ~ 62.71% and 7.14 ~ 82.14%, respectively. Our source code is available at https://github.com/pnpy6elp/Multi_Level_GRL.

In this study, we propose a novel graph representation learning (GRL) model, called Two-Level GRL with Subgraph-as-a-Node (SaaN 2L-GRL in short), that partitions input graphs into smaller subgraphs for effective and scalable GRL in two levels: 1) local GRL and 2) global GRL. To realize the two-level GRL in an efficient manner, we propose an abstracted graph, called Subgraph-as-a-Node Graph (SaaN in short), to effectively maintain the high-level graph topology while significantly reducing the size of the graph. By applying the SaaN graph to both local and global GRL, SaaN 2L-GRL can effectively preserve the overall structure of the entire graph while precisely representing the nodes within each subgraph. Through time complexity analysis, we confirm that SaaN 2L-GRL significantly reduces the learning time of existing GRL models by using the SaaN graph for global GRL, instead of using the original graph, and processing local GRL on subgraphs in parallel. Our extensive experiments show that SaaN 2L-GRL outperforms existing GRL models in both accuracy and efficiency. In addition, we show the effectiveness of SaaN 2L-GRL using diverse kinds of graph partitioning methods, including five community detection algorithms and representative edge- and vertex-cut algorithms.

In this paper, we propose a novel graph representation learning (GRL) model that aims to improve both representation accuracy and learning efficiency. We design a Two-Level GRL architecture based on the graph partitioning: 1) local GRL on nodes within each partitioned subgraph and 2) global GRL on subgraphs. By partitioning the graph through community detection, we enable elaborate node learning in the same community. Based on Two-Level GRL, we introduce an abstracted graph, Community-as-a-Node Graph(CaaN), to effectively maintain the high-level structure with a significantly reduced graph. By applying the CaaN graph to local and global GRL, we propose Two-Level GRL with Community-as-a-Node (CaaN 2L) that effectively maintains the global structure of the entire graph while accurately representing the nodes in each community. A salient point of the proposed model is that it can be applied to any existing GRL model by adopting it as the base model for local and global GRL. Through extensive experiments employing seven popular GRL models, we show that our model outperforms them in both accuracy and efficiency.

Third-generation DNA sequencing technologies such as single-molecule real-time sequencing (SMRT) and nanopore sequencing have the potential to fill the gaps in the existing genome databases since the raw sequences produced by these machines are much longer than those of previous generations and therefore result in more contiguous assemblies. However, these long reads have a high error rate, which makes the assembly process computationally challenging. Moreover, since existing long-read assemblers are designed to run on a single machine, they either take days to complete or run out of memory on even moderate-sized datasets. In this paper, we present a distributed long-read assembler that can assemble large-scale noisy sequence datasets on thousands of cores, resulting in orders of magnitude faster assembly times. By effectively using the map-reduce computation model with a distributed hash-map, both built using a high-performance active messaging middleware, we can assemble a PacBio human genome dataset with 139 billion base-pairs (about 130 GB) in about 33 minutes (using 2,560 cores) compared to more than 38 hours (using 28 cores) with the current state-of-the-art assembler.

Recent studies have shown that graph mining models are vulnerable to adversarial attacks. This paper proposes a robust meta network embedding framework, RoMNE, which improves the robustness of multiple network embedding on adversarial noisy networks while preserving the utility on original clean ones. First, we propose a generic meta learning based multiple network embedding model that can quickly adapt it to new embedding tasks on a variety of network data with only a small number of parameter and training updates. Second, Gumbel estimator and Gaussian smoothing techniques are introduced to implement differentiable approximation for optimizing non-differential objective of effective adversarial attacks. Last but not least, the adversarial attack and defense models are integrated into a dynamic adversarial training model. The competition of two models helps the latter be robust to adversarial attacks.

The advent of social networks and activity networks affords us an opportunity of utilizing explicit social information and activity information to improve the quality of recommendation in the presence of data sparsity. In this article, we present a social-influence-based collaborative filtering (SICF) framework over heterogeneous information networks with three unique features. First, we integrate different types of entities, links, attributes, and activities from rating networks, social networks, and activity networks into a unified social-influence-based collaborative filtering model through the intra-network and inter-network social influence. Second, we propose three social-influence propagation models to capture three kinds of information propagation within heterogeneous information networks: user-based influence propagation on user rating networks, item-based influence propagation on user-rating activity networks, and term-based influence propagation on user-review activity networks, respectively. We compute three kinds of social-influence-based user similarity scores based on three social-influence propagation models, respectively. Third, a unified social-influence-based CF prediction model is proposed to infer rating tastes by incorporating three kinds of social-influence-based similarity measures with different weighting factors. We design a weight-learning algorithm, SICF, to refine the prediction result by quantifying the contribution of each kind of information propagation to make a good balance between prediction accuracy and data sparsity. Extensive evaluation on real datasets demonstrates that SICF outperforms existing representative collaborative filtering methods.

As one of the fundamental tasks in data analytics, Influence Maximization methods have been widely used in many real-world applications. For instance, in social network analysis, after building a directed graph, where edges are weighted with influence probabilities, influence maximization methods can be used to find a set of users who can maximize the spread of information under certain cascade models. Despite their successes, however, one critical weakness of existing influence maximization methods lies in the fact that edges are weighted with historical probabilities. As such, influence maximization methods perform sub-optimal if there occur non-trivial changes in future. In response to this challenge, in this work, we propose a novel prediction-driven influence maximization method that accurately predicts future influence probabilities using graph convolutional networks and find seed users based on the predicted probabilities. The experiments with five real-world datasets show that our prediction accuracy is accurate (e.g., mean absolute percentage error less than 0.1) in many cases, and our prediction-driven influence maximization is very close to the optimal.

Online social networks are being widely used during unexpected large-scale disasters not only for sharing latest news but also requesting emergency rescues. Particularly, social network posts with their location information are becoming more important because they can be utilized for emergency management, urban planning, and various studies to understand effects of the disasters. Despite their importance, the percentage of such posts is generally tiny. In this paper, to address the location sparsity problem on Twitter in the event of disasters, we propose a deep learning-based framework to spatially analyze the disaster-related tweets by focusing on classifying tweets from affected areas of disasters. We also study effects of different deep learning architectures and input embedding techniques for this classification task. Our experimental results demonstrate that our ConvNet model with the Word2vec word embedding has the highest classification accuracy.

With the widespread use of GPS-equipped smartphones and Internet of Things devices, a huge amount of data with location information is being generated at an unprecedented rate. To gain a deeper insight into such a plethora of spatial data, scientists and engineers are widely using spatial queries for their big data applications. However, because of not only the massive spatial data size but also the complexity of spatial query processing, they are struggling to efficiently process the spatial queries. In this paper, we propose lightweight and scalable indexing and querying services for big spatial data stored in distributed storage systems or graph-based systems. Our spatial services have several advantages over existing approaches. First, our services can be easily applied to existing storage systems or graph-based models without modifying the internal implementation of existing systems/models. Second, our services achieve high pruning power by efficiently selecting only relevant spatial objects based on a simple yet effective filter. Third, our services support a customizable and easy-to-use control of index data size by adjusting the precision of indexed geometries. Lastly, our services support efficient updates of spatial data. Our experimental results using real-world datasets validate the effectiveness and efficiency of our spatial services.

While location-based services and applications are increasing in popularity, there are growing concerns over users' location privacy. Although there exist general purpose mobile permission systems and cloaking techniques, these techniques suffer from several problems when applied to continuous location and GPS access, as they are often rigid, coarse-grained, not sufficiently personalizable, and unaware of road network semantics. This paper proposes PrivacyZone, a novel system for constructing personalized fine-grained privacy quarantine regions and protecting users' privacy within these regions. PrivacyZone allows users to seamlessly enter their privacy specifications under spatial, temporal, and semantic customization. Novel challenges arise from having to enforce privacy zones for large volume and variety of users with frequent location updates. We show that naive privacy zone processing techniques are inefficient and cause excessive energy consumption. We therefore develop advanced processing techniques based on the concept of safe hibernation. We empirically evaluate our techniques to demonstrate their trade-offs with respect to hibernation time, computation effort, and network bandwidth usage. Our results show that PrivacyZone is efficient, scalable, and flexible, while preserving users' location privacy.

Recent advances in big data and deep learning technologies have enabled researchers across many disciplines to gain new insight into large and complex data. For example, deep neural networks are being widely used to analyze various types of data including images, videos, texts, and time-series data. In another example, various disciplines such as sociology, social work, and criminology are analyzing crowd-sourced and online social network data using big data technologies to gain new insight from a plethora of data. Even though many different types of data are being generated and analyzed in various domains, the development of distributed city-level cyberinfrastructure for effectively integrating such data to generate more value and gain insights is still not well-addressed in the research literature. In this paper, we present our current efforts and ultimate vision to build distributed cyberinfrastructure which integrates big data and deep learning technologies with a variety of data for enhancing public safety and livability in cites. We also introduce several methodologies and applications that we are developing on top of the cyberinfrastructure to support diverse community stakeholders in cities.

Spurred by a widening gap between hardware accelerators and traditional processors, numerous bioinformatics applications have harnessed the computing power of GPUs and reported substantial performance improvements compared to their CPU-based counterparts. However, most of these GPU-based applications only focus on the read alignment problem, while the field of de novo assembly still relies mostly on CPU-based solutions. This is primarily due to the nature of the assembly workload which is not only compute-intensive but also extremely data-intensive. Such workloads require large memories, making it difficult to adapt them to use GPUs with their limited memory capacities. To the best of our knowledge, no GPU-based assembler reported in the recent literature has attempted to assemble datasets larger than a few tens of gigabytes, whereas real sequence datasets are often several hundreds of gigabytes in size. In this paper, we present a new GPU-accelerated genome assembler called LaSAGNA, which can assemble large-scale sequence datasets using a single GPU by building string graphs from approximate all-pair overlaps. LaSAGNA can also run on multiple GPUs across multiple compute nodes connected by a high-speed network to expedite the assembly process. To utilize the limited memory on GPUs efficiently, LaSAGNA uses a semi-streaming approach that makes at most a logarithmic number of passes over the input data based on the available memory. Moreover, we propose a two-level streaming model, from disk to host memory and from host memory to device memory, to minimize disk I/O. Using LaSAGNA, we can assemble a 400 GB human genome dataset on a single NVIDIA K40 GPU in 17 hours, and in a little over 5 hours on an 8-node cluster of NVIDIA K20s.

Researches affirm that coflow scheduling/routing substantially shortens the average application inner communication time in data center networks(DCNs). The commonly desirable critical features of existing coflow scheduling/routing framework includes (1) coflow scheduling, (2) coflow routing, and (3) per-flow rate-limiting. However, to provide the 3 features, existing frameworks require customized computing frameworks, customized operating systems, or specific external commercial monitoring frameworks on software-defined networking(SDN) switches. These requirements defer or even prohibit the deployment of coflow scheduling/routing in production DCNs. In this paper, we design a coflow scheduling and routing framework, MinCOF which has minimal requirements on hosts and switches for cloud storage area networks(SANs) based on OpenFlow SDN. MinCOF accommodates all critical features of coflow scheduling/routing from previous works. The deployability in production environment is especially taken into consideration. The OpenFlow architecture is capable of processing the traffic load in a cloud SAN. Not necessary requirements for hosts from existing frameworks are migrated to the mature commodity OpenFlow 1.3 Switch and our coflow scheduler. Transfer applications on hosts only need slight enhancements on their existing connection establishment and progress reporting functions. Evaluations reveal that MinCOF decreases the average coflow completion time (CCT) by 12.94% compared to the latest OpenFlow-based coflow scheduling and routing framework.

High-performance analysis of big data demands more computing resources, forcing similar growth in computation cost. So, the challenge to the HPC system designers is providing not only high performance but also high performance at lower cost. For high performance yet cost effective cyberinfrastructure, we propose a new system model augmenting Amdahl's second law for balanced system to optimize price-performance-ratio. We express the optimal balance among CPU-speed, I/O-bandwidth and DRAM-size (i.e., Amdahl's I/O-and memory-number) in terms of application characteristics and hardware cost. Considering Xeon processor and recent hardware prices, we showed that a system needs almost 0.17GBPS I/O-bandwidth and 3GB DRAM per GHz CPU-speed to minimize the price-performance-ratio for data-and compute-intensive applications. To substantiate our claim, we evaluate three different cluster architectures: 1) SupermikeII, a traditional HPC cluster, 2) SwatIII, a regular datacenter, and 3) CeresII, a MicroBrick-based novel hyperscale system. CeresII with 6-Xeon-D1541 cores (2GHz/core), 1-NVMe SSD (2GBPS I/O-bandwidth) and 64GB DRAM per node, closely resembles the optimum produced by our model. Consequently, in terms of price-performance-ratio CeresII outperformed both SupermikeII (by 65-85%) and SwatIII (by 40-50%) for data-and compute-intensive Hadoop benchmarks (TeraSort and WordCount) and our own benchmark genome assembler based on Hadoop and Giraph.

Recent advances in deep learning have enabled researchers across many disciplines to uncover new insights about large datasets. Deep neural networks have shown applicability to image, time-series, textual, and other data, all of which are available in a plethora of research fields. However, their computational complexity and large memory overhead requires advanced software and hardware technologies to train neural networks in a reasonable amount of time. To make this possible, there has been an influx in development of deep learning software that aim to leverage advanced hardware resources. In order to better understand the performance implications of deep learning frameworks over these different resources, we analyze the performance of three different frameworks, Caffe, TensorFlow, and Apache SINGA, over several hardware environments. This includes scaling up and out with single-and multi-node setups using different CPU and GPU technologies. Notably, we investigate the performance characteristics of NVIDIA's state-of-the-art hardware technology, NVLink, and also Intel's Knights Landing, the most advanced Intel product for deep learning, with respect to training time and utilization. To our best knowledge, this is the first work concerning deep learning bench-marking with NVLink and Knights Landing. Through these experiments, we provide analysis of the frameworks' performance over different hardware environments in terms of speed and scaling. As a result of this work, better insight is given towards both using and developing deep learning tools that cater to current and upcoming hardware technologies.

Genome sequencing technology has witnessed tremendous progress in terms of throughput as well as cost per base pair, resulting in an explosion in the size of data. Consequently, typical sequence assembly tools demand a lot of processing power and memory and are unable to assemble big datasets unless run on hundreds of nodes. In this paper, we present a distributed assembler that achieves both scalability and memory efficiency by using partitioned de Bruijn graphs. By enhancing the memory-to-disk swapping and reducing the network communication in the cluster, we can assemble large sequences such as human genomes (452 GB) on just two nodes in 14.5 hours, and also scale up to 128 nodes in 23 minutes. We also assemble a synthetic wheat genome with 1.1 TB of raw reads on 8 nodes in 18.5 hours and on 128 nodes in 1.25 hours.

Road network-aware spatial alarms extend the concept of time-based alarms to spatial dimension and remind us when we travel on spatially constrained road networks and enter some predefined locations of interest in the future. This paper argues that road network-aware spatial alarms need to be processed by taking into account spatial constraints on road networks and mobility patterns of mobile subscribers. We show that the Euclidian distance-based spatial alarm processing techniques tend to incur high client energy consumption due to unnecessarily frequent client wakeups. We design and develop a road network-aware spatial alarm processing system, called ROADALARM, with three unique features. First, we introduce the concept of road network-based spatial alarms using road network distance measures. Instead of using a rectangular region, a road network-aware spatial alarm is a star-like subgraph with an alarm target as the center of the star and border points as the scope of the alarm region. Second, we describe a baseline approach for spatial alarm processing by exploiting two types of filters. We use subscription filter and Euclidean lower bound filter to reduce the amount of shortest path computations required in both computing alarm hibernation time and performing alarm checks at the server. Last but not the least, we develop a suite of optimization techniques using motion-aware filters, which enable us to further increase the hibernation time of mobile clients and reduce the frequency of wakeups and alarm checks, while ensuring high accuracy of spatial alarm processing. Our experimental results show that the road network-aware spatial alarm processing significantly outperforms existing Euclidean space-based approaches, in terms of both the number of wakeups and the hibernation time at mobile clients and the number of alarm checks at the server.

Iterative computation on large graphs has challenged system research from two aspects: (1) how to conduct high performance parallel processing for both in-memory and out-of-core graphs; and (2) how to handle large graphs that exceed the resource boundary of traditional systems by resource aware graph partitioning such that it is feasible to run large-scale graph analysis on a single PC. This paper presents GraphLego, a resource adaptive graph processing system with multi-level programmable graph parallel abstractions. GraphLego is novel in three aspects: (1) we argue that vertex-centric or edge-centric graph partitioning are ineffective for parallel processing of large graphs and we introduce three alternative graph parallel abstractions to enable a large graph to be partitioned at the granularity of subgraphs by slice, strip and dice based partitioning; (2) we use dice-based data placement algorithm to store a large graph on disk by minimizing non-sequential disk access and enabling more structured in-memory access; and (3) we dynamically determine the right level of graph parallel abstraction to maximize sequential access and minimize random access. GraphLego can run efficiently on different computers with diverse resource capacities and respond to different memory requirements by real-world graphs of different complexity. Extensive experiments show the competitiveness of GraphLego against existing representative graph processing systems, such as GraphChi, GraphLab and X-Stream.

Many popular web service networks are content-rich in terms of heterogeneous types of entities and links, associated with incomplete attributes. Clustering such heterogeneous service networks demands new clustering techniques that can handle two heterogeneity challenges: (1) multiple types of entities co-exist in the same service network with multiple attributes, and (2) links between entities have diverse types and carry different semantics. Existing heterogeneous graph clustering techniques tend to pick initial centroids uniformly at random, specify the number k of clusters in advance, and fix k during the clustering process. In this paper, we propose Service Cluster, a novel heterogeneous service network clustering algorithm with four unique features. First, we incorporate various types of entity, attribute and link information into a unified distance measure. Second, we design a Discrete Steepest Descent method to naturally produce initial k and initial centroids simultaneously. Third, we propose a dynamic learning method to automatically adjust the link weights towards clustering convergence. Fourth, we develop an effective optimization strategy to identify new suitable k and k well-chosen centroids at each clustering iteration. Extensive evaluation on real datasets demonstrates that Service Cluster outperforms existing representative methods in terms of both effectiveness and efficiency.

In recent years, systems researchers have devoted considerable effort to the study of large-scale graph processing. Existing distributed graph processing systems such as Pregel, based solely on distributed memory for their computations, fail to provide seamless scalability when the graph data and their intermediate computational results no longer fit into the memory; and most distributed approaches for iterative graph computations do not consider utilizing secondary storage a viable solution. This paper presents GraphMap, a distributed iterative graph computation framework that maximizes access locality and speeds up distributed iterative graph computations by effectively utilizing secondary storage. GraphMap has three salient features: (1) It distinguishes data states that are mutable during iterative computations from those that are read-only in all iterations to maximize sequential access and minimize random access. (2) It entails a two-level graph partitioning algorithm that enables balanced workloads and locality-optimized data placement. (3) It contains a proposed suite of locality-based optimizations that improve computational efficiency. Extensive experiments on several real-world graphs show that GraphMap outperforms existing distributed memory-based systems for various iterative graph algorithms.

Large-scale real-world graphs are known to have highly skewed vertex degree distribution and highly skewed edge weight distribution. Existing vertex-centric iterative graph computation models suffer from a number of serious problems: (1) poor performance of parallel execution due to inherent workload imbalance at vertex level; (2) inefficient CPU resource utilization due to short execution time for low-degree vertices compared to the cost of in-memory or on-disk vertex access; and (3) incapability of pruning insignificant vertices or edges to improve the computational performance. In this paper, we address the above technical challenges by designing and implementing a scalable, efficient, and provably correct two-tier graph parallel processing system, GraphTwist. At storage and access tier, GraphTwist maximizes parallel efficiency by employing three graph parallel abstractions for partitioning a big graph by slice, strip or dice based partitioning techniques. At computation tier, GraphTwist presents two utility-aware pruning strategies: slice pruning and cut pruning, to further improve the computational performance while preserving the computational utility defined by graph applications. Theoretic analysis is provided to quantitatively prove that iterative graph computations powered by utility-aware pruning techniques can achieve a very good approximation with bounds on the introduced error.

With more data generated and collected in a geographically distributed manner, combined by the increased computational requirements for large scale data-intensive analysis, we have witnessed the growing demand for geographically distributed Cloud datacenters and hybrid Cloud service provisioning, enabling organizations to support instantaneous demand of additional computational resources and to expand inhouse resources to maintain peak service demands by utilizing cloud resources. A key challenge for running applications in such a geographically distributed computing environment is how to efficiently schedule and perform analysis over data that is geographically distributed across multiple datacenters. In this paper, we first compare multi-datacenter Hadoop deployment with single-datacenter Hadoop deployment to identify the performance issues inherent in a geographically distributed cloud. A generalization of the problem characterization in the context of geographically distributed cloud datacenters is also provided with discussions on general optimization strategies. Then we describe the design and implementation of a suite of system-level optimizations for improving performance of Hadoop service provisioning in a geo-distributed cloud, including prediction-based job localization, configurable HDFS data placement, and data prefetching. Our experimental evaluation shows that our prediction based localization has very low error ratio, smaller than 5%, and our optimization can improve the execution time of Reduce phase by 48.6%.

Spatial queries are widely used in many data mining and analytics applications. However, a huge and growing size of spatial data makes it challenging to process the spatial queries efficiently. In this paper we present a lightweight and scalable spatial index for big data stored in distributed storage systems. Experimental results show the efficiency and effectiveness of our spatial indexing technique for different spatial queries.

In emerging information networks, having a privacy preserving index (or PPI) is critically important for locating information of interest for data sharing across autonomous providers while preserving privacy. An understudied problem for PPI techniques is how to provide controllable privacy preservation, given the innate difference of privacy concerns regarding different data owners. In this paper we present a personalized privacy preserving index, coined ε-PPI, which guarantees quantitative privacy preservation differentiated by personal identities. We devise a new common-identity attack that breaks existing PPI's and propose an identity-mixing protocol against the attack in ε-PPI. The proposed ε-PPI construction protocol is the first without any trusted third party and/or trust relationships between providers. We have implemented our ε-PPI construction protocol by using generic MPC techniques (secure multi-party computation) and optimized the performance to a practical level by minimizing the expensive MPC part.

The continued explosion of Twitter data has opened doors for many applications, such as location-based advertisement and entertainment using smartphones. Unfortunately, only about 0.58 percent of tweets are geo-tagged to date. To tackle the location sparseness problem, this paper presents a methodic

Large scale graph processing represents an interesting challenge due to the lack of locality. This paper presents Path Graph for improving iterative graph computation on graphs with billions of edges. Our system design has three unique features: First, we model a large graph using a collection of tree-based partitions and use an path-centric computation rather than vertex-centric or edge-centric computation. Our parallel computation model significantly improves the memory and disk locality for performing iterative computation algorithms. Second, we design a compact storage that further maximize sequential access and minimize random access on storage media. Third, we implement the path-centric computation model by using a scatter/gather programming model, which parallels the iterative computation at partition tree level and performs sequential updates for vertices in each partition tree. The experimental results show that the path-centric approach outperforms vertex centric and edge-centric systems on a number of graph algorithms for both in-memory and out-of-core graphs.

Big data business can leverage and benefit from the Clouds, the most optimized, shared, automated, and virtualized computing infrastructures. One of the important challenges in processing big data in the Clouds is how to effectively partition the big data to ensure efficient distributed processing of the data. In this paper we present a Scalable and yet customizable data PArtitioning framework, called SPA, for distributed processing of big RDF graph data. We choose big RDF datasets as our focus of the investigation for two reasons. First, the Linking Open Data cloud has put forwards a good number of big RDF datasets with tens of billions of triples and hundreds of millions of links. Second, such huge RDF graphs can easily overwhelm any single server due to the limited memory and CPU capacity and exceed the processing capacity of many conventional data processing software systems. Our data partitioning framework has two unique features. First, we introduce a suite of vertexcentric data partitioning building blocks to allow efficient and yet customizable partitioning of large heterogeneous RDF graph data. By efficient, we mean that the SPA data partitions can support fast processing of big data of different sizes and complexity. By customizable, we mean that the SPA partitions are adaptive to different query types. Second, we propose a selection of scalable techniques to distribute the building block partitions across a cluster of compute nodes in a manner that minimizes inter-node communication cost by localizing most of the queries on distributed partitions. We evaluate our data partitioning framework and algorithms through extensive experiments using both benchmark and real datasets. Our experimental results show that the SPA data partitioning framework is not only efficient for partitioning and distributing big RDF datasets of diverse sizes and structures but also effective for processing big data queries of different types and complexity.

A known problem for virtualized cloud data centers is the inter-VM communication inefficiency for data transfer between co-resident VMs. Several engineering efforts have been made on building a shared memory based channel between co-resident VMs. The implementations differ in terms of whether user/program transparency, OS kernel transparency or VMM transparency is supported. However, none of existing works has engaged in an in-depth measurement study with quantitative and qualitative analysis on performance improvements as well as tradeoffs introduced by such a residency-aware inter-VM communication mechanism. In this paper we present an extensive experimental study, aiming at addressing a number of fundamental issues and providing deeper insights regarding the design of a shared memory channel for co-resident VMs. Example questions include how much performance gains can a residency-aware shared memory inter-VM communication mechanism provide under different mixtures of local and remote network I/O workloads, what overhead will the residence-awareness detection and communication channel switch introduce over the remote inter-VM communication, what factors may exert significant impact on the throughput and latency performance of such a shared memory channel. We believe that this measurement study not only helps system developers to gain valuable lessons and generate new ideas to further improve the inter-VM communication performance. It also offers new opportunities for cloud service providers to deploy their services more efficiently and for cloud service consumers to improve the performance of their application systems running in the Cloud.

Spatial alarms are one of the fundamental functionalities for many LBSs. We argue that spatial alarms should be road network aware as mobile objects travel on spatially constrained road networks or walk paths. In this software system demonstration, we will present the first prototype system of ROADALARM - a spatial alarm processing system for moving objects on road networks. The demonstration system of ROAD-ALARM focuses on the three unique features of ROADALARM system design. First, we will show that the road network distance-based spatial alarm is best modeled using road network distance such as segment length-based and travel time-based distance. Thus, a road network spatial alarm is a star-like subgraph centered at the alarm target. Second, we will show the suite of ROADALARM optimization techniques to scale spatial alarm processing by taking into account spatial constraints on road networks and mobility patterns of mobile subscribers. Third, we will show that, by equipping the ROADALARM system with an activity monitoring-based control panel, we are able to enable the system administrator and the end users to visualize road network-based spatial alarms, mobility traces of moving objects and dynamically make selection or customization of the ROADALARM techniques for spatial alarm processing through graphical user interface. We show that the ROADALARM system provides both the general system architecture and the essential building blocks for location-based advertisements and location-based reminders.

We present MobiMix, a road network based mix-zone framework to protect location privacy of mobile users traveling on road networks. An alternative and complementary approach to spatial cloaking based location privacy protection is to break the continuity of location exposure by introducing techniques, such as mix-zones, where no applications can trace user movements. However, existing mixzone proposals fail to provide effective mix-zone construction and placement algorithms that are resilient to timing and transition attacks. In MobiMix, mix-zones are constructed and placed by carefully taking into consideration of multiple factors, such as the geometry of the zones, the statistical behavior of the user population, the spatial constraints on movement patterns of the users, and the temporal and spatial resolution of the location exposure. In this demonstration, we first introduce a visualization of the location privacy risks of mobile users traveling on road networks and show how mixzone based anonymization breaks the continuity of location exposure to protect user location privacy. We demonstrate a suite of road network mix-zone construction and placement methods that provide higher level of resilience to timing and transition attacks on road networks. We show the effectiveness of the MobiMix approach through detailed visualization using traces produced by GTMobiSim on different scales of geographic maps.

As the size and variety of information networks continue to grow in many scientific and engineering domains, we witness a growing demand for efficient processing of large heterogeneous graphs using a cluster of compute nodes in the Cloud. One open issue is how to effectively partition a large graph to process complex graph operations efficiently. In this paper, we present VB-Partitioner -- a distributed data partitioning model and algorithms for efficient processing of graph operations over large-scale graphs in the Cloud. Our VB-Partitioner has three salient features. First, it introduces vertex blocks (VBs) and extended vertex blocks (EVBs) as the building blocks for semantic partitioning of large graphs. Second, VB-Partitioner utilizes vertex block grouping algorithms to place those vertex blocks that have high correlation in graph structure into the same partition. Third, VB-Partitioner employs a VB-partition guided query partitioning model to speed up the parallel processing of graph pattern queries by reducing the amount of inter-partition query processing. We conduct extensive experiments on several real-world graphs with millions of vertices and billions of edges. Our results show that VB-Partitioner significantly outperforms the popular random block-based data partitioner in terms of query latency and scalability over large-scale graphs.

Massive volumes of big RDF data are growing beyond the performance capacity of conventional RDF data management systems operating on a single node. Applications using large RDF data demand efficient data partitioning solutions for supporting RDF data access on a cluster of compute nodes. In this paper we present a novel semantic hash partitioning approach and implement a Semantic HAsh Partitioning-Enabled distributed RDF data management system, called Shape. This paper makes three original contributions. First, the semantic hash partitioning approach we propose extends the simple hash partitioning method through direction-based triple groups and direction-based triple replications. The latter enhances the former by controlled data replication through intelligent utilization of data access locality, such that queries over big RDF graphs can be processed with zero or very small amount of inter-machine communication cost. Second, we generate locality-optimized query execution plans that are more efficient than popular multi-node RDF data management systems by effectively minimizing the inter-machine communication cost for query processing. Third but not the least, we provide a suite of locality-aware optimization techniques to further reduce the partition size and cut down on the inter-machine communication cost during distributed query processing. Experimental results show that our system scales well and can process big RDF datasets more efficiently than existing approaches.

State monitoring is widely used for detecting critical events and abnormalities of distributed systems. As the scale of such systems grows and the degree of workload consolidation increases in Cloud data centers, node failures and performance interferences, especially transient ones, become the norm rather than the exception. Hence, distributed state monitoring tasks are often exposed to impaired communication caused by such dynamics on different nodes. Unfortunately, existing distributed state monitoring approaches are often designed under the assumption of always-online distributed monitoring nodes and reliable inter-node communication. As a result, these approaches often produce misleading results which in turn introduce various problems to Cloud users who rely on state monitoring results to perform automatic management tasks such as auto-scaling. This paper introduces a new state monitoring approach that tackles this challenge by exposing and handling communication dynamics such as message delay and loss in Cloud monitoring environments. Our approach delivers two distinct features. First, it quantitatively estimates the accuracy of monitoring results to capture uncertainties introduced by messaging dynamics. This feature helps users to distinguish trustworthy monitoring results from ones heavily deviated from the truth, yet significantly improves monitoring utility compared with simple techniques that invalidate all monitoring results generated with the presence of messaging dynamics. Second, our approach also adapts to non-transient messaging issues by reconfiguring distributed monitoring algorithms to minimize monitoring errors. Our experimental results show that, even under severe message loss and delay, our approach consistently improves monitoring accuracy, and when applied to Cloud application auto-scaling, outperforms existing state monitoring techniques in terms of the ability to correctly trigger dynamic provisioning.

In this paper, we offer an in-depth IO characterization of the Android-based smartphone. We analyze the IO behaviors of a total of 14 Android applications from six different categories. We examine the correlations among seven IO attributes: originating application, file type, IO size, IO type (read/write), random/sequential, block semantics (Data/Metadata/Journal), and session type (buffered vs. synchronous IO). For the purposes of our study, we develop Mobile Storage Analyzer (MOST), a framework for collecting IO attributes across layers. Let us summarize our findings briefly. SQLite, which is the most popular tool for maintaining persistent data in Android, puts too much burden on the storage. For example, a single SQLite operation (update or insert) results in at least 11 write operations being sent to the storage. These are for creating short-lived files, updating database tables, and accessing EXT4 Journal. From the storage point of view, more than 50% of writes are for EXT4 Journal updating. Excluding Metadata and Journal accesses, 60-80% of the writes are random. More than 50% of the writes are synchronous. 4KB IO accounts for 70% of all writes. In the Android platform, each SQLite and EXT4 filesystem requires a great amount of effort to ensure reliability in supporting transactions and journaling, respectively. When they are combined, the results are rather dumb. The operations of SQLite and EXT4, when combined, generate unnecessarily excessive write operations to the NAND-based storage. This not only degrades IO performance but also significantly reduces the lifetime of the underlying NAND flash storage. The results of this study clearly suggest that SQLite, EXT4, and the underlying NAND-based storage need to be completely overhauled and vertically integrated so as to properly and effectively incorporate their respective characteristics.

Spatial alarm services are essential components of many location-based applications. One of the key technical challenges for supporting spatial alarms as a service is performance and scalability. This paper shows that the Euclidean distance-based spatial alarm processing techniques are inadequate for mobile users traveling on road networks due to the high overhead in terms of server load for alarm checks and the high energy consumption in terms of client wakeups. We design and develop RoadAlarm, a road network aware spatial alarm processing service, with three unique features. First, we introduce the concept of road network-based spatial alarms using road network distance measures and a set of metrics specialized for spatial alarm processing. Second, we develop the basic model for spatial alarm processing by exploiting two types of filters: subscription filter and Euclidean lower bound filter. Third and but not the least, we develop a suite of optimization techniques to further reduce the frequency of wakeups at mobile clients and the number of alarm checks at the alarm processing server, while ensuring high accuracy of spatial alarm processing. Our experimental results show that RoadAlarm outperforms existing Euclidean space-based approaches with high success rate (accuracy) and significantly increased hibernation time.

Mix-zones are recognized as an alternative and complementary approach to spatial cloaking based approach to location privacy protection. Mix-zones break the continuity of location exposure by ensuring that users' movements cannot be traced while they reside in a mix-zone. In this paper we provide an overview of various known attacks that make mix-zones on road networks vulnerable and illustrate a set of counter measures to make road network mix-zones attack resilient. Concretely, we categorize the vulnerabilities of road network mix-zones into two classes: one due to the road network characteristics and user mobility, and the other due to the temporal, spatial and semantic correlations of location queries. For instance, the timing information of users' entry and exit into a mix-zone provides information to launch a timing attack. The non-uniformity in the transitions taken at the road intersection may lead to transition attack. An example query correlation attack is the basic continual query (CQ) attacks, which attempt to break the anonymity of road network aware mix-zones by performing query correlation based inference. The CQ-timing attacks carry out inference attacks based on both query correlation and timing correlation, and the CQ-transition attacks execute inference attacks based on both query correlation and transition correlation. We study the factors that impact on the effectiveness of each of these attacks and evaluate the efficiency of the counter measures, such as non-rectangle mix-zones and delay tolerant mix-zones, through extensive experiments on traces produced by GTMobiSim at different scales of geographic maps.