The impressive performance of large language models (LLMs) also brings inherent toxicity risks, prompting the need for effective detoxification to support responsible deployment. Prevailing methods generally follow an inflexible model-specific fashion, addressing only individual models or model families. Moreover, overlooking the underlying toxic risks involved in the input prefix can lead to toxic accumulation during autoregressive generation. Existing methods rely on external strong attribute interventions to address this issue, which further exacerbates contextual semantic inconsistencies and makes it difficult to balance toxicity efficacy and generation quality. To address these concerns, we propose a novel Model-Agnostic Adaptive Detoxification (MAAD) framework. To address accumulating toxicity, we present prefix heuristics that serve as contextual signals, guiding the base LLM toward safer generation. Along this line, we construct an antidote dataset to support a lightweight model, Detoxifier, which steers the base LLM to make in-scope and reliable detoxifying distribution adjustments while preserving fluency and contextual understanding. Designed as an easy-to-deploy module, Detoxifier requires a small amount of data and can be seamlessly applied to various base LLMs with one-off training. Since over-purifying often reduces diversity, we also propose a dynamic truncation method called CW-cutoff sampling to trade off language model quality and diversity. Extensive experiments demonstrate that MAAD strikes a better balance between detoxification effectiveness and generation quality, while also maintaining model utility.

Steering Vector (SV) is a powerful technique for controlling Large Language Models (LLMs) by manipulating their activations without altering model weights. However, when constructed from sensitive data, SV poses significant privacy risks, as it may leak private information. Existing differential privacy (DP) techniques for constructing SV cannot be directly applied to training-based SV construction paradigms, which offer higher task performance. In this work, we present **PrivSV**, a general privacy-preserving approach for constructing SV with DP guarantees, compatible with arbitrary SV construction paradigms while maintaining high utility. In PrivSV, we propose three novel methods: a Layer-wise Noise-Resilient Reduction (LNR²) method to reduce the injected noise in high-dimensional SV; a Directional Prior Compensation (DPC) method to recover utility degraded by noise perturbation; and a Privacy-Aware Optimal Parameter Determination (POPD) method to adaptively maximize the performance of the final compensated SV. Extensive experiments on open-source LLMs of different families (i.e., LlaMa, Qwen, Mistral and Gemma) demonstrate that PrivSV outperforms several existing techniques across various privacy budgets.

Truth discovery has emerged as an effective tool to mitigate data inconsistency in crowdsensing by prioritizing data from high-quality responders. While local differential privacy (LDP) has emerged as a crucial privacy-preserving paradigm, existing studies under LDP rarely explore a worker's participation in specific tasks for sparse scenarios, which may also reveal sensitive information such as individual preferences and behaviors. Existing LDP mechanisms, when applied to truth discovery in sparse settings, may create undesirable dense distributions, provide insufficient privacy protection, and introduce excessive noise, compromising the efficacy of subsequent non-private truth discovery. Additionally, the interplay between noise injection and truth discovery remains insufficiently explored in the current literature. To address these issues, we propose a lOcally differentially private truth diSCovery approach for spArse cRowdsensing, namely OSCAR. The main idea is to use advanced optimization techniques to reconstruct the sparse data distribution and re-formalize truth discovery by considering the statistical characteristics of injected Laplacian noise while protecting the privacy of both the tasks being completed and the corresponding sensory data. Specifically, to address the data density concerns while alleviating noise, we design a randomized response based Bernoulli matrix factorization method BerRR. To recover the sparse structures from densified, perturbed data, we formalize a 0-1 integer programming problem and develop a sparse recovery solving method SpaIE based on implicit enumeration. We further devise a Laplacian-sensitive truth discovery method LapCRH that leverages maximum likelihood estimation to re-formalize truth discovery by measuring differences between noisy values and truths based on the statistical characteristic of Laplacian noise. Our comprehensive theoretical analysis establishes OSCAR's privacy guarantees, utility bounds, and computational complexity. Experimental results show that OSCAR surpasses the state-of-the-arts by at least 30% in accuracy improvement.

Data inconsistency often arises from multiple observed sensory data due to varying participant reliability for crowdsensing systems. Truth discovery, which includesWeight EstimationandTruth Aggregation, for estimating participant reliability weights and aggregating uploaded values from inconsistent observations respectively, has emerged as an effective solution to address this issue. While local differential privacy (LDP) provides strong privacy guarantees by allowing participants to perturb their data locally before submission, existing LDP-based studies are either designed for static scenarios or compromise on privacy and accuracy trade-off for data streams, satisfying only weaker versions of LDP or mere differential privacy. To effectively and efficiently obtain truths over streams under rigorous LDP, we proposeNANOwhich is locally differeNtially privAte truth discovery via updatiNg time stamp determinatiOn. The main idea lies in its integration of Laplacian noise for privacy protection and inherent Gaussian noise representing natural data variability for effective weight and truth estimations, coupled with the adaptive determination of updating time stamps. InNANO, to obtain theWeight EstimationandTruth Aggregationunder LDP, we design a mixed noise-aware truth discovery methodMixTDby modeling the mixed noise. To capture the dynamic nature of weight and truth evolutions, we develop a changing-aware updating time stamp determination methodCUDto selectively re-conduct truth discovery at specific time stamps. We also introduce a dynamic privacy budget management strategy, which accumulates unused budgets from skipped updates for critical timestamps. In this way,Weight EstimationandTruth Aggregationare limited to critical time stamps, which significantly reduces the privacy budget segmentation and computational costs. We demonstrate thatNANOprovides rigorous LDP guarantees while achieving bounded utility and computational complexity. Extensive experimental results over four real-world datasets and three synthetic datasets showcase thatNANOoutperforms the state-of-the-arts by at least 20% improvement with negligible extra efficiency loss.

Sum query is an important and fundamental operator for online analytical processing. In this paper, we focus on the process of answering sum queries over data cube, each of which consists of a collection of cuboids, while satisfying differential privacy (DP). Existing works fail to process the sum queries in online analytical processing with high utility due to sum queries' high sensitivity and the noise aggregation: constructing a base cuboid requires the data curator to answer a workload of linear sum queries under DP in advance, whose sensitivity will result in a large amount of DP noise, and the noise will finally be aggregated when constructing the remaining cuboids. To this end, we present a Differentially PRIvate Multi-dimensional Analytic Approach (PRIMA). In PRIMA, we propose a Symmetric Bounded Sum Query Processing Method (SBS) which reduces the sensitivity of sum queries by bounding both the maximum and minimum contribution of each record in the data table in a symmetricaly manner. Moreover, we propose a Hypothesis Testing based Prefix Sum Computing Method (SCOPE) to compute a base prefix-sum cuboid based on hypothesis testing. By employing the base prefix-sum cuboid, any remaining cuboid can be constructed with constant pieces of DP noise aggregated. We conduct experiments on both real-world and synthetic datasets. Experimental results confirm the effectiveness of PRIMA over existing works.

