More Web Proxy on the site http://driver.im/

research-article

COLIN: A Cache-Conscious Dynamic Learned Index with High Read/Write Performance

Authors:

Xiao-Liang Wang,

Xi-Ke XieAuthors Info & Claims

Journal of Computer Science and Technology, Volume 36, Issue 4

Pages 721 - 740

https://doi.org/10.1007/s11390-021-1348-2

Published: 01 July 2021 Publication History

Abstract

The recently proposed learned index has higher query performance and space efficiency than the conventional B+-tree. However, the original learned index has the problems of insertion failure and unbounded query complexity, meaning that it supports neither insertions nor bounded query complexity. Some variants of the learned index use an out-of-place strategy and a bottom-up build strategy to accelerate insertions and support bounded query complexity, but introduce additional query costs and frequent node splitting operations. Moreover, none of the existing learned indices are cache-friendly. In this paper, aiming to not only support efficient queries and insertions but also offer bounded query complexity, we propose a new learned index called COLIN (Cache-cOnscious Learned INdex). Unlike previous solutions using an out-of-place strategy, COLIN adopts an in-place approach to support insertions and reserves some empty slots in a node to optimize the node’s data placement. In particular, through model-based data placement and cache-conscious data layout, COLIN decouples the local-search boundary from the maximum error of the model. The experimental results on five workloads and three datasets show that COLIN achieves the best read/write performance among all compared indices and outperforms the second best index by 18.4%, 6.2%, and 32.9% on the three datasets, respectively.

References

[1]

Kraska T, Beutel A, Chi E H, Dean J, Polyzotis N. The case for learned index structures. In Proc. the 2018 International Conference on Management of Data, Jun. 2018, pp.489-504.

[2]

Galakatos A, Markovitch M, Binnig C, Fonseca R, Kraska T. FITing-Tree: A data-aware index structure. In Proc. the 2019 International Conference on Management of Data, Jun. 2019, pp.1189-1206.

[3]

Ferragina P, Vinciguerra G. The PGM-index: A fully-dynamic compressed learned index with provable worst-case bounds. Proceedings of the VLDB Endowment, 2020, 13(8): 1162-1175.

[4]

Ding J, Minhas U F, Yu J et al. ALEX: An updatable adaptive learned index. In Proc. the 2020 ACM International Conference on Management of Data, Jun. 2020, pp.969-984.

[5]

Shazeer N, Mirhoseini A, Maziarz K, Davis A, Le Q V, Hinton G E, Dean J. Outrageously large neural networks: The sparsely-gated mixture-of-experts layer. In Proc. the 5th International Conference on Learning Representations, April 2017.

[6]

Liu X, Lin Z, and Wang H Novel online methods for time series segmentation IEEE Transactions on Knowledge and Data Engineering 2008 20 12 1616-1626

[7]

Xu Z, Zhang R, Ramamohanarao K, Parampalli U. An adaptive algorithm for online time series segmentation with error bound guarantee. In Proc. the 15th International Conference on Extending Database Technology, Mar. 2012, pp.192-203.

[8]

Xie Q, Pang C, Zhou X, Zhang X, and Deng K Maximum error-bounded piecewise linear representation for online stream approximation The VLDB Journal 2014 23 6 915-937

[9]

Bentley JL and Yao AC An almost optimal algorithm for unbounded searching Information Processing Letters 1976 5 3 82-87

[10]

Hadian A, Heinis T. Considerations for handling updates in learned index structures. In Proc. the 2nd International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, Jul. 2019, Article No. 3.

[11]

Li X, Li J, Wang X. ASLM: Adaptive single layer model for learned index. In Proc. the 2019 International Conference on Database Systems for Advanced Applications, Apr. 2019, pp.80-95.

[12]

O’Neil P, Cheng EY, Gawlick D, and Oneil E The log-structured merge-tree (LSM-tree) Acta Informatica 1996 33 4 351-385

[13]

Bender M A, Hu H. An adaptive packed-memory array. ACM Transactions on Database Systems, 2007, 32(4): Article No. 26.

[14]

Ailamaki A, DeWitt D, Hill M, Wood D. DBMSs on a modern processor: Where does time go? In Proc. the 25th International Conference on Very Large Data Bases, Sept. 1999, pp.266-277.

[15]

Hadian A, Heinis T. Shift-Table: A low-latency learned index for range queries using model correction. In Proc. the 24th International Conference on Extending Database Technology, Mar. 2021, pp.253-264.

