Web 3.0, built on blockchain technology, prioritizes user privacy and autonomy, presenting new opportunities for financial systems while also complicating the regulation of illicit activities. In this study, we present a novel infrastructure named Pseudo Fine-tuning (PFT) that provides account matching services to combat financial crimes on account-based blockchains such as money laundering through coin-mixing services. The significance of PFT lies in overcoming the need for real labels to fine-tune language models for account matching, given the limited availability of labeled account pairs for the task. Specifically, our design involves (1) crafting pseudo-labeled pairs from transactions of an account across different periods, and (2) fine-tuning language models to distill knowledge from pseudo pairs, which is transferable to the target task. We provide an in-depth analysis to investigate the inherent knowledge acquired during the PFT process and the conditions conducive to its effectiveness. Comprehensive experiments on real-world datasets collected from coin-mixing services and ENS name services, corroborate that the framework delivers pronounced enhancements over state-of-the-art approaches. Our implementation is released at https://github.com/git-disl/PFT .

The dynamic nature of streaming data often introduces distribution shifts that challenge typical text classification models. This paper proposes an online learning framework tailored for streaming text classification under distribution shifts. First, we decompose a neural network-based text classification model into distinct modules and analyze the varying impact of updating these modules under different types of shifts. Based on this insight, we define three novel indicators to efficiently measure the extent of distribution shifts without evaluating the entire model. These indicators enable the development of predictive models that dynamically optimize module update strategies, balancing learning efficiency and accuracy in real-time. To the best of our knowledge, this is the first approach to systematically adapt model updates according to a trade-off between efficiency and accuracy in online text classification. Extensive experiments on real-world streaming datasets demonstrate the effectiveness of our method, which consistently outperforms both static update strategies and state-of-the-art online text classification models. Our code and data are publicly available athttps://github.com/bigbases/modular-online-adaptation.

Graph Contrastive Learning (GCL) has demonstrated substantial promise in enhancing the robustness and generalization of recommender systems, particularly by enabling models to leverage large-scale unlabeled data for improved representation learning. However, in this article, we reveal an unexpected vulnerability: the integration of GCL inadvertently increases the susceptibility of a recommender to targeted promotion attacks. Through both theoretical investigation and empirical validation, we identify the root cause as the spectral smoothing effect induced by contrastive optimization, which disperses item embeddings across the representation space and unintentionally enhances the exposure of target items. Building on this insight, we introduce a bi-level optimization attack method, named graph Contrastive Learning Recommendation Attack (CLeaR), which deliberately amplifies spectral smoothness and enables a systematic investigation of the susceptibility of GCL-based recommendation models to targeted promotion attacks. Our findings highlight the urgent need for robust countermeasures; in response, we further propose a Spectral-Irregularity Mitigation framework, named SIM, which accurately detects and suppresses targeted items without compromising model performance. Extensive experiments on multiple benchmark datasets demonstrate that, compared to existing targeted promotion attacks, GCL-based recommendation models exhibit greater susceptibility when evaluated with CLeaR, while SIM effectively mitigates these vulnerabilities.

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.

Federated learning (FL) is a privacy-preserving machine learning algorithm that enables multiple clients to collaborate. To respond to non-independent and identically distributed (non-IID) environments between clients, personalized FL (PFL) has been actively investigated. The typical PFL model consists of two parts: 1) the head (i.e., classifier) for the final classification and 2) the body (i.e., feature extractor) for extracting representations from local datasets. The head is maintained separately in each client for personalization; the body is aggregated for generalization. FedSDP introduces a bridge layer, called a personalized layer, between the head and the body to preserve individual, non-shared local prototypes for each client. A personalized layer decouples the body and head, strengthening the generalization and personalization, respectively. Based on this architecture, this study proposes a new PFL framework, Federated Self-Derived Prototypes (FedSDP), to dynamically balance personalization and generalization. To this end, we introduce two dynamic adjustments for generating self-derived prototypes: 1) global-local similarity weight (GL-Sim Weight) and 2) personalization early stopping indicator (P-Stop Indicator). GL-Sim Weight based on the similarity between the global and local prototypes is utilized to adjust the degree of personalization of each local model. PStop Indicator is calculated based on the changed degree of local parameters in each client, determining the early stopping for personalization in the client and further concentrating on generalization. Our comprehensive experiments demonstrate that FedSDP outperforms existing state-of-the-art FL frameworks, showing superior effectiveness in non-IID settings. Our code and data are available at https://github.com/bigbases/FedSDP.

This article presents FusionShot, a focal diversity-optimized few-shot ensemble learning approach for boosting the robustness and generalization performance of pre-trained few-shot models. The article makes three original contributions. First, we explore the unique characteristics of few-shot learning to ensemble multiple few-shot (FS) models by creating three alternative fusion channels. Second, we introduce the concept of focal error diversity to learn the most efficient ensemble teaming strategy, rather than assuming that an ensemble of a larger number of base models will outperform those sub-ensembles of smaller size. We develop a focal diversity ensemble pruning method to effectively prune out the candidate ensembles with low ensemble error diversity and recommend top- \( K \) FS ensembles with the highest focal error diversity. Finally, we capture the complex non-linear patterns of ensemble few-shot predictions by designing the learn-to-combine algorithm, which can learn the diverse weight assignments for robust ensemble fusion over different member models. Extensive experiments on representative few-shot benchmarks show that the top-K ensembles recommended by FusionShot can outperform the representative state-of-the-art (SOTA) few-shot models on novel tasks (different distributions and unknown at training) and can prevail over existing few-shot learners in both cross-domain settings and adversarial settings. For reproducibility purposes, FusionShot trained models, results, and code are made available at https://github.com/sftekin/fusionshot .

Continual learning aims to progressively acquire new knowledge while retaining previously learned information, addressing the challenge of catastrophic forgetting. This paper introduces a novel continual learning method, called SPrint, which is the first research effort to devise the principles of self-paced learning for solving continual learning problems. SPrint dynamically adapts the complexity of samples for both new and previous tasks in response to the model’s current learning capacity. It employs a self-paced loss function for sampling new tasks and a forgetting occurrence for sampling previous tasks with replay memory. Through extensive empirical evaluation, we demonstrate that SPrint consistently outperforms state-of-the-art methods in various continual learning benchmarks. Our source code is publicly available at https://github.com/bigbases/SPrint.

This study presents an adaptive online learning method for text classification under distribution shifts. We formulate a typical neural network-based text classification model as multiple logical modules. By leveraging the characteristics of the modules, we introduce three novel indicators to effectively measure the degree of dynamic distribution shifts without evaluating the model. To enhance online learning, we tactically trade off between learning efficiency and accuracy based on distribution shifts measured in real time. To the best of our knowledge, this is the first effort to adapt the model to the preference of learning efficiency or accuracy for online text classification. Extensive experiments on real-world streaming text datasets show that our method outperforms the best static update strategy and state-of-the-art online text classification models. Our code and data are available at https://github.com/bigbases/online-learning-text.

In this paper, we present a neural network-enabled data distribution aware sorting method, coined as NN-sort. Our approach explores the potential of developing deep learning techniques to speed up large-scale sort operations, enabling data distribution aware sorting as a deep learning service. Compared to traditional pairwise comparison-based sorting algorithms, which sort data elements by performing pairwise operations, NN-sort leverages the neural network model to learn the data distribution and uses it to map large-scale data elements into ordered ones. Our experiments demonstrate the significant advantage of using NN-sort. Measurements on both synthetic and real-world datasets show that NN-sort yields 2.18× to 10× performance improvement over traditional sorting algorithms.