In this paper, we initiate the study of privacy-preserving graph diffusion models (DMs) for graph generation while protecting the privacy of edges in training graphs. We propose an Edge Private Graph Diffusion Model (EPGDiff) which enforces the model parameters to satisfy edge differential privacy (edge-DP) by clipping and perturbing gradients during training. In EPGDiff, since introducing DP noise into the model parameters significantly affects the utility of the generated graphs, we propose a Homophily Enhanced Denoising Network (HEDN) to enhance the utility of the generated graphs by leveraging the homophilic correlation between node attributes and graph structure. Moreover, we propose a Degree Preserving Graph Decoder (DPGD) to calibrate the generated graphs by utilizing the graph structure statistics, i.e., the node degree vector. Experimental results on real social graph datasets confirm the effectiveness of EPGDiff.

Extreme Gradient Boosting (XGBoost) demonstrates excellent performance in practice and is widely used in both industry and academic research. This extensive application has led to a growing interest in employing multi-party data to develop more robust XGBoost models. In response to increasing concerns about privacy leakage, secure vertical federated XGBoost is proposed. It employs secure multi-party computation techniques, such as secret sharing (SS), to allow multiple parties holding vertically partitioned data, i.e., disjoint features on the same samples, to collaborate in constructing an XGBoost model. However, the running efficiency is the primary obstacle to the practical application of existing protocols, especially in multi-party settings. The reason is that these protocols not only require the execution of data-oblivious computations to protect intermediate results, leading to high computational complexity, but also involve a large number of SS-based non-linear operations with high overheads, e.g., division operations in gain score calculation and comparison operations in best split selection. To this end, we present a secure and efficient multi-party protocol for vertical federated XGBoost, called SecureXGB, which can perform the collaborative training of an XGBoost model in an SS-friendly manner. In SecureXGB, we first propose a parallelizable multi-party permutation method, which can secretly and efficiently permute all samples before model training to reduce the reliance on data-oblivious computations. Then, we design a linear gain score that can be evaluated without involving division operations and has equivalent utility to the original gain score. Finally, we develop a synchronous best split selection method to secretly identify the best split with the maximum gain score using a minimal number of comparison operations. Experimental results demonstrate that SecureXGB can achieve better training efficiency than state-of-the-art protocols without the loss of model accuracy.

Worker recruitment for area coverage maximization, typically requires participants to upload location information, which can deter potential participation without proper protection. While existing studies resort to geo-indistinguishability to address this concern, they primarily focus on either specific task locations (Target Coverage) or operate under pre-defined recruitment quotas for an interested region (Area Coverage). These focuses not only yield suboptimal area coverage when scaled but also fail to leverage valuable prior knowledge in the form of participants’ noisy historical registered locations, to enhance both location obfuscation and worker identification processes. To address these limitations, we presentWILTON, which optimizes area coverage under geo-indistinguishability by recruiting the minimum number of participants through the strategic utilization of noisy prior knowledge. InWILTON, to generate obfuscated locations, we propose a probabilistic and weight-aware input perturbation mechanism, which groups and weights prior locations rather than using only personal prior locations. To privately identify the recruited workers, we design a grid-based worker identification method, which provides a worst-case performance guarantee of ratio 1 − 1/eto the optimum. We provide a theoretical analysis of the privacy, utility, and complexity guarantees ofWILTON. Experimental results over two real-world datasets and one synthetic dataset show thatWILTONsurpasses the state-of-the-arts by at least 8% in area coverage improvement.

Matrix factorization-based recommendations have emerged as a cornerstone for many industrial recommendation algorithms. However, studies employing differential privacy often rely on a trusted server, while those implementing local differential privacy (LDP) frequently encounter substantial accuracy degradation and excessive communication overhead due to noise injection and frequent user interactions. Moreover, the presence of injected noise for privacy protection and inherent Gaussian noise within these perturbed values compounds the accuracy issues and may create a cascading effect under LDP, exacerbating the complexity of the problem at hand. To address these challenges, we proposeMENTOR, which isMixture model-based rEcommeNdations approach with matrix FacTORization under LDP. Its main idea lies in the adoption of a bounded input perturbation mechanism that closely approximates the Laplace distribution while providing rigorous LDP, coupled with accounting for various noise types present in the perturbed data. This approach allows us to reformulate the matrix factorization process with minimal user interaction, requiring only a single round of communication. In particular, to add noise, we design a bidirectional bounded LDP input perturbation mechanismBBVwhile minimizing variance. To generate recommendation results, we devise a matrix factorization techniqueGLMFbased on a Gaussian–Laplacian mixture model. Comprehensive experiments reveal thatMENTORoutperforms the state of the art by at least 15% inRMSEand 12% inF-Measure, showcasing its effectiveness in balancing privacy and utility in recommendation systems.

Multi-passage machine reading comprehension (MRC) aims to answer a question by multiple passages. Existing multi-passage MRC approaches have shown that employing passages with and without golden answers (i.e., labeled and unlabeled passages) for model training can improve prediction accuracy. However, when using the unlabeled passages, they either incur the wrong labeling problem or treat the labeled and unlabeled passages equally. In addition, they ignore the original passage information to verify the correctness of the answer. In this paper, we present MLDV-MRC, a novel approach for multi-passage MRC viaMulti-taskLearning andDualVerification. MLDV-MRC adopts the extract-then-select framework, where an extractor is first used to predict answer candidates, then a selector is used to choose the final answer. For the extractor, we adopt multi-task learning with generative adversarial training to train it by using both labeled and unlabeled passages. To train the extractor by backpropagation, we propose a hybrid method which combines boundary-based and content-based extracting methods to produce the answer candidate set and its representation. For the selector, we propose to leverage both the information from answer candidates and original passages to verify the final answer. In particular, we propose a global-local memory-augmented neural network to build the representations of original passages, which fuses the passage-level information and word-level information. The experimental results on three open-domain QA datasets confirm the effectiveness of our approach.

In this article, we study the problem of differentially private multi-party data sharing, where the involved parties assisted by a semi-honest curator collectively generate a shared dataset while satisfying differential privacy. Inspired by the success of data synthesis with the generative adversarial network (GAN), we propose a novel GAN-based differentially private multi-party data sharing approach named ATLAS. In ATLAS, we extend the original GAN to multiple discriminators, and let each party hold a discriminator while the curator holds a generator. To update the generator without compromising each party's privacy, we decompose the calculation of the generator's gradient and selectively sanitize thediscriminators’ responses. Additionally, we propose two methods to improve the utility of shared data, i.e., the collaborative discriminator filtering (CDF) method and the adaptive gradient perturbation (AGP) method. Specifically, the CDF method utilizes trained discriminators to refine synthetic records, while the AGP method adaptively adjusts the noise scale during training to reduce the impact of deferentially private noise on the final shared data. Extensive experiments on real-world datasets validate the superiority of our ATLAS approach.

