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

research-article

The Concurrent Learned Indexes for Multicore Data Storage

Authors:

Huan WangAuthors Info & Claims

ACM Transactions on Storage (TOS), Volume 18, Issue 1

Article No.: 8, Pages 1 - 35

https://doi.org/10.1145/3478289

Published: 29 January 2022 Publication History

Abstract

We present XIndex, which is a concurrent index library and designed for fast queries. It includes a concurrent ordered index (XIndex-R) and a concurrent hash index (XIndex-H). Similar to a recent proposal of the learned index, the indexes in XIndex use learned models to optimize index efficiency. Compared with the learned index, for the ordered index, XIndex-R is able to handle concurrent writes effectively and adapts its structure according to runtime workload characteristics. For the hash index, XIndex-H is able to avoid the resize operation blocking concurrent writes. Furthermore, the indexes in XIndex can index string keys much more efficiently than the learned index. We demonstrate the advantages of XIndex with YCSB, TPC-C (KV), which is a TPC-C-inspired benchmark for key-value stores, and micro-benchmarks. Compared with ordered indexes of Masstree and Wormhole, XIndex-R achieves up to 3.2× and 4.4× performance improvement on a 24-core machine. Compared with hash indexes of Intel TBB HashMap, XIndex-H achieves up to 3.1× speedup. The performance further improves by 91% after adding the optimizations on indexing string keys. The library is open-sourced.

References

[1]

Oana Balmau, Diego Didona, Rachid Guerraoui, Willy Zwaenepoel, Huapeng Yuan, Aashray Arora, Karan Gupta, and Pavan Konka. 2017. TRIAD: Creating synergies between memory, disk and log in log structured key-value stores. In 2017 USENIX Annual Technical Conference, USENIX ATC 2017, Santa Clara, CA, USA, July 12-14, 2017, Dilma Da Silva and Bryan Ford (Eds.). USENIX Association, 363–375. https://www.usenix.org/conference/atc17/technical-sessions/presentation/balmau.

Digital Library

[2]

Rudolf Bayer and Mario Schkolnick. 1977. Concurrency of operations on B-trees. Acta Informatica 9 (1977), 1–21. DOI:https://doi.org/10.1007/BF00263762

Digital Library

[3]

Timo Bingmann. 2013. STX B+ Tree C++ Template Classes. https://panthema.net/2007/stx-btree/. (2013).

[4]

Robert Binna, Eva Zangerle, Martin Pichl, Günther Specht, and Viktor Leis. 2018. HOT: A height optimized trie index for main-memory database systems. In Proceedings of the 2018 International Conference on Management of Data (SIGMOD’18). Association for Computing Machinery, New York, NY, USA, 521–534. DOI:https://doi.org/10.1145/3183713.3196896

Digital Library

[5]

Burton H. Bloom. 1970. Space/time trade-offs in hash coding with allowable errors. Commun. ACM 13, 7 (July 1970), 422–426. DOI:https://doi.org/10.1145/362686.362692

Digital Library

[6]

Philip Bohannon, Peter Mcllroy, and Rajeev Rastogi. 2001. Main-memory index structures with fixed-size partial keys. In Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data (SIGMOD’01). Association for Computing Machinery, New York, NY, USA, 163–174. DOI:https://doi.org/10.1145/375663.375681

[7]

Flavio Bonomi, Michael Mitzenmacher, Rina Panigrahy, Sushil Singh, and George Varghese. 2006. An improved construction for counting bloom filters. In Algorithms - ESA 2006, 14th Annual European Symposium, Zurich, Switzerland, September 11-13, 2006, Proceedings (Lecture Notes in Computer Science), Yossi Azar and Thomas Erlebach (Eds.), Vol. 4168. Springer, 684–695. DOI:https://doi.org/10.1007/11841036_61

[8]

Nathan G. Bronson, Jared Casper, Hassan Chafi, and Kunle Olukotun. 2010. A practical concurrent binary search tree. In Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP’10). Association for Computing Machinery, New York, NY, USA, 257–268. DOI:https://doi.org/10.1145/1693453.1693488

