索引是数据库提供高效检索服务的核心要素。然而传统空间索引的时空复杂度和数据体量正相关，随着数据量增长存在严重的数据膨胀和检索延迟问题。学习型索引通过机器学习捕捉和学习数据分布，其时空复杂度和数据体量无关，检索方式从传统直接深度检索向模型推理预测转变。这一转变为数据库高效管理开辟了新的路径，有望在大数据时代为数据库高效管理提供更强大的支持。来自浙江大学的张丰副教授及其团队在ISPRS Int. J. Geo-Inf. (ISPRS IJGI) 期刊发表了文章“SLBRIN: A Spatial Learned Index Based on BRIN”，介绍了一种基于块范围索引的新型空间学习索引结构，协同历史范围和当前范围，基于外存优化的块范围方法提升时空数据索引构建、检索和更新的性能。
SLBRIN的索引结构
研究过程与结果
为了优化查询性能和更新性能，作者在文中提出了一种新的空间学习索引结构SLBRIN。其核心思想是通过将索引对象分为两部分来简化空间索引问题，适用于空间查询的历史范围 (HR) 和适用于索引更新的当前范围 (CR)，并利用空间大数据的时空特征优化处理策略。对于HR，对空间字段进行Geohash编码和排序，索引条目被划分为一组在空间上具有近似数据量的规则四边形分区。对于每个分区范围，我们为空间查询构建一个一维学习索引。对于CR，为了最大限度地降低更新成本，范围直接沿着物理顺序进行分区，并采用简单的MBR作为摘要信息。
实验选用了纽约市2013年部分出租车轨迹数据 (NYCT)，约28236977条记录，均匀 (UNIFORM) 和正态分布 (NORMAL) 模拟数据集进行对比测试。实验结果表明，点范围查询中，SLBRIN将查询时间至少提高了2.8倍，最高提高了6.3倍，同时降低了IO成本；范围查询中，SLBRIN将查询时间至少提高了9.8倍，最高提高了76.4倍，范围大小越大，改进程度越高；SLBRIN在kNN检索中具有最佳的查询性能和最强的稳定性，稳定的查询时间为0.29 ms，IO成本低至10。这表明SLBRIN的查询策略有效地减少了空间填充曲线的跳跃性，且比其他空间学习索引的误差范围更小。
kNN近邻查询性能对比
研究总结
本文提出了一种基于块范围索引的空间学习索引结构SLBRIN，该结构具有范围、历史范围 (HR) 和当前范围 (CR) 的概念，优化了索引更新策略和查询策略，以满足实时空间数据的索引更新和空间查询的迫切需求。对于更新处理，将更新事务分解为串行和并行操作以提高并行性，并充分利用空间分布的时间接近性来稳定查询性能并提高更新性能。在查询处理方面，设计了基于空间学习索引的点查询、范围查询和kNN查询策略，并利用HR的空间划分和提出的空间位置编码对其进行了优化。从实验对比可以看到SLBRIN的优势：(1) 基于范围的索引结构是为物理存储设计的，具有较低的IO成本；(2) HR的划分有利于拟合空间分布，并获得较低的误差界限；(3) 具有空间位置编码的查询策略有效地减少了空间填充曲线跳跃特性引起的无效过滤。得益于学习索引和轻量级范围，SLBRIN在构建处理和更新处理方面提供了更低的存储成本和更好的性能。此外，SLBRIN在更新过程中表现出更强的查询性能稳定性。通过GPU和多进程加速改善再训练模型的索引构建和更新性能，表明SLBRIN有更合理的空间划分和更动态的索引结构。
原文出自ISPRS IJGI 期刊：https://www.mdpi.com/2220-9964/12/4/171
期刊主页：https://www.mdpi.com/journal/ijgi
ISPRS IJGI 期刊介绍
主编：Wolfgang Kainz, University of Vienna, Austria
期刊主题涵盖地理信息科学和技术各个方面，主要包括空间数据模型与管理、空间分析与决策、地理空间人工智能、地图制图、空间数据基础设施、地理空间网络、志愿地理信息、基于位置的服务、轨迹分析、智慧城市和前沿地理空间应用等。
2023 Impact Factor：2.8
2023 CiteScore：6.9
Time to First Decision：35.8 Days
Acceptance to Publication：2.2 Days
转载本文请联系原作者获取授权，同时请注明本文来自MDPI开放科学科学网博客。
链接地址：https://wap.sciencenet.cn/blog-3516770-1468793.html?mobile=1
收藏