Predicting information diffusion is a fundamental task in online social networks (OSNs).Recent studies mainly focus on the popularity prediction of specific content but ignore the correlation between multiple pieces of information.The topic is often used to correlate such information and can correspond to multi-source information.The popularity of a topic relies not only on information diffusion time but also on users' followership.Current solutions concentrate on hard time partition, lacking versatility.Meanwhile, the hop-based sampling adopted in state-of-the-art (SOTA) methods encounters redundant user followership.Moreover, many SOTA methods are not designed with good modularity and lack evaluation for each functional module and enlightening discussion.This paper presents a novel extensible framework, coined as HIF, for effective popularity prediction in OSNs with four original contributions.First, HIF adopts a soft partition of users and time intervals to better learn users' behavioral preferences over time.Second, HIF utilizes weighted sampling to optimize the construction of heterogeneous graphs and reduce redundancy.Furthermore, HIF supports multi-task collaborative optimization to improve its learning capability.Finally, as an extensible framework, HIF provides generic module slots to combine different submodules (e.g., RNNs,

Language models (LMs) have demonstrated superior performance in detecting fraudulent activities on Blockchains. Nonetheless, the sheer volume of Blockchain data results in excessive memory and computational costs when training LMs from scratch, limiting their capabilities to large-scale applications. In this paper, we present ZipZap, a framework tailored to achieve both parameter and computational efficiency when training LMs on large-scale transaction data. First, with the frequency-aware compression, an LM can be compressed down to a mere 7.5% of its initial size with an imperceptible performance dip. This technique correlates the embedding dimension of an address with its occurrence frequency in the dataset, motivated by the observation that embeddings of low-frequency addresses are insufficiently trained and thus negating the need for a uniformly large dimension for knowledge representation. Second, ZipZap accelerates the speed through the asymmetric training paradigm: It performs transaction dropping and cross-layer parameter-sharing to expedite the pre-training process, while revert to the standard training paradigm for fine-tuning to strike a balance between efficiency and efficacy, motivated by the observation that the optimization goals of pre-training and fine-tuning are inconsistent. Evaluations on real-world, large-scale datasets demonstrate that ZipZap delivers notable parameter and computational efficiency improvements for training LMs. Our implementation is available at: https://github.com/git-disl/ZipZap.

Many real-world applications require precise and fast time-series forecasting. Recent trends in time-series forecasting models are shifting from LSTM-based models to Transformer-based models. However, the Transformer-based model has a limited ability to represent sequential relationships in time-series data. In addition, the transformer-based model suffers from slow training and inference speed due to the bottleneck incurred by a deep encoder and step-by-step decoder inference. To address these problems, we propose a time-series forecasting optimized Transformer model, called TS-Fastformer. TS-Fastformer introduces three new optimizations: First, we propose a Sub Window Tokenizer for compressing input in a simple manner. The Sub Window Tokenizer reduces the length of input sequences to mitigate the complexity of self-attention and enables both single and multi-sequence learning. Second, we propose Time-series Pre-trained Encoder to extract effective representations through pre-training. This optimization enables TS-Fastformer to capture both seasonal and trend representations as well as to mitigate bottlenecks of conventional transformer models. Third, we propose the Past Attention Decoder to forecast target by incorporating past long short-term dependency patterns. Furthermore, Past Attention Decoder achieves high performance improvement by removing a trend distribution that changes over a long period. We evaluate the efficiency of our model with extensive experiments using seven real-world datasets and compare our model to six representative time-series forecasting approaches. The results show that the proposed TS-Fastformer reduces MSE by 10.1% compared to state-of-the-art model and demonstrates 21.6% faster training time compared to the existing fastest transformer, respectively.

Deep neural network ensembles combine the wisdom of multiple deep neural networks to improve the generalizability and robustness over individual networks. It has gained increasing popularity to study and apply deep ensemble techniques in the deep learning community. Some mission-critical applications utilize a large number of deep neural networks to form deep ensembles to achieve desired accuracy and resilience, which introduces high time and space costs for ensemble execution. However, it still remains a critical challenge whether a small subset of the entire deep ensemble can achieve the same or better generalizability and how to effectively identify these small deep ensembles for improving the space and time efficiency of ensemble execution. This article presents a novel deep ensemble pruning approach, which can efficiently identify smaller deep ensembles and provide higher ensemble accuracy than the entire deep ensemble of a large number of member networks. Our hierarchical ensemble pruning approach (HQ) leverages three novel ensemble pruning techniques. First, we show that the focal ensemble diversity metrics can accurately capture the complementary capacity of the member networks of an ensemble team, which can guide ensemble pruning. Second, we design a focal ensemble diversity based hierarchical pruning approach, which will iteratively find high quality deep ensembles with low cost and high accuracy. Third, we develop a focal diversity consensus method to integrate multiple focal diversity metrics to refine ensemble pruning results, where smaller deep ensembles can be effectively identified to offer high accuracy, high robustness and high ensemble execution efficiency. Evaluated using popular benchmark datasets, we demonstrate that the proposed hierarchical ensemble pruning approach can effectively identify high quality deep ensembles with better classification generalizability while being more time and space efficient in ensemble decision making. We have released the source codes on GitHub at https://github.com/git-disl/HQ-Ensemble .

Deep neural network ensembles hold the potential of improving generalization performance for complex learning tasks. This paper presents formal analysis and empirical evaluation to show that heterogeneous deep ensembles with high ensemble diversity can effectively leverage model learning heterogeneity to boost ensemble robustness. We first show that heterogeneous DNN models trained for solving the same learning problem, e.g., object detection, can significantly strengthen the mean average precision (mAP) through our weighted bounding box ensemble consensus method. Second, we further compose ensembles of heterogeneous models for solving different learning problems, e.g., object detection and semantic segmentation, by introducing the connected component labeling (CCL) based alignment. We show that this two-tier heterogeneity driven ensemble construction method can compose an ensemble team that promotes high ensemble diversity and low negative correlation among member models of the ensemble, strengthening ensemble robustness against both negative examples and adversarial attacks. Third, we provide a formal analysis of the ensemble robustness in terms of negative correlation. Extensive experiments validate the enhanced robustness of heterogeneous ensembles in both benign and adversarial settings. The appendix and source codes are available on GitHub at https://github.com/git-disl/HeteRobust.

Gradient leakage attacks are dominating privacy threats in federated learning, despite the default privacy that training data resides locally at the clients. Differential privacy has been the de facto standard for privacy protection and is deployed in federated learning to mitigate privacy risks. However, much existing literature points out that differential privacy fails to defend against gradient leakage. The paper presents ModelCloak, a principled approach based on differential privacy noise, aiming for safe-sharing client local model updates. The paper is organized into three major components. First, we introduce the gradient leakage robustness trade-off, in search of the best balance between accuracy and leakage prevention. The trade-off relation is developed based on the behavior of gradient leakage attacks throughout the federated training process. Second, we demonstrate that a proper amount of differential privacy noise can offer the best accuracy performance within the privacy requirement under a fixed differential privacy noise setting. Third, we propose dynamic differential privacy noise and show that the privacy-utility trade-off can be further optimized with dynamic model perturbation, ensuring privacy protection, competitive accuracy, and leakage attack prevention simultaneously.

Blockchain provides the unique and accountable channel for financial forensics by mining its open and immutable transaction data. A recent surge has been witnessed by training machine learning models with cryptocurrency transaction data for anomaly detection, such as money laundering and other fraudulent activities. This paper presents a holistic applied data science approach to fraud detection in the Bitcoin network with two original contributions. First, we contribute the Elliptic++dataset, which extends the Elliptic transaction dataset to include over 822k Bitcoin wallet addresses (nodes), each with 56 features, and 1.27M temporal interactions. This enables both the detection of fraudulent transactions and the detection of illicit addresses (actors) in the Bitcoin network by leveraging four types of graph data: (i) the transaction-to-transaction graph, representing the money flow in the Bitcoin network, (ii) the address-to-address interaction graph, capturing the types of transaction flows between Bitcoin addresses, (iii) the address-transaction graph, representing the bi-directional money flow between addresses and transactions (BTC flow from input address to one or more transactions and BTC flow from a transaction to one or more output addresses), and (iv) the user entity graph, capturing clusters of Bitcoin addresses representing unique Bitcoin users. Second, we perform fraud detection tasks on all four graphs by using diverse machine learning algorithms. We show that adding enhanced features from the address-to-address and the address-transaction graphs not only assists in effectively detecting both illicit transactions and illicit addresses, but also assists in gaining in-depth understanding of the root cause of money laundering vulnerabilities in cryptocurrency transactions and the strategies for fraud detection and prevention. The Elliptic++ dataset is released at https://www.github.com/git-disl/EllipticPlusPlus.

As various forms of fraud proliferate on Ethereum, it is imperative to safeguard against these malicious activities to protect susceptible users from being victimized. While current studies solely rely on graph-based fraud detection approaches, it is argued that they may not be well-suited for dealing with highly repetitive, skew-distributed and heterogeneous Ethereum transactions. To address these challenges, we propose BERT4ETH, a universal pre-trained Transformer encoder that serves as an account representation extractor for detecting various fraud behaviors on Ethereum. BERT4ETH features the superior modeling capability of Transformer to capture the dynamic sequential patterns inherent in Ethereum transactions, and addresses the challenges of pre-training a BERT model for Ethereum with three practical and effective strategies, namely repetitiveness reduction, skew alleviation and heterogeneity modeling. Our empirical evaluation demonstrates that BERT4ETH outperforms state-of-the-art methods with significant enhancements in terms of the phishing account detection and de-anonymization tasks. The code for BERT4ETH is available at: https://github.com/git-disl/BERT4ETH.

The choice of learning rate (LR) functions and policies has evolved from a simple fixed LR to the decaying LR and the cyclic LR, aiming to improve the accuracy and reduce the training time of Deep Neural Networks (DNNs). This article presents a systematic approach to selecting and composing an LR policy for effective DNN training to meet desired target accuracy and reduce training time within the pre-defined training iterations. It makes three original contributions. First, we develop an LR tuning mechanism for auto-verification of a given LR policy with respect to the desired accuracy goal under the pre-defined training time constraint. Second, we develop an LR policy recommendation system (LRBench) to select and compose good LR policies from the same and/or different LR functions through dynamic tuning, and avoid bad choices, for a given learning task, DNN model, and dataset. Third, we extend LRBench by supporting different DNN optimizers and show the significant mutual impact of different LR policies and different optimizers. Evaluated using popular benchmark datasets and different DNN models (LeNet, CNN3, ResNet), we show that our approach can effectively deliver high DNN test accuracy, outperform the existing recommended default LR policies, and reduce the DNN training time by 1.6-6.7× to meet a targeted model accuracy.

Neural network ensemble is a collaborative learning paradigm that utilizes multiple neural networks to solve a complex learning problem. Constructing predictive models with high generalization performance is an important and yet most challenging goal for robust intelligence systems in the presence of dirty data. Given a target learning task, popular approaches have been dedicated to find the top performing model. However, it is difficult in general to estimate the best model when available data is finite, possibly dirty, and insufficient for the problem. In this keynote, I will give an overview of a diversity-centric ensemble learning framework developed at Georgia Tech, including methodologies and algorithms for measuring, enforcing, and combining multiple neural networks by improving generalization performance of the overall system and maximizing ensemble utility and resilience to dirty data.

Popularity prediction is to predict the number of social network users involved in information diffusion. Recently, deep learning methods for popularity prediction advance traditional approaches that rely on hand-crafted features. However, existing approaches ignore the multi-source cascade that consists of multiple sub-cascades with different content but under the same topic. Different from single-source cascade, more cascading information can be observed from multi-source cascade and they are potentially correlated. How to correlate the diverse information and take advantage of them from both temporal and spatial aspects is critical for prediction. To this end, we propose a novel framework, called HEterogeneous Recurrent Integrated Graph Convolutional Neural Network (HERI-GCN). Specifically, we construct a heterogeneous cascade graph to model the multi-source cascade where time intervals are treated as heterogeneous time nodes. Besides, we propose a heterogeneous GCN to learn rich features from the multi-source cascade. RNN is organically integrated into the heterogeneous GCN to overcome the limited learning ability toward temporal and spatial data. We evaluate HERI-GCN through comparative experiments on three datasets. The experimental evaluation shows that HERI-GCN outperforms the state-of-the-art baseline methods.

Object detection has played a pivotal role in numerous mission-critical applications. This paper presents a focal error diversity framework, called EDI, for strengthening the robustness of object detection ensembles under benign and adversarial scenarios. We introduce an ensemble pruning method for object detection using a novel focal error diversity measure as the robustness synergy indicator. Given a base model pool, it recommends top sub-ensembles with a smaller ensemble size yet achieving equivalent or even better mAP performance than using all available object detection models as a large ensemble. This is made possible by our negative sampling methods for object detection to capture the degree of negative correlations and the focal error diversity to measure the failure independence of component detection models in an ensemble. Extensive experiments on three object detection benchmark datasets validate that EDI effectively selects space-time efficient object detection ensembles with high mAP performance.

This paper presents a novel approach to the problem of event-dense text and image cross-modal retrieval where the text contains the descriptions of numerous events. It is known that modality alignment is crucial for retrieval performance. However, due to the lack of event sequence information in the image, it is challenging to perform the fine-grain alignment of the event-dense text with the image. Our proposed approach incorporates the event-oriented features to enhance the cross-modal alignment, and applies the event-dense text-image retrieval to the food domain for empirical validation. Specifically, we capture the significance of each event by Transformer, and combine it with the identified key event elements, to enhance the discriminative ability of the learned text embedding that summarizes all the events. Next, we produce the image embedding by combining the event tag jointly shared by the text and image with the visual embedding of the event-related image regions, which describes the eventual consequence of all the events and facilitates the event-based cross-modal alignment. Finally, we integrate text embedding and image embedding with the loss optimization empowered with the event tag by iteratively regulating the joint embedding learning for cross-modal retrieval. Extensive experiments demonstrate that our proposed event-oriented modality alignment approach significantly outperforms the state-of-the-art approach with a 23.3% improvement on top-1 Recall for image-to-recipe retrieval on Recipe1M 10k test set.

This article introduces a two-phase deep feature engineering framework for efficient learning of semantics enhanced joint embedding, which clearly separates the deep feature engineering in data preprocessing from training the text-image joint embedding model. We use the Recipe1M dataset for the technical description and empirical validation. In preprocessing, we perform deep feature engineering by combining deep feature engineering with semantic context features derived from raw text-image input data. We leverage LSTM to identify key terms, deep NLP models from the BERT family, TextRank, or TF-IDF to produce ranking scores for key terms before generating the vector representation for each key term by using Word2vec. We leverage Wide ResNet50 and Word2vec to extract and encode the image category semantics of food images to help semantic alignment of the learned recipe and image embeddings in the joint latent space. In joint embedding learning, we perform deep feature engineering by optimizing the batch-hard triplet loss function with soft-margin and double negative sampling, taking into account also the category-based alignment loss and discriminator-based alignment loss. Extensive experiments demonstrate that our SEJE approach with deep feature engineering significantly outperforms the state-of-the-art approaches.

This paper presents a transparent Container Network Memory storage device, coined as CNetMem, aiming to address the open problem of unpredictable performance degradation of containers when the working set of an application no longer fits in container memory. First, CNetMem will enable application tenants running in a container to park their working set memory/file to a faster network memory storage by organizing a group of remote memory nodes as remote memory donors. This allows CNetMem to take advantage of remote idle memory on a cluster before resorting to a slow local I/O subsystem like local disk without any modification of host OS or application. Second, CNetMem provides a hybrid batching technique to remove or alleviate performance bottlenecks in the I/O performance critical path for remote memory read/write with replication or disk backup for fault tolerance. Third, CNetMem introduces a rank-based node selection algorithm to find the optimal node for placing remote memory blocks across cluster. This helps CNetMem to reduce the performance impact due to remote memory eviction. Extensive experiments are conducted on three big data applications and four machine learning workloads. The results show that CNetMem achieves up to 172× throughput improvements compared to vanilla Linux and up to 5.9× completion time improvements over existing approaches in big data and ML workload.

An efficient approach to managing big data workloads is to enable applications to work directly with huge pages. This can effectively avoid or reduce the memory fragmentation problem due to high frequent memory allocation and deallocation and significantly minimize the performance degradation of big data applications. This paper presents XPage, a huge page memory management framework, with three novel features. First, XPage by design can provide automated huge page managements with transparency to both OS and applications. Second, Xpage represents a memory management redesign that brings performance and memory saving to memory intensive applications by supporting dynamic huge page memory management without resorting to splitting huge pages for memory fragmentation. Third but not the least, XPage can efficiently minimize the internal fragmentation without impacting performance of applications. We conduct extensive experiments to evaluate the effectiveness of XPage in minimizing internal memory fragmentation in the presence of dynamic memory intensive big data workloads, by comparing XPage with vanilla Linux using 4KB base page and Linux with 2MB huge page.

This paper presents a three-tier modality alignment approach to learning text-image joint embedding, coined as JEMA, for cross-modal retrieval of cooking recipes and food images. The first tier improves recipe text embedding by optimizing the LSTM networks with term extraction and ranking enhanced sequence patterns, and optimizes the image embedding by combining the ResNeXt-101 image encoder with the category embedding using wideResNet-50 with word2vec. The second tier modality alignment optimizes the textual-visual joint embedding loss function using a double batch-hard triplet loss with soft-margin optimization. The third modality alignment incorporates two types of cross-modality alignments as the auxiliary loss regularizations to further reduce the alignment errors in the joint learning of the two modality-specific embedding functions. The category-based cross-modal alignment aims to align the image category with the recipe category as a loss regularization to the joint embedding. The cross-modal discriminator-based alignment aims to add the visual-textual embedding distribution alignment to further regularize the joint embedding loss. Extensive experiments with the one-million recipes benchmark dataset Recipe1M demonstrate that the proposed JEMA approach outperforms the state-of-the-art cross-modal embedding methods for both image-to-recipe and recipe-to-image retrievals.

Deep neural network ensembles have become attractive learning techniques with better generalizability over individual models. Some mission critical applications may require a large number of deep neural networks to achieve desirable accuracy and generalizability, making the ensemble execution costly with respect to runtime and space. This paper proposes a novel hierarchical ensemble pruning approach, which can effectively examine a given pool of M base models and identify smaller high quality deep ensembles of size $S(\ll M)$ with higher ensemble accuracy than the entire deep ensemble of all M models. Our hierarchical pruning approach, coined as HQ, combines three novel techniques. First, we show that the focal diversity metrics is innovative and can accurately capture the negative correlation among the member models of an ensemble, and the use of focal diversity metrics can boost ensemble accuracy. Second, we introduce a focal-diversity based hierarchical pruning algorithm to progressively identify low-cost ensembles with high ensemble diversity and accuracy. Third, we design a focal diversity consensus method to find smaller deep ensembles with low negative correlation. We demonstrate such ensembles offer high accuracy and high robustness while being more time and space efficient in ensemble decision making. Evaluated using two benchmark datasets, we show that the proposed focal diversity powered hierarchical pruning can find significantly smaller ensembles of deep neural network models while achieving the same or better classification generalizability.

Deep neural network (DNN) based object detection has become an integral part of numerous cyber-physical systems, perceiving physical environments and responding proactively to real-time events. Recent studies reveal that well-trained multi-task learners like DNN-based object detectors perform poorly in the presence of deception. This paper presents FUSE, a deception-resilient detection fusion approach with three novel contributions. First, we develop diversity-enhanced fusion teaming mechanisms, including diversity-enhanced joint training algorithms, for producing high diversity fusion detectors. Second, we introduce a three-tier detection fusion framework and a graph partitioning algorithm to construct fusion-verified detection outputs through three mutually reinforcing components: objectness fusion, bounding box fusion, and classification fusion. Third but not least, we provide a formal analysis of robustness enhancement by FUSE-protected systems. Extensive experiments are conducted on eleven detectors from three families of detection algorithms on two benchmark datasets. We show that FUSE guarantees strong robustness in mitigating the state-of-the-art deception attacks, including adversarial patches - a form of physical attacks using confined visual distortion.

Continuous Data Protection (CDP) is becoming instrumental in recovering applications from crypto-ransomware attacks. It enables fine-grained recovery through journaling, allowing the applications (its volumes) to recover to any previous state. While zero data loss can be achieved during recovery with CDP, the timestamp of the desired restore point, i.e., the one just prior to the attack, needs to be provided to reconstruct the volume. Such information is often unavailable in practice, and system administrators can only adopt a trial-and-error strategy to narrow down the time range of desired restore points by making multiple time-consuming recovery attempts. The recovery systems offer little guidance in pointing to the restore points containing a valid application state and reducing data loss. To address this problem, we equip the CDP-based recovery with machine intelligence. This demonstration showcases Smart Recovery Advisor (SRA), which offers interpretable, data-driven, and feedback-aware restore point recommendations that reduce the number of recovery attempts while minimizing data loss.

Deep neural networks (DNNs) have demonstrated impressive performance on many challenging machine learning tasks. However, DNNs are vulnerable to adversarial inputs generated by adding maliciously crafted perturbations to the benign inputs. As a growing number of attacks have been reported to generate adversarial inputs of varying sophistication, the defense-attack arms race has been accelerated. In this paper, we present MODEF, a cross-layer model diversity ensemble framework. MODEF intelligently combines unsupervised model denoising ensemble with supervised model verification ensemble by quantifying model diversity, aiming to boost the robustness of the target model against adversarial examples. Evaluated using eleven representative attacks on popular benchmark datasets, we show that MODEF achieves remarkable defense success rates, compared with existing defense methods, and provides a superior capability of repairing adversarial inputs and making correct predictions with high accuracy in the presence of black-box attacks.

We are entering an exciting era where human intelligence is being enhanced by machine intelligence through big data fueled artificial intelligence (AI) and machine learning (ML). However, recent work shows that DNN models trained privately are vulnerable to adversarial inputs. Such adversarial inputs inject small amount of perturbations to the input data to fool machine learning models to misbehave, turning a deep neural network against itself. As new defense methods are proposed, more sophisticated attack algorithms are surfaced. This arms race has been ongoing since the rise of adversarial machine learning. This keynote provides a comprehensive analysis and characterization of the most representative attacks and their defenses. As more and more mission critical systems are incorporating machine learning and AI as an essential component in their real-world big data applications and their big data service provisioning platforms or products, understanding and ensuring the verifiable robustness of deep learning becomes a pressing challenge in the presence of adversarial attacks. This includes (1) the development of formal metrics to quantitatively evaluate and measure the robustness of a DNN prediction with respect of intentional and unintentional artifacts and deceptions, (2) the comprehensive understanding of the blind spots and the invariants in the DNN trained models and the DNN training process, and (3) the statistical measurement of trust and distrust that we can place on a deep learning algorithm to perform reliably and truthfully. In this keynote talk, I will use empirical analysis and evaluation of our cross-layer strategic teaming defense framework and techniques to illustrate the feasibility of ensuring robust deep learning.

Learning Rate (LR) is an important hyper-parameter to tune for effective training of deep neural networks (DNNs). Even for the baseline of a constant learning rate, it is non-trivial to choose a good constant value for training a DNN. Dynamic learning rates involve multi-step tuning of LR values at various stages of the training process and offer high accuracy and fast convergence. However, they are much harder to tune. In this paper, we present a comprehensive study of 13 learning rate functions and their associated LR policies by examining their range parameters, step parameters, and value update parameters. We propose a set of metrics for evaluating and selecting LR policies, including the classification confidence, variance, cost, and robustness, and implement them in LRBench, an LR benchmarking system. LRBench can assist end-users and DNN developers to select good LR policies and avoid bad LR policies for training their DNNs. We tested LRBench on Caffe, an open source deep learning framework, to showcase the tuning optimization of LR policies. Evaluated through extensive experiments, we attempt to demystify the tuning of LR policies by identifying good LR policies with effective LR value ranges and step sizes for LR update schedules.

GPS-dependent localization, navigation and air traffic control (ATC) applications have had a significant impact on the modern aviation industry. However, the lack of encryption and authentication makes GPS vulnerable to spoofing attacks with the purpose of hijacking aerial vehicles or threatening air safety. In this paper, we propose GPS-Probe, a GPS spoofing detection algorithm that leverages the ATC messages that are periodically broadcasted by aerial vehicles. By continuously analyzing the received signal strength indicator (RSSI) and the timestamps at server (TSS) of the ATC messages, which are monitored by multiple ground sensors, GPS-Probe constructs a machine learning enabled framework to estimate the real position of the target aerial vehicle and to detect whether or not the position data is compromised by GPS spoofing attacks. Unlike existing techniques, GPS-Probe neither requires any updates of the GPS infrastructure nor updates of the GPS receivers. More importantly, it releases the requirement on time synchronization of the ground sensors distributed around the world. Using the real-world ATC data crowdsourced by the OpenSky Network, our experiment results show that GPS-Probe can achieve the detection accuracy and precision, of 81.7% and 85.3% respectively on average, and up to 89.7% and 91.5% respectively at the best.

Trajectory clustering aims at grouping similar trajectories into one cluster. It is an efficient way of finding the representative path or common trend shared by different moving objects, and also provides a foundation for movement pattern mining, anomaly detection and other applications. Existing trajectory clustering studies mainly rely on feature selection and similarity measurement based on their geographical and spatial properties. However, one obstacle hindering their wide usage is the problem of clustering accuracy in the presence of noisy or incomplete sensing data, due to limited sensory device quantity, communication errors, sensor failures, and sensor vacancy. This paper proposes an error-tolerant trajectory clustering approach by incorporating denoising methods.We propose the Robust Deep Attention Auto-encoders model (called Robust DAA) to learn the representations of low-dimensional denoising trajectories with three novel features. First, we present the deep attention auto-encoders by integrating the attention mechanism into the classical deep auto-encoder, which is capable of enhancing feature propagation and feature selection. Second, we train the deep attention auto-encoder by applying proximal method, back propagation and the Alternating Direction of Method of Multipliers (ADMM). As a result, our Robust DAA can reduce the negative influence of the noise on trajectory data. Finally, we perform clustering over the low-dimensional denoising representations using traditional clustering algorithms and demonstrates the quality of the clustering results by comparing our approach with existing representative methods. Extensive experiments are conducted on both synthetic datasets and real datasets. The results show that our approach outperforms the existing models in terms of accuracy, precision, recall and f1-score.

As more business workflow systems are being deployed in modern enterprises and organizations, more employee-activity log data are being collected and analyzed. In this paper, we develop a latent ability model (LAM) as a generative probabilistic learning framework for workforce analytics over employee-activity logs. The LAM development is novel in three aspects. First, we introduce the concept of latent ability variables to model hidden relations between employees and activities in terms of job performance, such as the set of skills provided by an employee and the set of skills required by an activity, and how well they matchup in employee-activity assignment. Second, we construct the latent ability model by learning latent ability parameters from the employee-activity log data using expectation-maximization and gradient descent. Finally, we leverage LAM to build inference and prediction models for employee performance prediction, employee ability comparison, and employee-activity matchup quality estimation. We evaluate the accuracy and efficiency of our approach using real log datasets collected from a workflow system deployed in the government of the city of Hangzhou, China, which consists of 5,287,621 log records over two years involving 744 activities and 1,725 employees. We show that LAM approach outperforms existing representative methods in both accuracy and efficiency.

Many big data applications are memory-intensive workloads and perform iterative analytics algorithms. When the dataset used in each iteration of the analytic job exceeds the physical memory of their allocation, this type of workloads suffers from serious performance degradation or experience out of memory error. Existing proposals focus on estimating working set size for accurate resource allocation of executors, but lack of desired efficiency and transparency. This paper presents an efficient shared-memory based memory paging service, called FastSwap. The design of FastSwap makes a number of original contributions. First, FastSwap improves VM memory swapping performance by leveraging idle host memory and redirecting the VM swapping traffic to the host-guest compressed shared memory swap area. Second, FastSwap develops a compressed swap page table as an efficient index structure to provide high utilization of shared memory swap area through supporting multi-granularity of compression factors. Third, FastSwap provides hybrid swap-out and proactive swap-in to further improve the performance of shared memory swapping. Finally, FastSwap is by design light-weighted and non-intrusive. We evaluate FastSwap using a set of well-known big data analytics workloads and benchmarks, such as Spark, Redis, HiBench, SparkBench and YCSB. The results show that FastSwap offers up to two orders of magnitude performance improvements over existing memory swapping methods and more than four orders of magnitude faster than conventional disk based VM swapping facility.

Big Data has fueled the wide deployment of Deep Learning (DL) in many fields, such as image classification, voice recognition and NLP. The growing number of open source DL software frameworks has put forward high demands on comparative study of their efficiency with respect to both runtime performance and accuracy. This paper presents a brief overview of our empirical evaluation of four representative DL frameworks: TensorFlow, Caffe, Torch and Theano through a comparative analysis and characterization. First, we show that the complex interactions among neural networks (NN), hyper-parameters, their specific runtime implementations and datasets are latent factors for the uncertainty of runtime performance and accuracy. Second, we characterized the CPU/GPU resource usage patterns under different configurations for different frameworks to obtain an in-depth understanding of the impact of different batch sizes. Third, we describe the data loading process of ImageNet for TensorFlow and present an experimental characterization of TensorFlow with respect to its data loading process when the dataset is too large to fit into the main memory of the CPU server. We conjecture that our experimental characterization and analysis can offer empirical guidance for users and application developers to select the right DL frameworks and configurations for their domain-specific learning tasks and datasets.

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.

NgramCNN is a deep convolutional neural network developed for classification of graphs based on common substructure patterns and their latent relationships in the collection of graphs. Our NgramCNN deep learning framework consists of three novel components: (1) The concept of n-gram graph block to transform each raw graph object into a sequence of n-gram blocks connected through overlapping regions. (2) The diagonal convolution layer to extract local patterns and connectivity features hidden in the n-gram blocks by performing n-gram normalization before conducting deep learning through the network of convolution layers. (3) The extraction of deeper global patterns based on the local patterns and the ways that they respond to overlapping regions by building a n-gram deep convolutional neural network. Extensive evaluation of NgramCNN using five real graph repositories from bioinformatics and social networks domains show the effectiveness of NgramCNN over the existing state of art methods with high accuracy and comparable performance.

Reachability query asks whether a vertex can reach another vertex on large directed graphs. It is one of the most fundamental graph operators and has attracted many researchers to study it. Although there are many approaches solving this problem, it still remains a challenging problem when it comes to leverage the three main costs: the index construction time, the index size, and the query time on large and dense graphs. In this paper, we propose a High Dimension Graph Labeling approach to answer reachability queries. First, we recursively partition a graph into disjoint non-shared graphs, among which there are no common vertices, and cross edges. Second, we build a four dimensional label - one dimension of layer, one dimension of sub-graph and two dimensions of interval for each vertex. With the layer label and the sub-graph label, we can determine the positions (non-shared graphs) of any two vertices. Two dimensional interval label is used to assist to answer the reachability queries for vertex pair in those non-shared graphs. Finally, we design algorithms to answer researchability queries efficiently. In order to speed up query answering, we also build two directional labels: up and down labels to filter vertices quickly. The extensive experiments on 28 large/small and dense/sparse graphs show that building the high dimensional index is quickly and the index size is also competitive compared with most of the state of the art approaches. The results also show that our approach is more scalable and efficient than the state-of-the-art approaches in answering reachability queries.

In Big data and IoT environments, process execution generates huge-sized data some of which is subsequently obtained by sensors. The main issue in such areas has been the necessity of analyzing data in order to suggest enhancements to processes. In this regard, evaluation of process model conformance to the execution log is of great importance. For this purpose, previous reports on process mining approaches have advocated conformance checking by fitness measure, which is a process that uses token replay and node-arc relations based on Petri net. However, fitness measure so far has not considered statistical significance, but just offers a numeric ratio. We herein propose a statistical verification method based on the Kolmogorov–Smirnov (K–S) test to judge whether two different log datasets follow the same process model. Our method can be easily extended to determinations that process execution actually follows a process model, by playing out the model and generating event log data from it. Additionally, in order to solve the problem of the trade-off between model abstraction and process conformance, we also propose the new concepts of Confidence Interval of Abstraction Value (CIAV) and Maximum Confidence Abstraction Value (MCAV). We showed that our method can be applied to any process mining algorithm (e.g. heuristic mining, fuzzy mining) that has parameters related to model abstraction. We expect that our method will come to be widely utilized in many applications dealing with business process enhancement involving process-model and execution-log analyses.

Most of mobile object trajectory clustering analysis to date has been focused on clustering the location points or sub-trajectories extracted from trajectory data. This paper presents TraceMob, a systematic approach to clustering whole trajectories of mobile objects traveling in road networks. TraceMob as a whole trajectory clustering framework has three unique features. First, we design a quality measure for the distance between two whole trajectories. By quality, we mean that the distance measure can capture the complex characteristics of trajectories as a whole including their varying lengths and their constrained movement in the road network space. Second, we develop an algorithm that transforms whole trajectories in a road network space into multidimensional data points in a euclidean space while preserving their relative distances in the transformed metric space. This transformation enables us to effectively shift the clustering task for whole mobile object trajectories in the complex road network space to the traditional clustering task for multidimensional data in a euclidean space. Third, we develop a cluster validation method for evaluating the clustering quality in both the transformed metric space and the road network space. Extensive experimental evaluation with trajectories generated on real road network maps of different cities shows that TraceMob produces higher quality clustering results and outperforms existing approaches by an order of magnitude.

Convolutional Neural Network (CNN) has gained attractions in image analytics and speech recognition in recent years. However, employing CNN for classification of graphs remains to be challenging. This paper presents the Ngram graph-block based convolutional neural network model for classification of graphs. Our Ngram deep learning framework consists of three novel components. First, we introduce the concept of n-gram block to transform each raw graph object into a sequence of n-gram blocks connected through overlapping regions. Second, we introduce a diagonal convolution step to extract local patterns and connectivity features hidden in these n-gram blocks by performing n-gram normalization. Finally, we develop deeper global patterns based on the local patterns and the ways that they respond to overlapping regions by building a n-gram deep learning model using convolutional neural network. We evaluate the effectiveness of our approach by comparing it with the existing state of art methods using five real graph repositories from bioinformatics and social networks domains. Our results show that the Ngram approach outperforms existing methods with high accuracy and comparable performance.

The emerging need for conducting complex analysis over big RDF datasets calls for scale-out solutions that can harness a computing cluster to process big RDF datasets. Queries over RDF data often involve complex self-joins, which would be very expensive to run if the data are not carefully partitioned across the cluster and hence distributed joins over massive amount of data are necessary. Existing RDF data partitioning methods can nicely localize simple queries but still need to resort to expensive distributed joins for more complex queries. In this paper, we propose a new data partitioning approach that takes use of the rich structural information in RDF datasets and minimizes the amount of data that have to be joined across different computing nodes. We conduct an extensive experimental study using two popular RDF benchmark data and one real RDF dataset that contain up to billions of RDF triples. The results indicate that our approach can produce a balanced and low redundant data partitioning scheme that can avoid or largely reduce the cost of distributed joins even for very complicated queries. In terms of query execution time, our approach can outperform the state-of-the-art methods by orders of magnitude.

Meta paths are good mechanisms to improve the quality of graph analysis on heterogeneous information networks. This paper presents a meta path graph clustering framework, VEPATHCLUSTER, that combines meta path vertex-centric clustering with meta path edge-centric clustering for improving the clustering quality of heterogeneous networks. First, we propose an edge-centric path graph model to capture the meta-path dependencies between pairwise path edges. We model a heterogeneous network containing M types of meta paths as M vertex-centric path graphs and M edge-centric path graphs. Second, we propose a clustering-based multigraph model to capture the fine-grained clustering-based relationships between pairwise vertices and between pairwise path edges. We perform clustering analysis on both a unified vertex-centric path graph and each edge-centric path graph to generate vertex clustering and edge clusterings of the original heterogeneous network respectively. Third, a reinforcement algorithm is provided to tightly integrate vertex-centric clustering and edge-centric clustering by mutually enhancing each other. Finally, an iterative learning strategy is presented to dynamically refine both vertex-centric clustering and edge-centric clustering by continuously learning the contributions and adjusting the weights of different path graphs.

The open nature of recommender systems makes them vulnerable to shilling attacks. Biased ratings are introduced in order to affect recommendations, have been shown to cause great harm to collaborative filtering algorithms. Most of previous research focuses on the differences between genuine profiles and attack profiles, ignoring the group characteristics in an attack. There exists class unbalance problems in SVM based detecting methods, that is, the detecting performance is not good when the amount of samples of attack profiles in training set is small. In this paper, we study the use of SVM based method and group characteristics in attack profiles to detect attack profiles. Based on this, a two phase detecting method SVM-TIA is proposed. In the first phase, Borderline-SMOTE method is used to alleviate the class unbalance problem in classification; a rough detecting result is obtained in this phase; the second phase is a fine-tuning phase whereby the target items in the potential attack profiles set are analysed. We conduct experiments on the MovieLens 100K Dataset and compare the performance of SVM-TIA with other shilling detecting methods to demonstrate the effectiveness of the proposed approach.

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.

Social influence analysis has shown great potential for strategic marketing decision. It is well known that people influence one another based on both their social connections and the social activities that they have engaged in the past. In this article, we develop an innovative and high-performance social influence based graph clustering framework with four unique features. First, we explicitly distinguish social connection based influence (self-influence) and social activity based influence (co-influence). We compute the self-influence similarity between two members based on their social connections within a single collaboration network, and compute the co-influence similarity by taking into account not only the set of activities that people participate but also the semantic association between these activities. Second, we define the concept of influence-based similarity by introducing a unified influence-based similarity matrix that employs an iterative weight update method to integrate self-influence and co-influence similarities. Third, we design a dynamic learning algorithm, called SI-C luster , for social influence based graph clustering. It iteratively partitions a large social collaboration network into K clusters based on both the social network itself and the multiple associated activity information networks, each representing a category of activities that people have engaged. To make the SI-C luster algorithm converge fast, we transform sophisticated nonlinear fractional programming problem with respect to multiple weights into a straightforward nonlinear parametric programming problem of single variable. Finally, we develop an optimization technique of diagonalizable-matrix approximation to speed up the computation of self-influence similarity and co-influence similarities. Our SI-Cluster-Opt significantly improves the efficiency of SI-Cluster on large graphs while maintaining high quality of clustering results. Extensive experimental evaluation on three real-world graphs shows that, compared to existing representative graph clustering algorithms, our SI-C luster -O pt approach not only achieves a very good balance between self-influence and co-influence similarities but also scales extremely well for clustering large graphs in terms of time complexity while meeting the guarantee of high density, low entropy and low Davies--Bouldin Index.

In emerging information networks, it is crucially important to provide efficient search on distributed documents while preserving their owners' privacy, for which privacy preserving indexes or PPI presents a possible solution. An understudied problem for the PPI techniques is how to provide differentiated privacy preservation in the presence of multi-keyword document search. The differentiation is necessary as terms and phrases bear innate differences in their semantic meanings. In this paper, we present ϵ-MPPI, the first work to provide the distributed document search with quantitatively differentiated privacy preservation. In the design of ϵ-MPPI, we identified a suite of challenging problems and proposed novel solutions. For one, we formulated the quantitative privacy computation as an optimization problem that strikes a balance between privacy preservation and search efficiency. We also addressed the challenging problem of secure ϵ-MPPI construction in the multi-domain information network which lacks mutual trusts between domains. Towards a secure ϵ-MPPIconstruction with practically acceptable performance, we proposed to optimize the performance of secure multi-party computations by making a novel use of secret sharing. We implemented the ϵ-MPPI construction protocol with a functioning prototype. We conducted extensive experiments to evaluate the prototype's effectiveness and efficiency based on a real-world dataset.

Distributed service networks are popular platforms for service providers to offer services to consumers and for service consumers to acquire services from unknown parties. eBay and Amazon are two well-known examples of enabling and hosting such service networks to connect service providers to service consumers. Trust management is a critical component for scaling such distributed service networks to a large and growing number of participants. In this article, we present ServiceTrust ++ , a feedback quality--sensitive and attack resilient trust management scheme for empowering distributed service networks with effective trust management capability. Compared with existing trust models, ServiceTrust ++ has several novel features. First, we present six attack models to capture both independent and colluding attacks with malicious cliques, malicious spies, and malicious camouflages. Second, we aggregate the feedback ratings based on the variances of participants’ feedback behaviors and incorporate feedback similarity as weight into the local trust algorithm. Third, we compute the global trust of a participant by employing conditional trust propagation based on the feedback similarity threshold. This allows ServiceTrust ++ to control and prevent malicious spies and malicious camouflage peers from boosting their global trust scores by manipulating the feedback ratings of good peers and by taking advantage of the uniform trust propagation. Finally, we systematically combine a trust-decaying strategy with a threshold value--based conditional trust propagation to further strengthen the robustness of our global trust computation against sophisticated malicious feedback. Experimental evaluation with both simulation-based networks and real network dataset Epinion show that ServiceTrust ++ is highly resilient against all six attack models and highly effective compared to EigenTrust, the most popular and representative trust propagation model to date.

The flexibility of the RDF data model has attracted an increasing number of organizations to store their data in an RDF format. With the rapid growth of RDF datasets, we envision that it is inevitable to deploy a cluster of computing nodes to process large-scale RDF data in order to deliver desirable query performance. In this paper, we address the challenging problems of data partitioning and query optimization in a scale-out RDF engine. We identify that existing approaches only focus on using fine-grained structural information for data partitioning, and hence fail to localize many types of complex queries. We then propose a radically different approach, where a coarse-grained structure, namely Rooted Sub-Graph (RSG), is used as the partition unit. By doing so, we can capture structural information at a much greater scale and hence are able to localize many complex queries. We also propose a k-means partitioning algorithm for allocating the RSGs onto the computing nodes as well as a query optimization strategy to minimize the inter-node communication during query processing. An extensive experimental study using benchmark datasets and real dataset shows that our engine, SemStore, outperforms existing systems by orders of magnitudes in terms of query response time.

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 the age of big data, key-value data updated by intensive write streams is increasingly common, e.g., in social event streams. To serve such data in a cost-effective manner, a popular new paradigm is to outsource it to the cloud and store it in a scalable key-value store while serving a large user base. Due to the limited trust in third-party cloud infrastructures, data owners have to sign the data stream so that the data users can verify the authenticity of query results from the cloud. In this paper, we address the problem of verifiable freshness for multi-version key-value data. We propose a memory-resident digest structure that utilizes limited memory effectively and can have efficient verification performance. The proposed structure is named IncBM-Tree because it can INCrementally build a Bloom filter-embedded Merkle Tree. We have demonstrated the superior performance of verification under small memory footprints for signing, which is typical in an outsourcing scenario where data owners and users have limited resources.

Multi-label classification of heterogeneous information networks has received renewed attention in social network analysis. In this paper, we present an activity-edge centric multi-label classification framework for analyzing heterogeneous information networks with three unique features. First, we model a heterogeneous information network in terms of a collaboration graph and multiple associated activity graphs. We introduce a novel concept of vertex-edge homophily in terms of both vertex labels and edge labels and transform a general collaboration graph into an activity-based collaboration multigraph by augmenting its edges with class labels from each activity graph through activity-based edge classification. Second, we utilize the label vicinity to capture the pairwise vertex closeness based on the labeling on the activity-based collaboration multigraph. We incorporate both the structure affinity and the label vicinity into a unified classifier to speed up the classification convergence. Third, we design an iterative learning algorithm, AEClass, to dynamically refine the classification result by continuously adjusting the weights on different activity-based edge classification schemes from multiple activity graphs, while constantly learning the contribution of the structure affinity and the label vicinity in the unified classifier. Extensive evaluation on real datasets demonstrates that AEClass outperforms existing representative methods in terms of both effectiveness and efficiency.

Ontology reuse offers great benefits by measuring and comparing ontologies. However, the state of art approaches for measuring ontologies neglects the problems of both the polymorphism of ontology representation and the addition of implicit semantic knowledge. One way to tackle these problems is to devise a mechanism for ontology measurement that is stable, the basic criteria for automatic measurement. In this paper, we present a graph derivation representation based approach (GDR) for stable semantic measurement, which captures structural semantics of ontologies and addresses those problems that cause unstable measurement of ontologies. This paper makes three original contributions. First, we introduce and define the concept of semantic measurement and the concept of stable measurement. We present the GDR based approach, a three-phase process to transform an ontology to its GDR. Second, we formally analyze important properties of GDRs based on which stable semantic measurement and comparison can be achieved successfully. Third but not the least, we compare our GDR based approach with existing graph based methods using a dozen real world exemplar ontologies. Our experimental comparison is conducted based on nine ontology measurement entities and distance metric, which stably compares the similarity of two ontologies in terms of their GDRs.

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.

Social networks continue to grow in size and the type of information hosted. We witness a growing interest in clustering a social network of people based on both their social relationships and their participations in activity based information networks. In this paper, we present a social influence based clustering framework for analyzing heterogeneous information networks with three unique features. First, we introduce a novel social influence based vertex similarity metric in terms of both self-influence similarity and co-influence similarity. We compute self-influence and co-influence based similarity based on social graph and its associated activity graphs and influence graphs respectively. Second, we compute the combined social influence based similarity between each pair of vertices by unifying the self-similarity and multiple co-influence similarity scores through a weight function with an iterative update method. Third, we design an iterative learning algorithm, SI-Cluster, to dynamically refine the K clusters by continuously quantifying and adjusting the weights on self-influence similarity and on multiple co-influence similarity scores towards the clustering convergence. To make SI-Cluster converge fast, we transformed a sophisticated nonlinear fractional programming problem of multiple weights into a straightforward nonlinear parametric programming problem of single variable. Our experiment results show that SI-Cluster not only achieves a better balance between self-influence and co-influence similarities but also scales extremely well for large graph clustering.

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.

The volume of RDF data continues to grow over the past decade and many known RDF datasets have billions of triples. A grant challenge of managing this huge RDF data is how to access this big RDF data efficiently. A popular approach to addressing the problem is to build a full set of permutations of (S, P, O) indexes. Although this approach has shown to accelerate joins by orders of magnitude, the large space overhead limits the scalability of this approach and makes it heavyweight. In this paper, we present TripleBit, a fast and compact system for storing and accessing RDF data. The design of TripleBit has three salient features. First, the compact design of TripleBit reduces both the size of stored RDF data and the size of its indexes. Second, TripleBit introduces two auxiliary index structures, ID-Chunk bit matrix and ID-Predicate bit matrix, to minimize the cost of index selection during query evaluation. Third, its query processor dynamically generates an optimal execution ordering for join queries, leading to fast query execution and effective reduction on the size of intermediate results. Our experiments show that TripleBit outperforms RDF-3X, MonetDB, BitMat on LUBM, UniProt and BTC 2012 benchmark queries and it offers orders of mangnitude performance improvement for some complex join queries.

With ubiquitous wireless connectivity and technological advances in mobile devices, we witness the growing demands and increasing market shares of mobile intelligent systems and technologies for real-time decision making and location-based knowledge discovery. Spatial alarms are considered as one of the fundamental capabilities for intelligent mobile location-based systems. Like time-based alarms that remind us the arrival of a future time point, spatial alarms remind us the arrival of a future spatial point. Existing approaches for scaling spatial alarm processing are focused on computing Alarm-Free Regions (A fr ) and Alarm-Free Period (A fp ) such that mobile objects traveling within an A fr can safely hibernate the alarm evaluation process for the computed A fp , to save battery power, until approaching the nearest alarm of interest. A key technical challenge in scaling spatial alarm processing is to efficiently compute A fr and A fp such that mobile objects traveling within an A fr can safely hibernate the alarm evaluation process during the computed A fp , while maintaining high accuracy. In this article we argue that on-demand computation of A fr is expensive and may not scale well for dense populations of mobile objects. Instead, we propose to maintain an index for both spatial alarms and empty regions (A fr ) such that for a given mobile user's location, we can find relevant spatial alarms and whether it is in an alarm-free region more efficiently. We also show that conventional spatial indexing methods, such as R-tree family, k -d tree, Quadtree, and Grid, are by design not well suited to index empty regions. We present Mondrian Tree – a region partitioning tree for indexing both spatial alarms and alarm-free regions. We first introduce the Mondrian Tree indexing algorithms, including index construction, search, and maintenance. Then we describe a suite of Mondrian Tree optimizations to further enhance the performance of spatial alarm processing. Our experimental evaluation shows that the Mondrian Tree index, as an intelligent technology for mobile systems, outperforms traditional index methods, such as R-tree, Quadtree, and k -d tree, for spatial alarm processing.

Social influences, the phenomena that one individual's actions can induce similar behaviors among his/her friends via their social ties, have been observed prevailingly in socially networked systems. While most existing work focuses on studying general, macro-level influence (e.g., diffusion); equally important is to understand social influence at microscopic scales (i.e., at the granularity of single individuals, actions, and time-stamps), which may benefit a range of applications. We propose μSI, a microscopic social-influence model wherein: individuals' actions are modeled as temporary interactions between social network (formed by individuals) and object network (formed by targets of actions); one individual's actions influence his/her friends in a dynamic, network-wise manner (i.e., dependent on both social and object networks). We develop for μSI a suite of novel inference tools that enable to answer questions of the form: How may an occurred interaction trigger another? More importantly, when and where may a new interaction be observed? We carefully address the computational challenges for inferencing over such semantically rich models by dynamically identifying sub-domains of interest and varying the precision of solutions over different sub-domains. We demonstrate the breadth and generality of μSI using two seemingly disparate applications. In the context of social tagging service, we show how it can help improve the accuracy and freshness of resource recommendation; in the context of mobile phone call service, we show how it can help improve the efficiency of paging operation.

Most proposed DHTs engage certain topology maintenance mechanisms specific to the static graphs on which they are based. The designs of these mechanisms are complicated and repeated with graph-relevant concerns. In this paper, we propose the “distributed line graphs” (DLG), a universal technique for designing DHTs based on arbitrary regular graphs. Using DLG, the main features of the initial graphs are preserved, and thus people can design a new DHT by simply choosing the graph with desirable features and applying DLG to it. We demonstrate the power of DLG by illustrating four DLG-enabled DHTs based on different graphs, namely, Kautz, de Bruijn, butterfly, and hypertree graphs. The effectiveness of our proposals is demonstrated through analysis, simulation, and implementation.

The past few years have witnessed an increasing demand for the next generation health information networks (e.g., NHIN[1]), which hold the promise of supporting large-scale information sharing across a network formed by autonomous healthcare providers. One fundamental capability of such information network is to support efficient, privacy-preserving (for both users and providers) search over the distributed, access controlled healthcare documents. In this paper we focus on addressing the privacy concerns of content providers; that is, the search should not reveal the specific association between contents and providers (a.k.a. content privacy). We propose SS-PPI, a novel privacy-preserving index abstraction, which, in conjunction of distributed access control-enforced search protocols, provides theoretically guaranteed protection of content privacy. Compared with existing proposals (e.g., flipping privacy-preserving index[2]), our solution highlights with a series of distinct features: (a) it incorporates access control policies in the privacy-preserving index, which improves both search efficiency and attack resilience; (b) it employs a fast index construction protocol via a novel use of the secrete-sharing scheme in a fully distributed manner (without trusted third party), requiring only constant (typically two) round of communication; (c) it provides information-theoretic security against colluding adversaries during index construction as well as query answering. We conduct both formal analysis and experimental evaluation of SS-PPI and show that it outperforms the state-of-the-art solutions in terms of both privacy protection and execution efficiency.

This paper presents MobiMix, a road network based mix-zone framework to protect location privacy of mobile users traveling on road networks. In contrast to spatial cloaking based location privacy protection, the approach in MobiMix is to break the continuity of location exposure by using mix-zones, where no applications can trace user movement. This paper makes two original contributions. First, we provide the formal analysis on the vulnerabilities of directly applying theoretical rectangle mix-zones to road networks in terms of anonymization effectiveness and attack resilience. We argue that effective mix-zones should be 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. Second, we develop a suite of road network mix-zone construction methods that provide higher level of attack resilience and yield a specified lower-bound on the level of anonymity. We evaluate the MobiMix approach through extensive experiments conducted on traces produced by GTMobiSim on different scales of geographic maps. Our experiments show that MobiMix offers high level of anonymity and high level of resilience to attacks compared to existing mix-zone approaches.

In location-based, mobile continual query (CQ) systems, two key measures of quality-of-service (QoS) are: freshness and accuracy. To achieve freshness, the CQ server must perform frequent query reevaluations. To attain accuracy, the CQ server must receive and process frequent position updates from the mobile nodes. However, it is often difficult to obtain fresh and accurate CQ results simultaneously, due to 1) limited resources in computing and communication and 2) fast-changing load conditions caused by continuous mobile node movement. Hence, a key challenge for a mobile CQ system is: How do we achieve the highest possible quality of the CQ results, in both freshness and accuracy, with currently available resources? In this paper, we formulate this problem as a load shedding one, and develop MobiQual—a QoS-aware approach to performing both update load shedding and query load shedding. The design of MobiQual highlights three important features. 1) Differentiated load shedding: We apply different amounts of query load shedding and update load shedding to different groups of queries and mobile nodes, respectively. 2) Per-query QoS specification: Individualized QoS specifications are used to maximize the overall freshness and accuracy of the query results. 3) Low-cost adaptation: MobiQual dynamically adapts, with a minimal overhead, to changing load conditions and available resources. We conduct a set of comprehensive experiments to evaluate the effectiveness of MobiQual. The results show that, through a careful combination of update and query load shedding, the MobiQual approach leads to much higher freshness and accuracy in the query results in all cases, compared to existing approaches that lack the QoS-awareness properties of MobiQual, as well as the solutions that perform query-only or update-only load shedding.

