{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:13:08Z","timestamp":1779174788002,"version":"3.51.4"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T00:00:00Z","timestamp":1701993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,12,8]]},"abstract":"<jats:p>The execution of analytical queries on massive datasets presents challenges due to long response times and high computational costs. As a result, the analysis of representative samples of data has emerged as an attractive alternative; this avoids the cost of processing queries against the entire dataset, while still producing statistically valid results. Unfortunately, the sampling techniques in common use sacrifice either sample quality or performance, and so are poorly suited for this task. However, it is possible to build high quality sample sets efficiently with the assistance of indexes. This introduces a new challenge: real-world data is subject to continuous update, and so the indexes must be kept up to date. This is difficult, because existing sampling indexes present a dichotomy; efficient sampling indexes are difficult to update, while easily updatable indexes have poor sampling performance. This paper seeks to address this gap by proposing a general and practical framework for extending most sampling indexes with efficient update support, based on splitting indexes into smaller shards, combined with a systematic approach to the periodic reconstruction. The framework's design space is examined, with an eye towards exploring trade-offs between update performance, sampling performance, and memory usage. Three existing static sampling indexes are extended using this framework to support updates, and the generalization of the framework to concurrent operations and larger-than-memory data is discussed. Through a comprehensive suite of benchmarks, the extended indexes are shown to match or exceed the update throughput of state-of-the-art dynamic baselines, while presenting significant improvements in sampling latency.<\/jats:p>","DOI":"10.1145\/3626744","type":"journal-article","created":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T14:01:21Z","timestamp":1702389681000},"page":"1-26","source":"Crossref","is-referenced-by-count":3,"title":["Practical Dynamic Extension for Sampling Indexes"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9265-652X","authenticated-orcid":false,"given":"Douglas B.","family":"Rumbaugh","sequence":"first","affiliation":[{"name":"Penn State University, University Park, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4857-900X","authenticated-orcid":false,"given":"Dong","family":"Xie","sequence":"additional","affiliation":[{"name":"Penn State University, University Park, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,12,12]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"2023. Delicious Dataset. http:\/\/konect.cc\/networks\/delicious-ti\/"},{"key":"e_1_2_2_2_1","unstructured":"2023. Open Street Map Dataset. https:\/\/planet.openstreetmap.org\/"},{"key":"e_1_2_2_3_1","unstructured":"2023. PostgreSQL Documentation. https:\/\/www.postgresql.org\/docs\/15\/sql-select.html"},{"key":"e_1_2_2_4_1","unstructured":"2023. Twitter Dataset. https:\/\/github.com\/ANLAB-KAIST\/traces\/releases\/tag\/twitter_rv.net"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2019.4"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2017.3"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465355"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2302.05682"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btac142"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387648"},{"key":"e_1_2_2_11_1","volume-title":"SILK: Preventing Latency Spikes in Log-Structured Merge Key-Value Stores. In 2019 USENIX Annual Technical Conference, USENIX ATC 2019","author":"Balmau Oana","year":"2019","unstructured":"Oana Balmau, Florin Dinu, Willy Zwaenepoel, Karan Gupta, Ravishankar Chandhiramoorthi, and Diego Didona. 2019. SILK: Preventing Latency Spikes in Log-Structured Merge Key-Value Stores. In 2019 USENIX Annual Technical Conference, USENIX ATC 2019, Renton, WA, USA, July 10--12, 2019, Dahlia Malkhi and Dan Tsafrir (Eds.). USENIX Association, 753--766. https:\/\/www.usenix.org\/conference\/atc19\/presentation\/balmau"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387643"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_2_14_1","volume-title":"Principles of Statistics","author":"Bulmer M.G.","unstructured":"M.G. Bulmer. 1979. Principles of Statistics. Dover, New York."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3589935"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3347146.3359363"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064054"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276980"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196927"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319903"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551853"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915249"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3483840"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741973"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007664"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/3--540--56939--1_77"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594545"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745757"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33013862"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882940"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3284551"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389731"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-003--1078--6"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.08.002"},{"key":"e_1_2_2_36_1","volume-title":"Random Sampling from Databases. Ph. D. Dissertation","author":"Olken Frank","unstructured":"Frank Olken. 1993. Random Sampling from Databases. Ph. D. Dissertation. University of California at Berkeley."},{"key":"e_1_2_2_37_1","volume-title":"VLDB'86 Twelfth International Conference on Very Large Data Bases, August 25--28","author":"Olken Frank","year":"1986","unstructured":"Frank Olken and Doron Rotem. 1986. Simple Random Sampling from Relational Databases. In VLDB'86 Twelfth International Conference on Very Large Data Bases, August 25--28, 1986, Kyoto, Japan, Proceedings, Wesley W. Chu, Georges Gardarin, Setsuo Ohsuga, and Yahiko Kambayashi (Eds.). Morgan Kaufmann, 160--169. http:\/\/www.vldb.org\/conf\/1986\/P160.PDF"},{"key":"e_1_2_2_38_1","volume-title":"Proceedings of the Fifteenth International Conference on Very Large Data Bases, August 22--25","author":"Olken Frank","year":"1989","unstructured":"Frank Olken and Doron Rotem. 1989. Random Sampling from B Trees. In Proceedings of the Fifteenth International Conference on Very Large Data Bases, August 22--25, 1989, Amsterdam, The Netherlands, Peter M. G. Apers and Gio Wiederhold (Eds.). Morgan Kaufmann, 269--277. http:\/\/www.vldb.org\/conf\/1989\/P269.PDF"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00140664"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0014927"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90093--4"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196905"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.47"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSST.2010.5496972"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3526068"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3147.3165"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.92917"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1049\/el:19740097"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452806"},{"key":"e_1_2_2_51_1","volume-title":"Proceedings of the 9th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2012","author":"Zaharia Matei","year":"2012","unstructured":"Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma, Murphy McCauly, Michael J. Franklin, Scott Shenker, and Ion Stoica. 2012. Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing. In Proceedings of the 9th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2012, San Jose, CA, USA, April 25--27, 2012, Steven D. Gribble and Dina Katabi (Eds.). USENIX Association, 15--28. https:\/\/www.usenix.org\/conference\/nsdi12\/technical-sessions\/presentation\/zaharia"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196931"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/3538598.3538606"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465998.3466002"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626744","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626744","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T12:58:59Z","timestamp":1755867539000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626744"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,8]]},"references-count":54,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12,8]]}},"alternative-id":["10.1145\/3626744"],"URL":"https:\/\/doi.org\/10.1145\/3626744","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,8]]}}}