Locations are usually necessary for task allocation in spatial crowdsourcing, which may put individual privacy in jeopardy without proper protection. Although existing studies have well explored the problem of location privacy protection in task allocation under geo-indistinguishability, they potentially assume the workers could perform any tasks, which might not be practical in reality. Moreover, they usually adopt planar laplacian mechanism to achieve geo-indistinguishability, which will introduce excessive noise due to its randomness and boundlessness. To this end, we propose a task alloCAtioNapproach via grOup-based noisEaddition under Geo-I, referred to asCANOE. Its main idea is that each worker uploads the noisy distances between his true location and the obfuscated locations of his preferred tasks instead of uploading his obfuscated location. In particular, to alleviate the total noise when conducting grouping, we put forward an optimized global grouping with adaptive local adjustment methodOGALwith convergence guarantee. To collect the noisy distances which are required for subsequent task allocation, we develop a utility-aware obfuscated distance collection methodUODCwith solid privacy and utility guarantees. We further theoretically analyze the privacy, utility and complexity guarantees ofCANOE. Extensive analyses and experiments over two real-world datasets confirm the effectiveness ofCANOE.

Truth discovery is an effective way to identify the aggregated truth of each task among multiple observed data drawn from different workers of varying reliabilities. However, existing studies are insufficient to protect individuals’ privacy, as they either just guarantee the weaker versions of local differential privacy (LDP) or potentially assume that the tasks are independent. In this paper, we, for the first time, investigate the problem of truth discovery while achieving the rigorous LDP for each worker with continuous inputs without the independence assumption. We present a locally differentially private truth discovery approach calledPrivTDSIbased on sampling and inference with solid privacy and utility guarantees. InPrivTDSI, the server first determines which values of each worker should be sampled according to a sample proportion and sends the indexes of these values to each worker. Then, each worker adds noise into the sampled values for privacy protection and uploads them to the server. After receiving the noisy sampled values from all the workers, the server first infers the unsampled values and then conducts truth discovery based on both the noisy sampled values and the inferred values. In particular, to determine the sample proportion, we formulate aconstrained nonlinear programmingproblem and give a closed-form solution to this problem. Moreover, to determine which values of each worker should be sampled while avoiding the situation where the values of some workers or tasks might not be sampled at all, we develop a two-stage sampling method calledTOSS. Furthermore, to infer the unsampled values accurately, we design a quality-aware inference method based on matrix factorization calledQualityMF. Experimental results on two real-world datasets and a synthetic dataset demonstrate the effectiveness of${PrivTDSI}$.

With the deep penetration of the Internet and mobile devices, preference rankings are being collected on a massive scale by diverse data collectors for various business demands. However, users’ preference rankings in many applications are highly sensitive. Without proper privacy protection mechanisms, it either puts individual privacy in jeopardy or hampers business opportunities due to users’ unwillingness to share their true rankings. In this paper, we initiate the study of collecting preference rankings under local differential privacy. The key technical challenge comes from the fact that the number of possible rankings could be large in practical settings, leading to excessive injected noise. To solve this problem, we present a novel approach SAFARI, whose main idea is to collect a set of distributions over small domains which are carefully chosen based on the riffle independent (RI) model to approximate the overall distribution of users’ rankings, and then generate a synthetic ranking dataset from the obtained distributions. By working on small domains instead of a large domain, SAFARI can significantly reduce the magnitude of added noise. In SAFARI, we design two transformation rules, namely Rule I and Rule II, to instruct users to transform their data to provide the information about the distributions of the small domains. In particular, we propose a method called LADE to precisely estimate the required distributions used for the structure learning of RI model. We also propose a new LDP method called SAFA for frequency estimation over multiple attributes that have small domains. We formally prove that SAFARI guarantees$\varepsilon$-local differential privacy. Extensive experiments on real datasets confirm the effectiveness of SAFARI.

In many real-world applications, data are distributed across different geographical regions, and may come from different distributions which result in multiple learning tasks. In such cases, distributed multi-task learning is usually used to learn the multiple related tasks to improve the generalization performance for each task. Among the distributed multi-task learning algorithms, distributed multi-task relationship learning (DMTRL) attracts much attention in the community as it learns task relationships from data, instead of imposing a prior task relatedness assumption. To perform DMTRL, task model or its gradient is transferred between task node and central server. There will be a potential privacy violation when the distributed data are possessed by different institutes and contain sensitive information (e.g., medical records). In this paper, we propose a distributed multi-task relationship learning approach under differential privacy called DRUPE, where privacy protection is achieved through perturbing the gradients at each task node. In particular, to reduce the high variance of the perturbed gradients and achieve fast convergence rate, we develop a variance reduction based gradient calibration method, which first estimates the gradient error from the previous perturbed gradients and then calibrates the current perturbed gradient by subtracting the gradient error term. Moreover, to alleviate the negative effect caused by the inaccurate task relationships that are inferred from the private task models, we present a task relationship calibration method which uses the least-squares approximation algorithm to calibrate the inaccurate pairwise relationships between the tasks. Experimental results on real-world datasets confirm the effectiveness of our approach.

Range query over data cubes is a powerful tool for online analytical processing (OLAP). In this paper, we focus on answering range queries while satisfying local differential privacy (LDP). The key technical challenges come from the problem of noise aggregation and the curse of high dimensionality: multiple LDP noise will be aggregated when answering range queries and collecting high-dimensional data under LDP will further degrade the utility of the results. To this end, we present a novel method called Prefix-Sum based Range QuerIes ProceSsing Method (PRISM). Its main idea is to selectively collect a few prefix-sums in a data-dependent way, and answer range queries over prefix-sum-based cubes based on which any range query can be processed by using constant pieces of prefix-sums. In PRISM, we first alleviate the problem of noise aggregation by proposing a LDP mechanism called Range based Randomized Response (RRR) and a new type of prefix-sums-based cube called Grained Prefix-Sum (GPS) cube. We then alleviate the curse of high dimensionality by proposing a Data-Dependent Selective Prefix-Sum Collection Strategy (DELFT). We conduct experiments on both real-world datasets and synthetic datasets. Experimental results confirm the effectiveness of PRISM over existing methods.

Deep neural networks are capable of making classification or prediction using large amounts of labeled data. When there's no or only a few labeled data available, domain adaptation can be adopted to transfer a model from the source domain where many labeled data are available to the target domain with few labeled data. In practice, in addition to private data, some public data are generally available and can be utilized as source domain. However, due to the exposure of the training model, the information of the private data may be potentially compromised. In this paper, we propose public data assisted differentially private deep learning methods which generalize well across different distributions of the private and public data. Specifically, two different methods are presented for different scenarios: unsupervised learning and supervised learning. The proposed methods can leverage the public data for higher performance while providing privacy guarantee for the private dataset. Empirical study on standard benchmark datasets validates the superiority of our approaches.