Monitoring global states of a distributed cloud application is a critical functionality for cloud datacenter management. State monitoring requires meeting two demanding objectives: high level of correctness, which ensures zero or low error rate, and high communication efficiency, which demands minimal communication cost in detecting state updates. Most existing work follows an instantaneous model which triggers state alerts whenever a constraint is violated. This model may cause frequent and unnecessary alerts due to momentary value bursts and outliers. Countermeasures of such alerts may further cause problematic operations. In this paper, we present a WIndow-based StatE monitoring (WISE) framework for efficiently managing cloud applications. Window-based state monitoring reports alerts only when state violation is continuous within a time window. We show that it is not only more resilient to value bursts and outliers, but also able to save considerable communication when implemented in a distributed manner based on four technical contributions. First, we present the architectural design and deployment options for window-based state monitoring with centralized parameter tuning. Second, we develop a new distributed parameter tuning scheme enabling WISE to scale to much more monitoring nodes as each node tunes its monitoring parameters reactively without global information. Third, we introduce two optimization techniques, including their design rationale, correctness and usage model, to further reduce the communication cost. Finally, we provide an in-depth empirical study of the scalability of WISE, and evaluate the improvement brought by the distributed tuning scheme and the two performance optimizations. Our results show that WISE reduces communication by 50-90 percent compared with instantaneous monitoring approaches, and the improved WISE gains a clear scalability advantage over its centralized version.