[9]

Nathan G. Bronson, Jared Casper, Hassan Chafi, and Kunle Olukotun. 2010. A practical concurrent binary search tree. SIGPLAN Not. 45, 5 (Jan. 2010), 257–268. DOI:https://doi.org/10.1145/1837853.1693488

Digital Library

[10]

Sang K. Cha, Sangyong Hwang, Kihong Kim, and Keunjoo Kwon. 2001. Cache-conscious concurrency control of main-memory indexes on shared-memory multiprocessor systems. In Proceedings of the 27th International Conference on Very Large Data Bases (VLDB’01). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 181–190.

Digital Library

[11]

Bernard Chazelle and Leonidas J. Guibas. 1986. Fractional cascading: I. A data structuring technique. Algorithmica 1, 2 (1986), 133–162. DOI:

Digital Library

[12]

Bernard Chazelle and Leonidas J. Guibas. 1986. Fractional cascading: II. Applications. Algorithmica 1, 2 (1986), 163–191. DOI:

[13]

Zhangyu Chen, Yu Huang, Bo Ding, and Pengfei Zuo. 2020. Lock-free concurrent level hashing for persistent memory. In 2020 USENIX Annual Technical Conference, USENIX ATC 2020, July 15-17, 2020, Ada Gavrilovska and Erez Zadok (Eds.). USENIX Association, 799–812. https://www.usenix.org/conference/atc20/presentation/chen.

Digital Library

[14]

Austin T. Clements, M. Frans Kaashoek, and Nickolai Zeldovich. 2012. Scalable address spaces using RCU balanced trees. In Proceedings of the Seventeenth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS XVII). Association for Computing Machinery, New York, NY, USA, 199–210. DOI:https://doi.org/10.1145/2150976.2150998

[15]

Austin T. Clements, M. Frans Kaashoek, and Nickolai Zeldovich. 2012. Scalable address spaces using RCU balanced trees. SIGPLAN Not. 47, 4 (March 2012), 199–210. DOI:https://doi.org/10.1145/2248487.2150998

[16]

Yifan Dai, Yien Xu, Aishwarya Ganesan, Ramnatthan Alagappan, Brian Kroth, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau. 2020. From WiscKey to bourbon: A learned index for log-structured merge trees. In 14th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2020, Virtual Event, November 4-6, 2020. USENIX Association, 155–171. https://www.usenix.org/conference/osdi20/presentation/dai.

Digital Library

[17]

Justin DeBrabant, Andrew Pavlo, Stephen Tu, Michael Stonebraker, and Stan Zdonik. 2013. Anti-caching: A new approach to database management system architecture. Proc. VLDB Endow. 6, 14 (Sept. 2013), 1942–1953. DOI:https://doi.org/10.14778/2556549.2556575

Digital Library

[18]

Cristian Diaconu, Craig Freedman, Erik Ismert, Per-Ake Larson, Pravin Mittal, Ryan Stonecipher, Nitin Verma, and Mike Zwilling. 2013. Hekaton: SQL server’s memory-optimized OLTP engine. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data (SIGMOD’13). Association for Computing Machinery, New York, NY, USA, 1243–1254. DOI:https://doi.org/10.1145/2463676.2463710

[19]

Jialin Ding, Umar Farooq Minhas, Jia Yu, Chi Wang, Jaeyoung Do, Yinan Li, Hantian Zhang, Badrish Chandramouli, Johannes Gehrke, Donald Kossmann, David Lomet, and Tim Kraska. 2020. ALEX: An updatable adaptive learned index. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (SIGMOD’20). Association for Computing Machinery, New York, NY, USA, 969–984. DOI:https://doi.org/10.1145/3318464.3389711

[20]

William B. Easton. 1971. Process synchronization without long-term interlock. In Proceedings of the Third ACM Symposium on Operating Systems Principles (SOSP’71). Association for Computing Machinery, New York, NY, USA, 95–100. DOI:https://doi.org/10.1145/800212.806505

[21]

Li Fan, Pei Cao, Jussara Almeida, and Andrei Z. Broder. 1998. Summary cache: A scalable wide-area web cache sharing protocol. In Proceedings of the ACM SIGCOMM’98 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM’98). Association for Computing Machinery, New York, NY, USA, 254–265. DOI:https://doi.org/10.1145/285237.285287

[22]

Paolo Ferragina and Giorgio Vinciguerra. 2020. The PGM-index: A fully-dynamic compressed learned index with provable worst-case bounds. Proc. VLDB Endow. 13, 8 (April 2020), 1162–1175. DOI:https://doi.org/10.14778/3389133.3389135

Digital Library

[23]

OpenStreetMap Foundation. 2019. OpenStreetMap on AWS. https://aws.amazon.com/public-datasets/osm. Accessed: 2019-4-24.

[24]

Edward Fredkin. 1960. Trie memory. Commun. ACM 3, 9 (Sept. 1960), 490–499. DOI:https://doi.org/10.1145/367390.367400

Digital Library

[25]

Alex Galakatos, Michael Markovitch, Carsten Binnig, Rodrigo Fonseca, and Tim Kraska. 2019. FITing-tree: A data-aware index structure. In Proceedings of the 2019 International Conference on Management of Data (SIGMOD’19). Association for Computing Machinery, New York, NY, USA, 1189–1206. DOI:https://doi.org/10.1145/3299869.3319860

[26]

Goetz Graefe, Hideaki Kimura, and Harumi Kuno. 2012. Foster B-trees. ACM Trans. Database Syst. 37, 3, Article 17 (Sept. 2012), 29 pages. DOI:https://doi.org/10.1145/2338626.2338630

[27]

Roberto Grossi and Giuseppe Ottaviano. 2015. Fast compressed tries through path decompositions. ACM J. Exp. Algorithmics 19, Article 3.4 (Jan. 2015), 20 pages. DOI:https://doi.org/10.1145/2656332

[28]

Maurice P. Herlihy and Jeannette M. Wing. 1990. Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12, 3 (July 1990), 463–492. DOI:https://doi.org/10.1145/78969.78972

Digital Library

[29]

Stratos Idreos, Kostas Zoumpatianos, Manos Athanassoulis, Niv Dayan, Brian Hentschel, Michael S. Kester, Demi Guo, Lukas M. Maas, Wilson Qin, Abdul Wasay, and Yiyou Sun. 2018. The periodic table of data structures. IEEE Data Eng. Bull. 41, 3 (2018), 64–75. http://sites.computer.org/debull/A18sept/p64.pdf.

[30]

Stratos Idreos, Kostas Zoumpatianos, Subarna Chatterjee, Wilson Qin, Abdul Wasay, Brian Hentschel, Mike S. Kester, Niv Dayan, Demi Guo, Minseo Kang, and Yiyou Sun. 2019. Learning data structure alchemy. IEEE Data Eng. Bull. 42, 2 (2019), 47–58. http://sites.computer.org/debull/A19june/p47.pdf.

[31]

Stratos Idreos, Kostas Zoumpatianos, Brian Hentschel, Michael S. Kester, and Demi Guo. 2018. The data calculator: Data structure design and cost synthesis from first principles and learned cost models. In Proceedings of the 2018 International Conference on Management of Data (SIGMOD’18). Association for Computing Machinery, New York, NY, USA, 535–550. DOI:https://doi.org/10.1145/3183713.3199671

[32]

Sudarsun Kannan, Nitish Bhat, Ada Gavrilovska, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau. 2018. Redesigning LSMs for nonvolatile memory with NoveLSM. In 2018 USENIX Annual Technical Conference, USENIX ATC 2018, Boston, MA, USA, July 11-13, 2018, Haryadi S. Gunawi and Benjamin Reed (Eds.). USENIX Association, 993–1005. https://www.usenix.org/conference/atc18/presentation/kannan.

Digital Library

[33]

Andreas Kipf, Ryan Marcus, Alexander van Renen, Mihail Stoian, Alfons Kemper, Tim Kraska, and Thomas Neumann. 2020. RadixSpline: A single-pass learned index. In Proceedings of the Third International Workshop on Exploiting Artificial Intelligence Techniques for Data Management (aiDM’20). Association for Computing Machinery, New York, NY, USA, Article 5, 5 pages. DOI:https://doi.org/10.1145/3401071.3401659

[34]

Tim Kraska, Mohammad Alizadeh, Alex Beutel, Ed H. Chi, Ani Kristo, Guillaume Leclerc, Samuel Madden, Hongzi Mao, and Vikram Nathan. 2019. SageDB: A learned database system. In CIDR 2019, 9th Biennial Conference on Innovative Data Systems Research, Asilomar, CA, USA, January 13-16, 2019, Online Proceedings. www.cidrdb.org. http://cidrdb.org/cidr2019/papers/p117-kraska-cidr19.pdf.

[35]

Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. 2018. The case for learned index structures. In Proceedings of the 2018 International Conference on Management of Data (SIGMOD’18). Association for Computing Machinery, New York, NY, USA, 489–504. DOI:https://doi.org/10.1145/3183713.3196909

[36]

H. T. Kung and John T. Robinson. 1981. On optimistic methods for concurrency control. ACM Trans. Database Syst. 6, 2 (June 1981), 213–226. DOI:https://doi.org/10.1145/319566.319567

Digital Library

[37]

Leslie Lamport. 1977. Concurrent reading and writing. Commun. ACM 20, 11 (Nov. 1977), 806–811. DOI:https://doi.org/10.1145/359863.359878

Digital Library

[38]

Viktor Leis, Alfons Kemper, and Thomas Neumann. 2013. The adaptive radix tree: ARTful indexing for main-memory databases. In Proceedings of the 2013 IEEE 29th International Conference on Data Engineering (ICDE’13). IEEE Computer Society, 38–49. DOI:https://doi.org/10.1109/ICDE.2013.6544812

[39]

Baptiste Lepers, Oana Balmau, Karan Gupta, and Willy Zwaenepoel. 2019. KVell: The design and implementation of a fast persistent key-value store. In Proceedings of the 27th ACM Symposium on Operating Systems Principles (SOSP’19). Association for Computing Machinery, New York, NY, USA, 447–461. DOI:https://doi.org/10.1145/3341301.3359628

Digital Library

[40]

Jure Leskovec, Lars Backstrom, and Jon Kleinberg. 2009. Meme-tracking and the dynamics of the news cycle. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’09). Association for Computing Machinery, New York, NY, USA, 497–506. DOI:https://doi.org/10.1145/1557019.1557077

Digital Library

[41]

Justin J. Levandoski, David B. Lomet, and Sudipta Sengupta. 2013. The Bw-tree: A B-tree for new hardware platforms. In 29th IEEE International Conference on Data Engineering, ICDE 2013, Brisbane, Australia, April 8-12, 2013, Christian S. Jensen, Christopher M. Jermaine, and Xiaofang Zhou (Eds.). IEEE Computer Society, 302–313. DOI:https://doi.org/10.1109/ICDE.2013.6544834

[42]

Pengfei Li, Yu Hua, Pengfei Zuo, and Jingnan Jia. 2019. A scalable learned index scheme in storage systems. CoRR abs/1905.06256 (2019). arXiv:1905.06256 http://arxiv.org/abs/1905.06256.

[43]

Pengfei Li, Hua Lu, Qian Zheng, Long Yang, and Gang Pan. 2020. LISA: A learned index structure for spatial data. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (SIGMOD’20). Association for Computing Machinery, New York, NY, USA, 2119–2133. DOI:https://doi.org/10.1145/3318464.3389703

[44]

Lanyue Lu, Thanumalayan Sankaranarayana Pillai, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau. 2016. WiscKey: Separating keys from values in SSD-conscious storage. In 14th USENIX Conference on File and Storage Technologies, FAST 2016, Santa Clara, CA, USA, February 22-25, 2016, Angela Demke Brown and Florentina I. Popovici (Eds.). USENIX Association, 133–148. https://www.usenix.org/conference/fast16/technical-sessions/presentation/lu.

Digital Library

[45]

Yandong Mao, Eddie Kohler, and Robert Tappan Morris. 2012. Cache craftiness for fast multicore key-value storage. In Proceedings of the 7th ACM European Conference on Computer Systems (EuroSys’12). Association for Computing Machinery, New York, NY, USA, 183–196. DOI:https://doi.org/10.1145/2168836.2168855

[46]

Paul Mckenney and John Slingwine. 1998. Read-copy update: Using execution history to solve concurrency problems. In Parallel and Distributed Computing and Systems. 509–518.

[47]

C. Mohan, Don Haderle, Bruce Lindsay, Hamid Pirahesh, and Peter Schwarz. 1992. ARIES: A transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging. ACM Trans. Database Syst. 17, 1 (March 1992), 94–162. DOI:https://doi.org/10.1145/128765.128770

Digital Library

[48]

Vikram Nathan, Jialin Ding, Mohammad Alizadeh, and Tim Kraska. 2020. Learning multi-dimensional indexes. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (SIGMOD’20). Association for Computing Machinery, New York, NY, USA, 985–1000. DOI:https://doi.org/10.1145/3318464.3380579

[49]

Patrick E. O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth J. O’Neil. 1996. The log-structured merge-tree (LSM-Tree). Acta Informatica 33, 4 (1996), 351–385. DOI:https://doi.org/10.1007/s002360050048

Digital Library

[50]

Anastasios Papagiannis, Giorgos Saloustros, Pilar González-Férez, and Angelos Bilas. 2018. An efficient memory-mapped key-value store for flash storage. In Proceedings of the ACM Symposium on Cloud Computing (SoCC’18). Association for Computing Machinery, New York, NY, USA, 490–502. DOI:https://doi.org/10.1145/3267809.3267824

Digital Library

[51]

Chuck Pheatt. 2008. Intel® threading building blocks. Journal of Computing Sciences in Colleges 23, 4 (2008), 298–298.

Digital Library

[52]

Felix Putze, Peter Sanders, and Johannes Singler. 2007. Cache-, hash- and space-efficient bloom filters. In Experimental Algorithms, 6th International Workshop, WEA 2007, Rome, Italy, June 6-8, 2007, Proceedings (Lecture Notes in Computer Science), Camil Demetrescu (Ed.), Vol. 4525. Springer, 108–121. DOI:https://doi.org/10.1007/978-3-540-72845-0_9

[53]

Karl Schnaitter, Serge Abiteboul, Tova Milo, and Neoklis Polyzotis. 2007. On-line index selection for shifting workloads. In Proceedings of the 23rd International Conference on Data Engineering Workshops, ICDE 2007, 15-20 April 2007, Istanbul, Turkey. IEEE Computer Society, 459–468. DOI:https://doi.org/10.1109/ICDEW.2007.4401029

[54]

Russell Sears and Raghu Ramakrishnan. 2012. BLSM: A general purpose log structured merge tree. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data (SIGMOD’12). Association for Computing Machinery, New York, NY, USA, 217–228. DOI:https://doi.org/10.1145/2213836.2213862

Digital Library

[55]

Ori Shalev and Nir Shavit. 2006. Split-ordered lists: Lock-free extensible hash tables. J. ACM 53, 3 (May 2006), 379–405. DOI:https://doi.org/10.1145/1147954.1147958

Digital Library

[56]

Stephen Tu, Wenting Zheng, Eddie Kohler, Barbara Liskov, and Samuel Madden. 2013. Speedy transactions in multicore in-memory databases. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles (SOSP’13). Association for Computing Machinery, New York, NY, USA, 18–32. DOI:https://doi.org/10.1145/2517349.2522713

[57]

Peng Wang, Guangyu Sun, Song Jiang, Jian Ouyang, Shiding Lin, Chen Zhang, and Jason Cong. 2014. An efficient design and implementation of LSM-tree based key-value store on open-channel SSD. In Proceedings of the Ninth European Conference on Computer Systems (EuroSys’14). Association for Computing Machinery, New York, NY, USA, Article 16, 14 pages. DOI:https://doi.org/10.1145/2592798.2592804

Digital Library

[58]

Xingbo Wu, Fan Ni, and Song Jiang. 2019. Wormhole: A fast ordered index for in-memory data management. In Proceedings of the Fourteenth EuroSys Conference 2019 (EuroSys’19). Association for Computing Machinery, New York, NY, USA, Article 18, 16 pages. DOI:https://doi.org/10.1145/3302424.3303955

[59]

Ting Yao, Yiwen Zhang, Jiguang Wan, Qiu Cui, Liu Tang, Hong Jiang, Changsheng Xie, and Xubin He. 2020. MatrixKV: Reducing write stalls and write amplification in LSM-tree based KV stores with matrix container in NVM. In 2020 USENIX Annual Technical Conference, USENIX ATC 2020, July 15-17, 2020, Ada Gavrilovska and Erez Zadok (Eds.). USENIX Association, 17–31. https://www.usenix.org/conference/atc20/presentation/yao.

Digital Library

[60]

Huanchen Zhang, David G. Andersen, Andrew Pavlo, Michael Kaminsky, Lin Ma, and Rui Shen. 2016. Reducing the storage overhead of main-memory OLTP databases with hybrid indexes. In Proceedings of the 2016 International Conference on Management of Data (SIGMOD’16). Association for Computing Machinery, New York, NY, USA, 1567–1581. DOI:https://doi.org/10.1145/2882903.2915222

[61]

Huanchen Zhang, Hyeontaek Lim, Viktor Leis, David G. Andersen, Michael Kaminsky, Kimberly Keeton, and Andrew Pavlo. 2018. SuRF: Practical range query filtering with fast succinct tries. In Proceedings of the 2018 International Conference on Management of Data (SIGMOD’18). Association for Computing Machinery, New York, NY, USA, 323–336. DOI:https://doi.org/10.1145/3183713.3196931

[62]

Wenting Zheng, Stephen Tu, Eddie Kohler, and Barbara Liskov. 2014. Fast databases with fast durability and recovery through multicore parallelism. In 11th USENIX Symposium on Operating Systems Design and Implementation, OSDI’14, Broomfield, CO, USA, October 6-8, 2014, Jason Flinn and Hank Levy (Eds.). USENIX Association, 465–477. https://www.usenix.org/conference/osdi14/technical-sessions/presentation/zheng_wenting.

Cited By

Zhang DZhang MTan XLiu J(2024)Bridging the Domain Gap in Scene Flow Estimation via Hierarchical Smoothness RefinementACM Transactions on Multimedia Computing, Communications, and Applications10.1145/366182320:8(1-21)Online publication date: 12-Jun-2024
https://dl.acm.org/doi/10.1145/3661823
Liu JZheng ZYang ZYang Y(2024)High Fidelity Makeup via 2D and 3D Identity Preservation NetACM Transactions on Multimedia Computing, Communications, and Applications10.1145/365647520:8(1-24)Online publication date: 13-Jun-2024
https://dl.acm.org/doi/10.1145/3656475
Zhang JSu KZhang H(2024)Making In-Memory Learned Indexes Efficient on DiskProceedings of the ACM on Management of Data10.1145/36549542:3(1-26)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654954
Show More Cited By

Index Terms

The Concurrent Learned Indexes for Multicore Data Storage
1. Information systems
  1. Data management systems
    1. Data structures
2. Theory of computation
  1. Design and analysis of algorithms
    1. Concurrent algorithms

Recommendations

ALEX: An Updatable Adaptive Learned Index
SIGMOD '20: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data

Recent work on "learned indexes" has changed the way we look at the decades-old field of DBMS indexing. The key idea is that indexes can be thought of as "models" that predict the position of a key in a dataset. Indexes can, thus, be learned. The ...
Making In-Memory Learned Indexes Efficient on Disk
SIGMOD

Learned indexes have been demonstrated to outperform traditional ones in memory-resident scenarios. However, recent studies show that they fail to outperform B+tree when extended to disks directly. In this paper, we argue that it is feasible to create ...
Benchmarking Learned and LSM Indexes for Data Sortedness
DBTest '24: Proceedings of the Tenth International Workshop on Testing Database Systems

