LIFOSS: a learned index scheme for streaming scenarios

Recently, researches on dynamic decision-making based on streaming data are in full swing. As an indispensable technology for data management and analysis, indexing methods are also evolving. The indexing paradigm named learned index has been proposed to replace the traditional B-tree family in some scenarios. It has been proved that learned indexes can provide higher lookup efficiency and lower storage cost overhead than traditional indexes. Usually, learned indexes assume that the data is static or at least the data distribution is unchanged. However, the streaming scenarios break the strong assumption. This paper presents a learned index scheme for streaming scenarios (LIFOSS for short), where the workloads insert, delete, and query data arbitrarily. Precisely, LIFOSS consists of three parts: a) an adaptive packed-memory array which stores data and handles updates with lower bound of performance guaranteed; b) a middle-layer model group, used to fit the cumulative distribution function of data; c) a feedback mechanism designed to update parameters of the model group above in real-time locally. Extensive experiments on two public datasets show that LIFOSS performs better than the state-of-the-art dynamic learned index method. LIFOSS reduces the lookup latency by at least \(6\%\), and its dynamic performance is more stable, requiring only a tiny amount of extra space.