干旱区生态环境知识资源中心(Arid): Oasis: An Optimal Disjoint Segmented Learned Range Filter

Arid

DOI	10.14778/3659437.3659447
	Oasis: An Optimal Disjoint Segmented Learned Range Filter
	Chen, Guanduo; He, Zhenying; Li, Meng; Luo, Siqiang
通讯作者	Luo, SQ
来源期刊	PROCEEDINGS OF THE VLDB ENDOWMENT
ISSN	2150-8097
出版年	2024
卷号	17 期号:8 页码:1911-1924
英文摘要	The learning-enhanced data structure has inspired the development of the range filter, bringing significantly better false positive rate (FPR) than traditional non-learned range filters. Its core idea is to employ piece-wise linear functions that uniformly map the entire key space into a bitmap sequentially. Nonetheless, such uniform mapping can be space-ineffective, impacting FPRs. This paper introduces Oasis, a novel learned range filter that divides the key space into disjointed intervals by excluding large empty ranges explicitly and optimally maps those unpruned intervals into a compressed bitmap. The configuration optimality in Oasis is guaranteed by a careful theoretical analysis. To enhance the versatility of Oasis, we further propose Oasis+, which integrates the design space of both learned and non-learned filters, delivering robust performance across a wide range of workloads. We evaluate the performance of both Oasis and Oasis+ when integrated into the key-value system RocksDB, using a diverse set of real-world and synthetic datasets and workloads. In RocksDB, Oasis and Oasis+ improve the performance by up to 1.4x and 6.2x when compared to state-of-the-art learned and non-learned range filters.
类型	Article
语种	英语
收录类别	SCI-E
WOS记录号	WOS:001253076500010
WOS关键词	INDEX
WOS类目	Computer Science, Information Systems ; Computer Science, Theory & Methods
WOS研究方向	Computer Science
资源类型	期刊论文
条目标识符	http://119.78.100.177/qdio/handle/2XILL650/405234
推荐引用方式 GB/T 7714	Chen, Guanduo,He, Zhenying,Li, Meng,et al. Oasis: An Optimal Disjoint Segmented Learned Range Filter[J],2024,17(8):1911-1924.
APA	Chen, Guanduo,He, Zhenying,Li, Meng,&Luo, Siqiang.(2024).Oasis: An Optimal Disjoint Segmented Learned Range Filter.PROCEEDINGS OF THE VLDB ENDOWMENT,17(8),1911-1924.
MLA	Chen, Guanduo,et al."Oasis: An Optimal Disjoint Segmented Learned Range Filter".PROCEEDINGS OF THE VLDB ENDOWMENT 17.8(2024):1911-1924.