Privacy has been identified as a vital requirement in designing and implementing data mining systems. In general, privacy preservation demands protecting both input and output privacy: the former refers to sanitizing the raw data itself before performing mining; while the latter refers to preventing the mining output (models or patterns) from malicious inference attacks. This article presents a systematic study on the problem of protecting output privacy in data mining, and particularly, stream mining: (i) we highlight the importance of this problem by showing that even sufficient protection of input privacy does not guarantee that of output privacy; (ii) we present a general inferencing and disclosure model that exploits the intrawindow and interwindow privacy breaches in stream mining output; (iii) we propose a light-weighted countermeasure that effectively eliminates these breaches without explicitly detecting them, while minimizing the loss of output accuracy; (iv) we further optimize the basic scheme by taking account of two types of semantic constraints, aiming at maximally preserving utility-related semantics while maintaining hard privacy guarantee; (v) finally, we conduct extensive experimental evaluation over both synthetic and real data to validate the efficacy of our approach.

We present the design and implementation of a new indexing technique, Mondrian tree. The Mondrian tree indexing method partitions the entire universe of discourse into spatial alarm monitoring regions and alarm-free regions. This enables us to reduce the number of on-demand alarm-free region computations, significant savings of both server load and client-to-server communication cost. We evaluate the efficiency of the Mondrian tree indexing approach and show that the Mondrian tree offers significant performance enhancements on spatial alarm processing at both the server side and the client side.

