Electric vehicles have become a trend as a replacement to gasoline-powered vehicles, and been promoted by worldwide policy makers as a solution to combat environmental problems and stimulate economy, whereas the lack of extreme fast charging infrastructure has become one main obstacle to broad adoption of electric vehicles. To promote the commercial success of electric vehicles, effective placement of electric vehicle (EV) charging stations is pivotal. While numerous studies address EV charging station placement, the integration of transportation network traffic, specifically equilibrium traffic assignment, where flows stabilize as drivers seek routes to minimize travel time, has been relatively limited. This research investigates equilibrium traffic assignment with the inclusion of extreme fast charging (XFC) stations and introduces an algorithmic solution. We assess diverse charging station placement strategies, including node-based and network-based approaches, weighing their respective advantages and drawbacks. Extensive experiments on real transportation networks of varying scales validate our algorithm and evaluate different charging station placement strategies. Many interesting findings are drawn from the study. For instance, increasing the number of XFC charging stations may not always result in reduced traffic time; the added value of extra stations beyond a certain threshold can be quite limited. The findings offer valuable insights for strategically deploying EV charging infrastructure, thus promoting electric vehicle adoption.

Adaptively Secure Attribute-Based Encryption with Outsourced Decryption" by

Recent works reveal that network embedding techniques enable many machine learning models to handle diverse downstream tasks on graph-structured data. However, as previous methods usually focus on learning embedding for a single network, they cannot learn representations transferable on multiple networks. Hence, it is important to design a network embedding algorithm that supports downstream model transferring on different networks, known as domain adaptation. In this article, we propose a Domain Adaptive Network Embedding framework, which applies Graph Convolutional Network to learn transferable embedding. In DANE, nodes from multiple networks are encoded to vectors via a shared and aligned embedding space. The distribution of embedding on different networks are further aligned by Adversarial Learning Regularization. To achieve better performance in scenarios where labels are provided, DANE adopts a cross-entropy error term of the GCN framework and class centroid aligning method. Moreover, DANE's advantages in learning transferable network embedding can be guaranteed theoretically. Extensive experiments reflect that the proposed framework outperforms other well-recognized network embedding baselines in cross-network domain adaptation tasks, and the semi-supervised components improve the performance significantly.

Electric vehicles have become a trend as a replacement to gasoline-powered vehicles, and been promoted by worldwide policy makers as a solution to combat environmental problems and stimulate economy, whereas the lack of extreme fast charging infrastructure has become one main obstacle to broad adoption of electric vehicles. To promote the commercial success of electric vehicles, millions of extreme fast charging stations are expected to be established in the next decade in the U.S. However, the widespread of electric vehicles and extreme fast charging infrastructure would impact transportation systems, such as mobility, congestion, equity, toll revenue, and infrastructure maintenance needs. As transportation infrastructure can last for a long time, effective planning must be able to predict the impact of projects and policies decades into the future. Given the nature of transportation systems that is of multiple interacting systems, this study develops mathematical models to quantitatively analyze this complicated and important problem. In particular, we utilize game theory to understand the dependency between the choices made by travelers, and the congestion and delay in the system with respect to traffic assignment. Our research results provide insights and guidance to strategic planning of extreme fast charging infrastructure.

Cloud-based workflow architecture has been widely used in e-science, e-business, smart city, and others, to automate business processes and improve their flexibility and maintainability. Online workflow executes in a collaborative and distributed environment and is prone to fraud and information leakage. Workflow authorization models are implemented to ensure that tasks are performed by authorized subjects with compliance of security/privacy polices. However, existing workflow authorization models have some limitations. First, most of the existing research focuses on static workflows, where an order arriving at a workflow traverses tasks in a fixed sequence. In many real applications, however, task routing is not deterministic, having a probability distribution or pattern that may be estimated from historical data. Second, existing research ignores practical resource constraints, like user utilization, order waiting time, etc. To address the limitations, this article studies the workflow authorization model under the more realistic dynamic settings. We formulate a workflow as a queueing system, so business constraints can be analytically represented, under reasonable assumptions. We model the studied problems as pseudo-Boolean satisfiaiblity problems and investigate their theoretical properties. We also develop algorithms and carry out computational studies. The experimental results show the effectiveness and efficiency of our developed solutions. Our research results are useful for production and process design in many real-life settings such as health care, online banking and electronic payment systems.

