ALEX: 一种可更新的自适应学习索引
该论文提出了一种名为 LIPP 的学习索引框架,该框架在支持多种索引操作的基础上,通过适当扩展树结构和动态调整策略来解决了先前学习索引的更新操作存在的问题,实验评估证明其优于现有解决方案。
Apr, 2021
本文将现存索引结构视为一种模型,并探讨通过深度学习建立新的索引结构的可行性及运行效率,试验证明,用神经网络实现的索引结构能够在速度上比传统 B 树结构优秀 70%,并在各种真实数据集上实现更好的内存效率,于是指出此方案对于未来数据管理系统的设计具有深远影响
Dec, 2017
本文针对使用学习索引结构替换传统索引结构的近期研究提出了一个统一的基准,将三种学习索引结构的调整良好的实现与多个最先进的 “传统” 基准进行了比较,并使用四个真实世界的数据集证明,学习索引结构确实可以在密集数组的只读内存工作负载中优于非学习索引。同时还研究了缓存、流水线、数据集大小和关键字大小对性能的影响,探讨了学习模型为何能够实现如此良好的性能,并研究其他特性,如多线程系统中的性能和构建时间。
Jun, 2020
本文从理论上证明,在数据分布的温和假设下,具有与非学习方法相同空间复杂度的学习索引可以在期望的 O (loglog n) 查询时间内回答查询,从而进一步巩固了学习索引的实证成功。
Jun, 2023
现在的研究趋势是将数据库索引结构视为机器学习模型,通过训练单个或多个机器学习模型来学习从键到数据集内位置的映射关系,从而实现改进搜索性能和减少空间需求。该调查重点关注学习多维索引结构,介绍了该研究领域的现状,解释了每个方法的核心概念,并根据多个明确定义的标准对这些方法进行分类。我们提供了一个分类法以对每个学习多维索引进行分类和归类,并根据此分类法对现有的学习多维索引文献进行了调查。此外,我们还提供了一个时间线来说明学习索引研究的发展历程,并重点介绍了这个新兴且非常活跃的领域中的几个挑战和未来研究方向。
Mar, 2024
本文介绍了 LearnedKV,一种新颖的分层键值存储系统,将 Log-Structured Merge 树与 Learned Index 无缝集成,从而实现与 SSD 上独立索引结构相比的读写性能。我们分析了 LSM 树性能与大小的关系,并展示了分层 Learned Index 如何显著减轻与大小相关的性能下降,特别是通过减少垃圾回收(GC)后重新插入导致的密集 I/O 操作。为了保持对新插入键的快速读取性能,我们引入了一种非阻塞转换机制,可以在 GC 期间以 minimal overhead 将现有的 LSM 树高效地转换为新的 Learned Index。我们通过多样化的工作负载进行了实验,在读请求和写性能方面,LearnedKV 在性能上超过了现有解决方案的 1.32 倍和 1.31 倍。
Jun, 2024
本文介绍一种名为 Flood 的多维内存索引,它能够根据特定数据集和工作负载自动适应自己,通过联合优化索引结构和数据存储,在真实世界的数据集和工作负载上比现有技术的多维索引或排序方式实现了高达三个数量级的更快性能。该研究为一个端到端学习的数据库系统奠定了基础。
Dec, 2019
在机器学习和经典数据结构的交叉领域中,这项研究关注了学习数据结构,这是一个具有重要方法论意义和高实用性影响的新领域。我们提出了一种新的思路,通过对任何排序集合字典进行学习,例如平衡二叉搜索树或其他非排序布局的二分搜索,从而在时间性能上取得了令人印象深刻的提升。
Sep, 2023