{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,23]],"date-time":"2025-12-23T10:41:44Z","timestamp":1766486504024,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,5,6]],"date-time":"2022-05-06T00:00:00Z","timestamp":1651795200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,5,6]],"date-time":"2022-05-06T00:00:00Z","timestamp":1651795200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004731","name":"Natural Science Foundation of Zhejiang Province","doi-asserted-by":"publisher","award":["2021C01109"],"award-info":[{"award-number":["2021C01109"]}],"id":[{"id":"10.13039\/501100004731","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Sci. Eng."],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Thanks to the rapid advances in artificial intelligence, a brand new venue for database performance optimization is through deep neural networks and the reinforcement learning paradigm. Alongside the long literature in this regime, an iconic and crucial problem is the index structure building. For this problem, the prior works have largely adopted a pure learning-based solution replacing the traditional methods such as a B-tree and Hashing. While this line of research has drawn much attention in the field, they ubiquitously abandon the semantic guarantees and also suffer from performance loss in certain scenarios. In this work, we propose the Neural Index Search (NIS) framework. The core to this framework is to train a search policy to find a near optimal combination plan over the existing index structures, together with the required configuration parameters associated with each index structure in the plan. We argue that compared against the pure learning approaches, NIS enjoys the advantages brought by the chosen conventional index structures and further robustly enhances the performance from any singular index structure. Extensive empirical results demonstrate that our framework achieves state-of-the-art performances on several benchmarks.<\/jats:p>","DOI":"10.1007\/s41019-022-00186-4","type":"journal-article","created":{"date-parts":[[2022,5,6]],"date-time":"2022-05-06T21:12:35Z","timestamp":1651871555000},"page":"87-101","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["Dynamic Index Construction with Deep Reinforcement Learning"],"prefix":"10.1007","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1866-9197","authenticated-orcid":false,"given":"Sai","family":"Wu","sequence":"first","affiliation":[]},{"given":"Ying","family":"Li","sequence":"additional","affiliation":[]},{"given":"Haoqi","family":"Zhu","sequence":"additional","affiliation":[]},{"given":"Junbo","family":"Zhao","sequence":"additional","affiliation":[]},{"given":"Gang","family":"Chen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,6]]},"reference":[{"key":"186_CR1","unstructured":"Zhang C, Zhang Y, Zhang W, Lin X (2013) Inverted linear quadtree: efficient top k spatial keyword search. In: 29th IEEE Int Conf Data Eng, pp 901\u2013912"},{"issue":"1","key":"186_CR2","first-page":"337","volume":"2","author":"G Cong","year":"2009","unstructured":"Cong G, Jensen CS, Wu D (2009) Efficient retrieval top-k most relevant spatial web objects. PVLDB 2(1):337\u2013348","journal-title":"PVLDB"},{"key":"186_CR3","doi-asserted-by":"crossref","unstructured":"Wang X, Zhang Y, Zhang W, Lin X, Wang W (2015) Ap-tree: efficiently support continuous spatial-keyword queries over stream. In: 31st IEEE Int Conf Data Eng, pp 1107\u20131118","DOI":"10.1109\/ICDE.2015.7113360"},{"key":"186_CR4","unstructured":"O\u2019Donoghue B, Munos R, Kavukcuoglu K, Mnih V (2017) Combining policy gradient and q-learning. In: 5th Int Conf Learn Representations"},{"key":"186_CR5","doi-asserted-by":"crossref","unstructured":"Kraska T, Beutel A, Chi EH, Dean J, Polyzotis N (2018) The case for learned index structures. In: Proc 2018 Int Conf Manag of Data, pp 489\u2013504","DOI":"10.1145\/3183713.3196909"},{"key":"186_CR6","unstructured":"Zoph B, Le QV (2017) Neural architecture search with reinforcement learn. In: 5th Int Conf Learn Representations"},{"issue":"8","key":"186_CR7","doi-asserted-by":"publisher","first-page":"1735","DOI":"10.1162\/neco.1997.9.8.1735","volume":"9","author":"S Hochreiter","year":"1997","unstructured":"Hochreiter S, Schmidhuber J (1997) Long short-term memory. Neural Comput 9(8):1735\u20131780","journal-title":"Neural Comput"},{"key":"186_CR8","unstructured":"Schulman J, Wolski F, Dhariwal P, Radford A, Klimov O (2017) Proximal policy optimization algorithms, CoRR, vol. abs\/1707.06347"},{"key":"186_CR9","doi-asserted-by":"crossref","unstructured":"Tai KS, Socher R, Manning CD (2015) Improved semantic representations from tree-structured long short-term memory networks. In: Proc 53rd Ann Meeting Assoc for Comput Linguistics and the 7th Int Joint Conf Natural Lang. Process. Asian Federation of Natural Lang. Process., pp 1556\u20131566","DOI":"10.3115\/v1\/P15-1150"},{"key":"186_CR10","doi-asserted-by":"crossref","unstructured":"Kipf A, Marcus R, van Renen A, Stoian M, Kemper A, Kraska T, Neumann T (2019) Sosd: a benchmark for learned indexes. NeurIPS Workshop Mach Learn for Syst","DOI":"10.14778\/3421424.3421425"},{"key":"186_CR11","doi-asserted-by":"crossref","unstructured":"Leis V, Kemper A, Neumann T (2013) The adaptive radix tree: artful indexing for main-memory databases. In: 29th IEEE Int Conf Data Eng, pp 38\u201349","DOI":"10.1109\/ICDE.2013.6544812"},{"key":"186_CR12","doi-asserted-by":"crossref","unstructured":"Kim C, Chhugani J, Satish N, Sedlar E, Nguyen AD, Kaldewey T, Lee VW, Brandt SA, Dubey P (2010) FAST: fast architecture sensitive tree search modern cpus and gpus. In: Proc ACM SIGMOD Int Conf Manag of Data, pp 339\u2013350","DOI":"10.1145\/1807167.1807206"},{"key":"186_CR13","doi-asserted-by":"crossref","unstructured":"Wang Z, Pavlo A, Lim H, Leis V, Zhang H, Kaminsky M, Andersen DG (2018) Building a bw-tree takes more than just buzz words. In: Proc 2018 Int Conf Manag of Data, pp 473\u2013488","DOI":"10.1145\/3183713.3196895"},{"issue":"8","key":"186_CR14","doi-asserted-by":"publisher","first-page":"1162","DOI":"10.14778\/3389133.3389135","volume":"13","author":"P Ferragina","year":"2020","unstructured":"Ferragina P, Vinciguerra G (2020) The pgm-index: a fully-dynamic compressed learned index with provable worst-case bounds. Proc VLDB Endow 13(8):1162\u20131175","journal-title":"Proc VLDB Endow"},{"key":"186_CR15","unstructured":"Pavlo A, Angulo G, Arulraj J, Lin H, Lin J, Ma L, Menon P, Mowry T, Perron M, Quah I, Santurkar S, Tomasic A, Toor S, Aken DV, Wang Z, Wu Y, Xian R, Zhang T (2017) Self-driving database management systems. In: Conf Innov Data Syst, Research"},{"issue":"12","key":"186_CR16","first-page":"1910","volume":"11","author":"B Zhang","year":"2018","unstructured":"Zhang B, Aken DV, Wang J, Dai T, Jiang S, Lao J, Sheng S, Pavlo A, Gordon GJ (2018) A demonstration ottertune automatic database manag. System tuning service. PVLDB 11(12):1910\u20131913","journal-title":"PVLDB"},{"key":"186_CR17","unstructured":"Pavlo A, Butrovich M, Joshi A, Ma L, Menon P, Aken DV, Lee L, Salakhutdinov R (2019) External vs. internal: an essay machine learning agents for autonomous database management systems. IEEE Data Eng Bull, pp 32\u201346"},{"key":"186_CR18","doi-asserted-by":"crossref","unstructured":"Zhang J, Liu Y, Zhou K, Li G, Xiao Z, Cheng B, Xing J, Wang Y, Cheng T, Liu L, Ran M, Li Z (2019) An end-to-end automatic cloud database tuning system using deep reinforcement learning. In: Proc 2019 Int Conf Manag of Data, pp 415\u2013432","DOI":"10.1145\/3299869.3300085"},{"issue":"12","key":"186_CR19","first-page":"2118","volume":"12","author":"G Li","year":"2019","unstructured":"Li G, Zhou X, Li S, Gao B (2019) Qtune: a query-aware database tuning system with deep reinforcement learning. PVLDB 12(12):2118\u20132130","journal-title":"PVLDB"},{"key":"186_CR20","unstructured":"Krishnan S, Yang Z, Goldberg K, Hellerstein JM, Stoica I (2018) Learning to optimize join queries with deep reinforcement learning, CoRR, vol. abs\/1808.03196"},{"key":"186_CR21","doi-asserted-by":"crossref","unstructured":"Yu X, Li G, Chai C, Tang N (2020) Reinforcement learning with tree-lstm for join order selection. In: 36th IEEE Int Conf Data Eng, IEEE pp 1297\u20131308","DOI":"10.1109\/ICDE48307.2020.00116"},{"key":"186_CR22","doi-asserted-by":"crossref","unstructured":"Trummer I, Wang J, Maram D, Moseley S, Jo S, Antonakakis J (2019) Skinnerdb: regret-bounded query evaluation via reinforcement learning. In: Proc 2019 Int Conf Manag of Data, pp 1153\u20131170","DOI":"10.1145\/3299869.3300088"},{"issue":"11","key":"186_CR23","first-page":"1705","volume":"12","author":"RC Marcus","year":"2019","unstructured":"Marcus RC, Negi P, Mao H, Zhang C, Alizadeh M, Kraska T, Papaemmanouil O, Tatbul N (2019) Neo: a learned query optimizer. PVLDB 12(11):1705\u20131718","journal-title":"PVLDB"},{"key":"186_CR24","doi-asserted-by":"crossref","unstructured":"Woltmann L, Hartmann C, Thiele M, Habich D, Lehner W (2019) Cardinality estimation with local deep learning models. In: Proc Second Int Workshop Exploiting Artif Intell Techn for Data Manag, pp 5:1\u20135:8","DOI":"10.1145\/3329859.3329875"},{"key":"186_CR25","unstructured":"Yang Z, Liang E, Kamsetty A, Wu C, Duan Y, Chen X, Abbeel P, Hellerstein JM, Krishnan S, Stoica I (2019) Selectivity estimation with deep likelihood models. CoRR, vol abs\/1905.04278"},{"issue":"3","key":"186_CR26","doi-asserted-by":"publisher","first-page":"307","DOI":"10.14778\/3368289.3368296","volume":"13","author":"J Sun","year":"2019","unstructured":"Sun J, Li G (2019) An end-to-end learning-based cost estimator. Proc VLDB Endow 13(3):307\u2013319","journal-title":"Proc VLDB Endow"},{"key":"186_CR27","unstructured":"Kipf A, Kipf T, Radke B, Leis V, Boncz PA, Kemper A (2019) Learned cardinalities: estimating correlated joins with deep learning. In: 9th Biennial Conf Innovative Data Syst, Research"},{"key":"186_CR28","unstructured":"Kraska T, Alizadeh M, Beutel A, Chi EH, Kristo A, Leclerc G, Madden S, Mao H, Nathan V (2019) Sagedb: a learned database system. In: 9th Biennial Conf Innovative Data Syst, Research"},{"key":"186_CR29","doi-asserted-by":"crossref","unstructured":"Marcus R, Zhang E, Kraska T (2020) Cdfshop: exploring and optimizing learned index structures. In: Proc 2020 Int Conf Manag of Data. ACM, pp 2789\u20132792","DOI":"10.1145\/3318464.3384706"},{"key":"186_CR30","doi-asserted-by":"crossref","unstructured":"Galakatos A, Markovitch M, Binnig C, Fonseca R, Kraska T (2019) Fiting-tree: a data-aware index structure. In: Proc 2019 Int Conf Manag of Data. ACM, pp 1189\u20131206","DOI":"10.1145\/3299869.3319860"},{"key":"186_CR31","doi-asserted-by":"crossref","unstructured":"Ding J, Minhas UF, Yu J, Wang C, Do J, Li Y, Zhang H, Chandramouli B, Gehrke J, Kossmann D, Lomet DB, Kraska T (2020) ALEX: an updatable adaptive learned index. In: Proc 2020 Int Conf Manag of Data. ACM, pp 969\u2013984","DOI":"10.1145\/3318464.3389711"},{"key":"186_CR32","doi-asserted-by":"crossref","unstructured":"Kipf A, Marcus R, van Renen A, Stoian M, Kemper A, Kraska T, Neumann T (2020) Radixspline: a single-pass learned index. In: Proc Third Int Workshop Exploiting Artif Intell Techn for Data Manag. ACM, pp 5:1\u20135:5","DOI":"10.1145\/3401071.3401659"},{"key":"186_CR33","doi-asserted-by":"crossref","unstructured":"Lan H, Bao Z, Peng Y (2020) An index advisor using deep reinforcement learning,\u201d in CIKM \u201920: the 29th ACM International conference on information and knowledge management, virtual event, Ireland, d\u2019Aquin M, Dietze S, Hauff C, Curry E, Cudr\u00e9-Mauroux P, Eds. ACM, 2020, pp 2105\u20132108. [Online]. Available: https:\/\/doi.org\/10.1145\/3340531.3412106","DOI":"10.1145\/3340531.3412106"}],"container-title":["Data Science and Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-022-00186-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41019-022-00186-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-022-00186-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,12]],"date-time":"2022-05-12T17:11:10Z","timestamp":1652375470000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41019-022-00186-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,6]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["186"],"URL":"https:\/\/doi.org\/10.1007\/s41019-022-00186-4","relation":{},"ISSN":["2364-1185","2364-1541"],"issn-type":[{"type":"print","value":"2364-1185"},{"type":"electronic","value":"2364-1541"}],"subject":[],"published":{"date-parts":[[2022,5,6]]},"assertion":[{"value":"23 February 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 March 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 April 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 May 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}