Approximate Query Processing over Secure Key/Value Stores

安全键/值存储可用于在中心位置存储大量数据，同时提供单元级访问控制以保护数据隐私（即，每个键-值对都有自己的安全标签）。这通常对许多对数据安全和隐私有强烈要求的领域（例如，医疗保健、政府）非常有吸引力。然而，阻止安全键/值存储被广泛采用的一个关键限制是，它们不能非常有效地支持分析查询。为了克服这一限制，在本提案中，我们将与PHEMI合作构建一个基于安全密钥/值存储的近似查询处理（AQP）引擎。关键的洞察力是允许用户在样本数据上运行分析查询，并返回带有误差条的近似答案。由于查询只需要在一个样本上执行，因此查询响应时间可以得到显著改善。我们将与phemi合作解决两个具有挑战性的研究问题：(1)如何有效地创建存储在键/值存储中的数据的随机样本；(2)如何有效地从样本中获得近似答案。据我们所知，我们是第一个在安全键/值存储上探索近似查询处理的人。PI在AQP系统开发方面有多年的成功经验。PHEMI是一家总部位于加拿大的大数据仓库初创公司。他们使用名为Accumulo的安全键值存储作为其产品的主要数据存储。我们期望这个合作研究项目不仅对PHEMI的产品有益，而且对如何构建一个真实的AQP系统产生深远的影响。

Secure key/value stores can be used to store a large amount of data in a central place while providing cell-levelaccess control to protect data privacy (i.e., each key-value pair has its own security label). This is often veryattractive to many domains (e.g., healthcare, government) that have a strong requirement for data security andprivacy. However, a key limitation that stops secure key/value stores from being widely adopted is that theycannot support analytical queries very efficiently.To overcome the limitation, in this proposal, we will collaborate with PHEMI to build an approximate queryprocessing (AQP) engine over secure key/value stores. The key insight is to allow users to run analyticalqueries on a sample data and return them approximate answers with error bars. Since the queries only need tobe executed on a sample, the query response time can be significantly improved. We will work together withPHEMI to address two challenging research problems: (1) how to efficiently create a random sample of thedata stored in key/value stores; (2) how to efficiently obtain approximate answers from a sample. To the best ofour knowledge, we are the first to explore approximate query processing over secure key/value stores.The PI has many years of successful experience in AQP system development. PHEMI is a big data warehousestartup headquartered in Canada. They use a secure key-value store called Accumulo as the main data store oftheir products. We anticipate that the collaborative research project will not only be beneficial to PHEMI'sproducts but also have a profound impact on how to architect a real-world AQP system.