Wireless Positioning Systems (WPS) are popular alternative localization methods, especially in dense urban areas where GPS has known limitations. Map-matching (MM) has been used as an approach to improve the accuracy of the estimated locations of WiFi Access Points (APs), and thus the accuracy of a wireless positioning system. Large-scale wireless positioning differs from satellite based positioning in at least two aspects: First, wireless positioning systems typically derive the location estimates based on war-driving access point (AP) data. Second, the locations of the AP beacons are not generally known at the same precision as that of the satellite locations. This results in lower accuracy and a lower confidence factor in the use of wireless positioning. This paper presents a fast selective look-ahead map-matching technique, called SLAMM. Existing MM algorithms developed for real-time location tracking of a moving vehicle are ill-suited for matching large collections of war-driving data due to the time complexity. Another unique feature of SLAMM is the map-matching of critical location samples in an AP trace to the road network before matching non-critical samples. Our experiments over a real dataset of 70 million AP samples show that SLAMM is accurate and significantly faster than the traditional MM approaches.

Monitoring global states of an application deployed over distributed nodes becomes prevalent in today's datacenters. State monitoring requires not only correct monitoring results but also minimum communication cost for efficiency and scalability. Most existing work adopts an instantaneous state monitoring approach, which triggers state alerts whenever a constraint is violated. Such an approach, however, may cause frequent and unnecessary state alerts due to unpredictable monitored value bursts and momentary outliers that are common in large-scale Internet applications. These false alerts may further lead to expensive and problematic counter-measures. To address this issue, we introduce window-based state monitoring in this paper. Window-based state monitoring evaluates whether state violation is continuous within a time window, and thus, gains immunity to short-term value bursts and outliers. Furthermore, we find that exploring the monitoring time window at distributed nodes achieves significant communication savings over instantaneous monitoring. Based on this finding, we develop WISE, a system that efficiently performs WIndow-based StatE monitoring at datacenter-scale. WISE is highlighted with three sets of techniques. First, WISE uses distributed filtering time windows and intelligently avoids global information collecting to achieve communication efficiency, while guaranteeing monitoring correctness at the same time. Second, WISE provides a suite of performance tuning techniques to minimize communication cost based on a sophisticated cost model. Third, WISE also employs a set of novel performance optimization techniques. Extensive experiments over both real world and synthetic traces show that WISE achieves a 50% - 90% reduction in communication cost compared with existing instantaneous monitoring approaches and simple alternative schemes.

As a severe threat in anonymized data publication, proximity breach is gaining increasing attention. Such breach occurs when an attacker learns with high confidence that the sensitive information of a victim associates with a set of semantically proximate values, even though not sure about the exact one. Recently (¿, ¿)-dissimilarity [14] has been proposed as an effective countermeasure against general proximity attack. In this paper, we present a detailed analytical study on the fulfillment of this principle, derive criteria to efficiently test its satisfiability for given microdata, and point to a novel anonymization model, XCOLOR, with theoretical guarantees on both operation efficiency and utility preservation.

Mobile commerce and location based services (LBS) are some of the fastest growing IT industries in the last five years. Location update of mobile clients is a fundamental capability in mobile commerce and all types of LBS. Higher update frequency leads to higher accuracy, but incurs unacceptably high cost of location management at the location servers. We propose RoadTrack -- a road-network based, query-aware location update framework with two unique features. First, we introduce the concept of precincts to control the granularity of location update resolution for mobile clients that are not of interest to any active location query services. Second, we define query encounter points for mobile objects that are targets of active location query services, and utilize these encounter points to define the adequate location update schedule for each mobile. The RoadTrack framework offers three unique advantages. First, encounter points as a fundamental query awareness mechanism enable us to control and differentiate location update strategies for mobile clients in the vicinity of active location queries, while meeting the needs of location query evaluation. Second, we employ system-defined precincts to manage the desired spatial resolution of location updates for different mobile clients and to control the scope of query awareness to be capitalized by a location update strategy. Third, our road-network based check-free interval optimization further enhances the effectiveness of the Road-Track query-aware location update scheduling algorithm. This optimization provides significant cost reduction for location update management at both mobile clients and location servers. We evaluate the RoadTrack location update approach using a real world road-network based mobility simulator. Our experimental results demonstrate that the RoadTrack query aware location update approach outperforms existing representative location update strategies in terms of both client energy efficiency and server processing load.

With the popularity of voting systems in cyberspace, there is growing evidence that current voting systems can be manipulated by fake votes. This problem has attracted many researchers working on guarding voting systems in two areas: relieving the effect of dishonest votes by evaluating the trust of voters, and limiting the resources that can be used by attackers, such as the number of voters and the number of votes. In this paper, we argue that powering voting systems with trust and limiting attack resources are not enough. We present a novel attack named as Reputation Trap (RepTrap). Our case study and experiments show that this new attack needs much less resources to manipulate the voting systems and has a much higher success rate compared with existing attacks. We further identify the reasons behind this attack and propose two defense schemes accordingly. In the first scheme, we hide correlation knowledge from attackers to reduce their chance to affect the honest voters. In the second scheme, we introduce robustness-of-evidence, a new metric, in trust calculation to reduce their effect on honest voters. We conduct extensive experiments to validate our approach. The results show that our defense schemes not only can reduce the success rate of attacks but also significantly increase the amount of resources an adversary needs to launch a successful attack.

This work presents a systematic study of the problem of protecting general proximity privacy, with findings applicable to most existing data models. Our contributions are multi-folded: we highlighted and formulated proximity privacy breaches in a data-model-neutral manner; we proposed a new privacy principle (epsiv,delta)k-dissimilarity, with theoretically guaranteed protection against linking attacks in terms of both exact and proximate QI-SA associations; we provided a theoretical analysis regarding the satisfiability of (epsiv,delta)k-dissimilarity, and pointed to promising solutions to fulfilling this principle.

Modern communication networks generate massive volume of operational event data, e.g., alarm, alert, and metrics, which can be used by a network management system (NMS) to diagnose potential faults. In this work, we introduce a new class of indexable fault signatures that encode temporal evolution of events generated by a network fault as well as topological relationships among the nodes where these events occur. We present an efficient learning algorithm to extract such fault signatures from noisy historical event data, and with the help of novel space-time indexing structures, we show how to perform efficient, online signature matching. We provide results from extensive experimental studies to explore the efficacy of our approach and point out potential applications of such signatures for many different types of networks including social and information networks.

Consider a mobile client who travels over roads and wishes to receive location-based services (LBS) from untrusted service providers. How might the user obtain such services without exposing her private position information? Meanwhile, how could the privacy protection mechanism incur no disincentive, e.g., excessive computation or communication cost, for any service provider or mobile user to participate in such a scheme? We detail this problem and present a general model for privacy-aware mobile services. A series of key features distinguish our solution from existing ones: a) it adopts the network-constrained mobility model (instead of the conventional random-waypoint model) to capture the privacy vulnerability of mobile users; b) it regards the attack resilience (for mobile users) and the query-processing cost (for service providers) as two critical measures for designing location privatization solutions, and provides corresponding analytical models; c) it proposes a robust and scalable location anonymization model, XStar, which best leverages the two measures; d) it introduces multi-folded optimizations in implementing XStar, which lead to further performance improvement. A comprehensive experimental evaluation is conducted to validate the analytical models and the efficacy of XStar.

With fast-paced growth of digital data and exploding storage management costs, enterprises are looking for new ways to effectively manage their data. One such cost-effective paradigm is the cloud storage model also referred to as Storage-as-a-Service, in which enterprises outsource their storage to a storage service provider (SSP) by storing data (usually encrypted) at a remote SSP-managed site and accessing it over a high speed network. Along with storage capacity used, the SSP often charges clients on the amount of data that is accessed from the SSP site. Thus, it is in the interest of the client enterprise to download only relevant content. This makes search over outsourced storage an important capability. Searching over encrypted outsourced storage, however, is a complex challenge. Each enterprise has different access privileges for different users and this access control needs to be preserved during search (for example, ensuring that a user cannot search through data that is inaccessible from the filesystem due to its permissions). Secondly, the search mechanism has to preserve confidentiality from the SSP and indices can not be stored in plain text. In this article, we present a new filesystem search technique that integrates access control and indexing/search mechanisms into a unified framework to support access control aware search. Our approach performs indexing within the trusted enterprise domain and uses a novel access control barrel (ACB) primitive to encapsulate access control within these indices. The indices are then systematically encrypted and shipped to the SSP for hosting. Unlike existing enterprise search techniques, our approach is resilient to various common attacks that leak private information. Additionally, to the best of our knowledge, our approach is a first such technique that allows search indices to be hosted at the SSP site, thus effectively providing search-as-a-service . This does not require the client enterprise to fully trust the SSP for data confidentiality. We describe the architecture and implementation of our approach and a detailed experimental analysis comparing with other approaches.

