用机器学习模型构建更小的差分隐私索引，提升加密数据库查询效率。
Differentially Private Learned Indexes
- 用学习型索引替代传统索引，将模型作为键值到位置的映射结构。
- 在保证差分隐私的前提下，索引大小仅随数据量增长，不随键空间线性扩张。
- 适合对存储开销敏感、需保护隐私的云数据库查询场景。
本文研究在受信任执行环境（TEEs）保护的加密数据库中高效回答谓词查询的问题。现代数据库常通过索引加速查询，将属性值（键）映射到排序数据数组中的位置。然而，传统索引会泄露强数据依赖信息，无法直接用于加密数据。现有方法采用差分隐私（DP）生成带噪声的索引，虽能提供可证明的隐私保障，但通常导致存储成本高，索引大小往往与键空间呈线性关系。为解决此问题，我们提出利用学习型索引——一种将机器学习模型用作索引结构的新技术——来构建更紧凑的差分隐私索引。该方法显著降低存储开销，同时保持高效的查询性能。
原文摘要 · Abstract (English)
In this paper, we address the problem of efficiently answering predicate queries on encrypted databases, those secured by Trusted Execution Environments (TEEs), which enable untrusted providers to process encrypted user data without revealing its contents. A common strategy in modern databases to accelerate predicate queries is the use of indexes, which map attribute values (keys) to their corresponding positions in a sorted data array. This allows for fast lookup and retrieval of data subsets that satisfy specific predicates. Unfortunately, indexes cannot be directly applied to encrypted databases due to strong data dependent leakages. Recent approaches apply differential privacy (DP) to construct noisy indexes that enable faster access to encrypted data while maintaining provable privacy guarantees. However, these methods often suffer from large storage costs, with index sizes typically scaling linearly with the key space. To address this challenge, we propose leveraging learned indexes, a trending technique that repurposes machine learning models as indexing structures, to build more compact DP indexes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。