Skip to content

Latest commit

 

History

History
168 lines (145 loc) · 14.6 KB

README.md

File metadata and controls

168 lines (145 loc) · 14.6 KB
Raw

IndexStructureJourney

2024 DKU System Software Lab Index Study

Goals

  • Study Index and Learned Index Structures
  • Write a open-source document.
  • (Optional) Write a research paper on what you learned.

Schedule

Paper Presentation

Date Content Presenter
Week 1 24-01-03 "Traditional Index" Hojin Shin
Week 2 24-01-10 "Traditional Index" Hojin Shin
"A Learned Index Journey" Minguk Choi
Week 3 24-01-17 "No Hot Spot Non-blocking Skip List", ICDCS 13 Nakyeong Kim, Suhwan Shin
Week 4 24-01-24 "Benchmarking learned indexes.", VLDB 20 Yeojin Oh, Zhu Yongjie
"S3: A Scalable In-memory Skip-List Index for Key-Value Store", VLDB 19 Boseung Kim, Yeongyu Choi
Week 5 24-01-31 "Learned Index: A Comprehensive Experimental Evaluation." VLDB 23 Nakyeong Kim, Suhwan Shin, Yeongyu Choi
Week 6 24-02-07 Lunar New Year Holiday
Week 7 24-02-14 "Cache craftiness for fast multicore key-value storage", EuroSys '12 Boseung Kim, Yeojin Oh, Zhu Yongjie
Week 8 24-02-21 "The adaptive radix tree: ARTful indexing for main-memory databases", ICDE 13 Nakyeong Kim, Suhwan Shin
Week 9 24-02-28 "Film: A fully learned index for larger-than-memory databases", VLDB 23 Boseung Kim, Yeojin Oh, Zhu Yongjie

Evaluation Presentation

Presenter Contents
Week 4 24-01-24 Nakyeong Kim, Suhwan Shin No Hot Spot Non-Blocking Skip List - Range Query Experiment
Week 5 24-01-31 Boseung Kim, Yeojin Oh, Zhu Yongjie Apply SIMD to RMI
Week 6 24-02-07 Lunar New Year Holiday
Week 7 24-02-14 Nakyeong Kim, Suhwan Shin LIPP Observations
Boseung Kim, Yeojin Oh, Zhu Yongjie Applying SIMD in Linear Regression
Week 8 24-02-21 Nakyeong Kim, Suhwan Shin LIPP Observations Enhancement
Boseung Kim, Yeojin Oh, Zhu Yongjie SIMD + RMI
Week 9 24-02-28 Nakyeong Kim, Suhwan Shin LIPP New Hypothesis
Boseung Kim, Yeojin Oh, Zhu Yongjie Revisiting HW Parallelism in Learned Indexes

|

Paper & Lecture List

Benchmarks

  • Traditional Index : Index-Microbench
    • Traditional Index : SkipList, B+TreeRTM, B+TreeOLC, BwTree, ARTOLC, MassTree
  • Read-Only Learned Index : LIST
    • Learned Index : sRMI, sPGM-Index, sRS
    • Traditional Index : sCHT, sRT, sB+Tree(STX B+-Tree), sART, sIBTree
  • Updatable Learned Index : GRE
    • Learned Index : ALEX, ALEX+, LIPP, LIPP+, PGM-Index, XIndex, FINEdex
    • Traditional Index : STX B+Tree, B+TreeOLC, ART, ART-OLC, HOT, HOT-ROWEX, MassTree, Wormhole