Significant developments and advancement pertaining to electric vehicle (EV) technologies, such as extreme fast charging (XFC), have been witnessed in the last decade. However, there are still many challenges to the wider deployment of EVs. One of the major barriers is its availability of fast charging stations. A possible solution is to build a fast charging sharing system, by encouraging small business owners or even householders to install and share their fast charging devices, by reselling electricity energy sourced from traditional utility companies or their own solar grid. To incentivize such a system, a smart dynamic pricing scheme is needed to facilitate those growing markets with fast charging stations. The pricing scheme is expected to take into account the dynamics intertwined with pricing, demand, and environment factors, in an effort to maximize the long-term profit with the optimal price. To this end, this paper formulates the problem of dynamic pricing for fast charging as a Markov decision process and accordingly proposes several algorithmic schemes for different applications. Experimental study is conducted with useful and interesting insights.

The anonymous password authentication scheme proposed in ACSAC'10 under an unorthodox approach of password wrapped credentials advanced anonymous password authentication to be a practically ready primitive, and it is being standardized. In this paper, we improve on that scheme by proposing a new method of "public key suppression" for achieving server-designated credential verifiability, a core technicality in materializing the concept of password wrapped credential. Besides better performance, our new method simplifies the configuration of the authentication server, rendering the resulting scheme even more practical. Further, we extend the idea of password wrapped credential to biometric wrapped credential}, to achieve anonymous biometric authentication. As expected, biometric wrapped credentials help break the linear server-side computation barrier intrinsic in the standard setting of biometric authentication. Experimental results validate the feasibility of realizing efficient anonymous biometric authentication.

To make the search engine more user-friendly, commercial search engines commonly develop applications to provide suggestion or recommendation for every posed query. Clustering semantically similar queries acts as an essential prerequisite to function well in those applications. However, clustering queries effectively is quite challenging, since they are usually short, incomplete and ambiguous. Existing prevalent clustering methods, such as K-Means or DBSCAN cannot guarantee good performance in such a highly dimensional environment. Through analyzing users’ click-through query logs, hierarchical agglomerative clustering gives good results but is computationally quite expensive. This paper identifies a novel feature for clustering search queries based on a key insight – queries’ top ranked search results can themselves be used to quantify query similarity. After investigating such feature, we propose a new similarity metric for comparing those diverse queries. This facilitates us to develop two very efficient and accurate algorithms integrated in query clustering. We conduct comprehensive experiments to compare the accuracy of our approach against the known baselines along two dimensions: 1) quantifying the cohesion/separation of clustered queries, and 2) justifying the results by real-world Internet users. The experimental results demonstrate that our two algorithms and the similarity metric can generate more accurate results within a significantly shorter time.

Statistical database auditing is the process of checking aggregate queries that are submitted in a continuous manner, to prevent inference disclosure. Compared to other data protection mechanisms, auditing has the features of flexibility and maximum information. Auditing is typically accomplished by examining responses to past queries to determine whether a new query can be answered. It has been recognized that query denials release information and can cause data disclosure. This paper proposes an auditing mechanism that is free of query denial threat and applicable to mixed types of aggregate queries, including sum, max, min, deviation, etc. The core ideas are (i) deriving the complete information leakage from each query denial and (ii) carrying the complete leaked information derived from past answered and denied queries to audit each new query. The information leakage deriving problem can be formulated as a set of parametric optimization programs, and the whole auditing process can be modeled as a series of convex optimization problems.

Role mining is to define a role set to implement the role-based access control (RBAC) system and regarded as one of the most important and costliest implementation phases. While various role mining models have been proposed, we find that user experience/perception – one ultimate goal for any information system – is surprisingly ignored by the existing works. One advantage of RBAC is to support multiple role assignments and allow a user to activate the necessary role to perform the tasks at each session. However, frequent role activating and deactivating can be a tendinous thing from the user perspective. A user-friendly RBAC system is expected to assign few roles to every user. So in this paper we propose to incorporate to the role mining process a user-role assignment constraint that mandates the maximum number of roles each user can have. Under this rationale, we formulate user-oriented role mining as the user role mining problem, where all users have the same maximal role assignments, the personalized role mining problem, where users can have different maximal role assignments, and the approximate versions of the two problems, which tolerate a certain amount of deviation from the complete reconstruction. The extra constraint on the maximal role assignments poses a great challenge to role mining, which in general is already a hard problem. We examine some typical existing role mining methods to see their applicability to our problems. In light of their insufficiency, we present a new algorithm, which is based on a novel dynamic candidate role generation strategy, tailored to our problems. Experiments on benchmark data sets demonstrate the effectiveness of our proposed algorithm.

