Learned Index Resources

Surveys

• The Case for Learned Index Structures. Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, Neoklis Polyzotis. SIGMOD 2018.

• Learned data structures. Paolo Ferragina and Giorgio Vinciguerra. Recent Trends in Learning From Data. Studies in Computational Intelligence, vol 896.

• A Tutorial on Learned Multi-dimensional Indexes. Abdullah Al-Mamun, Hao Wu, Walid G. Aref. SIGSPATIAL 2020.

One Dimensional Learned Index

• A-Tree: A Bounded Approximate Index Structure. Alex Galakatos, Michael Markovitch, Carsten Binnig, Rodrigo Fonseca, Tim Kraska. SIGMOD 2018.

• FITing-Tree: A Data-aware Index Structure. Alex Galakatos, Michael Markovitch, Carsten Binnig, Rodrigo Fonseca, Tim Kraska. SIGMOD 2019.

• Hist-Tree: Those Who Ignore It Are Doomed to Learn. Andrew Crotty. CIDR 2021.

• PolyFit: Polynomial-based Indexing Approach for Fast Approximate Range Aggregate Queries. Zhe Li, Tsz Nam Chan, Man Lung Yiu, Christian S. Jensen EDBT, 2021.

Updatable Learned Index

• XIndex: A Scalable Learned Index for Multicore Data Storage. Chuzhe Tang, Youyun Wang, Zhiyuan Dong, Gansen Hu, Zhaoguo Wang, Minjie Wang, Haibo Chen. PPoPP 2020.

• The PGM-Index: A Fully-Dynamic Compressed Learned Index with Provable Worst-Case Bounds. Paolo Ferragina, Giorgio Vinciguerra. VLDB 2020.

• ALEX: An Updatable Adaptive Learned Index. Jialin Ding, Umar Farooq Minhas, Jia Yu, Chi Wang, Jaeyoung Do, Yinan Li, Hantian Zhang, Badrish Chandramouli, Johannes Gehrke, Donald Kossmann, David Lomet, Tim Kraska. SIGMOD 2020.

• Updatable Learned Index with Precise Positions. Jiacheng Wu, Yong Zhang, Shimin Chen, Jin Wang, Yu Chen, Chunxiao Xing. VLDB 2021.

• Are updatable learned indexes ready?. Chaichon Wongkham, Baotong Lu, Chris Liu, Zhicong Zhong, Eric Lo, Tianzheng Wang. PVLDB 2022.

Spatial Learned Index

• The Case for Learned Spatial Indexes. Varun Pandey, Alexander van Renen, Andreas Kipf, Ibrahim Sabek, Jialin Ding, Alfons Kemper. AIDB 2020.

• Effectively Learning Spatial Indices. Jianzhong Qi, Guanli Liu, Christian S. Jensen, Lars Kulik. VLDB 2020.

• LISA: A Learned Index Structure for Spatial Data. Pengfei Li, Hua Lu, Qian Zheng, Long Yang, Gang Pan. SIGMOD 2020.

• Spatial Interpolation-based Learned Index for Range and kNN Queries. Songnian Zhang, Suprio Ray, Rongxing Lu, Yandong Zheng. arXiv 2021.

• The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data. Tu Gu, Kaiyu Feng, Gao Cong, Cheng Long, Zheng Wang, Sheng Wang. arXiv 2021.

• LHist: Towards Learning Multi-dimensional Histogram for Massive Spatial Data. Qiyu Liu, Yanyan Shen, and Lei Chen. ICDE 2021.

Multi / High Dimensional Learned Index

• Qd-tree: Learning Data Layouts for Big Data Analytics. Zongheng Yang, Badrish Chandramouli, Chi Wang, Johannes Gehrke, Yinan Li, Umar Farooq Minhas, Per-Åke Larson, Donald Kossmann, Rajeev Acharya. SIGMOD 2020.

• A Study of Learned KD Tree Based on Learned Index. P. Yongxin, Z. Wei, Z. Lin and D. Hongle. 2020 International Conference on Networking and Network Applications (NaNA).

• The ML-Index: A Multidimensional, Learned Index for Point, Range, and Nearest-Neighbor Queries. Angjela Davitkova, Evica Milchevski, Sebastian Michel. EDBT 2020.

• The "AI+R"-Tree: An Instance-Optimized R-tree. Abdullah-Al-Mamun, Ch. Md. Rakin Haider, Jianguo Wang, Walid G. Aref. MDM 2022

• The Case for ML-Enhanced High-Dimensional Indexes. Rong Kang, Wentao Wu, Chen Wang, Ce Zhang, Jianmin Wang. AIDB 2021.

Approximate Query Processing

• ML-AQP: Query-Driven Approximate Query Processing based on Machine Learning. Fotis Savva, Christos Anagnostopoulos, Peter Triantafillou. ACM Symposium on Neural Gaze Detection 2018.

• LAQP: Learning-based Approximate Query Processing. Meifan Zhang, Hongzhi Wang. arXiv 2020.

• Learned Approximate Query Processing: Make it Light, Accurate and Fast. Qingzhi Ma, Ali M. Shanghooshabad, Mehrdad Almasi, Meghdad Kurmanji, Peter Triantafillou. CIDR 2021.

• Learned Metric Index. Matej Antol, Jaroslav Ol’ha, Terézia Slanináková, Vlastislav Dohnal. Information Systems. 2021.

• A learned index for approximate kNN queries in high-dimensional spaces. Lingli Li, Jingwen Cai, Jie Xu. Knowledge and Information Systems 2022.

Other Resources

High dimesional Data

• High-Dimensional Similarity Query Processing for Data Science. Jianbin Qin, Wei Wang, Chuan Xiao, Ying Zhang, Yaoshu Wang. KDD 2021

• Indexing High-Dimensional Data for Efficient In-Memory Similarity Search. Bin Cui, Beng Chin Coi, Jianwen Su, K.-L. Tan. IEEE Transactions on Knowledge and Data Engineering 2005.

• Searching in High-Dimensional Spaces: Index Structures for Improving the Performance of Multimedia Databases. Christian Böhm, Stefan Berchtold, Daniel A. Keim.

Website

• http://dsg.csail.mit.edu/mlforsystems/papers/

Learn to Hash

• https://towardsdatascience.com/learning-to-hash-36367b9814f1
• https://cs.nju.edu.cn/lwj/L2H.html
• https://learning2hash.github.io/

Spatial Data

• Geospatial | GeoHash | R-Tree | QuadTree
• RBush — a high-performance JavaScript R-tree-based 2D spatial index for points and rectangles

Online Machine learning

• Awesome Online Machine Learning

Machine Learning resources

• FOUNDATIONS OF MACHINE LEARNING
• https://www.kdnuggets.com/2017/03/seven-more-steps-machine-learning-python.html
• https://course.fast.ai/Resources/book.html