Traditional Index

  • Tree-based
    • Douglas Comer, "Ubiquitous B-Tree", ACM Computing Surveys, 1979
    • R. Bayer, et al. "Organization and maintenance of large ordered indices", SIGFIDET '70
    • Justin J. Levandoski, et al. "The Bw-Tree: A B-tree for new hardware platform", ICDE 2013 :octocat:
    • J. Rao, et al. "Making B+-Trees Cache Conscious in Main Memory", SIGMOD 2000 :octocat:
    • J. Rao, et al. "Cache Conscious Indexing for Decision-Support in Main Memory", VLDB '99 :octocat:
    • Changkyu Kim et al. "FAST: fast architecture sensitive tree search on modern CPUs and GPUs", SIGMOD '10
    • Yandong Mao, et al. "Cache craftiness for fast multicore key-value storage", EuroSys '12 :octocat:
    • Viktor Leis, et al. "The adaptive radix tree: ARTful indexing for main-memory databases", ICDE 2013 :octocat:
    • Wook-Hee Kim, et al. "PACTree: A High Performance Persistent Range Index Using PAC Guidelines", SOSP '21 :octocat:
    • Se Kwon Lee, et al. "WORT: Write Optimal Radix Tree for Persistent Memory Storage Systems", FAST '17 :octocat:
  • List-based
    • William Pugh, "Skip lists: a probabilistic alternative to balanced trees", Communications of the ACM 1990
    • Zhongle Xie, et al. "Parallelizing Skip Lits for In-Memory Multi-Core Database Systems", ICDE 2017
    • Jeseong Yeon, et al. "JellyFish: A Fast Skip List with MVCC", Middleware '20
    • Tyler Crain, et al. "No Hot Spot Non-blocking Skip List", ICDCS 2013
    • Henry Daly, et al. "NUMASK: High Performance Scalable Skip List for NUMA", DISC 2018 :octocat:
    • Yedam Na, et al. "ESL: A High-Performance Skiplist with Express Lane", MDPI 2023
    • Zhongle Xie, et al. "PI: a parallel in-memory skip list based index", CoRR 2016
    • Tadeusz Kobus, et al. "Jiffy: a lock-free skip list with batch updates and snapshots", PPoPP '22 :octocat:
    • Vitaly Aksenov, et al. "The splay-list: a distribution-adaptive concurrent skip-list", Distributed Computing 2023
  • Hash-based
    • Tudor David, et al. "Asynchronized Concurrency: The Secret to Scaling Concurrent Search Data Structures", ACM SGARCH '15 :octocat:
    • Vikram Narayanan, et al. "DRAMHiT: A Hash Table Architected for the Speed of DRAM", EuroSys '23
    • Daokun Hu, et al. "Halo: A Hybrid PMem-DRAM Persistent Hash Index with Fast Recovery", SIGMOD '20 :octocat:
  • Hybrid Technique
    • Jingtian Zhang, et al. "S3: a scalable in-memory skip-list index for key-value store", VLDB 2019
    • Sprenger, et al. "Cache-Sensitive Skip List: Efficient Range Queries on Modern CPUs", Data Management on New Hardware 2016 :octocat:
    • Hokeun Cha, et al. "Blink-hash: An Adaptive Hybrid Index for In-Memory Time-Series Databases", VLDB 2023
    • Hongbo Kang, et al. "PIM-Tree: A Skew-Resistant Index for Processing-in-Memory", VLDB 2022
    • Ajit mathew, et al. "HydraList: a scalable in-memory index using asynchronous updates and partial replication", VLDB 2020
    • Wenlong Ma, et al. "BiloKey: A Scalable Bi-Index Locality-Aware In-Memory Key-Value Store", IEEE TPDS 2019
  • Survey
    • Z. Xie, et al. "A Comprehensive Performance Evaluation of Modern In-Memory Indices", ICDE 2018
    • Abdullah Talha Kabakus, et al, "A performance evaluation of in-memory databases", J. King Saud Univ. Comput. Inf. Sci. 2017
    • Venkata Sai Pavan Kumar Vadrevu et al, "Tutorial: The Ubiquitous Skiplist, its Variants, and Applications in Modern Big Data Systems"

Learned Index

Read-Only Learned Index

  • Maltry, Marcel, et al. "A critical analysis of recursive model indexes.", VLDB 22 :octocat:
  • Ferragina, Paolo, et al. "The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds.", VLDB 20 :octocat: 📊
  • Kipf, Andreas, et al. "RadixSpline: a single-pass learned index.", aiDM@SIGMOD 20:octocat: 🎬
  • Marcus, Ryan, et al. "Benchmarking learned indexes.", VLDB 20 :octocat:
  • Minguk, Choi, et al. "Can Learned Indexes be Build-Efficient? A Deep Dive into Sampling Trade-Offs.", SIGMOD 24 :octocat:

Updatable Learned Index

  • Ding, Jialin, et al. "ALEX: an updatable adaptive learned index.", SIGMOD 20 🎬 :octocat:
  • Wu, Jiacheng, et al. "Updatable learned index with precise positions.", VLDB 21 🎬 :octocat:
  • Wongkham, Chaichon, et al. "Are updatable learned indexes ready?", VLDB 22' :octocat:
  • Sun, Zhaoyan, et al. "Learned Index: A Comprehensive Experimental Evaluation." VLDB 23.
  • Ge, Jiake, et al. "SALI: A Scalable Adaptive Learned Index Framework based on Probability Models.", SIGMOD 24 :octocat:

Algorithm & Application

  • Error-Bounded PLA Model
    • Xie, Qing, et al. "Maximum error-bounded piecewise linear representation for online stream approximation." VLDB journal 14 :octocat:
  • Key-Value Store
    • Dai, Yifan, et al. "From {WiscKey} to Bourbon: A Learned Index for {Log-Structured} Merge Trees.", OSDI 20 :octocat:
    • Yu, Geoffrey X., et al. "Treeline: an update-in-place key-value store for modern storage.", VLDB 22 :octocat: 📊
  • NVM Device
    • Lu, Baotong, et al. "APEX: A high-performance learned index on persistent memory.", VLDB 21 :octocat:
    • Ge, Jiake, et al. "Cutting Learned Index into Pieces: An In-depth Inquiry into Updatable Learned Indexes." ICDE 23.
  • FTL
    • Sun, Jinghan, et al. "Leaftl: A learning-based flash translation layer for solid-state drives.", ASPLOS 23 :octocat:

Extensive ML4System Paper List

Lecture

For Beginners

Members

Schedule

  • Date: Every Wensday in January, February
  • Time: 14:00 ~ 16:00
  • Place: Dankook University Software ICT Hall Room 507