Freshness and accuracy are two key measures of quality of service (QoS) in location-based, mobile continual queries (CQs). However, it is often difficult to provide both fresh and accurate CQ results due to (a) limited resources in computing and communication and (b) fast-changing load conditions caused by continuous mobile node movement. Thus a key challenge for a mobile CQ system is: How do we achieve the highest possible quality of the query results, in both freshness and accuracy, with currently available resources under changing load conditions? In this paper, we formulate this problem as a load shedding one, and develop MobiQual - a QoS-aware framework for performing both update load shedding and query load shedding. The design of MobiQual highlights three important features. (1)Differentiatedloadshedding: Different amounts of query and update load shedding are applied to different groups of queries and mobile nodes, respectively. (2)Per-queryQoSspecifications: The overall freshness and accuracy of the query results are maximized with individualized QoS specifications. (3)Low-costadaptation: MobiQual dynamically adapts, with a minimal overhead, to changing load conditions and available resources. We show that, through a careful combination of update and query load shedding, the MobiQual approach leads to much higher freshness and accuracy in the query results in all cases, compared to existing approaches.

With fast paced growth of digital data and exploding storage management costs, enterprises are looking for new ways to effectively manage their data. One such cost-effective paradigm is the storage-as-a-service model, in which enterprises outsource their storage to a storage service provider (SSP) by storing data at a remote SSP-managed site and accessing it over a high speed network. Often for a variety of reasons, enterprises find it unacceptable to fully trust the SSP and prefer to store data in an encrypted form. This typically limits collaboration and data sharing among enterprise users due to complex key management and access control challenges. In this paper, we propose a platform called SHAROES that provides data sharing capability over such outsourced storage environments. SHAROES provide rich *nix-like data sharing semantics over SSP stored data, without trusting the SSP for data confidentiality or access control. SHAROES is unique in its ability in reducing user involvement during setup and operation through the use of in-band key management and allows a near-seamless transition of existing storage environments to the new model. It is also superior in performance by minimizing the use of expensive public-key cryptography in metadata management. We present the architecture and implementation of various SHAROES components and our experiments demonstrate performance superior to other proposals by over 40% on a number of benchmarks.

Privacy preservation in data mining demands protecting both input and output privacy. The former refers to sanitizing the raw data itself before performing mining. The latter refers to preventing the mining output (model/pattern) from malicious pattern-based inference attacks. The preservation of input privacy does not necessarily lead to that of output privacy. This work studies the problem of protecting output privacy in the context of frequent pattern mining over data streams. After exposing the privacy breaches existing in current stream mining systems, we propose Butterfly, a light-weighted countermeasure that can effectively eliminate these breaches without explicitly detecting them, meanwhile minimizing the loss of the output accuracy. We further optimize the basic scheme by taking account of two types of semantic constraints, aiming at maximally preserving utility-related semantics while maintaining the hard privacy and accuracy guarantee. We conduct extensive experiments over real- life datasets to show the effectiveness and efficiency of our approach.

This paper presents PrivacyGrid - a framework for supporting anonymous location-based queries in mobile information delivery systems. The PrivacyGrid framework offers three unique capabilities. First, it provides a location privacy protection preference profile model, called location P3P, which allows mobile users to explicitly define their preferred location privacy requirements in terms of both location hiding measures (e.g., location k-anonymity and location l-diversity) and location service quality measures (e.g., maximum spatial resolution and maximum temporal resolution). Second, it provides fast and effective location cloaking algorithms for location k-anonymity and location l-diversity in a mobile environment. We develop dynamic bottom-up and top-down grid cloaking algorithms with the goal of achieving high anonymization success rate and efficiency in terms of both time complexity and maintenance cost. A hybrid approach that carefully combines the strengths of both bottom-up and top-down cloaking approaches to further reduce the average anonymization time is also developed. Last but not the least, PrivacyGrid incorporates temporal cloaking into the location cloaking process to further increase the success rate of location anonymization. We also discuss PrivacyGrid mechanisms for supporting anonymous location queries. Experimental evaluation shows that the PrivacyGrid approach can provide close to optimal location k-anonymity as defined by per user location P3P without introducing significant performance penalties.

We propose the SocialTrust framework for tamper-resilient trust establishment in online social networks. Two of the salient features of SocialTrust are its dynamic revision of trust by (i) distinguishing relationship quality from trust; and (ii) incorporating a personalized feedback mechanism for adapting as the social network evolves.

This paper investigates the strategic decisions of online vendors for offering different mechanism, such as sampling and online reviews of information products, to increase their online sales. Focusing on measuring the effectiveness of electronic market design (offering reviews, sampling, or both), our study shows that online markets behavior as communication markets, and consumers learn product quality information both passively (reading online reviews) and actively but subjectively (listening to music sampling). Using data from Amazon, first we show that sampling along is a strong product quality signal that reduces the product uncertainty after controlling for halo effect. In general, products with sampling option enjoy a higher conversion rate (which leads to better sales) than those without sampling because sampling decreases the uncertainty of consuming experience goods. Second, the impact of online reviews on sales conversion rate is lower for experience goods with a sampling option than those without. Third, when the uncertainty of the societal reviews is higher, sampling plays a more important role because it mitigates such uncertainty introduced by online reviews.

Recently, we have seen increasing numbers of denial of service (DoS) attacks against online services and Web applications either for extortion reasons or for impairing and even disabling the competition. These DoS attacks have increasingly targeted the application level. Application-level DoS attacks emulate the same request syntax and network-level traffic characteristics as those of legitimate clients, thereby making the attacks much harder to detect and counter. Moreover, such attacks often target bottleneck resources such as disk bandwidth, database bandwidth, and CPU resources. In this article, we propose handling DoS attacks by using a twofold mechanism. First, we perform admission control to limit the number of concurrent clients served by the online service. Admission control is based on port hiding that renders the online service invisible to unauthorized clients by hiding the port number on which the service accepts incoming requests. Second, we perform congestion control on admitted clients to allocate more resources to good clients. Congestion control is achieved by adaptively setting a client's priority level in response to the client's requests in a way that can incorporate application-level semantics. We present a detailed evaluation of the proposed solution using two sample applications: Apache HTTPD and the TPCW benchmark (running on Apache Tomcat and IBM DB2). Our experiments show that the proposed solution incurs low performance overhead and is resilient to DoS attacks.

We describe DSphere - a decentralized system for crawling, indexing, searching and ranking of documents in the World Wide Web. Unlike most of the existing search technologies that depend heavily on a page-centric view of the Web, we advocate a source-centric view of the Web and propose a decentralized architecture for crawling, indexing and searching the Web in a distributed source-specific fashion. A fully decentralized crawler is developed to crawl the World Wide Web where each peer is assigned the responsibility of crawling a specific set of documents referred to as a source collection. Link analysis techniques are used for ranking documents. Traditional link analysis techniques suffer from problems like slow refresh rate and vulnerabilities to Web Spam. We propose a source-based link analysis approach, which computes fast and accurate ranking scores for all crawled documents.

To provide high-quality results for location-based, continual queries (CQs) in a mobile system, the query processor usually demands receiving frequent position updates from the mobile nodes. However, processing frequent updates often causes the query processor to become overloaded, under which updates must be dropped randomly, bringing down the query-result accuracy and negating the benefits of frequent updates. In this paper, we develop LIRA - a lightweight, region-aware load-shedding technique for preventively reducing the position-update load of a query processor, while maintaining high-quality query results. Instead of receiving too many updates and then randomly dropping some of them, LIRA uses a region-aware partitioning mechanism to identify the most beneficial shedding regions to cut down the position updates sent by the mobile nodes within those regions. Based on the densities of mobile nodes and queries in a region, LIRA judiciously applies different amounts of update reduction for different regions, aiming to minimize the negative impacts of load shedding on query-result accuracy. Experimental results show that LIRA is vastly superior to random update dropping and clearly outperforms other alternatives that do not possess region-aware load-shedding capabilities. Moreover, due to its lightweight nature, LIRA introduces very little overhead.

Tuple dropping, though commonly used for load shedding in most stream operations, is inadequate for m-way, windowed stream joins. The join output rate can be overly reduced because it fails to exploit the time correlations likely to exist among interrelated streams. In this paper, we introduce GrubJoin; an adaptive, m-way, windowed stream join that effectively performs time correlation-aware CPU load shedding. GrubJoin maximizes the output rate by achieving near-optimal window harvesting, which picks only the most profitable window segments for the join. Due to combinatorial explosion of possible m-way join sequences involving window segments, m-way, windowed stream joins pose several unique challenges. We focus on addressing two of them: (1) How can we quickly determine the optimal window harvesting configuration for any m-way, windowed stream join? (2) How can we monitor and learn the time correlations among the streams with high accuracy and minimal overhead? To tackle these challenges, we formalize window harvesting as an optimization problem, develop greedy heuristics to determine near-optimal window harvesting configurations and use approximation techniques to capture the time correlations. Our experimental results show that GrubJoin is vastly superior to tuple dropping when time correlations exist and is equally effective when time correlations are nonexistent.

Data perturbation is a popular technique for privacy-preserving data mining. The major challenge of data perturbation is balancing privacy protection and data quality, which are normally considered as a pair of contradictive factors. We propose that selectively preserving only the task/model specific information in perturbation would improve the balance. Geometric data perturbation, consisting of random rotation perturbation, random translation perturbation, and noise addition, aims at preserving the important geometric properties of a multidimensional dataset, while providing better privacy guarantee for data classification modeling. The preliminary study has shown that random geometric perturbation can well preserve model accuracy for several popular classification models, including kernel methods, linear classifiers, and SVM classifiers, while it also revealed some security concerns to random geometric perturbation. In this paper, we address some potential attacks to random geometric perturbation and design several methods to reduce the threat of these attacks. Experimental study shows that the enhanced geometric perturbation can provide satisfactory privacy guarantee while still well preserving model accuracy for the discussed data classification models.

Tuple dropping, though commonly used for load shedding in most data stream operations, is generally inadequate for multiway windowed stream joins. The join output rate can be unnecessarily reduced because tuple dropping fails to exploit the time correlations that are likely to exist among interrelated streams. In this paper, we introduce GrubJoin-an adaptive multiway windowed stream join that effectively performs time correlation-aware CPU load shedding. GrubJoin maximizes the output rate by achieving near-optimal window harvesting, which picks only the most profitable segments of individual windows for the join. Due mainly to the combinatorial explosion of possible multiway join sequences involving different window segments, GrubJoin faces unique challenges that do not exist for binary joins, such as determining the optimal window harvesting configuration in a time-efficient manner and learning the time correlations among the streams without introducing overhead. To tackle these challenges, we formalize window harvesting as an optimization problem, develop greedy heuristics to determine near-optimal window harvesting configurations, and use approximation techniques to capture the time correlations. Our experimental results show that GrubJoin is vastly superior to tuple dropping when time correlations exist and is equally effective when time correlations are nonexistent.

In recent years, edge computing has emerged as a popular mechanism to deliver dynamic Web content to clients. However, many existing edge cache networks have not been able to harness the full potential of edge computing technology. In this paper, we argue and experimentally demonstrate that cooperation among the individual edge caches coupled with scalable server-driven document consistency mechanisms can significantly enhance the capabilities and performance of edge cache networks in delivering fresh dynamic content. However, designing large-scale cooperative edge cache networks presents many research challenges. Toward addressing these challenges, this paper presents cooperative edge cache grid (cooperative EC grid, for short)-a large-scale cooperative edge cache network for efficiently delivering highly dynamic Web content with varying server update frequencies. The design of the cooperative EC grid focuses on the scalability and reliability of dynamic content delivery in addition to cache hit rates, and it incorporates several novel features. We introduce the concept of cache clouds as a generic framework of cooperation in large-scale edge cache networks. The architectural design of the cache clouds includes dynamic hashing-based document lookup and update protocols, which dynamically balance lookup and update loads among the caches in the cloud. We also present cooperative techniques for making the document lookup and update protocols resilient to the failures of individual caches. This paper reports a series of simulation-based experiments which show that the overheads of cooperation in the cooperative EC grid are very low, and our architecture and techniques enhance the performance of the cooperative edge networks.

Distributed privacy preserving data mining tools are critical for mining multiple databases with a minimum information disclosure. We present a framework including a general model as well as multi-round algorithms for mining horizontally partitioned databases using a privacy preserving k Nearest Neighbor (kNN) classifier.

It is widely recognized that developing efficient and fully automated algorithms for clustering large transactional datasets is a challenging problem. In this paper, we propose a fast, memory-efficient, and scalable clustering algorithm for analyzing transactional data. Our approach has three unique features. First, we use the concept of Weighted Coverage Density as a categorical similarity measure for efficient clustering of transactional datasets. The concept of weighted coverage density is intuitive and allows the weight of each item in a cluster to be changed dynamically according to the occurrences of items. Second, we develop two transactional data clustering specific evaluation metrics based on the concept of large transactional items and the coverage density respectively. Third, we implement the weighted coverage density clustering algorithm and the two clustering validation metrics using a fully automated transactional clustering framework, called SCALE (Sampling, Clustering structure Assessment, cLustering and domain-specific Evaluation). The SCALE framework is designed to combine the weighted coverage density measure for clustering over a sample dataset with self-configuring methods that can automatically tune the two important parameters of the clustering algorithms: (1) the candidates of the best number K of clusters; and (2) the application of two domain-specific cluster validity measures to find the best result from the set of clustering results. We have conducted experimental evaluation using both synthetic and real datasets and our results show that the weighted coverage density approach powered by the SCALE framework can efficiently generate high quality clustering results in a fully automated manner.

Analyzing clustering structures in data streams can provide critical information for making decision in realtime. In this paper, we present a framework for detecting the change of critical clustering structure in categorical data streams. The framework consists of the Hierarchical Entropy Tree structure (HE-Tree) and the extended ACE clustering algorithm. HE-Tree can efficiently capture the entropy property of the categorical data streams and allow us to draw precise clustering information from the data stream for high-quality BkPLots with the extended ACE algorithm.

We present an adaptive distributed query-sampling framework that is quality-conscious for extracting high-quality text database samples. The framework divides the query-based sampling process into an initial seed sampling phase and a quality-aware iterative sampling phase. In the second phase the sampling process is dynamically scheduled based on estimated database size and quality parameters derived during the previous sampling process. The unique characteristic of our adaptive query-based sampling framework is its self-learning and self-configuring ability based on the overall quality of all text databases under consideration. We introduce three quality-conscious sampling schemes for estimating database quality, and our initial results show that the proposed framework supports higher-quality document sampling than existing approaches.