[16]

Tang C, Wang Y, Hu G et al. XIndex: A scalable learned index for multicore data storage. In Proc. the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Feb. 2020, pp.308-320.

[17]

Kipf A, Marcus R, van Renen A, Stoian M, Kemper A, Kraska T, Neumann T. RadixSpline: A single-pass learned index. In Proc. the 3rd International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, Jun. 2020, Article No. 5.

[18]

Neumann T, Michel S. Smooth interpolating histograms with error guarantees. In Proc. the 25th British National Conference on Databases, July 2008, pp.126-138.

[19]

Bilgram R. Cost models for learned index with insertions [Master Thesis]. Department of Computer Science, Aalborg University, 2019.

[20]

Wang Y, Tang C, Wang Z, Chen H. SIndex: A scalable learned index for string keys. In Proc. the 11th ACM SIGOPS Asia-Pacific Workshop on Systems, Aug. 2020, pp.17-24.

[21]

Llaveshi A, Sirin U, Ailamaki A, West R. Accelerating B+-tree search by using simple machine learning techniques. In Proc. the 1st International Workshop on Applied AI for Database Systems and Applications, Aug. 2019.

[22]

Hadian A, Heinis T. Interpolation-friendly B-trees: Bridging the gap between algorithmic and learned indexes. In Proc. the 22nd International Conference on Extending Database Technology, Mar. 2019, pp.710-713.

[23]

Hadian A, Heinis T. MADEX: Learning-augmented algorithmic index structures. In Proc. the 2nd International Workshop on Applied AI for Database Systems and Applications, Aug. 2020.

[24]

Li P, Lu H, Zheng Q, Yang L, Pan G. LISA: A learned index structure for spatial data. In Proc. the 2020 International Conference on Management of Data, Jun. 2020, pp.2119-2133.

[25]

Qi J, Liu G, Jensen C S, Kulik L. Effectively learning spatial indices. Proceedings of the VLDB Endowment, 2020, 13(11): 2341-2354.

[26]

Nathan V, Ding J, Alizadeh M, Kraska T. Learning multidimensional indexes. In Proc. the 2020 International Conference on Management of Data, Jun. 2020, pp.985-1000.

[27]

Ding J, Nathan V, Alizadeh M, Kraska T. Tsunami: A learned multi-dimensional index for correlated data and skewed workloads. Proceedings of the VLDB Endowment, 2020, 14(2): 74-86.

[28]

Zhou X, Chai C, Li G, Sun J. Database meets artificial intelligence: A survey. IEEE Transactions on Knowledge and Data Engineering.

[29]

Sun J, Li G. An end-to-end learning-based cost estimator. Proceedings of the VLDB Endowment, 2019, 13(3): 307-319.

[30]

Rodriguez L V, Yusuf F, Lyons S, Paz E, Rangaswami R, Liu J, Zhao M, Narasimhan G. Learning cache replacement with CACHEUS. In Proc. the 19th USENIX Conference on File and Storage Technologies, Feb. 2021, pp.341-354.

[31]

Zhou X, Sun J, Li G, Feng J. Query performance prediction for concurrent queries using graph embedding. Proceedings of the VLDB Endowment, 2020, 13(9): 1416-1428.

[32]

Fan J, Liu T, Li G, Chen J, Shen Y, Du X. Relational data synthesis using generative adversarial networks: A design space exploration. Proceedings of the VLDB Endowment, 2020, 13(11): 1962-1975.

[33]

Cooper B F, Silberstein A, Tam E, Ramakrishnan R, Sears R. Benchmarking cloud serving systems with YCSB. In Proc. the 1st ACM Symposium on Cloud Computing, Jun. 2010, pp.143-154.

[34]

Jin P, Ou Y, Härder T, Li Z. AD-LRU: An efficient buffer replacement algorithm for ash-based databases. Data & Knowledge Engineering, 2012, 72: 83-102.

Cited By