In this paper, we tackle the problem of collecting individual trajectories under local differential privacy. The key challenge is how to achieve high utility of the collected trajectories while satisfying the strong privacy guarantee. To overcome this challenge, we present a novel approach, which is referred to as PrivTC. In PrivTC, we first design a locally differentially private grid construction method to instruct the aggregator to lay an appropriate grid on the given geospatial domain. Then we propose a locally differentially private spectral learning method to help the aggregator learn the Hidden Markov Model (HMM) from users' trajectories discretized by the constructed grid. Finally, the aggregator generates a synthetic trajectory dataset as a surrogate for the original one from the learned HMM. Extensive experiments on real datasets confirm the effectiveness of PrivTC.

Domain adaptation solves a learning problem in a target domain by utilizing the training data in a different but related source domain. As a simple and efficient method for domain adaptation, correlation alignment transforms the distribution of the source domain by utilizing the covariance matrix of the target domain, such that a model trained on the transformed source data can be applied to the target data. However, when source and target domains come from different institutes, exchanging information between the two domains might pose a potential privacy risk. In this paper, for the first time, we propose a differentially private correlation alignment approach for domain adaptation called PRIMA, which can provide privacy guarantees for both the source and target data. In PRIMA, to relieve the performance degradation caused by perturbing the covariance matrix in high dimensional setting, we present a random subspace ensemble based covariance estimation method which splits the feature spaces of source and target data into several low dimensional subspaces. Moreover, since perturbing the covariance matrix may destroy its positive semi-definiteness, we develop a shrinking based method for the recovery of positive semi-definiteness of the covariance matrix. Experimental results on standard benchmark datasets confirm the effectiveness of our approach.

Abstract Entity linking is a fundamental task in natural language processing. The task of entity linking with knowledge graphs aims at linking mentions in text to their correct entities in a knowledge graph like DBpedia or YAGO2. Most of existing methods rely on hand‐designed features to model the contexts of mentions and entities, which are sparse and hard to calibrate. In this paper, we present a neural model that first combines co‐attention mechanism with graph convolutional network for entity linking with knowledge graphs, which extracts features of mentions and entities from their contexts automatically. Specifically, given the context of a mention and one of its candidate entities' context, we introduce the co‐attention mechanism to learn the relatedness between the mention context and the candidate entity context, and build the mention representation in consideration of such relatedness. Moreover, we propose a context‐aware graph convolutional network for entity representation, which takes both the graph structure of the candidate entity and its relatedness with the mention context into consideration. Experimental results show that our model consistently outperforms the baseline methods on five widely used datasets.

In this paper, we study the problem of publishing vertically partitioned data under differential privacy, where different attributes of the same set of individuals are held by multiple parties. In this setting, with the assistance of a semi-trusted curator, the involved parties aim to collectively generate an integrated dataset while satisfying differential privacy for each local dataset. Based on the latent tree model (LTM), we present a differentially private latent tree (DPLT) approach, which is, to the best of our knowledge, the first approach to solving this challenging problem. In DPLT, the parties and the curator collaboratively identify the latent tree that best approximates the joint distribution of the integrated dataset, from which a synthetic dataset can be generated. The fundamental advantage of adopting LTM is that we can use the connections between a small number of latent attributes derived from each local dataset to capture the cross-dataset dependencies of the observed attributes in all local datasets such that the joint distribution of the integrated dataset can be learned with little injected noise and low computation and communication costs. DPLT is backed up by a series of novel techniques, including two-phase latent attribute generation (TLAG), tree index based correlation quantification (TICQ) and distributed Laplace perturbation protocol (DLPP). Extensive experiments on real datasets demonstrate that DPLT offers desirable data utility with low computation and communication costs.

Multi-passage machine reading comprehension (MRC) aims to answer a question by multiple passages. Existing multi-passage MRC approaches have shown that employing passages with and without golden answers (i.e. labeled and unlabeled passages) for model training can improve prediction accuracy. In this paper, we present MG-MRC, a novel approach for multi-passage MRC via multi-task learning with generative adversarial training. MG-MRC adopts the extract-then-select framework, where an extractor is first used to predict answer candidates, then a selector is used to choose the final answer. In MG-MRC, we adopt multi-task learning to train the extractor by using both labeled and unlabeled passages. In particular, we use labeled passages to train the extractor by supervised learning, while using unlabeled passages to train the extractor by generative adversarial training, where the extractor is regarded as the generator and a discriminator is introduced to evaluate the generated answer candidates. Moreover, to train the extractor by backpropagation in the generative adversarial training process, we propose a hybrid method which combines boundary-based and content-based extracting methods to produce the answer candidate set and its representation. The experimental results on three open-domain QA datasets confirm the effectiveness of our approach.

In this paper, we tackle the problem of answering multi-dimensional range queries under local differential privacy. There are three key technical challenges: capturing the correlations among attributes, avoiding the curse of dimensionality, and dealing with the large domains of attributes. None of the existing approaches satisfactorily deals with all three challenges. Overcoming these three challenges, we first propose an approach called Two-Dimensional Grids (TDG). Its main idea is to carefully use binning to partition the two-dimensional (2-D) domains of all attribute pairs into 2-D grids that can answer all 2-D range queries and then estimate the answer of a higher dimensional range query from the answers of the associated 2-D range queries. However, in order to reduce errors due to noises, coarse granularities are needed for each attribute in 2-D grids, losing fine-grained distribution information for individual attributes. To correct this deficiency, we further propose Hybrid-Dimensional Grids (HDG), which also introduces 1-D grids to capture finer-grained information on distribution of each individual attribute and combines information from 1-D and 2-D grids to answer range queries. To make HDG consistently effective, we provide a guideline for properly choosing granularities of grids based on an analysis of how different sources of errors are impacted by these choices. Extensive experiments conducted on real and synthetic datasets show that HDG can give a significant improvement over the existing approaches.

In this paper, we study the problem of publishing high-dimensional data in a distributed multi-party environment under differential privacy. In particular, with the assistance of a semi-trusted curator, the parties (i.e., local data owners) collectively generate a synthetic integrated dataset while satisfying ε-differential privacy. To solve this problem, we present a differentially private sequential update of Bayesian network (DP-SUBN) approach. In DP-SUBN, the parties and the curator collaboratively identify the Bayesian network N that best fits the integrated dataset in a sequential manner, from which a synthetic dataset can then be generated. The fundamental advantage of adopting the sequential update manner is that the parties can treat the intermediate results provided by previous parties as their prior knowledge to direct how to learn N. The core of DP-SUBN is the construction of the search frontier, which can be seen as a priori knowledge to guide the parties to update N. By exploiting the correlations of attribute pairs, we propose exact and heuristic methods to construct the search frontier. In particular, to privately quantify the correlations of attribute pairs without introducing too much noise, we first put forward a non-overlapping covering design (NOCD) method, and then devise a dynamic programming method for determining the optimal parameters used in NOCD. Through privacy analysis, we show that DP-SUBN satisfies ε-differential privacy. Extensive experiments on real datasets demonstrate that DP-SUBN offers desirable data utility with low communication cost.