We consider the problem of distributed continuous data delivery services in an overlay network of heterogeneous nodes. Each node in the system can be a source for any number of data streams and at the same time be a consumer node that is receiving streams sourced at other nodes. A consumer node may define a filter on a source stream such that only the desired portion of the stream is delivered, minimizing the amount of unnecessary bandwidth consumption. By heterogeneous, we mean that nodes not only may have varying network bandwidths and computing resources but also different interests in terms of the filters and the rates of the data streams they are interested in. Our objective is to construct an efficient stream delivery network in which nodes cooperate in forwarding data streams in the presence of constrained resources. We formalize this distributed stream delivery problem as an optimization one by starting with a simple setup where the network topology is fixed and node bandwidth characteristics are known. The goal of the optimization is to find valid delivery graphs with minimum bandwidth consumption. We extend this problem formulation to QoS-aware stream delivery, in order to handle the bandwidth constrained cases in which unwanted drops and delays are inevitable. We provide a classification of delivery graph construction schemes, and in light of this classification we develop pragmatic quality-aware stream delivery (QASD) algorithms. These algorithms aim at constructing efficient stream delivery graphs in a distributed setting, where global knowledge is not available and network characteristics are not known in advance. We introduce a set of evaluation metrics and provide experimental results to illustrate the effectiveness of our proposed algorithms under these metrics.

This paper describes a motion-adaptive indexing scheme for efficient evaluation of moving continual queries (MCQs) over moving objects. It uses the concept of motion-sensitive bounding boxes (MSBs) to model moving objects and moving queries. These bounding boxes automatically adapt their sizes to the dynamic motion behaviors of individual objects. Instead of indexing frequently changing object positions, we index less frequently changing object and query MSBs, where updates to the bounding boxes are needed only when objects and queries move across the boundaries of their boxes. This helps decrease the number of updates to the indexes. More importantly, we use predictive query results to optimistically precalculate query results, decreasing the number of searches on the indexes. Motion-sensitive bounding boxes are used to incrementally update the predictive query results. Furthermore, we introduce the concepts of guaranteed safe radius and optimistic safe radius to extend our motion-adaptive indexing scheme to evaluating moving continual k-nearest neighbor (kNN) queries. Our experiments show that the proposed motion-adaptive indexing scheme is efficient for the evaluation of both moving continual range queries and moving continual kNN queries.

With continued advances in communication network technology and sensing technology, there is astounding growth in the amount of data produced and made available through cyberspace. Efficient and high-quality clustering of large datasets continues to be one of the most important problems in large-scale data analysis. A commonly used methodology for cluster analysis on large datasets is the three-phase framework of sampling/summarization, iterative cluster analysis, and disk-labeling. There are three known problems with this framework which demand effective solutions. The first problem is how to effectively define and validate irregularly shaped clusters, especially in large datasets. Automated algorithms and statistical methods are typically not effective in handling these particular clusters. The second problem is how to effectively label the entire data on disk (disk-labeling) without introducing additional errors, including the solutions for dealing with outliers, irregular clusters, and cluster boundary extension. The third obstacle is the lack of research about issues related to effectively integrating the three phases. In this article, we describe iVIBRATE---an interactive visualization-based three-phase framework for clustering large datasets. The two main components of iVIBRATE are its VISTA visual cluster-rendering subsystem which invites human interplay into the large-scale iterative clustering process through interactive visualization, and its adaptive ClusterMap labeling subsystem which offers visualization-guided disk-labeling solutions that are effective in dealing with outliers, irregular clusters, and cluster boundary extension. Another important contribution of iVIBRATE development is the identification of the special issues presented in integrating the two components and the sampling approach into a coherent framework, as well as the solutions for improving the reliability of the framework and for minimizing the amount of errors generated within the cluster analysis process. We study the effectiveness of the iVIBRATE framework through a walkthrough example dataset of a million records and we experimentally evaluate the iVIBRATE approach using both real-life and synthetic datasets. Our results show that iVIBRATE can efficiently involve the user in the clustering process and generate high-quality clustering results for large datasets.

We present an adaptive load shedding approach for windowed stream joins. In contrast to the conventional approach of dropping tuples from the input streams, we explore the concept of selective processing for load shedding. We allow stream tuples to be stored in the windows and shed excessive CPU load by performing the join operations, not on the entire set of tuples within the windows, but on a dynamically changing subset of tuples that are learned to be highly beneficial. We support such dynamic selective processing through three forms of runtime adaptations: adaptation to input stream rates, adaptation to time correlation between the streams and adaptation to join directions. Indexes are used to further speed up the execution of stream joins. Experiments are conducted to evaluate our adaptive load shedding in terms of output rate. The results show that our selective processing approach to load shedding is very effective and significantly outperforms the approach that drops tuples from the input streams.

Data perturbation techniques are one of the most popular models for privacy preserving data mining (Agrawal and Srikant, 2000; Aggarwal and Yu, 2004). It is especially convenient for applications where the data owners need to export/publish the privacy-sensitive data. A data perturbation procedure can be simply described as follows. Before the data owner publishes the data, they randomly change the data in certain way to disguise the sensitive information while preserving the particular data property that is critical for building the data models. Several perturbation techniques have been proposed recently, among which the most typical ones are randomization approach (Agrawal and Srikant, 2000) and condensation approach (Aggarwal and Yu, 2004).

Reputation systems have been popular in estimating the trustworthiness and predicting the future behavior of nodes in a large-scale distributed system where nodes may transact with one another without prior knowledge or experience. One of the fundamental challenges in distributed reputation management is to understand vulnerabilities and develop mechanisms that can minimize the potential damages to a system by malicious nodes. In this paper, we identify three vulnerabilities that are detrimental to decentralized reputation management and propose TrustGuard - a safeguard framework for providing a highly dependable and yet efficient reputation system. First, we provide a dependable trust model and a set of formal methods to handle strategic malicious nodes that continuously change their behavior to gain unfair advantages in the system. Second, a transaction based reputation system must cope with the vulnerability that malicious nodes may misuse the system by flooding feedbacks with fake transactions. Third, but not least, we identify the importance of filtering out dishonest feedbacks when computing reputation-based trust of a node, including the feedbacks filed by malicious nodes through collusion. Our experiments show that, comparing with existing reputation systems, our framework is highly dependable and effective in countering malicious nodes regarding strategic oscillating behavior, flooding malevolent feedbacks with fake transactions, and dishonest feedbacks.

This paper presents the QA-Pagelet as a fundamental data preparation technique for large-scale data analysis of the deep Web. To support QA-Pagelet extraction, we present the Thor framework for sampling, locating, and partioning the QA-Pagelets from the deep Web. Two unique features of the Thor framework are 1) the novel page clustering for grouping pages from a deep Web source into distinct clusters of control-flow dependent pages and 2) the novel subtree filtering algorithm that exploits the structural and content similarity at subtree level to identify the QA-Pagelets within highly ranked page clusters. We evaluate the effectiveness of the Thor framework through experiments using both simulation and real data sets. We show that Thor performs well over millions of deep Web pages and over a wide range of sources, including e-commerce sites, general and specialized search engines, corporate Web sites, medical and legal resources, and several others. Our experiments also show that the proposed page clustering algorithm achieves low-entropy clusters, and the subtree filtering algorithm identifies QA-Pagelets with excellent precision and recall.

Constructing Web pages from fragments has been shown to provide significant benefits for both content generation and caching. In order for a Web site to use fragment-based content generation, however, good methods are needed for fragmenting the Web pages. Manual fragmentation of Web pages is expensive, error prone, and unscalable. This paper proposes a novel scheme to automatically detect and flag fragments that are cost-effective cache units in Web sites serving dynamic content. Our approach analyzes Web pages with respect to their information sharing behavior, personalization characteristics, and change patterns. We identify fragments which are shared among multiple documents or have different lifetime or personalization characteristics. Our approach has three unique features. First, we propose a framework for fragment detection, which includes a hierarchical and fragment-aware model for dynamic Web pages and a compact and effective data structure for fragment detection. Second, we present an efficient algorithm to detect maximal fragments that are shared among multiple documents. Third, we develop a practical algorithm that effectively detects fragments based on their lifetime and personalization characteristics. This paper shows the results when the algorithms are applied to real Web sites. We evaluate the proposed scheme through a series of experiments, showing the benefits and costs of the algorithms. We also study the impact of using the fragments detected by our system on key parameters such as disk space utilization, network bandwidth consumption, and load on the origin servers.

With the rapid increase of data in many areas, clustering on large datasets has become an important problem in data analysis. Since cluster is a highly iterative process, cluster on large datasets prefers short iteration on a relatively small representative set. Thus, a two-phase framework sampling/summarization - iterative cluster analysis is often applied in practice. Since the clustering result only labels the small representative set, there are problems with extending the result to the entire large dataset, which are almost ignored by the traditional clustering research. This extending is often named as labeling process. Labeling irregular shaped clusters, distinguishing outliers and extending cluster boundary are the main problems in this stage. We address these problems and propose a visualization-based approach to dealing with them precisely. This approach partially involves human into the process of defining and refining the structure ClusterMap. Based on this structure, the ClusterMap algorithm scans the large dataset to adapt the boundary extension and generate the cluster labels for the entire dataset. Experimental result shows that ClusterMap can preserve cluster quality considerably with low computational cost, compared to the distance-comparison-based labeling algorithms.

This paper describes a motion adaptive indexing scheme for efficient evaluation of moving continual queries (MCQs) over moving objects. It uses the concept of motion-sensitive bounding boxes (MSBs) to model moving objects and moving queries. These bounding boxes automatically adapt their sizes to the dynamic motion behaviors of individual objects. Instead of indexing frequently changing object positions, we index less frequently changing object and query MSBs, where updates to the bounding boxes are needed only when objects and queries move across the boundaries of their boxes. This helps decrease the number of updates to the indexes. More importantly, we use predictive query results to optimistically precalculate query results, decreasing the number of searches on the indexes. Motion-sensitive bounding boxes are used to incrementally update the predictive query results. Our experiments show that the proposed motion adaptive indexing scheme is efficient for the evaluation of moving continual range queries.

We introduce the concept of a QA-Pagelet to refer to the content region in a dynamic page that contains query matches. We present THOR, a scalable and efficient mining system for discovering and extracting QA-Pagelets from the deep Web. A unique feature of THOR is its two-phase extraction framework. In the first phase, pages from a deep Web site are grouped into distinct clusters of structurally-similar pages. In the second phase, pages from each page cluster are examined through a subtree filtering algorithm that exploits the structural and content similarity at subtree level to identify the QA-Pagelets.

Dividing web pages into fragments has been shown to provide significant benefits for both content generation and caching. In order for a web site to use fragment-based content generation, however, good methods are needed for dividing web pages into fragments. Manual fragmentation of web pages is expensive, error prone, and unscalable. This paper proposes a novel scheme to automatically detect and flag fragments that are cost-effective cache units in web sites serving dynamic content. We consider the fragments to be interesting if they are shared among multiple documents or they have different lifetime or personalization characteristics. Our approach has three unique features. First, we propose a hierarchical and fragment-aware model of the dynamic web pages and a data structure that is compact and effective for fragment detection. Second, we present an efficient algorithm to detect maximal fragments that are shared among multiple documents. Third, we develop a practical algorithm that effectively detects fragments based on their lifetime and personalization characteristics. We evaluate the proposed scheme through a series of experiments, showing the benefits and costs of the algorithms. We also study the impact of adopting the fragments detected by our system on disk space utilization and network bandwidth consumption.

We introduce the ActivityFlow specification language for flexible specification, composition, and coordination of workflow activities. The most interesting features of the ActivityFlow specification language include: (1) a collection of specification mechanisms, allowing workflow designers to use a uniform workflow specification interface to describe different types (i.e., ad-hoc, administrative, or production) of workflows involved in their organizational processes– this feature helps to increase the flexibility of workflow processes in accommodating various types of changes; (2) a set of activity modeling facilities, enabling workflow designers to describe the flow of work declaratively and incrementally, allowing to reason about correctness and security of complex workflow activities independently from their underlying implementation mechanisms; (3) an open architecture that supports user interaction as well as collaboration of workflow systems of different organizations, and a set of workflow activity restructuring operators to respond to dynamic changes of workflow activities. We end the paper with a series of simulation-based experiments that demonstrate the effectiveness of these restructuring operators and the implementation architecture of the ActivityFlow system.

The sharing of caches among proxies is an important technique to reduce Web traffic, alleviate network bottlenecks, and improve response time of document requests. Most existing work on cooperative caching has been focused on serving misses collaboratively. Very few have studied the effect of cooperation on document placement schemes and its potential enhancements on cache hit ratio and latency reduction. We propose a new document placement scheme which takes into account the contentions at individual caches in order to limit the replication of documents within a cache group and increase document hit ratio. The main idea of this new scheme is to view the aggregate disk space of the cache group as a global resource of the group and uses the concept of cache expiration age to measure the contention of individual caches. The decision of whether to cache a document at a proxy is made collectively among the caches that already have a copy of this document. We refer to this new document placement scheme as the Expiration Age-based scheme (EA scheme). The EA scheme effectively reduces the replication of documents across the cache group, while ensuring that a copy of the document always resides in a cache where it is likely to stay for the longest time. We report our study on the potentials and limits of the EA scheme using both analytic modeling and trace-based simulation. The analytical model compares and contrasts the existing (ad hoc) placement scheme of cooperative proxy caches with our new EA scheme and indicates that the EA scheme improves the effectiveness of aggregate disk usage, thereby increasing the average time duration for which documents stay in the cache. The trace-based simulations show that the EA scheme yields higher hit rates and better response times compared to the existing document placement schemes used in most of the caching proxies.

Peer-to-peer (P2P) online communities are commonly perceived as an environment offering both opportunities and threats. One way to minimize threats in such communities is to use community-based reputations to help estimate the trustworthiness of peers. We present PeerTrust - a reputation-based trust supporting framework, which includes a coherent adaptive trust model for quantifying and comparing the trustworthiness of peers based on a transaction-based feedback system, and a decentralized implementation of such a model over a structured P2P network. PeerTrust model has two main features. First, we introduce three basic trust parameters and two adaptive factors in computing trustworthiness of peers, namely, feedback a peer receives from other peers, the total number of transactions a peer performs, the credibility of the feedback sources, transaction context factor, and the community context factor. Second, we define a general trust metric to combine these parameters. Other contributions of the paper include strategies used for implementing the trust model in a decentralized P2P environment, evaluation mechanisms to validate the effectiveness and cost of PeerTrust model, and a set of experiments that show the feasibility and benefit of our approach.

