Open Access. Powered by Scholars. Published by Universities.®
Databases and Information Systems Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Keyword
-
- Approximate algorithms (1)
- Black boxes (1)
- Building blockes (1)
- Cardinalities (1)
- Corresponding weights (1)
-
- Different domains (1)
- Exact algorithms (1)
- Health condition (1)
- Heuristic techniques (1)
- High dimensional data (1)
- High-dimensional dataset (1)
- Information leakage (1)
- Lifestyle choices (1)
- Novel strategies (1)
- Number distribution (1)
- Number partitioning (1)
- Personal information (1)
- Preference functions (1)
- Privacy concerns (1)
- Privacy preserving (1)
- Private information retrieval (1)
- Pruning techniques (1)
- Resource-efficient (1)
- Road network (1)
- Shortest path (1)
- Shortest path computations (1)
- Subset sum (1)
- User's preferences (1)
Articles 1 - 4 of 4
Full-Text Articles in Databases and Information Systems
Computing Immutable Regions For Subspace Top-K Queries, Kyriakos Mouratidis, Hwee Hwa Pang
Computing Immutable Regions For Subspace Top-K Queries, Kyriakos Mouratidis, Hwee Hwa Pang
Kyriakos MOURATIDIS
Given a high-dimensional dataset, a top-k query can be used to shortlist the k tuples that best match the user’s preferences. Typically, these preferences regard a subset of the available dimensions (i.e., attributes) whose relative significance is expressed by user-specified weights. Along with the query result, we propose to compute for each involved dimension the maximal deviation to the corresponding weight for which the query result remains valid. The derived weight ranges, called immutable regions, are useful for performing sensitivity analysis, for finetuning the query weights, etc. In this paper, we focus on top-k queries with linear preference functions over …
Shortest Path Computation With No Information Leakage, Kyriakos Mouratidis, Man Lung Yiu
Shortest Path Computation With No Information Leakage, Kyriakos Mouratidis, Man Lung Yiu
Kyriakos MOURATIDIS
Shortest path computation is one of the most common queries in location-based services (LBSs). Although particularly useful, such queries raise serious privacy concerns. Exposing to a (potentially untrusted) LBS the client’s position and her destination may reveal personal information, such as social habits, health condition, shopping preferences, lifestyle choices, etc. The only existing method for privacy-preserving shortest path computation follows the obfuscation paradigm; it prevents the LBS from inferring the source and destination of the query with a probability higher than a threshold. This implies, however, that the LBS still deduces some information (albeit not exact) about the client’s location …
Enhancing Access Privacy Of Range Retrievals Over B+Trees, Hwee Hwa Pang, Jilian Zhang, Kyriakos Mouratidis
Enhancing Access Privacy Of Range Retrievals Over B+Trees, Hwee Hwa Pang, Jilian Zhang, Kyriakos Mouratidis
Kyriakos MOURATIDIS
Users of databases that are hosted on shared servers cannot take for granted that their queries will not be disclosed to unauthorized parties. Even if the database is encrypted, an adversary who is monitoring the I/O activity on the server may still be able to infer some information about a user query. For the particular case of a B+-tree that has its nodes encrypted, we identify properties that enable the ordering among the leaf nodes to be deduced. These properties allow us to construct adversarial algorithms to recover the B+-tree structure from the I/O traces generated by range queries. Combining …
Heuristic Algorithms For Balanced Multi-Way Number Partitioning, Jilian Zhang, Kyriakos Mouratidis, Hwee Hwa Pang
Heuristic Algorithms For Balanced Multi-Way Number Partitioning, Jilian Zhang, Kyriakos Mouratidis, Hwee Hwa Pang
Kyriakos MOURATIDIS
Balanced multi-way number partitioning (BMNP) seeks to split a collection of numbers into subsets with (roughly) the same cardinality and subset sum. The problem is NP-hard, and there are several exact and approximate algorithms for it. However, existing exact algorithms solve only the simpler, balanced two-way number partitioning variant, whereas the most effective approximate algorithm, BLDM, may produce widely varying subset sums. In this paper, we introduce the LRM algorithm that lowers the expected spread in subset sums to one third that of BLDM for uniformly distributed numbers and odd subset cardinalities. We also propose Meld, a novel strategy for …