Differentially Private Learned Indexes

• URL: http://arxiv.org/abs/2410.21164v1
• Date: Mon, 28 Oct 2024 16:04:58 GMT
• Title: Differentially Private Learned Indexes
• Authors: Jianzhang Du, Tilak Mudgal, Rutvi Rahul Gadre, Yukui Luo, Chenghong Wang,
• Abstract summary: We address the problem of efficiently answering predicate queries on encrypted databases, those secured by Trusted Execution Environments (TEEs) 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. Unfortunately, indexes cannot be directly applied to encrypted databases due to strong data dependent leakages. We propose leveraging learned indexes, a trending technique that repurposes machine learning models as indexing structures, to build more compact DP indexes.
• Score: 4.290415158471898
• License:
• Abstract: 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.

Related papers

• Annotative Indexing [8.684302613224338]
  Annotative indexing is a novel framework that unifies and generalizes traditional inverted indexes, column stores, object stores, and graph databases. Annotative indexing can provide the underlying indexing framework for databases that support knowledge graphs, entity, semi-structured data, and ranked.
  arXiv  Detail & Related papers  (2024-11-09T19:07:58Z)
• Operational Advice for Dense and Sparse Retrievers: HNSW, Flat, or Inverted Indexes? [62.57689536630933]
  We provide experimental results on the BEIR dataset using the open-source Lucene search library. Our results provide guidance for today's search practitioner in understanding the design space of dense and sparse retrievers.
  arXiv  Detail & Related papers  (2024-09-10T12:46:23Z)
• Semi-Parametric Retrieval via Binary Token Index [71.78109794895065]
  Semi-parametric Vocabulary Disentangled Retrieval (SVDR) is a novel semi-parametric retrieval framework. It supports two types of indexes: an embedding-based index for high effectiveness, akin to existing neural retrieval methods; and a binary token index that allows for quick and cost-effective setup, resembling traditional term-based retrieval. It achieves a 3% higher top-1 retrieval accuracy compared to the dense retriever DPR when using an embedding-based index and a 9% higher top-1 accuracy compared to BM25 when using a binary token index.
  arXiv  Detail & Related papers  (2024-05-03T08:34:13Z)
• LIST: Learning to Index Spatio-Textual Data for Embedding based Spatial Keyword Queries [53.843367588870585]
  List K-kNN spatial keyword queries (TkQs) return a list of objects based on a ranking function that considers both spatial and textual relevance. There are two key challenges in building an effective and efficient index, i.e., the absence of high-quality labels and the unbalanced results. We develop a novel pseudolabel generation technique to address the two challenges.
  arXiv  Detail & Related papers  (2024-03-12T05:32:33Z)
• WISK: A Workload-aware Learned Index for Spatial Keyword Queries [46.96314606580924]
  We propose WISK, a learned index for spatial keyword queries. We show that WISK achieves up to 8x speedup in querying time with comparable storage overhead.
  arXiv  Detail & Related papers  (2023-02-28T03:45:25Z)
• Bridging the Gap Between Indexing and Retrieval for Differentiable Search Index with Query Generation [98.02743096197402]
  Differentiable Search Index (DSI) is an emerging paradigm for information retrieval. We propose a simple yet effective indexing framework for DSI, called DSI-QG. Empirical results on popular mono-lingual and cross-lingual passage retrieval datasets show that DSI-QG significantly outperforms the original DSI model.
  arXiv  Detail & Related papers  (2022-06-21T06:21:23Z)
• LSI: A Learned Secondary Index Structure [24.324528705706104]
  We introduce Learned Secondary Index (LSI), a first attempt to use learned indexes for indexing unsorted data. We show that LSI achieves comparable lookup performance to state-of-the-art secondary indexes while being up to 6x more space efficient.
  arXiv  Detail & Related papers  (2022-05-11T20:49:44Z)
• A Learned Index for Exact Similarity Search in Metric Spaces [25.330353637669386]
  LIMS is proposed to use data clustering and pivot-based data transformation techniques to build learned indexes. Machine learning models are developed to approximate the position of each data record on the disk. Extensive experiments on real-world and synthetic datasets demonstrate the superiority of LIMS compared with traditional indexes.
  arXiv  Detail & Related papers  (2022-04-21T11:24:55Z)
• The Case for Learned Spatial Indexes [62.88514422115702]
  We use techniques proposed from a state-of-the art learned multi-dimensional index structure (namely, Flood) to answer spatial range queries. We show that (i) machine learned search within a partition is faster by 11.79% to 39.51% than binary search when using filtering on one dimension. We also refine using machine learned indexes is 1.23x to 1.83x times faster than closest competitor which filters on two dimensions.
  arXiv  Detail & Related papers  (2020-08-24T12:09:55Z)
• Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads [29.223401893397714]
  We introduce Tsunami, which achieves up to 6X faster query performance and up to 8X smaller index size than existing learned multi-dimensional indexes.
  arXiv  Detail & Related papers  (2020-06-23T19:25:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.