Severe privacy leakage in the AOL search log incident has attracted considerable worldwide attention. However, all the web users' daily search intents and behavior are collected in such data, which can be invaluable for researchers, data analysts and law enforcement personnel to conduct social behavior study [14], criminal investigation [5] and epidemics detection [10]. Thus, an important and challenging research problem is how to sanitize search logs with strong privacy guarantee and sufficiently retained utility. Existing approaches in search log sanitization are capable of only protecting the privacy under a rigorous standard [24] or maintaining good output utility [25] . To the best of our knowledge, there is little work that has perfectly resolved such tradeoff in the context of search logs, meeting a high standard of both requirements. In this paper, we propose a sanitization framework to tackle the above issue in a distributed manner. More specifically, our framework enables different parties to collaboratively generate search logs with boosted utility while satisfying Differential Privacy. In this scenario, two privacy-preserving objectives arise: first, the collaborative sanitization should satisfy differential privacy; second, the collaborative parties cannot learn any private information from each other. We present an efficient protocol -Collaborative sEarch Log Sanitization (CELS) to meet both privacy requirements. Besides security/privacy and cost analysis, we demonstrate the utility and efficiency of our approach with real data sets.

Community detection is an important task for social networks, which helps us understand the functional modules on the whole network. Among different community detection methods based on graph structures, modularity-based methods are very popular recently, but suffer a well-known resolution limit problem. This paper connects modularity-based methods with correlation analysis by subtly reformatting their math formulas and investigates how to fully make use of correlation analysis to change the objective function of modularity-based methods, which provides a more natural and effective way to solve the resolution limit problem. In addition, a novel theoretical analysis on the upper bound of different objective functions helps us understand their bias to different community sizes, and experiments are conducted on both real life and simulated data to validate our findings.

Role Based Access Control (RBAC) is accepted as the de facto access control model for organizations of all sizes. However, engineering the right set of roles is crucial to enable the correct deployment of RBAC within an organization. Indeed, discovering an optimal and correct set of roles from existing permission assignments, referred to as the role mining problem (RMP), has gained significant attention in recent years. Role Mining is itself an instantiation of Boolean matrix decomposition – wherein a Boolean matrix is decomposed into two Boolean matrices giving a set of basis vectors and their appropriate combination. In fact, such decompositions are useful in a number of application domains beyond role engineering, including text mining as well as knowledge discovery. While a Boolean matrix can be decomposed in many ways, however, certain decompositions better characterize the semantics associated with the original matrix in a succinct but comprehensive way. Indeed, one can find different decompositions that are optimal with respect to different criteria that may match various semantics. In this paper, we first present a number of variants of the optimal Boolean matrix decomposition problem, including usage RMP, basic RMP, δ-approximate RMP, and edge RMP, that have pragmatic implications in the context of role mining. We then present a unified framework for modeling the optimal Boolean matrix decomposition and its variants using integer linear programming (ILP). Such modeling allows us to directly adopt the huge body of heuristic solutions and tools developed for integer linear programming. We also develop efficient heuristics and solutions for each RMP variant, and validate them by a comprehensive experimental evaluation.

Web search logs contain extremely sensitive data, as evidenced by the recent AOL incident. However, storing and analyzing search logs can be very useful for many purposes (i.e. investigating human behavior). Thus, an important research question is how to privately sanitize search logs. Several search log anonymization techniques have been proposed with concrete privacy models. However, in all of these solutions, the output utility of the techniques is only evaluated rather than being maximized in any fashion. Indeed, for effective search log anonymization, it is desirable to derive the outputs with optimal utility while meeting the privacy standard. In this paper, we propose utility-maximizing sanitization based on the rigorous privacy standard of differential privacy, in the context of search logs. Specifically, we utilize optimization models to maximize the output utility of the sanitization for different applications, while ensuring that the production process satisfies differential privacy. An added benefit is that our novel randomization strategy maintains the schema integrity in the output search logs. A comprehensive evaluation on real search logs validates the approach and demonstrates its robustness and scalability.