Database systems use indexes on frequently accessed attributes to accelerate query and transaction processing. This requires paying the cost of maintaining and updating those indexes, which can be thought of as the process of adding structure (e.g., sort)...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Storage

ACM Transactions on Storage Volume 18, Issue 1

February 2022

245 pages

ISSN:1553-3077

EISSN:1553-3093

DOI:10.1145/3512348

Editor:
Sam H. Noh
Ulsan National Institute of Science and Technology, Ulsan, Republic of Korea

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 January 2022

Accepted: 01 July 2021

Revised: 01 March 2021

Received: 01 August 2020

Published in TOS Volume 18, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Refereed

Funding Sources

National Natural Science Foundation of China
HighTech Support Program from Shanghai Committee of Science and Technology
National Key Research and Development Program of China

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
1,162
Total Downloads

Downloads (Last 12 months)201
Downloads (Last 6 weeks)22

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang DZhang MTan XLiu J(2024)Bridging the Domain Gap in Scene Flow Estimation via Hierarchical Smoothness RefinementACM Transactions on Multimedia Computing, Communications, and Applications10.1145/366182320:8(1-21)Online publication date: 12-Jun-2024
https://dl.acm.org/doi/10.1145/3661823
Liu JZheng ZYang ZYang Y(2024)High Fidelity Makeup via 2D and 3D Identity Preservation NetACM Transactions on Multimedia Computing, Communications, and Applications10.1145/365647520:8(1-24)Online publication date: 13-Jun-2024
https://dl.acm.org/doi/10.1145/3656475
Zhang JSu KZhang H(2024)Making In-Memory Learned Indexes Efficient on DiskProceedings of the ACM on Management of Data10.1145/36549542:3(1-26)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654954
Ma YZhao CHuang BLi XBasu A(2024)RAST: Restorable Arbitrary Style TransferACM Transactions on Multimedia Computing, Communications, and Applications10.1145/363877020:5(1-21)Online publication date: 22-Jan-2024
https://dl.acm.org/doi/10.1145/3638770
Ma ZWang SLuo XGu ZChen CLi JHua XLu G(2024)HARR: Learning Discriminative and High-Quality Hash Codes for Image RetrievalACM Transactions on Multimedia Computing, Communications, and Applications10.1145/362716220:5(1-23)Online publication date: 22-Jan-2024
https://dl.acm.org/doi/10.1145/3627162
Wang RHao YHu LLi XChen MMiao YHumar I(2024)Efficient Crowd Counting via Dual Knowledge DistillationIEEE Transactions on Image Processing10.1109/TIP.2023.334360933(569-583)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TIP.2023.3343609
Zhang YJin GLi JZhang T(2024)Hierarchical Storage for Massive Social Network Data Based on Improved Decision TreeMobile Networks and Applications10.1007/s11036-024-02426-5Online publication date: 30-Sep-2024
https://doi.org/10.1007/s11036-024-02426-5
Ge JZhang HShi BLuo YGuo YChai YChen YPan A(2023)SALI: A Scalable Adaptive Learned Index Framework based on Probability ModelsProceedings of the ACM on Management of Data10.1145/36267521:4(1-25)Online publication date: 12-Dec-2023
https://dl.acm.org/doi/10.1145/3626752
Hou SLi JMin WHou QZhao YZheng YJiang S(2023)Deep Learning for Logo Detection: A SurveyACM Transactions on Multimedia Computing, Communications, and Applications10.1145/361130920:3(1-23)Online publication date: 23-Oct-2023
https://dl.acm.org/doi/10.1145/3611309
Chen YJhong SHsia C(2023)Roadside Unit-based Unknown Object Detection in Adverse Weather Conditions for Smart Internet of VehiclesACM Transactions on Management Information Systems10.1145/355492313:4(1-21)Online publication date: 3-Jan-2023
https://dl.acm.org/doi/10.1145/3554923
Show More Cited By

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View full text|Download PDF

View Issue’s Table of Contents