本文已被:浏览 285次 下载 1079次
Received:March 17, 2025 Revised:April 08, 2025
Received:March 17, 2025 Revised:April 08, 2025
中文摘要: 在大数据时代, 海量数据的存取已成为制约系统性能的关键瓶颈. 尽管学习索引凭借高查询效率和低空间开销在大规模数据管理中得到广泛应用, 但在局部数据分布偏斜, 尤其遭遇投毒攻击时, 其性能会显著下降. 传统学习索引依赖固定阈值的就地插入策略, 为维持局部有序性, 随机插入可能触发高代价的重训练和数据移动操作, 既耗费大量计算资源, 又导致系统响应不稳定和吞吐量下降. 为此, 本文提出了一种基于缓冲区平滑机制的加权线性回归索引(BPS-WLRI). 该方法首先引入加权线性回归模型, 对数据分布进行精细拟合, 从而有效降低索引树深度和重训练频率; 同时, 采用哈希桶缓冲结构优化就地插入过程, 有效缓解因严格维护有序性而引发的大规模数据移动问题; 此外, 还设计了缓冲点平滑策略, 实现缓冲区合并时仅对局部结构进行增量更新, 避免了全局重构的高昂开销. 实验结果表明, 在投毒攻击极端负载下, BPS-WLRI的吞吐量分别比ALEX、PGM、LIPP、DILI、SALI和AULID提高了1.81倍、4.32倍、2.22倍、2.06倍、1.41倍和1.39倍, 验证了其在动态数据负载和恶意攻击场景下的高效性与稳定性.
Abstract:In the era of big data, the storage and retrieval of massive data have become a critical bottleneck for system performance. Although learned indexes hold widespread application in large-scale data management through their high query efficiency and low space overhead, their performance is significantly degraded under skewed local data distribution, especially in the presence of poisoning attacks. Traditional learned indexes rely on an in-place insertion strategy with fixed thresholds. However, to maintain local sorted order, random insertion may trigger costly retraining and data movement operations, which consume substantial computational resources and result in unstable system responsiveness and reduced throughput. To this end, this study proposes a buffered point smoothing weighted linear regression insertion (BPS-WLRI) mechanism. Firstly, this method introduces a weighted linear regression model to finely fit the data distribution, thereby effectively reducing the index tree depth and retraining frequency. Meanwhile, a hash-bucket buffer structure is employed to optimize the in-place insertion process, effectively mitigating the large-scale data movements caused by strict maintenance of sorted order. Additionally, a buffer-point smoothing strategy is designed to ensure that during buffer merging, only local structures are incrementally updated, thereby avoiding the high overhead of global restructuring. Experimental results demonstrate that under extreme poisoning attack loads, BPS-WLRI achieves throughput improvements of 1.81 times, 4.32 times, 2.22 times, 2.06 times, 1.41 times, and 1.39 times over ALEX, PGM, LIPP, DILI, SALI, and AULID respectively. These results confirm the efficiency and stability of the proposed algorithm under dynamic data loads and malicious attack scenarios.
keywords: database learned index buffer smoothing mechanism weighted linear regression local skewed distribution
文章编号: 中图分类号: 文献标志码:
基金项目:
引用文本:
李林昊,何海钊.BPS-WLRI: 面向局部偏斜工作负载的鲁棒索引设计.计算机系统应用,2025,34(11):82-94
LI Lin-Hao,HE Hai-Zhao.BPS-WLRI: Robust Index Design for Local Skewed Workload.COMPUTER SYSTEMS APPLICATIONS,2025,34(11):82-94
李林昊,何海钊.BPS-WLRI: 面向局部偏斜工作负载的鲁棒索引设计.计算机系统应用,2025,34(11):82-94
LI Lin-Hao,HE Hai-Zhao.BPS-WLRI: Robust Index Design for Local Skewed Workload.COMPUTER SYSTEMS APPLICATIONS,2025,34(11):82-94