In this paper, we initiate the study of collecting preference rankings under local differential privacy. The key technical challenge comes from the fact that the number of possible rankings increases factorially in the number of items to rank. In practical settings, this number could be large, leading to excessive injected noise. To solve this problem, we present a novel approach called SAFARI. The general idea is to collect a set of distributions over small domains which are carefully chosen based on the riffle independent model to approximate the overall distribution of users' rankings, and then generate a synthetic ranking dataset from the obtained distributions. By working on small domains instead of a large domain, SAFARI can significantly reduce the magnitude of added noise. Extensive experiments on real datasets confirm the effectiveness of SAFARI.

It has been shown that stock price movements are influenced by news. To predict stock movements with news, many existing works rely only on the news title since the news content may contain irrelevancies which seriously degrade the prediction accuracy. However, we observe that there is still useful information in the content which is not reflected in the title, and simply ignoring the content will result in poor performance. In this paper, taking advantage of neural representation learning, we propose a hierarchical complementary attention network (HCAN) to capture valuable complementary information in news title and content for stock movement prediction. In HCAN, we adopt a two-level attention mechanism to quantify the importances of the words and sentences in a given news. Moreover, we design a novel measurement for calculating the attention weights to avoid capturing redundant information in the news title and content. Experimental results on news datasets show that our proposed model outperforms the state-of-the-art techniques.

Community Question Answering (CQA) has increasingly become an important service for people asking questions and providing answers online, which enables people to help each other by sharing knowledge. Recently, with accumulation of users and contents, much concern has arisen over the efficiency and answer quality of CQA services. To address this problem, question routing has been proposed which aims at routing new questions to suitable answerers, who have both high possibility and high ability to answer the questions. In this paper, we formulate question routing as a multi-objective ranking problem, and present a multi-objective learning-to-rank approach for question routing (MLQR), which can simultaneously optimize the answering possibility and answer quality of routed users. In MLQR, realizing that questions are relatively short and usually attached with tags, we first propose a tagword topic model (TTM) to derive topical representations of questions. Based on TTM, we then develop features for each question-user pair, which are captured at both platform level and thread level. In particular, the platform-level features summarize the information of a user from his/her history posts in the CQA platform, while the thread-level features model the pairwise competitions of a user with others in his/her answered threads. Finally, we extend a state-of-the-art learning-to-rank algorithm for training a multi-objective ranking model. Extensive experimental results on real-world datasets show that our MLQR can outperform state-of-the-art methods in terms of both answering possibility and answer quality.

In this paper, we present an encoder-decoder model for distant supervised relation extraction. Given an entity pair and its sentence bag as input, in the encoder component, we employ the convolutional neural network to extract the features of the sentences in the sentence bag and merge them into a bag representation. In the decoder component, we utilize the long short-term memory network to model relation dependencies and predict the target relations in a sequential manner. In particular, to enable the sequential prediction of relations, we introduce a measure to quantify the amounts of information the relations take in their sentence bag, and use such information to determine the order of the relations of a sentence bag during model training. Moreover, we incorporate the attention mechanism into our model to dynamically adjust the bag representation to reduce the impact of sentences whose corresponding relations have been predicted. Extensive experiments on a popular dataset show that our model achieves significant improvement over state-of-the-art methods.

In this paper, we study the location‐aware targeted influence maximization problem in social networks, which finds a seed set to maximize the influence spread over the targeted users. In particular, we consider those users who have both topic and geographical preferences on promotion products as targeted users. To efficiently solve this problem, one challenge is how to find the targeted users and compute their preferences efficiently for given requests. To address this challenge, we devise a TR‐tree index structure, where each tree node stores users' topic and geographical preferences. By traversing the TR‐tree in depth‐first order, we can efficiently find the targeted users. Another challenge of the problem is to devise algorithms for efficient seeds selection. We solve this challenge from two complementary directions. In one direction, we adopt the maximum influence arborescence (MIA) model to approximate the influence spread, and propose two efficient approximation algorithms with approximation ratio, which prune some candidate seeds with small influences by precomputing users' initial influences offline and estimating the upper bound of their marginal influences online. In the other direction, we propose a fast heuristic algorithm to improve efficiency. Experiments conducted on real‐world data sets demonstrate the effectiveness and efficiency of our proposed algorithms.

Mining frequent subgraphs from a collection of input graphs is an important task for exploratory data analysis on graph data. However, if the input graphs contain sensitive information, releasing discovered frequent subgraphs may pose considerable threats to individual privacy. In this paper, we study the problem of frequent subgraph mining (FSM) under the rigorous differential privacy model. We present a two-phase differentially private FSM algorithm, which is referred to as DFG. In DFG, frequent subgraphs are privately identified in the first phase, and the noisy support of each identified frequent subgraph is calculated in the second phase. In particular, to privately identity frequent subgraphs, we propose a frequent subgraph identification approach, which can improve the accuracy of discovered frequent subgraphs through candidate pruning. Moreover, to compute the noisy support of each identified frequent subgraph, we devise a lattice-based noisy support computation approach, which leverages the inclusion relations between the discovered frequent subgraphs to improve the accuracy of the noisy supports. Through formal privacy analysis, we prove that DFG satisfies ε-differential privacy. Extensive experimental results on real datasets show that DFG can privately find frequent subgraphs while achieving high data utility.

With the rapid development of location-based services in mobile Internet, spatial keyword queries have been widely employed in various real-life applications in recent years. To realize the great flexibility and cost savings, more and more data owners are motivated to outsource their spatio-textual data services to the cloud. However, directly outsourcing such services to the untrusted cloud may arise serious privacy concerns. In this paper, we study the privacy-preserving top-$k$spatial keyword query problem in untrusted cloud environments. Existing studies primarily focus on the design of privacy-preserving schemes for either spatial or keyword queries, and they cannot be applied to solve the privacy-preserving spatial keyword query problem. To address this problem, we present a novel privacy-preserving top-$k$spatial keyword query scheme. In particular, we build an encrypted tree index to facilitate privacy-preserving top-$k$spatial keyword queries, where spatial and textual data are encrypted in a unified way. To search with the encrypted tree index, we propose two effective techniques for the similarity computations between queries and tree nodes under encryption. To improve query performance on large-scale spatio-textual data, we further propose a keyword-based secure pruning method. Thorough analysis shows the validity and security of our scheme. Extensive experimental results on real datasets demonstrate our scheme achieves high efficiency and good scalability.

With the development of large-scale knowledge bases, people are building systems which give simple answers to questions based on consolidate facts. In this paper, we focus on simple questions, which ask about only a subject and relation in the knowledge base. Observing that certain parts of a question usually overlap with names of its corresponding subject and relation in the knowledge base, we argue that a question is formed by a mixture of copying and generation. To model that, we propose a sequence-to-sequence (seq2seq) architecture which encodes a candidate subject-relation pair and decodes it into the given question, where the decoding probability is used to select the best candidate. In our decoder, the copying mode points the subject or relation and duplicates its name, while the generating mode summarizes the meaning of the subject-relation pair and produces a word to smooth the question. Realizing that although sometimes a subject or relation is pointed, different names or keywords might be used, we also incorporate a paraphrasing mode to supplement the copying mode using an automatically mined lexicon. Extensive experiments on the largest dataset exhibit our better performance compared with the state-of-the-art methods.

