SAM: A Spatial-Aware Learned Index for Disk-Based Multi-dimensional Search

Although existing learned multi-dimensional indexes achieve fast similarity query processing, they still incur high I/O cost and large computational consumption. To address these issues, we propose a spatial-aware learned index for disk-based multi-dimensional search (SAM for short). Its core idea is to use a data transformation technique based on dual-distance metric to map more similar data in space into compact regions and the mapped values are totally ordinal. SAM partitions data into clusters, redistributes data by utilizing a pivot for each cluster and Euclidean distance and Manhattan distance and uses a learned index to approximate the position of each data record on disk. Our experimental evaluation on real-world and synthetic datasets shows that SAM outperforms the SOTA learned indexes by ∼2× for range queries and ∼9× for nearest neighbor queries.