In today's networked world, resource providers and consumers are distributed globally and locally, especially under current cloud computing environment. However, with resource constraints, optimization is necessary to ensure the best possible usage of such scarce resources. Distributed linear progr amming (DisLP) problems allow collaborative agents to jointly maximize profits or minimize costs with a linear objective function while conforming to several shared as well as local linear constraints. Since each agent's share of the global constraints and the local constraints generally refer to its private limitations or capacities, serious privacy problems may arise if such information is revealed. While there have been some solutions raised that allow secure computation of such problems, they typically rely on inefficient protocols with enormous computation and communication cost. In this paper, we study the DisLP problems where constraints are arbitrarily partitioned and every agent privately holds a set of variables, and propose secure and extremely efficient approach based on mathematical transformation in two adversary models – semi-honest and malicious model. Specifically, we first present a secure column generation (SCG) protocol that securely solves the above DisLP problem amongst two or more agents without any private information disclosure, assuming semi-honest behavior (all agents properly follow the protocol but may be curious to derive private information from other agents). Furthermore, we discuss potential selfish actions and colluding issues in malicious model (distributed agents may corrupt the protocol to gain extra benefit) and propose an incentive compatible protocol to resolve such malicious behavior. To address the effectiveness of our protocols, we present security analysis for both adversary models as well as the communication/computation cost analysis. Finally, our experimental results validate the efficiency of our approach and demonstrate its scalability.

The role mining problem has received considerable attention recently. Among the many solutions proposed, the Boolean matrix decomposition (BMD) formulation has stood out, which essentially discovers roles by decomposing the binary matrix representing user-to-permission assignment (UPA) into two matrices-user-to-role assignment (UA) and permission-to-role assignment (PA). However, supporting certain embedded constraints, such as separation of duty (SoD) and exceptions, is critical to the role mining process. Otherwise, the mined roles may not capture the inherent constraints of the access control policies of the organization. None of the previously proposed role mining solutions, including BMD, take into account these underlying constraints while mining. In this paper, we extend the BMD so that it reflects such embedded constraints by proposing to allow negative permissions in roles or negative role assignments for users. Specifically, by allowing negative permissions in roles, we are often able to use less roles to reconstruct the same given user-permission assignments. Moreover, from the resultant roles we can discover underlying constraints such as separation of duty constraints. This feature is not supported by any existing role mining approaches. Hence, we call the role mining problem with negative authorizations the constraint-aware role mining problem (CRM). We also explore other interesting variants of the CRM, which may occur in real situations. To enable CRM and its variants, we propose a novel approach, extended Boolean matrix decomposition (EBMD), which addresses the ineffectiveness of BMD in its ability of capturing underlying constraints. We analyze the computational complexity for each of CRM variants and present heuristics for problems that are proven to be NP-hard.

Enterprises outsourcing their databases to the cloud and authorizing multiple users for access represents a typical use scenario of cloud storage services. In such a case of database outsourcing, data encryption is a good approach enabling the data owner to retain its control over the outsourced data. Searchable encryption is a cryptographic primitive allowing for private keyword based search over the encrypted database. The above setting of enterprise outsourcing database to the cloud requires multi-user searchable encryption, whereas virtually all of the existing schemes consider the single-user setting. To bridge this gap, we are motivated to propose a practical multi-user searchable encryption scheme, which has a number of advantages over the known approaches. The associated model and security requirements are also formulated. We further discuss to extend our scheme in several ways so as to achieve different search capabilities.

Mining discrete patterns in binary data is important for many data analysis tasks, such as data sampling, compression, and clustering. An example is that replacing individual records with their patterns would greatly reduce data size and simplify subsequent data analysis tasks. As a straightforward approach, rank-one binary matrix approximation has been actively studied recently for mining discrete patterns from binary data. It factorizes a binary matrix into the multiplication of one binary pattern vector and one binary presence vector, while minimizing mismatching entries. However, this approach suffers from two serious problems. First, if all records are replaced with their respective patterns, the noise could make as much as 50% in the resulting approximate data. This is because the approach simply assumes that a pattern is present in a record as long as their matching entries are more than their mismatching entries. Second, two error types, 1-becoming-0 and 0-becoming-1, are treated evenly, while in many application domains they are discriminated. To address the two issues, we propose weighted rank-one binary matrix approximation. It enables the tradeoff between the accuracy and succinctness in approximate data and allows users to impose their personal preferences on the importance of different error types. The decision problem, however, as proved in the paper is NP-complete. To solve it, several different mathematical programming formulations are provided, from which 2-approximation algorithms are derived for some special cases. An adaptive tabu search heuristic is presented for solving the general problem, and our experimental study shows the effectiveness of the heuristic.

Clustering of search engine queries has attracted significant attention in recent years. Many search engine applications such as query recommendation require query clustering as a pre-requisite to function properly. Indeed, clustering is necessary to unlock the true value of query logs. However, clustering search queries effectively is quite challenging, due to the high diversity and arbitrary input by users. Search queries are usually short and ambiguous in terms of user requirements. Many different queries may refer to a single concept, while a single query may cover many concepts. Existing prevalent clustering methods, such as K-Means or DBSCAN cannot assure good results in such a diverse environment. Agglomerative clustering gives good results but is computationally quite expensive. This paper presents a novel clustering approach based on a key insight -- search engine results might themselves be used to identify query similarity. We propose a novel similarity metric for diverse queries based on the ranked URL results returned by a search engine for queries. This is used to develop a very efficient and accurate algorithm for clustering queries. Our experimental results demonstrate more accurate clustering performance, better scalability and robustness of our approach against known baselines.

As more and more organizations collect, store, and release large amounts of personal information, it is increasingly important for the organizations to conduct privacy risk assessment so as to comply with various emerging privacy laws and meet information providers' demands. Existing statistical database security and inference control solutions may not be appropriate for protecting privacy in many new uses of data as these methods tend to be either less or over-restrictive in disclosure limitation or are prohibitively complex in practice. We address a fundamental question in privacy risk assessment which asks: how to accurately derive bounds for protected information from inaccurate released information or, more particularly, from bounds of released information. We give an explicit formula for calculating such bounds from bounds, which we call square bounds or S-bounds. Classic F-bounds in statistics become a special case of S-bounds when all released bounds retrograde to exact values. We propose a recursive algorithm to extend our S-bounds results from two dimensions to high dimensions. To assess privacy risk for a protected database of personal information given some bounds of released information, we define typical privacy disclosure measures. For each type of disclosure, we investigate the distribution patterns of privacy breaches as well as effective and efficient controls that can be used to eliminate privacy risk, both based on our S-bounds results.

Contingency tables are widely used in many fields to analyze the relationship or infer the association between two or more variables. Indeed, due to their simplicity and ease, they are one of the first methods used to analyze gathered data. Typically, the construction of contingency tables from sou rce data is considered straightforward since all data is supposed to be aggregated at a single party. However, in many cases, the collected data may actually be federated among different parties. While construction of the global contingency tables would still be of immense interest, privacy and security concerns may restrict the data owners from free sharing of the raw data. In this paper, we propose techniques for enabling secure construction of contingency tables from both horizontally and vertically partitioned data. Our methods are efficient and secure. We also examine cases where the constructed contingency table may itself leak too much information and discuss potential solutions. In order to protect certain sensitive cell values against being inferred from the marginal totals of a constructed contingency table, we further address the problem of how to securely publish the marginal totals.

In a database system, disclosure of confidential private data may occur if users can put together the answers of past queries. Traditional access control mechanisms cannot guard against such breaches to private data. Online auditing techniques have been advanced to limit such disclosure of private data. Essentially, before answering any query, these techniques inspect the answers of the past queries to determine whether answering this query would compromise the stated data disclosure policies. While the primary requirement for online auditing is high efficiency, existing auditing approaches are expensive with respect to both computational time and space. Specifically, this cost is excessive in the general case of auditing arbitrary aggregate queries over real-valued confidential attributes with respect to interval-based privacy disclosure.

With the vast increase in collection and storage of data, the problem of data summarization is most critical for effective data management. Since much of this data is categorical in nature, it can be viewed in terms of a Boolean matrix. Boolean matrix decomposition (BMD) has been used to provide concise and interpretable representations of Boolean data sets. A Boolean matrix can be expressed as a product of two Boolean matrices, where the first matrix represents a set of meaningful concepts, and the second describes how the observed data can be expressed as combinations of those concepts. Typically, the combination is only in terms of the set union. In other words, a successful Boolean matrix decomposition gives a set of concepts and shows how every column of the input data can be expressed as a union of some subset of those concepts. However, this way of modeling only incompletely represents real data semantics. Essentially, it ignores a critical component -- the set difference operation: a column can be expressed as the combination of union of certain concepts as well as the exclusion of other concepts. This has two significant benefits. First, the total number of concepts required to describe the data may itself be reduced. Second, a more succinct summarization may be found for every column. In this paper, we propose the extended Boolean matrix decomposition (EBMD) problem, which aims to factor Boolean matrices using both the set union and set difference operations. We study several variants of the problem, show that they are NP-hard, and propose efficient heuristics to solve them. Extensive experimental results demonstrate the power of EBMD.

Because of its ease of administration, role-based access control (RBAC) has become the norm to enforcing security in most of today's organizations. For implementing RBAC, it is important to devise a complete and correct set of roles. This task, known as role engineering, has been identified as one of the costliest components in deploying RBAC. A key problem with respect to role engineering is that there is no formal metric for measuring the goodness/interestingness of the devised set of roles. Recently, Vaidya et al. [26], formally define the role mining problem (RMP) as the problem of discovering an optimal set of roles from existing user permissions, and analyze its theoretical bounds. Essentially, given a user-permission assignment (UPA), the basic RMP is to discover the user-role assignment relation (UA) and role-permission assignment relation (PA) such that the number of roles required is minimum. In this paper, we present another interesting and useful problem, called the edge-RMP, with a different minimality objective. The edge-RMP, requires the discovery of a complete and correct set of roles such that the discovered |UA|+|PA| is the minimum possible. Minimal |UA|+|PA| is a useful metric as it would minimize the administrative burden since less number of assignments need to be managed. Although the basic-RMP and the edge-RMP appear to be related problems, we demonstrate with concrete examples that they are, in fact, independent of each other. We prove that the edge-RMP is an NP-hard problem by reducing the known “vertex cover problem” to the decision version of the edge-RMP. Another important contribution of this paper is to provide a binary integer programming solution to this problem by showing that the edge-RMP can be formulated in that form. As a result, one can directly borrow existing implementation solutions for binary integer programming and guide further research in this direction. We also propose a heuristic solution for large scale problems, and experimentally validate our algorithm.

A decomposition of a binary matrix into two matrices gives a set of basis vectors and their appropriate combination to form the original matrix. Such decomposition solutions are useful in a number of application domains including text mining, role engineering as well as knowledge discovery. While a binary matrix can be decomposed in several ways, however, certain decompositions better characterize the semantics associated with the original matrix in a succinct but comprehensive way. Indeed, one can find different decompositions optimizing different criteria matching various semantics. In this paper, we first present a number of variants to the optimal Boolean matrix decomposition problem that have pragmatic implications. We then present a unified framework for modeling the optimal binary matrix decomposition and its variants using binary integer programming. Such modeling allows us to directly adopt the huge body of heuristic solutions and tools developed for binary integer programming. Although the proposed solutions are applicable to any domain of interest, for providing more meaningful discussions and results, in this paper, we present the binary matrix decomposition problem in a role engineering context, whose goal is to discover an optimal and correct set of roles from existing permissions, referred to as the role mining problem (RMP). This problem has gained significant interest in recent years as role based access control has become a popular means of enforcing security in databases. We consider several variants of the above basic RMP, including the min-noise RMP, delta-approximate RMP and edge-RMP. Solutions to each of them aid security administrators in specific scenarios. We then model these variants as Boolean matrix decomposition and present efficient heuristics to solve them.

The fundamental problem for inference control in data cubes is how to efficiently calculate the lower and upper bounds for each cell value given the aggregations of cell values over multiple dimensions. In this paper, we provide the first practical solution for estimating exact bounds in two-dimensional irregular data cubes (that is, data cubes in which certain cell values are known to a snooper). Our results imply that the exact bounds cannot be obtained by a direct application of the Frechet bounds in some cases. We then propose a new approach to improve the classic Frechet bounds for any high-dimensional data cube in the most general case. The proposed approach improves upon the Frechet bounds in the sense that it gives bounds that are at least as tight as those computed by Frechet yet is simpler in terms of time complexity. Based on our solutions to the fundamental problem, we discuss various security applications such as privacy protection of released data, fine-grained access control, and auditing, and identify some future research directions.

The fundamental problem for inference control in data cubes is how to efficiently calculate the lower and upper bounds for each cell value given the aggregations of cell values over multiple dimensions. In this paper, we provide the first practical solution for estimating exact bounds in two-dimensional irregular data cubes (i.e., data cubes in which certain cell values are known to a snooper). Our results imply that the exact bounds cannot be obtained by a direct application of the Frechet bounds in some cases. We then propose a new approach to improve the classic Frechet bounds for any high-dimensional data cube in the most general case. The proposed approach improves upon the Frechet bounds in the sense that it gives bounds that are at least as tight as those computed by Frechet, yet is simpler in terms of time complexity. Based on our solutions to the fundamental problem, we discuss two security applications, privacy protection of released data and fine-grained access control and auditing.