Sampling schemes can provide fast approximate answers to aggregation queries. However, weighted sampling must create a sample for each measure column, which leads to expensive storage cost for any table with dozens of columns. To address this issue, we generalize both measure-biased sampler and priority sampler, which can compress the samples but still provide fast approximate answers to both distribution query and subset-sum query within a user-specified error bound. We also extend the priority sampler to support multiple types of aggregates for arbitrary subset. Our generalized samplers achieve a remarkable improvement over the original samplers in terms of the error metrics.

In this paper, we propose BiTDB, a built-in Trusted Execution Environment (TEE) database for embedded systems, to realize higher system availability while ensuring data confidentiality. With BiTDB, dilemmas that the state-of-the-art research work on secure embedded databases has to face can be significantly reduced and eliminated, including (i) complicated research and realization on searchable encryption algorithms (SEA), (ii) limited support to all database operations, and (iii) almost none of specific design and optimizations toward built-in TEE embedded databases. Through BiTDB, all database operations can process plaintext in TEE instead of retrieving ciphertext by developing complicated SEAs. To enable BiTDB to handle database files in Rich Execution Environment (REE) as local ones, we extend the TEE OS with generic file I/O libraries. Then, we contribute three critical optimizations to significantly reduce redundant memory and file operations between TEE and REE, and BiTDB achieve better system performance and availability in embedded systems. Finally, we have implemented the prototype system based on OP-TEE and SQLite for several typical platforms, including virtualization and hardware environments. The TPC-H test shows BiTDB can achieve 85% (on average) of the original database performance while guaranteeing data confidentiality and integrity.

Query with aggregates is one of the most important classes of ad-hoc queries. Since query response time is critical in many scenarios, small errors are usually tolerable for query processing. In this work, we adopt sampling to provide fast approximate answers to distribution query and subset-sum query. On the one hand, uniform sampler is sub-optimal. On the other hand, both measure-biased sampler and priority sampler need to create a sample for each measure column. It leads to expensive storage cost, when there are dozens or hundreds of measure columns in the table. To address this issue, we generalize both measure-biased sampler and priority sampler, which can compress the samples but still provide fast approximate answers to both distribution query and subset-sum query within a user-specified error bound. Besides, we establish the relationship between measure-biased sampler and priority sampler by constructing a measure-biased sample from a priority sample. We also extend the priority sampler to support multiple types of aggregates for arbitrary subset. In the extensive experimental evaluation, our generalized samplers achieve a remarkable improvement over the original samplers in terms of the error metrics.

In cloud computing, remote accesses over the cloud data inevitably bring the issue of trust. Despite strong encryption schemes, adversaries can still learn sensitive information from encrypted data by observing data access patterns. Oblivious RAMs (ORAMs) are proposed to protect against access pattern attacks. However, directly deploying ORAM constructions in an encrypted database brings large computational overhead. In this work, we focus on oblivious joins over a cloud database. Existing studies in the literature are restricted to either primary-foreign key joins or binary equi-joins. Our major contribution is to support general band joins and multiway equi-joins. For oblivious join without ORAMs, we extend the existing binary equi-join algorithm to support general band joins obliviously. For oblivious join with ORAMs, we integrate$B$-tree indices into ORAMs for each input table and retrieve blocks through the indices in join processing. The key point is to avoid retrieving tuples that make no contribution to the final join result and bound the number of accesses to each$B$-tree index. The effectiveness and efficiency of our algorithms are demonstrated through extensive evaluations over real-world datasets. Our method shows orders of magnitude speedup for oblivious multiway equi-joins in comparison with baseline algorithms.

In this paper, we propose BiTDB, a built-in Trusted Execution Environment (TEE) database for embedded systems, to realize higher system availability while ensuring data confidentiality. With BiTDB, dilemmas that the state-of-the-art research work on secure embedded databases has to face can be significantly reduced and eliminated, including (i) complicated research and realization on searchable encryption algorithms (SEA), (ii) limited support to all database operations, and (iii) almost none of specific design and optimizations toward build-in TEE embedded databases. Through BiTDB, all database operations can process plaintext in TEE instead of retrieving ciphertext by developing complicated SEAs. To enable BiTDB to handle database files in Rich Execution Environment (REE) as local ones, we extend the TEE OS with generic file I/O libraries. Then, we contribute three critical optimizations to significantly reduce redundant memory and file operations between TEE and REE, and BiTDB achieve better system performance and availability in embedded systems. Finally, we have implemented the prototype system based on OP-TEE and SQLite for several typical platforms, including virtualization and hardware environments. The TPC-H test shows BiTDB can achieve 85% (on average) of the original database performance while guaranteeing data confidentiality and integrity. Our project repository is athttps://github.com/CharlieMCY/BiTDB.

In this paper, we incorporate the realistic scenario of key protection into link privacy preserving and propose the target-link privacy preserving (TPP) model: target links referred to as targets are the most important and sensitive objectives that would be intentionally attacked by adversaries, in order that need privacy protections, while other links of less privacy concerns are properly released to maintain the graph utility. The goal of TPP is to limit the target disclosure by deleting a budget limited set of alternative non-target links referred to as protectors to defend the adversarial link predictions for all targets. Traditional link privacy preserving treated all links as targets and concentrated on structural level protections in which serious link disclosure and high graph utility loss is still the bottleneck of graph releasing today, while TPP focuses on the target level protections in which key protection is implemented on a tiny fraction of critical targets to achieve better privacy protection and lower graph utility loss. Currently there is a lack of clear TPP problem definition, provable optimal or near optimal protector selection algorithms and scalable implementations on large-scale social graphs. Firstly, we introduce the TPP model and propose a dissimilarity function used for measuring the defense ability against privacy analyzing for the targets. We consider two different problems by budget assignment settings: 1) we protect all targets and to optimize the dissimilarity of all targets with a single budget; 2) besides the protections of all targets, we also care about the protection of each target by assigning a local budget to every target. Moreover, we propose two local protector selections, namely cross-target and with-target pickings. Each problem with each protector picking selection is corresponding to a greedy algorithm. We also implement scalable implementations for all greedy algorithms by limiting the selection scale of protectors, and we prove that all greedy-based algorithms achieve approximation by holding the monotonicity and submodularity. Through experiments on large real social graphs, we demonstrate the effectiveness and efficiency of the proposed target link protection methods.

A sketch is a probabilistic data structure that is used to record frequencies of items in a multi-set. Sketches have been applied in a variety of fields, such as data stream processing, natural language processing, distributed data sets etc. In this paper, we propose a new sketch, called Slim-Fat (SF) sketch, which has a much smaller memory footprint for query while supporting updates. The key idea behind our proposed SF-sketch is to maintain two separate sketches: a small sketch called Slimsubsketch and a large sketch called Fat-subsketch. The Slimsubsketch enables fast and accurate querying. The Fat-subsketch is used to assist the insertion and deletion from Slim-subsketch. We implemented and evaluated SF-sketch along with several prior sketches and compared them side by side. Our experimental results show that SF-sketch significantly outperforms the most commonly used CM-sketch in terms of accuracy. The full version is provided at arXiv.org [12].