Hashing has attracted broad research interests in large scale image retrieval due to its high search speed and efficient storage. Recently, many deep hashing methods have been proposed to perform simultaneous nonlinear feature learning and hash projection learning, which have shown superior performance compared to hand-crafted feature based hashing methods. Nonlinear projection functions have shown their advantages over the linear ones due to their powerful generalization capabilities. To improve the performance of deep hashing methods by generalizing projection functions, we propose the idea of implementing a pure nonlinear deep hashing network architecture. By consolidating the above idea, this paper presents a Deep Supervised Hashing architecture with Nonlinear Projections (DSHNP). In particular, soft decision trees are adopted as the nonlinear projection functions, since they can generate differentiable nonlinear outputs and can be trained with deep neural networks in an end-to-end way. Moreover, to make the hash codes as independent as possible, we design two regularizers imposed on the parameter matrices of the leaves in the soft decision trees. Extensive evaluations on two benchmark image datasets show that the proposed DSHNP outperforms several state-of-the-art hashing methods.

Abstract The rapid growth of event‐based social networks (EBSNs) has generated great demand for personalized event recommendation. Indeed, new events are published every day in EBSNs. In this paper, we focus on the problem of recommending new events (i.e., the newly published events that have not yet received any user response) to registered users in EBSNs. Notice that collaborative filtering is ineffective for recommending new events due to the short lifetime of events and the lack of historical information, that is, the cold‐start problem. A straightforward approach to address this problem is to adopt content‐based recommendation techniques, for example, deriving user interests through the content information of the events they attended. Nevertheless, we observe that organizer influence and geographical preference also play important roles in a user's decision to participate in an event. Motivated by this observation, we combine user interest, organizer influence, and geographical preference to present a unified model for new event recommendation. In particular, we utilize a topic model to derive user interests while adopting matrix factorization to infer organizer influences on users from the interactions between users and organizers. Moreover, we model users' geographical preferences via their location histories of attended events. We conduct a performance evaluation using real‐world data collected from DoubanEvent. The experimental results demonstrate the effectiveness of our proposed recommendation model.

Location-aware publish/subscribe is an important location-based service based on server-initiated model. Often times, the owner of massive spatio-textual messages and subscriptions outsources its location-aware publish/subscribe services to a third-party service provider, for example, cloud service provider, who is responsible for delivering messages to their relevant subscribers. The issue arising here is that the messages delivered by the service provider might be tailored for profit purposes, intentionally or not. Therefore, it is essential to develop mechanisms which allow subscribers to verify the correctness of the messages delivered by the service provider. In this paper, we study the problem of authenticating messages in outsourced location-aware publish/subscribe services. We propose an authenticated framework which not only can deliver the messages efficiently but also can make the subscribers’ authentication available with low cost. Extensive experiments on a real-world dataset demonstrate the effectiveness and efficiency of our proposed authenticated framework.

Community Question Answering (CQA) has increasingly become an important service for people asking questions and providing answers online, which enables people to help each other by sharing knowledge. Recently, with accumulation of users and contents, much concern has arisen over the efficiency and answer quality of CQA services. To address this problem, question routing has been proposed which aims at routing new questions to suitable answerers, who have both high possibility and high ability to answer the questions. In this paper, we formulate question routing as a multi-objective ranking problem, and present a multi-objective learning-to-rank approach for question routing (MLQR), which can simultaneously optimize the answering possibility and answer quality of routed users. In MLQR, realizing that questions are relatively short and usually attached with tags, we first propose a tagword topic model (TTM) to derive topical representations of questions. Based on TTM, we then develop features for each question-user pair, which are captured at both platform level and thread level. In particular, the platform-level features summarize the information of a user from his/her history posts in the CQA platform, while the thread-level features model the pairwise competitions of a user with others in his/her answered threads. Finally, we extend a state-of-the-art learning-to-rank algorithm for training a multi-objective ranking model. Extensive experimental results on real-world datasets show that our MLQR can outperform state-of-the-art methods in terms of both answering possibility and answer quality.

In this paper, we study the novel problem of publishing high-dimensional data in a distributed multi-party environment under differential privacy. In particular, with the assistance of a semi-trusted curator, the involved parties (i.e., local data owners) collectively generate a synthetic integrated dataset while satisfying ε-differential privacy for any local dataset. To solve this problem, we present a differentially private sequential update of Bayesian network (DP-SUBN) solution. In DP-SUBN, the parties and the curator collaboratively identify the Bayesian network ℕ that best fits the integrated dataset D in a sequential manner, from which a synthetic dataset can then be generated. The fundamental advantage of adopting the sequential update manner is that the parties can treat the statistical results provided by previous parties as their prior knowledge to direct how to learn ℕ. The core of DP-SUBN is the construction of the search frontier, which can be seen as a priori knowledge to guide the parties to update ℕ. To improve the fitness of ℕ and reduce the communication cost, we introduce a correlation-aware search frontier construction (CSFC) approach, where attribute pairs with strong correlations are used to construct the search frontier. In particular, to privately quantify the correlations of attribute pairs without introducing too much noise, we first propose a non-overlapping covering design (NOCD) method, and then introduce a dynamic programming method to find the optimal parameters used in NOCD to ensure that the injected noise is minimum. Through formal privacy analysis, we show that DP-SUBN satisfies ε-differential privacy for any local dataset. Extensive experiments on a real dataset demonstrate that DP-SUBN offers desirable data utility with low communication cost.

Frequent itemset mining (FIM) is one of the most fundamental problems in data mining. It has practical importance in a wide range of application areas such as decision support, Web usage mining, bioinformatics, etc. Given a database, where each transaction contains a set of items, FIM tries to find itemsets that occur in transactions more frequently than a given threshold. Despite valuable insights the discovery of frequent itemsets can potentially provide, if the data is sensitive (e.g., web browsing history and medical records), releasing the discovered frequent itemsets might pose considerable threats to individual privacy.

Mining frequent subgraphs from a collection of input graphs is an important topic in data mining research. However, if the input graphs contain sensitive information, releasing frequent subgraphs may pose considerable threats to individual's privacy. In this paper, we study the problem of frequent subgraph mining (FGM) under the rigorous differential privacy model. We introduce a novel differentially private FGM algorithm, which is referred to as DFG. In this algorithm, we first privately identify frequent subgraphs from input graphs, and then compute the noisy support of each identified frequent subgraph. In particular, to privately identify frequent subgraphs, we present a frequent subgraph identification approach which can improve the utility of frequent subgraph identifications through candidates pruning. Moreover, to compute the noisy support of each identified frequent subgraph, we devise a lattice-based noisy support derivation approach, where a series of methods has been proposed to improve the accuracy of the noisy supports. Through formal privacy analysis, we prove that our DFG algorithm satisfies ε-differential privacy. Extensive experimental results on real datasets show that the DFG algorithm can privately find frequent subgraphs with high data utility.