Kim MHwang JHeo GCho SMahajan DPark J(2024)Accelerating String-Key Learned Index Structures via Memoization-Based Incremental TrainingProceedings of the VLDB Endowment10.14778/3659437.365943917:8(1802-1815)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.14778/3659437.3659439
Zhang RHuang YLiang SSun SMa SHuan CChen LLu ZXu YYan MWu J(2024)Revisiting Learned Index with Byte-addressable Persistent StorageProceedings of the 53rd International Conference on Parallel Processing10.1145/3673038.3673113(929-938)Online publication date: 12-Aug-2024
https://dl.acm.org/doi/10.1145/3673038.3673113
Chu ZZhang ZJin PWang XLuo YZhao XDe V(2024)LIVAK: A High-Performance In-Memory Learned Index for Variable-Length KeysProceedings of the 61st ACM/IEEE Design Automation Conference10.1145/3649329.3657385(1-6)Online publication date: 23-Jun-2024
https://dl.acm.org/doi/10.1145/3649329.3657385
Show More Cited By

Index Terms

COLIN: A Cache-Conscious Dynamic Learned Index with High Read/Write Performance
1. Information systems

Index terms have been assigned to the content through auto-classification.

Recommendations

The Case for Learned Index Structures
SIGMOD '18: Proceedings of the 2018 International Conference on Management of Data

Indexes are models: a \btree-Index can be seen as a model to map a key to the position of a record within a sorted array, a Hash-Index as a model to map a key to a position of a record within an unsorted array, and a BitMap-Index as a model to indicate ...
A learned spatial textual index for efficient keyword queries
Abstract
Spatial textual indexing techniques allow one to efficiently access and process large volume of geospatial data, and recent research efforts have demonstrated that learned indexes can lead to better performance in comparison to conventional ...
Spatial Queries Based on Learned Index
Spatial Data and Intelligence
Abstract
With the popularity of location-based services, the scale of spatial data is increasing. Spatial indexes play an important role in spatial databases, and their performance determines the efficiency of data access and query processing. Most of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Computer Science and Technology

Journal of Computer Science and Technology Volume 36, Issue 4

Jul 2021

242 pages

ISSN:1000-9000

Issue’s Table of Contents

© Institute of Computing Technology, Chinese Academy of Sciences 2021.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 July 2021

Accepted: 13 June 2021

Received: 01 February 2021

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kim MHwang JHeo GCho SMahajan DPark J(2024)Accelerating String-Key Learned Index Structures via Memoization-Based Incremental TrainingProceedings of the VLDB Endowment10.14778/3659437.365943917:8(1802-1815)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.14778/3659437.3659439
Zhang RHuang YLiang SSun SMa SHuan CChen LLu ZXu YYan MWu J(2024)Revisiting Learned Index with Byte-addressable Persistent StorageProceedings of the 53rd International Conference on Parallel Processing10.1145/3673038.3673113(929-938)Online publication date: 12-Aug-2024
https://dl.acm.org/doi/10.1145/3673038.3673113
Chu ZZhang ZJin PWang XLuo YZhao XDe V(2024)LIVAK: A High-Performance In-Memory Learned Index for Variable-Length KeysProceedings of the 61st ACM/IEEE Design Automation Conference10.1145/3649329.3657385(1-6)Online publication date: 23-Jun-2024
https://dl.acm.org/doi/10.1145/3649329.3657385
Luo YJin PChu ZWang XYuan YZhang ZLuo YWu XZou P(2024)Morphtree: a polymorphic main-memory learned index for dynamic workloadsThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-023-00823-y33:4(1065-1084)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s00778-023-00823-y
Li JWang ZCong GLong CKiah HCui B(2023)Towards Designing and Learning Piecewise Space-Filling CurvesProceedings of the VLDB Endowment10.14778/3598581.359858916:9(2158-2171)Online publication date: 10-Jul-2023
https://dl.acm.org/doi/10.14778/3598581.3598589
Zhang ZChu ZJin PLuo YXie XWan SLuo YWu XZou PZheng CWu GRudoff A(2022)PLINProceedings of the VLDB Endowment10.14778/3565816.356582616:2(243-255)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.14778/3565816.3565826
Ding YZhao XJin P(2022)An Error-Bounded Space-Efficient Hybrid Learned Index with High Lookup PerformanceDatabase and Expert Systems Applications10.1007/978-3-031-12426-6_17(216-228)Online publication date: 22-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-12426-6_17
Liu GLuo YJin P(2022)HATree: A Hotness-Aware Tree Index with In-Node Hotspot Cache for NVM/DRAM-Based Hybrid Memory ArchitectureDatabase Systems for Advanced Applications10.1007/978-3-031-00123-9_44(560-568)Online publication date: 11-Apr-2022
https://dl.acm.org/doi/10.1007/978-3-031-00123-9_44

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents