{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:20:03Z","timestamp":1750220403683,"version":"3.41.0"},"reference-count":77,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,9,20]],"date-time":"2021-09-20T00:00:00Z","timestamp":1632096000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF\u00a0805476, CCF\u00a0822388, CNS 1408695, CNS 1755615, CCF 2106827, CCF 2118832, CCF 1439084, CCF 1725543, CSR 1763680, CCF 1716252, CCF 1617618, IIS 1247726, CNS 1938709, and CNS 1938180"],"award-info":[{"award-number":["CCF\u00a0805476, CCF\u00a0822388, CNS 1408695, CNS 1755615, CCF 2106827, CCF 2118832, CCF 1439084, CCF 1725543, CSR 1763680, CCF 1716252, CCF 1617618, IIS 1247726, CNS 1938709, and CNS 1938180"]}]},{"DOI":"10.13039\/100006234","name":"Sandia National Laboratories","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006234","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100016682","name":"VMware","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100016682","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Netapp Faculty Fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2021,9,30]]},"abstract":"<jats:p>Storage devices have complex performance profiles, including costs to initiate IOs (e.g., seek times in hard drives), parallelism and bank conflicts (in SSDs), costs to transfer data, and firmware-internal operations.<\/jats:p>\n          <jats:p>\n            The Disk-access Machine (DAM) model simplifies reality by assuming that storage devices transfer data in blocks of size\n            <jats:italic>B<\/jats:italic>\n            and that all transfers have unit cost. Despite its simplifications, the DAM model is reasonably accurate. In fact, if\n            <jats:italic>B<\/jats:italic>\n            is set to the half-bandwidth point, where the latency and bandwidth of the hardware are equal, then the DAM approximates the IO cost on any hardware to within a factor of\u00a02.\n          <\/jats:p>\n          <jats:p>\n            Furthermore, the DAM model explains the popularity of B-trees in the 1970s and the current popularity of B\n            <jats:sup>\u025b<\/jats:sup>\n            -trees and log-structured merge trees. But it fails to explain why some B-trees use small nodes, whereas all B\n            <jats:sup>\u025b<\/jats:sup>\n            -trees use large nodes. In a DAM, all IOs, and hence all nodes, are the same size.\n          <\/jats:p>\n          <jats:p>In this article, we show that the affine and PDAM models, which are small refinements of the DAM model, yield a surprisingly large improvement in predictability without sacrificing ease of use. We present benchmarks on a large collection of storage devices showing that the affine and PDAM models give good approximations of the performance characteristics of hard drives and SSDs, respectively.<\/jats:p>\n          <jats:p>\n            We show that the affine model explains node-size choices in B-trees and B\n            <jats:sup>\u025b<\/jats:sup>\n            -trees. Furthermore, the models predict that B-trees are highly sensitive to variations in the node size, whereas B\n            <jats:sup>\u025b<\/jats:sup>\n            -trees are much less sensitive. These predictions are born out empirically.\n          <\/jats:p>\n          <jats:p>\n            Finally, we show that in both the affine and PDAM models, it pays to organize data structures to exploit varying IO size. In the affine model, B\n            <jats:sup>\u025b<\/jats:sup>\n            -trees can be optimized so that all operations are simultaneously optimal, even up to lower-order terms. In the PDAM model, B\n            <jats:sup>\u025b<\/jats:sup>\n            -trees (or B-trees) can be organized so that both sequential and concurrent workloads are handled efficiently.\n          <\/jats:p>\n          <jats:p>We conclude that the DAM model is useful as a first cut when designing or analyzing an algorithm or data structure but the affine and PDAM models enable the algorithm designer to optimize parameter choices and fill in design details.<\/jats:p>","DOI":"10.1145\/3470635","type":"journal-article","created":{"date-parts":[[2021,9,20]],"date-time":"2021-09-20T18:27:58Z","timestamp":1632162478000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["External-memory Dictionaries in the Affine and PDAM Models"],"prefix":"10.1145","volume":"8","author":[{"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[{"name":"Stony Brook University, Stony Brook, NY"}]},{"given":"Alex","family":"Conway","sequence":"additional","affiliation":[{"name":"VMware Research, Palo Alto, USA"}]},{"given":"Mart\u00edn","family":"Farach-Colton","sequence":"additional","affiliation":[{"name":"Rutgers University, Piscataway, NJ USA"}]},{"given":"William","family":"Jannen","sequence":"additional","affiliation":[{"name":"Williams College, Williamstown, USA"}]},{"given":"Yizheng","family":"Jiao","sequence":"additional","affiliation":[{"name":"The University of North Carolina at Chapel Hill, Chapel Hill, USA"}]},{"given":"Rob","family":"Johnson","sequence":"additional","affiliation":[{"name":"VMware Research, Palo Alto, USA"}]},{"given":"Eric","family":"Knorr","sequence":"additional","affiliation":[{"name":"Harvard University, Boston, USA"}]},{"given":"Sara","family":"Mcallister","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Forbes Avenue, Pittsburgh, USA"}]},{"given":"Nirjhar","family":"Mukherjee","sequence":"additional","affiliation":[{"name":"The University of North Carolina at Chapel Hill"}]},{"given":"Prashant","family":"Pandey","sequence":"additional","affiliation":[{"name":"Lawrence Berkeley National Laboratory and University of California Berkeley, Berkeley, USA"}]},{"given":"Donald E.","family":"Porter","sequence":"additional","affiliation":[{"name":"The University of North Carolina at Chapel Hill, Chapel Hill, USA"}]},{"given":"Jun","family":"Yuan","sequence":"additional","affiliation":[{"name":"Pace University, New York, USA"}]},{"given":"Yang","family":"Zhan","sequence":"additional","affiliation":[{"name":"The University of North Carolina at Chapel Hill, Chapel Hill, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,9,20]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"mkfs.btrfs. [n.d.]. Manual page. Retrieved from https:\/\/btrfs.wiki.kernel.org\/index.php\/Manpage\/mkfs.btrfs.  mkfs.btrfs. [n.d.]. Manual page. Retrieved from https:\/\/btrfs.wiki.kernel.org\/index.php\/Manpage\/mkfs.btrfs."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0071-1"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the EEF Summer School on Massive Data Sets.","author":"Arge Lars","year":"2002","unstructured":"Lars Arge . 2002 . External-memory geometric data structures . In Proceedings of the EEF Summer School on Massive Data Sets. Lars Arge. 2002. External-memory geometric data structures. In Proceedings of the EEF Summer School on Massive Data Sets."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378573"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2010.5470440"},{"key":"e_1_2_1_7_1","unstructured":"Microsoft Azure. 2016. How to Use Batching to Improve SQL Database Application Performance. Retrieved from https:\/\/docs.microsoft.com\/en-us\/azure\/sql-database\/sql-database-use-batching-to-improve-performance.  Microsoft Azure. 2016. How to Use Batching to Improve SQL Database Application Performance. Retrieved from https:\/\/docs.microsoft.com\/en-us\/azure\/sql-database\/sql-database-use-batching-to-improve-performance."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288683"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935767"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902276"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.155"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323210"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.40"},{"key":"e_1_2_1_14_1","first-page":"341","article-title":"Cache-Oblivious B-Trees","volume":"35","author":"Bender Michael A.","year":"2005","unstructured":"Michael A. Bender , Erik Demaine , and Martin Farach-Colton . 2005 . Cache-Oblivious B-Trees . Journal on Computing 35 , 2 (2005), 341 \u2013 358 . Michael A. Bender, Erik Demaine, and Martin Farach-Colton. 2005. Cache-Oblivious B-Trees. Journal on Computing 35, 2 (2005), 341\u2013358.","journal-title":"Journal on Computing"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248393"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00026"},{"key":"e_1_2_1_17_1","volume-title":"An introduction to B-trees and write-optimization. :login","author":"Bender Michael A.","year":"2015","unstructured":"Michael A. Bender , Martin Farach-Colton , William Jannen , Rob Johnson , Bradley C. Kuszmaul , Donald E. Porter , Jun Yuan , and Yang Zhan . 2015. An introduction to B-trees and write-optimization. :login ; Mag . 40, 5 ( Oct. 2015 ), 22\u201328. Michael A. Bender, Martin Farach-Colton, William Jannen, Rob Johnson, Bradley C. Kuszmaul, Donald E. Porter, Jun Yuan, and Yang Zhan. 2015. An introduction to B-trees and write-optimization. :login; Mag. 40, 5 (Oct. 2015), 22\u201328."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350275"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056117"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142385"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316342"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916)","author":"Blelloch Guy E.","year":"2016","unstructured":"Guy E. Blelloch , Jeremy T. Fineman , Phillip B. Gibbons , Yan Gu , and Julian Shun . 2016 . Efficient algorithms with asymmetric read and write costs . In Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916) . 14:1\u201314:18. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2016.0 10.4230\/LIPIcs.ESA.2016.0 Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, and Julian Shun. 2016. Efficient algorithms with asymmetric read and write costs. In Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916). 14:1\u201314:18. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2016.0"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210381"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810479.1810519"},{"volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910)","author":"Brodal Gerth S.","key":"e_1_2_1_25_1","unstructured":"Gerth S. Brodal , Erik D. Demaine , Jeremy T. Fineman , John Iacono , Stefan Langerman , and J. Ian Munro . 2010. Cache-oblivious dynamic dictionaries with update\/query tradeoffs . In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910) . 1448\u20131456. Gerth S. Brodal, Erik D. Demaine, Jeremy T. Fineman, John Iacono, Stefan Langerman, and J. Ian Munro. 2010. Cache-oblivious dynamic dictionaries with update\/query tradeoffs. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910). 1448\u20131456."},{"key":"e_1_2_1_26_1","volume-title":"Brodal and Rolf Fagerberg","author":"Gerth","year":"2003","unstructured":"Gerth S. Brodal and Rolf Fagerberg . 2003 . Lower bounds for external-memory dictionaries. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903). 546\u2013554. Gerth S. Brodal and Rolf Fagerberg. 2003. Lower bounds for external-memory dictionaries. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903). 546\u2013554."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900)","author":"Buchsbaum Adam L.","year":"2000","unstructured":"Adam L. Buchsbaum , Michael H. Goldwasser , Suresh Venkatasubramanian , and Jeffery Westbrook . 2000 . On external-memory graph traversal . In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900) . 859\u2013860. Adam L. Buchsbaum, Michael H. Goldwasser, Suresh Venkatasubramanian, and Jeffery Westbrook. 2000. On external-memory graph traversal. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900). 859\u2013860."},{"key":"e_1_2_1_28_1","unstructured":"Mark Callaghan. 2011. Something Awesome in InnoDB\u2014The Insert Buffer. Retrieved from https:\/\/www.facebook.com\/notes\/mysql-at-facebook\/something-awesome-in-innodb-the-insert-buffer\/492969385932\/.  Mark Callaghan. 2011. Something Awesome in InnoDB\u2014The Insert Buffer. Retrieved from https:\/\/www.facebook.com\/notes\/mysql-at-facebook\/something-awesome-in-innodb-the-insert-buffer\/492969385932\/."},{"volume-title":"Proceedings of the International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures (ADMS\u201910)","author":"Canim Mustafa","key":"e_1_2_1_29_1","unstructured":"Mustafa Canim , Christian A. Lang , George A. Mihaila , and Kenneth A. Ross . 2010. Buffered Bloom filters on solid state storage . In Proceedings of the International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures (ADMS\u201910) . Mustafa Canim, Christian A. Lang, George A. Mihaila, and Kenneth A. Ross. 2010. Buffered Bloom filters on solid state storage. In Proceedings of the International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures (ADMS\u201910)."},{"key":"e_1_2_1_30_1","article-title":"Internal parallelism of flash memory-based solid-state drives","volume":"12","author":"Chen Feng","year":"2016","unstructured":"Feng Chen , Binbing Hou , and Rubao Lee . 2016 . Internal parallelism of flash memory-based solid-state drives . Trans. Stor. 12 , 3, Article 13 (May 2016), 39 pages. DOI:https:\/\/doi.org\/10.1145\/2818376 10.1145\/2818376 Feng Chen, Binbing Hou, and Rubao Lee. 2016. Internal parallelism of flash memory-based solid-state drives. Trans. Stor. 12, 3, Article 13 (May 2016), 39 pages. DOI:https:\/\/doi.org\/10.1145\/2818376","journal-title":"Trans. Stor."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564710"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2013.04.008"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"volume-title":"File systems fated for senescence? Nonsense, says science! In Proceedings of the 15th USENIX Conference on File and Storage Technologies (FAST\u201917). 45\u201358","author":"Conway Alexander","key":"e_1_2_1_34_1","unstructured":"Alexander Conway , Ainesh Bakshi , Yizheng Jiao , William Jannen , Yang Zhan , Jun Yuan , Michael A. Bender , Rob Johnson , Bradley C. Kuszmaul , Donald E. Porter , and Martin Farach-Colton . 2017. File systems fated for senescence? Nonsense, says science! In Proceedings of the 15th USENIX Conference on File and Storage Technologies (FAST\u201917). 45\u201358 . Alexander Conway, Ainesh Bakshi, Yizheng Jiao, William Jannen, Yang Zhan, Jun Yuan, Michael A. Bender, Rob Johnson, Bradley C. Kuszmaul, Donald E. Porter, and Martin Farach-Colton. 2017. File systems fated for senescence? Nonsense, says science! In Proceedings of the 15th USENIX Conference on File and Storage Technologies (FAST\u201917). 45\u201358."},{"key":"e_1_2_1_35_1","volume-title":"How to fragment your file system. login: 42, 2","author":"Conway Alex","year":"2017","unstructured":"Alex Conway , Ainesh Bakshi , Yizheng Jiao , Yang Zhan , Michael A. Bender , William Jannen , Rob Johnson , Bradley C. Kuszmaul , Donald E. Porter , Jun Yuan , and Martin Farach-Colton . 2017. How to fragment your file system. login: 42, 2 ( 2017 ). Retrieved from https:\/\/www.usenix.org\/publications\/login\/summer2017\/conway. Alex Conway, Ainesh Bakshi, Yizheng Jiao, Yang Zhan, Michael A. Bender, William Jannen, Rob Johnson, Bradley C. Kuszmaul, Donald E. Porter, Jun Yuan, and Martin Farach-Colton. 2017. How to fragment your file system. login: 42, 2 (2017). Retrieved from https:\/\/www.usenix.org\/publications\/login\/summer2017\/conway."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP\u201918)","author":"Conway Alexander","year":"2018","unstructured":"Alexander Conway , Martin Farach-Colton , and Philip Shilane . 2018 . Optimal hashing in external memory . In Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP\u201918) . 39:1\u201339:14. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.39 10.4230\/LIPIcs.ICALP.2018.39 Alexander Conway, Martin Farach-Colton, and Philip Shilane. 2018. Optimal hashing in external memory. In Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP\u201918). 39:1\u201339:14. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.39"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 11th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage\u201919)","author":"Conway Alex","year":"2019","unstructured":"Alex Conway , Eric Knorr , Yizheng Jiao , Michael A. Bender , William Jannen , Rob Johnson , Donald E. Porter , and Martin Farach-Colton . 2019 . Filesystem aging: It\u2019s more usage than fullness . In Proceedings of the 11th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage\u201919) . Alex Conway, Eric Knorr, Yizheng Jiao, Michael A. Bender, William Jannen, Rob Johnson, Donald E. Porter, and Martin Farach-Colton. 2019. Filesystem aging: It\u2019s more usage than fullness. In Proceedings of the 11th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage\u201919)."},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 5th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage\u201913)","author":"Desnoyers Peter","year":"2013","unstructured":"Peter Desnoyers . 2013 . What systems researchers need to know about NAND flash . In Proceedings of the 5th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage\u201913) . Peter Desnoyers. 2013. What systems researchers need to know about NAND flash. In Proceedings of the 5th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage\u201913)."},{"volume-title":"Proceedings of the 4th USENIX Conference on Hot Topics in Storage and File Systems (HotStorage\u201912)","author":"Esmet John","key":"e_1_2_1_39_1","unstructured":"John Esmet , Michael A. Bender , Martin Farach-Colton , and Bradley C. Kuszmaul . 2012. The TokuFS streaming file system . In Proceedings of the 4th USENIX Conference on Hot Topics in Storage and File Systems (HotStorage\u201912) . 14. John Esmet, Michael A. Bender, Martin Farach-Colton, and Bradley C. Kuszmaul. 2012. The TokuFS streaming file system. In Proceedings of the 4th USENIX Conference on Hot Topics in Storage and File Systems (HotStorage\u201912). 14."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2071379.2071383"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2595635"},{"key":"e_1_2_1_42_1","unstructured":"Google Inc.[n.d.]. LevelDB: A Fast and Lightweight Key\/value Database Library By Google. Retrieved from https:\/\/github.com\/google\/leveldb.  Google Inc.[n.d.]. LevelDB: A Fast and Lightweight Key\/value Database Library By Google. Retrieved from https:\/\/github.com\/google\/leveldb."},{"volume-title":"Proceedings of the 12th European Conference on Computer Systems (EuroSys\u201917)","author":"He Jun","key":"e_1_2_1_43_1","unstructured":"Jun He , Sudarsun Kannan , Andrea C. Arpaci-Dusseau , and Remzi H . Arpaci-Dusseau. 2017. The unwritten contract of solid state drives . In Proceedings of the 12th European Conference on Computer Systems (EuroSys\u201917) . 127\u2013144. Jun He, Sudarsun Kannan, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau. 2017. The unwritten contract of solid state drives. In Proceedings of the 12th European Conference on Computer Systems (EuroSys\u201917). 127\u2013144."},{"key":"e_1_2_1_44_1","unstructured":"IBM. 2017. Buffered Inserts in Partitioned Database Environments. Retrieved from https:\/\/www.ibm.com\/support\/knowledgecenter\/SSEPGG_10.5.0\/com.ibm.db2.luw.apdv.embed.doc\/doc\/c0061906.html.  IBM. 2017. Buffered Inserts in Partitioned Database Environments. Retrieved from https:\/\/www.ibm.com\/support\/knowledgecenter\/SSEPGG_10.5.0\/com.ibm.db2.luw.apdv.embed.doc\/doc\/c0061906.html."},{"key":"e_1_2_1_45_1","unstructured":"IBM Informix. [n.d.]. Understanding SQL Insert Cursors. Retrieved from https:\/\/www.ibm.com\/support\/knowledgecenter\/en\/SSBJG3_2.5.0\/com.ibm.gen_busug.doc\/c_fgl_InsertCursors_002.htm.  IBM Informix. [n.d.]. Understanding SQL Insert Cursors. Retrieved from https:\/\/www.ibm.com\/support\/knowledgecenter\/en\/SSBJG3_2.5.0\/com.ibm.gen_busug.doc\/c_fgl_InsertCursors_002.htm."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087583"},{"volume-title":"Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST\u201915)","author":"Jannen William","key":"e_1_2_1_47_1","unstructured":"William Jannen , Jun Yuan , Yang Zhan , Amogh Akshintala , John Esmet , Yizheng Jiao , Ankur Mittal , Prashant Pandey , Phaneendra Reddy , Leif Walsh , Michael A. Bender , Martin Farach-Colton , Rob Johnson , Bradley C. Kuszmaul , and Donald E. Porter . 2015. BetrFS: A right-optimized write-optimized file system . In Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST\u201915) . 301\u2013315. William Jannen, Jun Yuan, Yang Zhan, Amogh Akshintala, John Esmet, Yizheng Jiao, Ankur Mittal, Prashant Pandey, Phaneendra Reddy, Leif Walsh, Michael A. Bender, Martin Farach-Colton, Rob Johnson, Bradley C. Kuszmaul, and Donald E. Porter. 2015. BetrFS: A right-optimized write-optimized file system. In Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST\u201915). 301\u2013315."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/645925.671517"},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the OpenSQL Camp.","author":"Kuszmaul Bradley C.","year":"2009","unstructured":"Bradley C. Kuszmaul . 2009 . How fractal trees work . In Proceedings of the OpenSQL Camp. Bradley C. Kuszmaul. 2009. How fractal trees work. In Proceedings of the OpenSQL Camp."},{"key":"e_1_2_1_50_1","unstructured":"Amanda McPherson. [n.d.]. A Conversation with Chris Mason on Btrfs: The Next Generation File System for Linux. Retrieved from https:\/\/www.linuxfoundation.org\/blog\/2009\/06\/a-conversation-with-chris-mason-on-btrfs\/.  Amanda McPherson. [n.d.]. A Conversation with Chris Mason on Btrfs: The Next Generation File System for Linux. Retrieved from https:\/\/www.linuxfoundation.org\/blog\/2009\/06\/a-conversation-with-chris-mason-on-btrfs\/."},{"key":"e_1_2_1_51_1","unstructured":"MySQL 5.7 Reference Manual. [n.d.]. Chapter 15 The InnoDB Storage Engine. Retrieved from http:\/\/dev.mysql.com\/doc\/refman\/5.7\/en\/innodb-storage-engine.html.  MySQL 5.7 Reference Manual. [n.d.]. Chapter 15 The InnoDB Storage Engine. Retrieved from http:\/\/dev.mysql.com\/doc\/refman\/5.7\/en\/innodb-storage-engine.html."},{"key":"e_1_2_1_52_1","unstructured":"NuDB. 2016. NuDB: A Fast Key\/value Insert-only Database for SSD Drives in C++11. Retrieved from https:\/\/github.com\/vinniefalco\/NuDB.  NuDB. 2016. NuDB: A Fast Key\/value Insert-only Database for SSD Drives in C++11. Retrieved from https:\/\/github.com\/vinniefalco\/NuDB."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_1_54_1","unstructured":"Oracle. 2017. Tuning the Database Buffer Cache. Retrieved from https:\/\/docs.oracle.com\/database\/121\/TGDBA\/tune_buffer_cache.htm.  Oracle. 2017. Tuning the Database Buffer Cache. Retrieved from https:\/\/docs.oracle.com\/database\/121\/TGDBA\/tune_buffer_cache.htm."},{"key":"e_1_2_1_55_1","unstructured":"Oracle Corporation. [n.d.]. MySQL 5.5 Reference Manual. Retrieved from https:\/\/dev.mysql.com\/doc\/refman\/5.5\/en\/innodb-file-space.html.  Oracle Corporation. [n.d.]. MySQL 5.5 Reference Manual. Retrieved from https:\/\/dev.mysql.com\/doc\/refman\/5.5\/en\/innodb-file-space.html."},{"key":"e_1_2_1_56_1","unstructured":"Oracle Corporation.2015. Oracle BerkeleyDB Reference Guide. Retrieved from http:\/\/sepp.oetiker.ch\/subversion-1.5.4-rp\/ref\/am_conf\/pagesize.html.  Oracle Corporation.2015. Oracle BerkeleyDB Reference Guide. Retrieved from http:\/\/sepp.oetiker.ch\/subversion-1.5.4-rp\/ref\/am_conf\/pagesize.html."},{"key":"e_1_2_1_57_1","unstructured":"Oracle Corporation. 2016. Setting Up Your Data Warehouse System. Retrieved from https:\/\/docs.oracle.com\/cd\/B28359_01\/server.111\/b28314\/tdpdw_system.htm.  Oracle Corporation. 2016. Setting Up Your Data Warehouse System. Retrieved from https:\/\/docs.oracle.com\/cd\/B28359_01\/server.111\/b28314\/tdpdw_system.htm."},{"key":"e_1_2_1_58_1","volume-title":"Proceedings of the USENIX Annual Technical Conference (USENIX ATC\u201916)","author":"Papagiannis Anastasios","year":"2016","unstructured":"Anastasios Papagiannis , Giorgos Saloustros , Pilar Gonz\u00e1lez-F\u00e9rez , and Angelos Bilas . 2016 . Tucana: Design and implementation of a fast and efficient scale-up key-value store . In Proceedings of the USENIX Annual Technical Conference (USENIX ATC\u201916) . 537\u2013550. Anastasios Papagiannis, Giorgos Saloustros, Pilar Gonz\u00e1lez-F\u00e9rez, and Angelos Bilas. 2016. Tucana: Design and implementation of a fast and efficient scale-up key-value store. In Proceedings of the USENIX Annual Technical Conference (USENIX ATC\u201916). 537\u2013550."},{"key":"e_1_2_1_59_1","unstructured":"John Paul. [n.d.]. Teradata Thoughts. Retrieved from http:\/\/teradata-thoughts.blogspot.com\/2013\/10\/teradata-13-vs-teradata-14_20.html.  John Paul. [n.d.]. Teradata Thoughts. Retrieved from http:\/\/teradata-thoughts.blogspot.com\/2013\/10\/teradata-13-vs-teradata-14_20.html."},{"volume-title":"Cache-Oblivious Algorithms. Master\u2019s thesis. Department of Electrical Engineering and Computer Science","author":"Prokop Harald","key":"e_1_2_1_60_1","unstructured":"Harald Prokop . 1999. Cache-Oblivious Algorithms. Master\u2019s thesis. Department of Electrical Engineering and Computer Science , Massachusetts Institute of Technology . Harald Prokop. 1999. Cache-Oblivious Algorithms. Master\u2019s thesis. Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132765"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/146941.146943"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.268881"},{"key":"e_1_2_1_64_1","unstructured":"SAP. 2017. RLV Data Store for Write-Optimized Storage. Retrieved from http:\/\/help-legacy.sap.com\/saphelp_iq1611_iqnfs\/helpdata\/en\/a3\/13783784f21015bf03c9b06ad16fc0\/content.htm.  SAP. 2017. RLV Data Store for Write-Optimized Storage. Retrieved from http:\/\/help-legacy.sap.com\/saphelp_iq1611_iqnfs\/helpdata\/en\/a3\/13783784f21015bf03c9b06ad16fc0\/content.htm."},{"key":"e_1_2_1_65_1","volume-title":"Seltzer","author":"Smith Keith A.","year":"1997","unstructured":"Keith A. Smith and Margo I . Seltzer . 1997 . File system aging\u2014Increasing the relevance of file system benchmarks. In Measurement and Modeling of Computer Systems . 203\u2013213. Keith A. Smith and Margo I. Seltzer. 1997. File system aging\u2014Increasing the relevance of file system benchmarks. In Measurement and Modeling of Computer Systems. 203\u2013213."},{"key":"e_1_2_1_66_1","unstructured":"SNIA. 2018. Solid State Storage (SSS) Performance Test Specification (PTS). Retrieved from https:\/\/www.snia.org\/sites\/default\/files\/technical_work\/PTS\/SSS_PTS_2.0.1.pdf.  SNIA. 2018. Solid State Storage (SSS) Performance Test Specification (PTS). Retrieved from https:\/\/www.snia.org\/sites\/default\/files\/technical_work\/PTS\/SSS_PTS_2.0.1.pdf."},{"key":"e_1_2_1_67_1","volume-title":"Last Accessed","author":"DB.","year":"2018","unstructured":"Toku DB. [n.d.]. https:\/\/github.com\/percona\/PerconaFT , Last Accessed Sep. 24 2018 .. TokuDB. [n.d.]. https:\/\/github.com\/percona\/PerconaFT, Last Accessed Sep. 24 2018.."},{"key":"e_1_2_1_68_1","unstructured":"Tokutek Inc.[n.d.]. TokuMX\u2014MongoDB Performance Engine. Retrieved from https:\/\/www.percona.com\/software\/mongo-database\/percona-tokumx.  Tokutek Inc.[n.d.]. TokuMX\u2014MongoDB Performance Engine. Retrieved from https:\/\/www.percona.com\/software\/mongo-database\/percona-tokumx."},{"key":"e_1_2_1_69_1","unstructured":"Tokutek Inc.2013. TokuDB: MySQL Performance MariaDB Performance. Retrieved from http:\/\/www.tokutek.com\/products\/tokudb-for-mysql\/.  Tokutek Inc.2013. TokuDB: MySQL Performance MariaDB Performance. Retrieved from http:\/\/www.tokutek.com\/products\/tokudb-for-mysql\/."},{"key":"e_1_2_1_70_1","unstructured":"Vertica. 2017. WOS (Write Optimized Store). Retrieved from https:\/\/my.vertica.com\/docs\/7.1.x\/HTML\/Content\/Authoring\/Glossary\/WOSWriteOptimizedStore.htm.  Vertica. 2017. WOS (Write Optimized Store). Retrieved from https:\/\/my.vertica.com\/docs\/7.1.x\/HTML\/Content\/Authoring\/Glossary\/WOSWriteOptimizedStore.htm."},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/384192.384193"},{"key":"e_1_2_1_72_1","first-page":"2","article-title":"Algorithms for parallel memory, I: Two-level memories","volume":"12","author":"Vitter Jeffrey Scott","year":"1994","unstructured":"Jeffrey Scott Vitter and Elizabeth A. M. Shriver . 1994 . Algorithms for parallel memory, I: Two-level memories . Algorithmica 12 , 2 - 3 (1994), 110\u2013147. Jeffrey Scott Vitter and Elizabeth A. M. Shriver. 1994. Algorithms for parallel memory, I: Two-level memories. Algorithmica 12, 2-3 (1994), 110\u2013147.","journal-title":"Algorithmica"},{"key":"e_1_2_1_73_1","first-page":"2","article-title":"Algorithms for parallel memory, II: Hierarchical multilevel memories","volume":"12","author":"Vitter Jeffrey Scott","year":"1994","unstructured":"Jeffrey Scott Vitter and Elizabeth A. M. Shriver . 1994 . Algorithms for parallel memory, II: Hierarchical multilevel memories . Algorithmica 12 , 2 \u2013 3 (1994), 148\u2013169. Jeffrey Scott Vitter and Elizabeth A. M. Shriver. 1994. Algorithms for parallel memory, II: Hierarchical multilevel memories. Algorithmica 12, 2\u20133 (1994), 148\u2013169.","journal-title":"Algorithmica"},{"key":"e_1_2_1_75_1","unstructured":"Jimmy Xiang. 2012. Apache HBase Write Path. Retrieved from http:\/\/blog.cloudera.com\/blog\/2012\/06\/hbase-write-path\/.  Jimmy Xiang. 2012. Apache HBase Write Path. Retrieved from http:\/\/blog.cloudera.com\/blog\/2012\/06\/hbase-write-path\/."},{"volume-title":"Proceedings of the 14th USENIX Conference on File and Storage Technologies (FAST\u201916)","author":"Yuan Jun","key":"e_1_2_1_76_1","unstructured":"Jun Yuan , Yang Zhan , William Jannen , Prashant Pandey , Amogh Akshintala , Kanchan Chandnani , Pooja Deo , Zardosht Kasheff , Leif Walsh , Michael A. Bender , Martin Farach-Colton , Rob Johnson , Bradley C. Kuszmaul , and Donald E. Porter . 2016. Optimizing every operation in a write-optimized file system . In Proceedings of the 14th USENIX Conference on File and Storage Technologies (FAST\u201916) . 1\u201314. Jun Yuan, Yang Zhan, William Jannen, Prashant Pandey, Amogh Akshintala, Kanchan Chandnani, Pooja Deo, Zardosht Kasheff, Leif Walsh, Michael A. Bender, Martin Farach-Colton, Rob Johnson, Bradley C. Kuszmaul, and Donald E. Porter. 2016. Optimizing every operation in a write-optimized file system. In Proceedings of the 14th USENIX Conference on File and Storage Technologies (FAST\u201916). 1\u201314."},{"key":"e_1_2_1_77_1","article-title":"Writes wrought right, and other adventures in file system optimization","volume":"13","author":"Yuan Jun","year":"2017","unstructured":"Jun Yuan , Yang Zhan , William Jannen , Prashant Pandey , Amogh Akshintala , Kanchan Chandnani , Pooja Deo , Zardosht Kasheff , Leif Walsh , Michael A. Bender , Martin Farach-Colton , Rob Johnson , Bradley C. Kuszmaul , and Donald E. Porter . 2017 . Writes wrought right, and other adventures in file system optimization . Trans. Stor. 13 , 1 (2017), 3:1\u20133:26. Jun Yuan, Yang Zhan, William Jannen, Prashant Pandey, Amogh Akshintala, Kanchan Chandnani, Pooja Deo, Zardosht Kasheff, Leif Walsh, Michael A. Bender, Martin Farach-Colton, Rob Johnson, Bradley C. Kuszmaul, and Donald E. Porter. 2017. Writes wrought right, and other adventures in file system optimization. Trans. Stor. 13, 1 (2017), 3:1\u20133:26.","journal-title":"Trans. Stor."},{"key":"e_1_2_1_78_1","volume-title":"Proceedings of the 16th USENIX Conference on File and Storage Technologies (FAST\u201918)","author":"Zhan Yang","year":"2018","unstructured":"Yang Zhan , Alexander Conway , Yizheng Jiao , Eric Knorr , Michael A. Bender , Martin Farach-Colton , William Jannen , Rob Johnson , Donald E. Porter , and Jun Yuan . 2018 . The full path to full-path indexing . In Proceedings of the 16th USENIX Conference on File and Storage Technologies (FAST\u201918) . 123\u2013138. Yang Zhan, Alexander Conway, Yizheng Jiao, Eric Knorr, Michael A. Bender, Martin Farach-Colton, William Jannen, Rob Johnson, Donald E. Porter, and Jun Yuan. 2018. The full path to full-path indexing. In Proceedings of the 16th USENIX Conference on File and Storage Technologies (FAST\u201918). 123\u2013138."}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3470635","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3470635","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3470635","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:55Z","timestamp":1750191535000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3470635"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,20]]},"references-count":77,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9,30]]}},"alternative-id":["10.1145\/3470635"],"URL":"https:\/\/doi.org\/10.1145\/3470635","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2021,9,20]]},"assertion":[{"value":"2020-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}