A spatio-textual similarity join searches a spatio-textual data collection and reports the object pairs that satisfy the specified spatial distance threshold and textual similarity threshold. However, when the data owner outsources the join computations to a third-party cloud service provider, the service provider may send incomplete or incorrect join results to the data owner. In this paper, we propose a pairwise authentication scheme, a cluster based scheme and an order and bound based scheme to authenticate the results of spatiotextual similarity joins. Extensive experiments on a real-world dataset verify the effectiveness and efficiency of our proposed schemes in terms of various performance metrics.

Abstract In this paper, we study the problem of authentication of spatio‐textual similarity join queries in untrusted cloud environments. To solve this problem, we first propose a pairwise authentication scheme, where object pairs are considered as basic processing units. In this scheme, an object hash tree is proposed for the data owner (DO) to build the authenticated data structure (ADS) over the data collection. Moreover, during join processing, a pair table is introduced for the service provider (SP) to construct the verification object (VO) for client's authentication. However, when clients authenticate the join results, they have large number of pairs to examine, which leads to excessive computation cost. Therefore, we then propose an optimized MR*‐tree‐based scheme. In this scheme, the DO spatially organizes the objects in an ADS called MR*‐tree, which combines the concepts of the Merkle hash tree and the R*‐tree. Based on the MR*‐tree, the SP employs the depth‐first search strategy to find the join results and constructs the VO according to the visited nodes of the MR*‐tree. Our extensive experiments on the real‐world dataset verify the effectiveness and efficiency of our proposed schemes on several performance metrics, including the data preprocessing time, running time, VO size, and authentication time. Copyright © 2016 John Wiley & Sons, Ltd.

In this paper, we study the problem of mining frequent sequences under the rigorous differential privacy model. We explore the possibility of designing a differentially private frequent sequence mining (FSM) algorithm which can achieve both high data utility and a high degree of privacy. We found, in differentially private FSM, the amount of required noise is proportionate to the number of candidate sequences. If we could effectively prune those unpromising candidate sequences, the utility and privacy tradeoff can be significantly improved. To this end, by leveraging a sampling-based candidate pruning technique, we proposePFS$^2$, a novel differentially private FSM algorithm. It is the first algorithm that supports the general gap-constrained FSM in the context of differential privacy. The gap constraints in FSM can be used to limit the mining results to a controlled set of frequent sequences. In ourPFS$^2$algorithm, the core is to utilize sample databases to prune the candidate sequences generated based on the downward closure property. In particular, we use the noisy local support of candidate sequences in the sample databases to estimate which candidate sequences are potentially frequent. To improve the accuracy of such private estimations, a gap-aware sequence shrinking method is proposed to enforce the length constraint on the sample databases. Moreover, to calibrate the amount of noise required by differential privacy, a gap-aware sensitivity computation method is proposed to obtain the sensitivity of the local support computations with different gap constraints. Furthermore, to decrease the probability of misestimating frequent sequences as infrequent, a threshold relaxation method is proposed to relax the user-specified threshold for the sample databases. Through formal privacy analysis, we show that ourPFS$^2$algorithm is$\epsilon$-differentially private. Extensive experiments on real datasets illustrate that ourPFS$^2$algorithm can privately find frequent sequences with high accuracy.

In this paper, we study the problem of mining frequent sequences under the rigorous differential privacy model. We explore the possibility of designing a differentially private frequent sequence mining (FSM) algorithm which can achieve both high data utility and a high degree of privacy. We found, in differentially private FSM, the amount of required noise is proportionate to the number of candidate sequences. If we could effectively reduce the number of unpromising candidate sequences, the utility and privacy tradeoff can be significantly improved. To this end, by leveraging a sampling-based candidate pruning technique, we propose a novel differentially private FSM algorithm, which is referred to as PFS2. The core of our algorithm is to utilize sample databases to further prune the candidate sequences generated based on the downward closure property. In particular, we use the noisy local support of candidate sequences in the sample databases to estimate which sequences are potentially frequent. To improve the accuracy of such private estimations, a sequence shrinking method is proposed to enforce the length constraint on the sample databases. Moreover, to decrease the probability of misestimating frequent sequences as infrequent, a threshold relaxation method is proposed to relax the user-specified threshold for the sample databases. Through formal privacy analysis, we show that our PFS2algorithm is ϵ-differentially private. Extensive experiments on real datasets illustrate that our PFS2algorithm can privately find frequent sequences with high accuracy.

This paper studies the problem of energy-efficient scheduling for parallel tasks in high-performance computing systems, such as clusters and data centers. Our goal is to minimize the energy consumption of parallel tasks within a deadline constraint. Among the existing techniques that reduce the energy for computing systems, dynamic voltage and frequency scaling (DVFS) is generally considered as a promising technique that can strike a balance between the energy consumption and the performance for tasks. By using the DVFS technique, the main line of research is to slack the non-critical path tasks to reduce energy consumption of parallel tasks. However, the existing studies slack the tasks greedily and could not efficiently utilize the slack-room, i.e. the idle time of the processors. In this paper, we develop a novel slacking concept, partial optimal slacking (POS), which can take full advantage of the slack-room by slack-sharing. Our formal analysis shows that POS can lead to optimum energy reduction in the partial task set. Based on the POS concept, we propose a new scheduling algorithm for parallel tasks, namely enhanced an energy-efficient scheduling (EES) algorithm. Through extensive evaluation studies, the results demonstrate that the EES algorithm can further improve the energy efficiency of parallel tasks while meeting the deadline constraint.

With rapid advances in wireless communication, mobile devices and positioning technologies, location-based services (LBS) have recently emerged as one of today's most important applications in mobile networks. To obtain great flexibility and cost savings, LBS providers may outsource their data services to the cloud. However, to protect data privacy, sensitive data have to be encrypted before outsourcing, which may impede the functionality and performance of the data services. In this paper, to make one step closer towards practical deployment of LBS in the cloud, we study the problem of secure and efficient k-nearest neighbor (kNN) query processing over encrypted spatial data. Although there exist a number of studies on kNN query processing over encrypted data, few of them can provide security and efficiency simultaneously. To this end, we present a secure and efficient kNN query (SEkQ) scheme. In this scheme, a new encryption method, namely, asymmetric scalar-product-preserving encryption with Laplace noise (ASPELN) is proposed, which can resist both the chosen-plaintext and known-plaintext attacks. Based on ASPELN, an encrypted hierarchical index called SR-tree (short for Secure R-tree) is devised to facilitate efficient kNN query processing on encrypted spatial data. To search with the SR-tree index, two effective methods, namely, anchor-assisted position determination and position-distinguished trapdoor generation are proposed for the distance computations between the query point and SR-tree nodes under encryption. Thorough analysis shows the validity and security of the proposed scheme. Extensive experimental results on real datasets further demonstrate the proposed scheme can achieve high efficiency and good scalability. Copyright © 2015 John Wiley & Sons, Ltd.

