基于学习的索引性能基准测试
本文将现存索引结构视为一种模型,并探讨通过深度学习建立新的索引结构的可行性及运行效率,试验证明,用神经网络实现的索引结构能够在速度上比传统 B 树结构优秀 70%,并在各种真实数据集上实现更好的内存效率,于是指出此方案对于未来数据管理系统的设计具有深远影响
Dec, 2017
本文讨论了学习索引在 DBMS 索引中的应用,并介绍了一种新的学习索引 ALEX,其结合了学习索引的核心思想和成熟的存储和索引技术,可在动态更新的数据库工作负载中实现高性能和低内存占用。
May, 2019
该论文提出了一种名为 LIPP 的学习索引框架,该框架在支持多种索引操作的基础上,通过适当扩展树结构和动态调整策略来解决了先前学习索引的更新操作存在的问题,实验评估证明其优于现有解决方案。
Apr, 2021
本文从理论上证明,在数据分布的温和假设下,具有与非学习方法相同空间复杂度的学习索引可以在期望的 O (loglog n) 查询时间内回答查询,从而进一步巩固了学习索引的实证成功。
Jun, 2023
现在的研究趋势是将数据库索引结构视为机器学习模型,通过训练单个或多个机器学习模型来学习从键到数据集内位置的映射关系,从而实现改进搜索性能和减少空间需求。该调查重点关注学习多维索引结构,介绍了该研究领域的现状,解释了每个方法的核心概念,并根据多个明确定义的标准对这些方法进行分类。我们提供了一个分类法以对每个学习多维索引进行分类和归类,并根据此分类法对现有的学习多维索引文献进行了调查。此外,我们还提供了一个时间线来说明学习索引研究的发展历程,并重点介绍了这个新兴且非常活跃的领域中的几个挑战和未来研究方向。
Mar, 2024
在机器学习和经典数据结构的交叉领域中,这项研究关注了学习数据结构,这是一个具有重要方法论意义和高实用性影响的新领域。我们提出了一种新的思路,通过对任何排序集合字典进行学习,例如平衡二叉搜索树或其他非排序布局的二分搜索,从而在时间性能上取得了令人印象深刻的提升。
Sep, 2023
本文介绍了 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
通过重新实现 DistMult 模型,本文发现几乎所有在 FB15k 标准数据集上发布的模型的准确性都可以被我们适当调整基线模型超越,表明最近模型的性能改进可能不是由于架构变化,而是由于超参数调整或不同的训练目标。这应促使未来的研究重新考虑如何评估和报告模型的性能。
May, 2017
用一次数据扫描就可以构建、具有与现有最先进的索引模型相竞争的大小和查询性能的学习型索引 ——RadixSpline, 并通过 SOSD 基准评估展示了它的竞争力,尽管它只有两个参数。
Apr, 2020