There has been significant interest in the development of anonymization schemes for publishing graph data. However, privacy is a major concern in dealing with graph data. In this paper, an integrated framework for ensuring privacy in the presence of an authorization mechanism is proposed. Access control mechanisms provide additional safeguard against data breaches and ensure that only authorized information is available to end-users based on their assigned roles. The integrated framework highlights a tradeoff between privacy and authorized privileges. To attain a pre-specified privacy level, access privileges might need to be relaxed. For the proposed framework, we formulate the k-anonymous Bi-objective Graph Partitioning (k-BGP) problem and provide its hardness results. Heuristics solutions are developed to solve the constraint problem. The framework provides an anonymous view based on the target class of role-based workloads for graph data. The proposed heuristics are empirically evaluated and a detailed security analysis of the framework in terms of risk associated with re-identification attack is conducted.

Graphs are used for representing and understanding objects and their relationships for numerous applications such as social networks, semantic webs, and biological networks. Integrity assurance of data and query results for graph databases is an essential security requirement. In this paper, we propose two efficient integrity verification schemes - HMACs for graphs (gHMAC) for two-party data sharing, and redactable HMACs for graphs (rgHMAC) for third-party data sharing, such as a cloud-based graph database service. The proposed schemes have linear complexity in terms of the number of vertices and edges in the graphs, which is shown to be optimal. Our experimental results corroborate that the proposed HMAC-based schemes for graphs are highly efficient as compared to the digital signature-based schemes - computation of HMAC tags is about 10 times faster than the computation of digital signatures.

Graphs are used for representing and understanding objects and their relationships for numerous applications such as social networks, Semantic Webs, and biological networks. Integrity assurance of data and query results for graph databases is an essential security requirement. In this paper, we propose two efficient integrity verification schemes-HMACs for graphs (gHMAC) for two-party data sharing, and redactable HMACs for graphs (rgHMAC) for third-party data sharing, such as a cloud-based graph database service. We compute one HMAC value for both the schemes and two other verification objects for rgHMAC scheme that are shared with the verifier. We show that the proposed schemes are provably secure with respect to integrity attacks on the structure and/or content of graphs and query results. The proposed schemes have linear complexity in terms of the number of vertices and edges in the graphs, which is shown to be optimal. Our experimental results corroborate that the proposed HMAC-based schemes for graphs are highly efficient as compared to the digital signature-based schemes-computation of HMAC tags is about 10 times faster than the computation of digital signatures.

Use of graph-structured data models is on the rise - in graph databases, in representing biological and healthcare data as well as geographical data. In order to secure graph-structured data, and develop cryptographically secure schemes for graph databases, it is essential to formally define and develop suitable collision resistant one-way hashing schemes and show them they are efficient. The widely used Merkle hash technique is not suitable as it is, because graphs may be directed acyclic ones or cyclic ones. In this paper, we are addressing this problem. Our contributions are: (1) define the practical and formal security model of hashing schemes for graphs, (2) define the formal security model of perfectly secure hashing schemes, (3) describe constructions of hashing and perfectly secure hashing of graphs, and (4) performance results for the constructions. Our constructions use graph traversal techniques, and are highly efficient for hashing, redaction, and verification of hashes graphs. We have implemented the proposed schemes, and our performance analysis on both real and synthetic graph data sets support our claims.

Decision Support Systems (DSS) are information systems that support decision making processes. In many scenarios these systems are built on top of data managed by DBMSs and make extensive use of its underlying grouping and aggregation capabilities, i.e., Group-by operation. Unfortunately, the standard grouping operator has the inherent limitation of being based only on equality, i.e., all the tuples in a group share the same values of the grouping attributes. Similarity-based Group-by (SGB) has been recently proposed as an extension aimed to overcome this limitation. SGB allows fast formation of groups with similar objects under different grouping strategies and the pipelining of results for further processing. This demonstration presents how SGB can be effectively used to build useful DSSs. The presented DSS has been built around the data model and queries of the TPC-H benchmark intending to be representative of complex business analysis applications. The system provides intuitive dashboards that exploit similarity aggregation queries to analyze: (1) customer clustering, (2) profit and revenue, (3) marketing campaigns, and (4) discounts. The presented DSS runs on top of PostgreSQL whose query engine is extended with similarity grouping operators.

Privacy preservation has become an important requirement in information systems that deal with personal data. In many cases this requirement is imposed by laws that recognize the right of data owners to control whom their information is shared with and the purposes for which it can be shared. Hippocratic databases have been proposed as an answer to this privacy requirement; they extend the architecture of standard DBMSs with components that ensure personal data is handled in compliance with its associated privacy definitions. Previous work in Hippocratic databases has proposed the design of some of these components. Unfortunately, there has not been much work done to implement these components as an integral part of a DBMS and study the problems faced to realize the Hippocratic databases. The main goal of the 'Hippocratic PostgreSQL' project is to perform this implementation and study. The project includes the implementation of components to support limited disclosure, limited retention time, and management of multiple policies and policy versions. This demo presents the use of these components both from a terminal-based SQL command interface and through a Web-based healthcare application that makes use of the implemented database-level privacy features. Hippocratic PostgreSQL has the novel feature of augmenting both k-anonymity and generalization hierarchies into the Hippocratic DBMS engine functionality. Several interesting problems emerge as a result and their solutions are presented in the context of this demo.

We demonstrate bdbms, an extensible database engine for biological databases, bdbms started on the observation that database technology has not kept pace with the specific requirements of biological databases and that several needed key functionalities are not supported at the engine level. While bdbms aims at supporting several of these functionalities, this demo focuses on: (1) Annotation and provenance management including storage, indexing, querying, and propagation, (2) Local dependency tracking of dependencies and derivations among data items, and (3) Update authorization to support data curation. We demonstrate how bdbms enables biologists to manipulate their databases, annotations, and derivation information in a unified database system using the Purdue ionomics information management system (PiiMS) as a case study.

Conventional Association Rule Mining algorithms require a user-specified minimum support threshold to mine the frequent itemsets (FIs). However, selecting such an optimum support threshold, to find the desired resulting FIs, is a tough proposition. There will be too many or too few resulting FIs if the threshold is not selected appropriately. Therefore, it is more desirable to have a solution that allows the users to control the amount of results. In this paper, we propose an efficient implementation for a constraint based FI mining problem, i.e. to mine N k-itemsets with the highest support for k up to a certain kmax value. The results thus obtained are called N-most interesting itemsets [1]. We have devised and implemented two new efficient algorithms, named NFOLD-growth and LOOPBACKNFOLD-growth, for the above-mentioned problem. Our implementation is based on a novel data structure, SOTrieIT (Support-Ordered Trie Itemset), proposed recently in literature [2]. Our simulations show that our algorithms significantly outperform the previous solutions for the same problem in terms of execution time. In addition to being support independent and incremental, the algorithms are also more space-efficient than the previous algorithms.