Co-clustering has emerged to be a powerful data mining tool for two-dimensional co-occurrence and dyadic data. However, co-clustering algorithms often require significant computational resources and have been dismissed as impractical for large data sets. Existing studies have provided strong empirical evidence that expectation-maximization (EM) algorithms (e.g., k-means algorithm) with sequential updates can significantly reduce the computational cost without degrading the resulting solution. Motivated by this observation, we introduce sequential updates for alternate minimization co-clustering (AMCC) algorithms which are variants of EM algorithms, and also show that AMCC algorithms with sequential updates converge. We then propose two approaches to parallelize AMCC algorithms with sequential updates in a distributed environment. Both approaches are proved to maintain the convergence properties of AMCC algorithms. Based on these two approaches, we present a new distributed framework, Co-ClusterD, which supports efficient implementations of AMCC algorithms with sequential updates. We design and implement Co-ClusterD, and show its efficiency through two AMCC algorithms: fast nonnegative matrix tri-factorization (FNMTF) and information theoretic co-clustering (ITCC). We evaluate our framework on both a local cluster of machines and the Amazon EC2 cloud. Empirical results show that AMCC algorithms implemented in Co-ClusterD can achieve a much faster convergence and often obtain better results than their traditional concurrent counterparts.

Recently, there has been a growing interest in designing differentially private data mining algorithms. Frequent itemset mining (FIM) is one of the most fundamental problems in data mining. In this paper, we explore the possibility of designing a differentially private FIM algorithm which can not only achieve high data utility and a high degree of privacy, but also offer high time efficiency. To this end, we propose a differentially private FIM algorithm based on the FP-growth algorithm, which is referred to as PFP-growth. The PFP-growth algorithm consists of a preprocessing phase and a mining phase. In the preprocessing phase, to improve the utility and privacy tradeoff, a novel smart splitting method is proposed to transform the database. For a given database, the preprocessing phase needs to be performed only once. In the mining phase, to offset the information loss caused by transaction splitting, we devise a run-time estimation method to estimate the actual support of itemsets in the original database. In addition, by leveraging the downward closure property, we put forward a dynamic reduction method to dynamically reduce the amount of noise added to guarantee privacy during the mining process. Through formal privacy analysis, we show that our PFP-growth algorithm is ε-differentially private. Extensive experiments on real datasets illustrate that our PFP-growth algorithm substantially outperforms the state-of-the-art techniques.

Virtual network embedding, which means mapping virtual networks requested by users to a shared substrate network maintained by an Internet service provider, is a key function that network virtualization needs to provide. Prior work on virtual network embedding has primarily focused on maximizing the revenue of the Internet service provider and did not consider the energy cost in accommodating such requests. As energy cost is more than half of the operating cost of the substrate networks, while trying to accommodate more virtual network requests, minimizing energy cost is critical for infrastructure providers. In this paper, we make the first effort toward energy-aware virtual network embedding. We first propose an energy cost model and formulate the energy-aware virtual network embedding problem as an integer linear programming problem. We then propose two efficient energy-aware virtual network embedding algorithms: a heuristic-based algorithm and a particle-swarm-optimization-technique-based algorithm. We implemented our algorithms in C++ and performed side-by-side comparison with prior algorithms. The simulation results show that our algorithms significantly reduce the energy cost by up to 50% over the existing algorithm for accommodating the same sequence of virtual network requests.

Co-clustering is a powerful data mining tool for co-occurrence and dyadic data. As data sets become increasingly large, the scalability of co-clustering becomes more and more important. In this paper, we propose two approaches to parallelize co-clustering with sequential updates in a distributed environment. Based on these two approaches, we present a new distributed framework, Co-ClusterD, that supports efficient implementations of co-clustering algorithms with sequential updates. We design and implement Co-ClusterD, and show its efficiency through two co-clustering algorithms: fast nonnegative matrix tri-factorization (FNMTF) and information theoretic co-clustering (ITCC). We evaluate our framework on both a local cluster of machines and the Amazon EC2 cloud. Our evaluation shows that co-clustering algorithms implemented in Co-ClusterD can achieve better results and run faster than their traditional concurrent counterparts.

How to achieve energy efficiency to run a cloud data center is a major challenge in the era of rising electricity cost and environmental protection. Various techniques have been devised to help reduce energy consumption for cloud data centers that consist of a large number of identical servers, including dynamic allocation of active servers, consolidating diverse applications to run on them, and adjusting the CPU speed of an active server. Leveraging these techniques, we use an Online Coloring Bin Packing problem to model the consolidation problem and devise an effective application-aware approximation algorithm to find a near-optimal solution. We show a 1.7 asymptotic approximation ratio. We then apply a Predictive Bayesian Network model to identify daily workload patterns and adjust resource provisioning accordingly. We evaluate our approaches using traces collected from a real data center and demonstrate that (1) our prediction algorithm is effective in estimating future demands, (2) our coordinated approaches can provide significant savings of energy and operational costs close to the near-optimal offline solution, and (3) our approaches incur little reliability costs in term of wear-and-tear of server components.

In light of rapid increase of electricity cost, many business organizations have to find new ways to cut the electricity bill. This paper studies how to reduce the electricity cost in geographical inter-domain virtual network embedding, which embeds virtual networks requested by users to multiple geographically distributed substrate networks run by an infrastructure provider. Previous researches have primarily focused on finding embedding methods to increase revenues by accommodating more virtual network requests, with little attention to reducing the electricity cost. To bridge this gap, we formulate an electricity cost model and design an efficient cost-aware virtual network embedding algorithm by exploiting the location-varying and time-varying diversities of the electricity price and optimizing the energy consumption. Through extensive simulations, we show that our algorithm can significantly reduce the electricity cost by up to 21% over the existing cost-oblivious algorithm, while maintaining nearly the same revenues for the infrastructure provider.

In recent years large graph processing has emerged to be a popular application for companies because of the increasing large Web graph and social networks. The ever growing scale of graphs and recent emergence of cloud computing poses challenges to their efficient and cost-conscious scheduling approach for processing tasks. In this paper, we focus on the use of cloud resources for dispatching large graph processing tasks. We design a novel framework EComer that can be easily integrated into existing cloud infrastructure. The key component of this framework is a cost-conscious scheduling heuristic, called CCSH, which is an extension of Heterogeneous Earliest Finish Time (HEFT). Our algorithm CCSH first constructs a priority list of tasks and then assigns the task with the highest priority value to the cost-efficient virtual machine in a cloud setting. The comparison study, based on randomly generated large graphs and a real-life astronomy application model, demonstrates that our algorithm outperforms HEFT by exhibiting significant monetary cost savings at a reasonable increase in overall execution time.