{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T01:52:55Z","timestamp":1775785975627,"version":"3.50.1"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:p>Recent works on learned index open a new direction for the indexing field. The key insight of the learned index is to approximate the mapping between keys and positions with piece-wise linear functions. Such methods require partitioning key space for a better approximation. Although lots of heuristics are proposed to improve the approximation quality, the bottleneck is that the segmentation overheads could hinder the overall performance.<\/jats:p>\n          <jats:p>\n            This paper tackles the approximation problem by applying a\n            <jats:italic>distribution transformation<\/jats:italic>\n            to the keys before constructing the learned index. A two-stage Normalizing-Flow-based Learned index framework (NFL) is proposed, which first transforms the original complex key distribution into a near-uniform distribution, then builds a learned index leveraging the transformed keys. For effective distribution transformation, we propose a Numerical Normalizing Flow (Numerical NF). Based on the characteristics of the transformed keys, we propose a robust After-Flow Learned Index (AFLI). To validate the performance, comprehensive evaluations are conducted on both synthetic and real-world workloads, which shows that the proposed NFL produces the highest throughput and the lowest tail latency compared to the state-of-the-art learned indexes.\n          <\/jats:p>","DOI":"10.14778\/3547305.3547322","type":"journal-article","created":{"date-parts":[[2022,9,7]],"date-time":"2022-09-07T16:09:53Z","timestamp":1662566993000},"page":"2188-2200","source":"Crossref","is-referenced-by-count":29,"title":["NFL"],"prefix":"10.14778","volume":"15","author":[{"given":"Shangyu","family":"Wu","sequence":"first","affiliation":[{"name":"City University of Hong Kong, Hong Kong"}]},{"given":"Yufei","family":"Cui","sequence":"additional","affiliation":[{"name":"City University of Hong Kong, Hong Kong"}]},{"given":"Jinghuan","family":"Yu","sequence":"additional","affiliation":[{"name":"City University of Hong Kong, Hong Kong"}]},{"given":"Xuan","family":"Sun","sequence":"additional","affiliation":[{"name":"City University of Hong Kong, Hong Kong"}]},{"given":"Tei-Wei","family":"Kuo","sequence":"additional","affiliation":[{"name":"National Taiwan University, Taiwan"}]},{"given":"Chun Jason","family":"Xue","sequence":"additional","affiliation":[{"name":"City University of Hong Kong, Hong Kong"}]}],"member":"320","published-online":{"date-parts":[[2022,9,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR46437.2021.00092"},{"key":"e_1_2_1_2_1","volume-title":"A Learned Approach to Design Compressed Rank\/Select Data Structures. ACM Transactions on Algorithms (TALG)","author":"Boffa Antonio","year":"2021","unstructured":"Antonio Boffa , Paolo Ferragina , and Giorgio Vinciguerra . 2021. A Learned Approach to Design Compressed Rank\/Select Data Structures. ACM Transactions on Algorithms (TALG) ( 2021 ). Antonio Boffa, Paolo Ferragina, and Giorgio Vinciguerra. 2021. A Learned Approach to Design Compressed Rank\/Select Data Structures. ACM Transactions on Algorithms (TALG) (2021)."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the Thirty-Fifth Conference on Uncertainty in Artificial Intelligence (UAI)","volume":"115","author":"Cao Nicola De","year":"2019","unstructured":"Nicola De Cao , Wilker Aziz , and Ivan Titov . 2019 . Block Neural Autoregressive Flow . In Proceedings of the Thirty-Fifth Conference on Uncertainty in Artificial Intelligence (UAI) , Vol. 115 . 1263--1273. Nicola De Cao, Wilker Aziz, and Ivan Titov. 2019. Block Neural Autoregressive Flow. In Proceedings of the Thirty-Fifth Conference on Uncertainty in Artificial Intelligence (UAI), Vol. 115. 1263--1273."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW53142.2021.00019"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI). 155--171","author":"Dai Yifan","unstructured":"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 Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI). 155--171 . 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 Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI). 155--171."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389711"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425880"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 3rd International Conference on Learning Representations (ICLR).","author":"Dinh Laurent","year":"2015","unstructured":"Laurent Dinh , David Krueger , and Yoshua Bengio . 2015 . NICE: Non-linear Independent Components Estimation . In Proceedings of the 3rd International Conference on Learning Representations (ICLR). Laurent Dinh, David Krueger, and Yoshua Bengio. 2015. NICE: Non-linear Independent Components Estimation. In Proceedings of the 3rd International Conference on Learning Representations (ICLR)."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 5th International Conference on Learning Representations (ICLR).","author":"Dinh Laurent","year":"2017","unstructured":"Laurent Dinh , Jascha Sohl-Dickstein , and Samy Bengio . 2017 . Density estimation using Real NVP . In Proceedings of the 5th International Conference on Learning Representations (ICLR). Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. 2017. Density estimation using Real NVP. In Proceedings of the 5th International Conference on Learning Representations (ICLR)."},{"key":"e_1_2_1_11_1","unstructured":"Wikimedia downloads. 2013. http:\/\/dumps.wikimedia.org.  Wikimedia downloads. 2013. http:\/\/dumps.wikimedia.org."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3464509.3464891"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2021.04.015"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC)","volume":"212","author":"Ferragina Paolo","year":"2021","unstructured":"Paolo Ferragina , Giovanni Manzini , and Giorgio Vinciguerra . 2021 . Repetition-and Linearity-Aware Rank\/Select Dictionaries . In Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC) , Vol. 212 . 64:1--64:16. Paolo Ferragina, Giovanni Manzini, and Giorgio Vinciguerra. 2021. Repetition-and Linearity-Aware Rank\/Select Dictionaries. In Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC), Vol. 212. 64:1--64:16."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-43883-8_2"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389135"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319860"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2168651.2168654"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732279.2732280"},{"key":"e_1_2_1_20_1","volume-title":"Neural Autoregressive Flows. In Proceedings of the 35th International Conference on Machine Learning (ICML)","volume":"80","author":"Huang Chin-Wei","year":"2083","unstructured":"Chin-Wei Huang , David Krueger , Alexandre Lacoste , and Aaron C. Courville . 2018 . Neural Autoregressive Flows. In Proceedings of the 35th International Conference on Machine Learning (ICML) , Vol. 80 . 2083 --2092. Chin-Wei Huang, David Krueger, Alexandre Lacoste, and Aaron C. Courville. 2018. Neural Autoregressive Flows. In Proceedings of the 35th International Conference on Machine Learning (ICML), Vol. 80. 2083--2092."},{"key":"e_1_2_1_21_1","volume-title":"Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018 (NeurIPS). 10236--10245","author":"Diederik","unstructured":"Diederik P. Kingma and Prafulla Dhariwal. 2018. Glow: Generative Flow with Invertible 1\u00d71 Convolutions . In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018 (NeurIPS). 10236--10245 . Diederik P. Kingma and Prafulla Dhariwal. 2018. Glow: Generative Flow with Invertible 1\u00d71 Convolutions. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018 (NeurIPS). 10236--10245."},{"key":"e_1_2_1_22_1","first-page":"4743","article-title":"Improved variational inference with inverse autoregressive flow","volume":"29","author":"Kingma Durk P.","year":"2016","unstructured":"Durk P. Kingma , Tim Salimans , Rafal Jozefowicz , Xi Chen , Ilya Sutskever , and Max Welling . 2016 . Improved variational inference with inverse autoregressive flow . Advances in Neural Information Processing Systems 29 (2016), 4743 -- 4751 . Durk P. Kingma, Tim Salimans, Rafal Jozefowicz, Xi Chen, Ilya Sutskever, and Max Welling. 2016. Improved variational inference with inverse autoregressive flow. Advances in Neural Information Processing Systems 29 (2016), 4743--4751.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 2nd International Conference on Learning Representations (ICLR).","author":"Diederik","unstructured":"Diederik P. Kingma and Max Welling. 2014. Auto-Encoding Variational Bayes . In Proceedings of the 2nd International Conference on Learning Representations (ICLR). Diederik P. Kingma and Max Welling. 2014. Auto-Encoding Variational Bayes. In Proceedings of the 2nd International Conference on Learning Representations (ICLR)."},{"key":"e_1_2_1_24_1","volume-title":"SOSD: A Benchmark for Learned Indexes. CoRR","author":"Kipf Andreas","year":"2019","unstructured":"Andreas Kipf , Ryan Marcus , Alexander van Renen , Mihail Stoian , Alfons Kemper , Tim Kraska , and Thomas Neumann . 2019 . SOSD: A Benchmark for Learned Indexes. CoRR (2019). Andreas Kipf, Ryan Marcus, Alexander van Renen, Mihail Stoian, Alfons Kemper, Tim Kraska, and Thomas Neumann. 2019. SOSD: A Benchmark for Learned Indexes. CoRR (2019)."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3401071.3401659"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389703"},{"key":"e_1_2_1_28_1","volume-title":"A Pluggable Learned Index Method via Sampling and Gap Insertion. CoRR","author":"Li Yaliang","year":"2021","unstructured":"Yaliang Li , Daoyuan Chen , Bolin Ding , Kai Zeng , and Jingren Zhou . 2021. A Pluggable Learned Index Method via Sampling and Gap Insertion. CoRR ( 2021 ). Yaliang Li, Daoyuan Chen, Bolin Ding, Kai Zeng, and Jingren Zhou. 2021. A Pluggable Learned Index Method via Sampling and Gap Insertion. CoRR (2021)."},{"key":"e_1_2_1_29_1","unstructured":"Intel Math Kernel Library. 2003. https:\/\/www.intel.com\/content\/www\/us\/en\/developer\/tools\/oneapi\/onemkl.html.  Intel Math Kernel Library. 2003. https:\/\/www.intel.com\/content\/www\/us\/en\/developer\/tools\/oneapi\/onemkl.html."},{"key":"e_1_2_1_30_1","unstructured":"The C++ B-Tree library implemented by Google. 2011. https:\/\/code.google.com\/archive\/p\/cpp-btree.  The C++ B-Tree library implemented by Google. 2011. https:\/\/code.google.com\/archive\/p\/cpp-btree."},{"key":"e_1_2_1_31_1","volume-title":"Umar Farooq Minhas, and Tianzheng Wang","author":"Lu Baotong","year":"2021","unstructured":"Baotong Lu , Jialin Ding , Eric Lo , Umar Farooq Minhas, and Tianzheng Wang . 2021 . APEX : A High-Performance Learned Index on Persistent Memory. CoRR ( 2021). Baotong Lu, Jialin Ding, Eric Lo, Umar Farooq Minhas, and Tianzheng Wang. 2021. APEX: A High-Performance Learned Index on Persistent Memory. CoRR (2021)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0475-4"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035959"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380579"},{"key":"e_1_2_1_35_1","unstructured":"OpenStreetMap on Amazon AWS. 2018. https:\/\/registry.opendata.aws\/osm\/.  OpenStreetMap on Amazon AWS. 2018. https:\/\/registry.opendata.aws\/osm\/."},{"key":"e_1_2_1_36_1","volume-title":"Masked Autoregressive Flow for Density Estimation. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017 (NeurIPS). 2338--2347","author":"Papamakarios George","year":"2017","unstructured":"George Papamakarios , Iain Murray , and Theo Pavlakou . 2017 . Masked Autoregressive Flow for Density Estimation. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017 (NeurIPS). 2338--2347 . George Papamakarios, Iain Murray, and Theo Pavlakou. 2017. Masked Autoregressive Flow for Density Estimation. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017 (NeurIPS). 2338--2347."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229866"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 32nd International Conference on Machine Learning (ICML)","volume":"37","author":"Rezende Danilo Jimenez","year":"2015","unstructured":"Danilo Jimenez Rezende and Shakir Mohamed . 2015 . Variational Inference with Normalizing Flows . In Proceedings of the 32nd International Conference on Machine Learning (ICML) , Vol. 37 . 1530--1538. Danilo Jimenez Rezende and Shakir Mohamed. 2015. Variational Inference with Normalizing Flows. In Proceedings of the 32nd International Conference on Machine Learning (ICML), Vol. 37. 1530--1538."},{"key":"e_1_2_1_39_1","unstructured":"Amazon sales rank data for print and kindle books. 2018. https:\/\/www.kaggle.com\/ucffool\/amazon-sales-rank-data-for-print-and-kindle-books.  Amazon sales rank data for print and kindle books. 2018. https:\/\/www.kaggle.com\/ucffool\/amazon-sales-rank-data-for-print-and-kindle-books."},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 2019 International Conference on Management of Data (SIGMOD). 36--53","author":"Sandt Peter Van","unstructured":"Peter Van Sandt , Yannis Chronis , and Jignesh M. Patel . 2019. Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search? . In Proceedings of the 2019 International Conference on Management of Data (SIGMOD). 36--53 . Peter Van Sandt, Yannis Chronis, and Jignesh M. Patel. 2019. Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search?. In Proceedings of the 2019 International Conference on Management of Data (SIGMOD). 36--53."},{"key":"e_1_2_1_41_1","volume-title":"PLEX: Towards Practical Learned Indexing. CoRR","author":"Stoian Mihail","year":"2021","unstructured":"Mihail Stoian , Andreas Kipf , Ryan Marcus , and Tim Kraska . 2021 . PLEX: Towards Practical Learned Indexing. CoRR (2021). Mihail Stoian, Andreas Kipf, Ryan Marcus, and Tim Kraska. 2021. PLEX: Towards Practical Learned Indexing. CoRR (2021)."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3332466.3374547"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2019.00121"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3409963.3410496"},{"key":"e_1_2_1_45_1","volume-title":"DeFlow: Learning Complex Image Degradations From Unpaired Data With Conditional Flows. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 94--103","author":"Wolf Valentin","year":"2021","unstructured":"Valentin Wolf , Andreas Lugmayr , Martin Danelljan , Luc Van Gool , and Radu Timofte . 2021 . DeFlow: Learning Complex Image Degradations From Unpaired Data With Conditional Flows. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 94--103 . Valentin Wolf, Andreas Lugmayr, Martin Danelljan, Luc Van Gool, and Radu Timofte. 2021. DeFlow: Learning Complex Image Degradations From Unpaired Data With Conditional Flows. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 94--103."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3457390.3457393"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3547305.3547322","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:16:36Z","timestamp":1672226196000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3547305.3547322"}},"subtitle":["robust learned index via distribution transformation"],"short-title":[],"issued":{"date-parts":[[2022,6]]},"references-count":46,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["10.14778\/3547305.3547322"],"URL":"https:\/\/doi.org\/10.14778\/3547305.3547322","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,6]]}}}