The existing approaches to fragment-based publishing, delivery and caching of web pages assume that the web pages are manually fragmented at their respective web sites. However manual fragmentation of web pages is expensive, error prone, and not scalable. This paper proposes a novel scheme to automatically detect and flag possible fragments in a web site. Our approach is basedonananalysisofthewebpagesdynamicallygeneratedat given web sites with respect to their information sharing behavior, personalization characteristics and change patterns. Categories and Subject Descriptors: H.3.3 [Information Systems- Information storage and retrieval]: Information search and retrieval

The automatic clustering algorithms are known to work well in dealing with clusters of regular shapes, e.g. compact spherical/elongated shapes, but may incur higher error rates when dealing with arbitrarily shaped clusters. Although some efforts have been devoted to addressing the problem of skewed datasets, the problem of handling clusters with irregular shapes is still in its infancy, especially in terms of dimensionality of the datasets and the precision of the clustering results considered. Not surprisingly, the statistical indices works ineffective in validating clusters of irregular shapes, too. We address the problem of clustering and validating arbitrarily shaped clusters with a visual framework (VISTA). The main idea of the VISTA approach is to capitalize on the power of visualization and interactive feedbacks to encourage domain experts to participate in the clustering revision and clustering validation process.

We illustrate how a domain scientist can perform a complex scientific task by interleaving data access, querying, and manipulation, as well as analytical steps and computations in complex, problem specific ways. We show how our system is used by a geneticist for solving the problem of discovering the so-called "co-regulated" genes by interlinking data and computation from several Web sites, local computations, as well as local and remote databases. The main distinctive features of our system (compared, e.g., to the ZOO environment (Ioannidis et al., 1996)) include: (i) executable workflows run as Web services; (ii) abstract workflows employ concept names and semantic types that are higher-level (and thus more "scientist friendly") than executable workflows; and (iii) our system supports automatic translation of the latter into the former.

Clustering is a technique commonly used in scientific research. The task of clustering inevitably involves human participation - the clustering is not finished when the computer/algorithm finishes but the user has evaluated, understood and accepted the patterns. This defines a human involved "clustering-analysis/evaluation" iteration. Instead of neglecting this human involvement, we provide a visual framework (VISTA) with all power of algorithmic approaches (since their result can be visualized), and in addition we allow the user to steer/monitor/refine the clustering process with domain knowledge. The visual-rendering result also provides a precise pattern for fast post-processing.

Article Share on Ginga: a self-adaptive query processing system Authors: Henrique Paques Georgia Institute of Technology Georgia Institute of TechnologyView Profile , Ling Liu Georgia Institute of Technology Georgia Institute of TechnologyView Profile , Calton Pu Georgia Institute of Technology Georgia Institute of TechnologyView Profile Authors Info & Claims CIKM '02: Proceedings of the eleventh international conference on Information and knowledge managementNovember 2002 Pages 655–658https://doi.org/10.1145/584792.584910Online:04 November 2002Publication History 3citation398DownloadsMetricsTotal Citations3Total Downloads398Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

No abstract available.

WebCQ is a prototype system for large-scale Web information monitoring and delivery.It makes heavy use of the structure present i n h ypertext and the concept of continual queries.In this paper we discuss both mechanisms that We-bCQ uses to discover and detect changes to the World Wide Web (the Web) pages eciently, and the methods to notify users of interesting changes with a personalized customization.The WebCQ system consists of four main components: a c hange detection robot that discovers and detects changes, a proxy cache service that reduces communication tracs to the original information servers, a personalized presentation tool that highlights changes detected by W ebCQ sentinels, and a change noti cation service that delivers fresh information to the right users at the right time.A salient feature of our change detection robot is its ability to support various types of web page sentinels for detecting, presenting, and delivering interesting changes to web pages.This paper describes the WebCQ system with an emphasis on general issues in designing and engineering a large-scale information change monitoring system on the Web.

The paper describes the methodology and the software development of XWRAP, an XML-enabled wrapper construction system for semi-automatic generation of wrapper programs. By XML-enabled we mean that the metadata about information content that are implicit in the original Web pages will be extracted and encoded explicitly as XML tags in the wrapped documents. In addition, the query based content filtering process is performed against the XML documents. The XWRAP wrapper generation framework has three distinct features. First, it explicitly separates tasks of building wrappers that are specific to a Web source from the tasks that are repetitive for any source, and uses a component library to provide basic building blocks for wrapper programs. Second, it provides a user friendly interface program to allow wrapper developers to generate their wrapper code with a few mouse clicks. Third and most importantly, we introduce and develop a two-phase code generation framework. The first phase utilizes an interactive interface facility to encode the source-specific metadata knowledge identified by individual wrapper developers as declarative information extraction rules. The second phase combines the information extraction rules generated at the first phase with the XWRAP component library to construct an executable wrapper program for the given Web source. We report the initial experiments on performance of the XWRAP code generation system and the wrapper programs generated by XWRAP.

Query routing is an intelligent service that can direct query requests to appropriate servers that are capable of answering the queries. The goal of a query routing system is to provide efficient associative access to a large, heterogeneous, distributed collection of information providers by routing a user query to the most relevant information sources that can provide the best answer. Effective query routing not only minimizes the query response time and the overall processing cost, but also eliminates a lot of unnecessary communication overhead over the global networks and over the individual information sources.

Modern digital libraries require user-friendly and yet responsive access to the rapidly growing, heterogeneous, and distributed collection of information sources. The increasing volume and diversity of digital information available online have led to a growing problem that conventional data management systems do not have, namely finding which information sources out of many candidate choices are the most relevant to answer a given user query. It refer to this problem as the query routing problem. In this paper we introduce the notation and issues of query routing, and present a practical solution for designing a scalable query routing system based on multilevel progressive pruning strategies. The key idea is to create and maintain user query profiles and source capability profiles independently, and to provide algorithms that can dynamically discover relevant information sources for a given query through the smart use of user query profiles and source capability profiles, including the mechanisms for interleaving query routing with query parallelization and query execution process to continue the pruning at run-time. Comparing with the keyword-based indexing techniques adopted in most of the search engines and software, our approach offers fine-granularity of interest matching, thus it is more powerful and effective for handling queries with complex conditions.

Article Free Access Share on TAM: a system for dynamic transactional activity management Authors: Tong Zhou Department of Computer Science & Engineering, Oregon Graduate Institute, Portland, OR Department of Computer Science & Engineering, Oregon Graduate Institute, Portland, ORView Profile , Ling Liu Department of Computer Science & Engineering, Oregon Graduate Institute, Portland, OR Department of Computer Science & Engineering, Oregon Graduate Institute, Portland, ORView Profile , Calton Pu Department of Computer Science & Engineering, Oregon Graduate Institute, Portland, OR Department of Computer Science & Engineering, Oregon Graduate Institute, Portland, ORView Profile Authors Info & Claims SIGMOD '99: Proceedings of the 1999 ACM SIGMOD international conference on Management of dataJune 1999Pages 571–573https://doi.org/10.1145/304182.304580Published:01 June 1999Publication History 2citation336DownloadsMetricsTotal Citations2Total Downloads336Last 12 Months16Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We introduce the concept of continual queries, describe the design of a distributed event-driven continual query system-OpenCQ, and outline the initial implementation of OpenCQ on top of the distributed interoperable information mediation system DIOM. Continual queries are standing queries that monitor update of interest and return results whenever the update reaches specified thresholds. In OpenCQ, users may specify to the system the information they would like to monitor (such as the events or the update thresholds they are interested in). Whenever the information of interest becomes available, the system immediately delivers it to the relevant users; otherwise, the system continually monitors the arrival of the desired information and pushes it to the relevant users as it meets the specified update thresholds. In contrast to conventional pull-based data management systems such as DBMSs and Web search engines, OpenCQ exhibits two important features: it provides push-enabled, event-driven, content-sensitive information delivery capabilities; and it combines pull and push services in a unified framework. By event-driven we mean that the update events of interest to be monitored are specified by users or applications. By content-sensitive, we mean the evaluation of the trigger condition happens only when a potentially interesting change occurs. By push-enabled, we mean the active delivery of query results or triggering of actions without user intervention.

Article Free Access Share on Dynamic restructuring of transactional workflow activities: a practical implementation method Authors: Tong Zhou Department of Computer Science & Engineering, Oregon Graduate Institute, P.O.Box 91000, Portland, OR Department of Computer Science & Engineering, Oregon Graduate Institute, P.O.Box 91000, Portland, ORView Profile , Calton Pu Department of Computer Science & Engineering, Oregon Graduate Institute, P.O.Box 91000, Portland, OR Department of Computer Science & Engineering, Oregon Graduate Institute, P.O.Box 91000, Portland, ORView Profile , Ling Liu Department of Computer Science & Engineering, Oregon Graduate Institute, P.O.Box 91000, Portland, OR Department of Computer Science & Engineering, Oregon Graduate Institute, P.O.Box 91000, Portland, ORView Profile Authors Info & Claims CIKM '98: Proceedings of the seventh international conference on Information and knowledge managementNovember 1998 Pages 378–385https://doi.org/10.1145/288627.288683Online:01 November 1998Publication History 6citation301DownloadsMetricsTotal Citations6Total Downloads301Last 12 Months4Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We describe a family of activity-split and activity-join operations with a notion of validity. The key idea of introducing the set of activity-split and activity-join operations is to allow users to restructure ongoing activities in anticipation of uncertainty so that any significant performance loss due to unexpected unavailablity or delay of shared resources can be avoided or reduced through release of early committed resources or transferring ownership of uncommitted resources. To guarantee the correctness of new activities generated by activity-split or activity-join operations, we define the notion of validity of activity restructuring operations and identify the cases where the correctness is ensured and the cases where activity-split or activity-join are illegal due to the inconsistency incurred.

The CQ project at OGI, funded by DARPA, aims at developing a scalable toolkit and techniques for update monitoring and event-driven information delivery on the net. The main feature of the CQ project is a “personalized update monitoring” toolkit based on continual queries [3]. Comparing with the pure pull (such as DBMSs, various web search engines) and pure push (such as Pointcast, Marimba, Broadcast disks) technology, the CQ project can be seen as a hybrid approach that combines the pull and push technology by supporting personalized update monitoring through a combined client-pull and server-push paradigm.

We present the systematic design and development of a distributed query scheduling service (DQS) in the context of DIOM, a distributed and interoperable query mediation system.26 DQS consists of an extensible architecture for distributed query processing, a three-phase optimization algorithm for generating efficient query execution schedules, and a prototype implementation. Functionally, two important execution models of distributed queries, namely moving query to data or moving data to query, are supported and combined into a unified framework, allowing the data sources with limited search and filtering capabilities to be incorporated through wrappers into the distributed query scheduling process. Algorithmically, conventional optimization factors (such as join order) are considered separately from and refined by distributed system factors (such as data distribution, execution location, heterogeneous host capabilities), allowing for stepwise refinement through three optimization phases: Compilation, parallelization, site selection and execution. A subset of DQS algorithms has been implemented in Java to demonstrate the practicality of the architecture and the usefulness of the distributed query scheduling algorithm in optimizing execution schedules for inter-site queries.

A seamless approach to the incremental design and reuse of object oriented methods and query specifications is presented. We argue for avoiding or minimizing the effort required for manually reprogramming methods and queries due to schema modifications, and demonstrate how the role of polymorphic reuse mechanisms is exploited for enhancing the adaptiveness of database programs against schema evolution in an object oriented database. The salient features of our approach are the use of propagation patterns and a mechanism for propagation pattern refinement. Propagation patterns are employed as an interesting specification formalism for modeling operational requirements. They encourage the reuse of operational specifications against the structural modification of an object oriented schema. Propagation pattern refinement is suited for the specification of reusable operational modules. It promotes the reusability of propagation patterns toward the operational requirement changes. This approach has a formal basis and emphasizes structural derivation of specifications. The main innovations are in raising the level of abstraction for behavioral schema design, and for making possible the derivation of operational semantics from structural specifications. As a result, both the modularity and reusability of object oriented schemas are increased.

Previous studies in data mining have yielded efficient algorithms for discovering association rules.To increase the expressiveness and relevance of the discovered rules, researche~s typically augment the thresholds with domain-specific knowledge.Most existing proposals use the relational approach to organize and maintain these multi-level concept hierarchies.We argue that an object-oriented approach is better suited for focusing the search and regulating the mining of association rules both at multi-levels within one concept hierarchy, and across multiple concept hierarchies.We propose an adaptive encodhtg scheme for focusing the mining on semantically deeper and more informative knowledge.We demonstrate that the application of an object-oriented approach provides us with the benefits of a flexible combination of multiple multi-level concept hierarchies for focusing the mining on more informative and refined knowledge, and also allows us to enjoy seamless integration of multi-level concept hierarchies with legacy databases.In addition, by using an adaptive encoding scheme, efficient algorithms developed for discovering association rules can be integrated into the object-oriented framework with no or little extm cost.

A large-scale interoperable database system operating in a dynamic environment should provide uniform access user interface to its components, scalability to larger networks, evolution of database schema and applications, flexible composability of client and server components, and preserve component autonomy. To address the research issues presented by such systems, we introduce the Distributed Interoperable Object Model (DIOM). DIOM's main features include the explicit representation of and access to semantics in data sources through the DIOM base interfaces, the use of interface abstraction mechanisms (such as specialization, generalization, aggregation and import) to support incremental design and construction of compound interoperation interfaces, the deferment of conflict resolution to the query submission time instead of at the time of schema integration, and a clean interface between distributed interoperable objects that supports the independent evolution and management of such...

We develop a selection of design and evaluation rules for building an adaptive schema in an object-oriented data and knowledge base system. This set of style rules include not only those which we use to preserve validity and minimality of an object-oriented schema, but also those which help us to promote extensibility, reusability and adaptiveness of an object-oriented schema against future requirement changes. We encourage to use the set of style rules proposed as a means for validating quality of a schema, and for transforming an object-oriented schema into a better style regarding to adaptiveness and robustness, rather than as a user-oriented method solely for designing the schema.

A polymorphic approach to the incremental design and reuse of object-oriented methods and query specifications is presented. Using this approach, the effort required for manually reprogramming methods and queries due to schema modifications can be avoided or minimized. The salient features of of our approach are the use of propagation patterns and a mechanism for propagation pattern refinement. Propagation patterns can be employed as an interesting specification formalism for modeling operational requirements in object-oriented database systems. They encourage the reuse of operational specifications against the structural modification of an object-oriented schema. Propagation pattern refinement is suited for the specification of reusable operational modules, and for achieving reusability of propagation patterns towards the operational requirement changes.>