Many complex natural and technological systems are commonly modeled as count-weighted graphs, where nodes represent entities, edges model relationships between them, and edge weights define some counting statistics associated with each relationship. As graph data usually contain sensitive information about entities, preserving privacy when releasing this type of data becomes an important issue. In this context, differential privacy (DP) has become the de facto standard for data release under strong privacy guarantees. When dealing with DP for weighted graphs, most state-of-the-art works assume that the graph topology is known. However, in several real-world applications, the privacy of the graph topology also needs to be ensured. In this paper, we aim to bridge the gap between DP and count-weighted graph data release, considering both graph structure and edge weights as private information. We first adapt the weighted graph DP definition to take into account the privacy of the graph structure. We then develop two novel approaches to privately releasing count-weighted graphs under the notions of global and local DP. We also leverage the post-processing property of DP to improve the accuracy of the proposed techniques considering graph domain constraints. Experiments using real-world graph data demonstrate the superiority of our approaches in terms of utility over existing techniques, enabling subsequent computation of a variety of statistics on the released graph with high utility, in some cases comparable to the non-private results.

Differential privacy is the state-of-the-art formal definition for data release under strong privacy guarantees. A variety of mechanisms have been proposed in the literature for releasing the noisy output of numeric queries (e.g., using the Laplace mechanism), based on the notions of global sensitivity and local sensitivity. However, although there has been some work on generic mechanisms for releasing the output of non-numeric queries using global sensitivity (e.g., the Exponential mechanism), the literature lacks generic mechanisms for releasing the output of non-numeric queries using local sensitivity to reduce the noise in the query output. In this work, we remedy this shortcoming and present the local dampening mechanism. We adapt the notion of local sensitivity for the non-numeric setting and leverage it to design a generic non-numeric mechanism. We illustrate the effectiveness of the local dampening mechanism by applying it to two diverse problems: (i) Influential node analysis. Given an influence metric, we release the top-k most influential nodes while preserving the privacy of the relationship between nodes in the network; (ii) Decision tree induction. We provide a private adaptation to the ID3 algorithm to build decision trees from a given tabular dataset. Experimental results show that we could reduce the use of privacy budget by 3 to 4 orders of magnitude for Influential node analysis and increase accuracy up to 12% for Decision tree induction when compared to global sensitivity based approaches.

Differential privacy is a model which gives strong privacy guarantees. It was designed to make difficult to distinguish individuals' records on statistical databases while maximizing data utility. Differential privacy approaches usually assume that database records are sampled independently, i.e., each record of this database is independent of the rest. However, this assumption is not always true in the context of real-world applications. In this paper we propose DiPCoDing, a novel approach to calculate the correlation between records in statistical databases using clusterization. For this matter, we have considered Density-Based Spatial Clustering of Applications with Noise (DBSCAN) and Gaussian Mixture Model (GMM). Our method aims to group similar records, which are more likely to be correlated, to reduce the sensitivity of differential privacy and consequently the amount of noise added to the query answer, increasing data utility while providing privacy for correlated data. The experimental results of our approach showed that relative errors and noisy answers are significantly lower than those from existing works.

As the amount of collected social network information in RDF format grows, the development of solutions for the privacy of individuals, their attributes and relationships with others becomes an important subject of study. However, data privacy solutions are not well suitable for this specific type of data, mainly because they usually do not consider relationships between individuals, which are crucial to semantic data and social networks. Differential privacy is one of the most suitable techniques for statistical queries and, although it has been extensively studied in many papers, there is still much research to be done in this context. This paper presents two main contributions for privacy preserving statistic queries containing sensitive information about relationships between individuals. The first one is a complete approach to applying ϵ-differential privacy for RDF data and the second one presents an index-like data structure to efficiently compute parameters for the differential privacy mechanism: the query's actual value and data sensitivity for the given query. We conclude by evaluating our contributions over three real social network datasets presenting utility analysis for different values of ϵ. We also show the performance benefit of our index-like data structure for sensitivity calculation.

Cloud computing is a recent trend of technology that aims to provide unlimited, on-demand, elastic computing and data storage resources. In this context, cloud services decrease the need for local data storage and the infrastructure costs. However, hosting confidential data at a cloud storage service requires the transfer of control of the data to a semi-trusted external provider. Therefore, data confidentiality is the top concern from the cloud issues list. Recently, three main approaches have been introduced to ensure data confidentiality in cloud services: data encryption; combination of encryption and fragmentation; and fragmentation. Besides, other strategies use a mix of these three main approaches. In this paper, we present i-OBJECT, a new approach to preserve data confidentiality in cloud environments. The proposed mechanism uses information decomposition to split data into unrecognizable parts and store them in different cloud service providers. Experimental results show the potential efficiency of i-OBJECT.

In this paper we present an algorithm for optimal processing of time-dependent sequenced route queries in road networks, i.e., given a road network where the travel time over an edge is time-dependent and a given ordered list of categories of interest, we find the fastest route between an origin and destination that passes through a sequence of points of interest belonging to each of the specified categories of interest. Our approach uses the A* search paradigm equipped with an admissible heuristic function, thus guaranteed to yield the optimal solution, along with a pruning scheme for further reducing the search space. Our experiments using a real data set have shown our proposed solution to be up to two orders of magnitude faster than a previous solution extended to handle time-dependency.

We consider the problem of finding the k nearest points of interest from a given location in time-dependent road networks, i.e., One where travel time along each edge is a function of the departure time, and where the operating times of the points of interest are also taken into consideration. More specifically, we address the following query: find the k points of interest in which a user can start to be served in the minimum amount of time, accounting for both the travel time to the point of interest and the waiting time, if it is closed. Previous works have proposed solutions to answer kNN queries considering the time dependency of the network but not the operating times of the points of interest. We propose and discuss three solutions to this type of query which are based on the previously proposed incremental network expansion and use the A search algorithm equipped with suitable heuristic functions. We also present experimental results comparing the number of disk access required in each solution with respect to a few different parameters.