{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T23:40:10Z","timestamp":1755906010224,"version":"3.44.0"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"name":"NSF","award":["IIS-2348919, IIS-2402823"],"award-info":[{"award-number":["IIS-2348919, IIS-2402823"]}]},{"name":"Infosys"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,9]]},"abstract":"<jats:p>Effective data discovery is a cornerstone of modern data-driven decision-making. Yet, identifying datasets with specific distributional characteristics, such as percentiles or preferences, remains challenging. While recent proposals have enabled users to search based on percentile predicates, much of the research in data discovery relies on heuristic methods, which often result in biased outcomes. This paper presents the first theoretically backed framework that unifies data discovery under centralized and decentralized settings.<\/jats:p>\n          <jats:p>\n            More specifically, let\n            <jats:italic toggle=\"yes\">P<\/jats:italic>\n            ={P\n            <jats:sub>1<\/jats:sub>\n            ,..., P\n            <jats:sub>N<\/jats:sub>\n            } be a repository of\n            <jats:italic toggle=\"yes\">N<\/jats:italic>\n            datasets, such that each P\n            <jats:sub>i<\/jats:sub>\n            \u2282 \u211d\n            <jats:sup>d<\/jats:sup>\n            , where\n            <jats:italic toggle=\"yes\">d<\/jats:italic>\n            is a constant. We study the percentile-aware indexing (Ptile) problem and the preference-aware indexing (Pref) problem under the centralized and the federated setting. In the centralized setting, we assume direct access to the datasets in\n            <jats:italic toggle=\"yes\">P<\/jats:italic>\n            . In the federated setting we are given a synopsis\n            <jats:italic toggle=\"yes\">S<\/jats:italic>\n            <jats:sub>\n              P\n              <jats:sub>i<\/jats:sub>\n            <\/jats:sub>\n            which is a compressed representation of P\n            <jats:sub>i<\/jats:sub>\n            that captures the structure of P\n            <jats:sub>i<\/jats:sub>\n            , for every i \u2208 [N]. For the Ptile problem, the goal is to construct a data structure such that given a predicate (query rectangle R and an interval \u03b8) report all indexes\n            <jats:italic toggle=\"yes\">J<\/jats:italic>\n            such that j \u2208 J if and only if |P\n            <jats:sub>j<\/jats:sub>\n            \u2229 R|\/|P\n            <jats:sub>j<\/jats:sub>\n            | \u2208 [N]. For the Ptile problem, the goal is to construct a data structure such that given a predicate (query vector v\n            <jats:sup>\u2192<\/jats:sup>\n            and an interval \u03b8) report all indexes\n            <jats:italic toggle=\"yes\">J<\/jats:italic>\n            such that j \u2208 J if and only if \u03c9\n            <jats:sub>k<\/jats:sub>\n            (P\n            <jats:sub>j<\/jats:sub>\n            ,v\n            <jats:sup>\u2192<\/jats:sup>\n            )\u2208 \u03b8, where \u03c9\n            <jats:sub>k<\/jats:sub>\n            (p\n            <jats:sub>j<\/jats:sub>\n            ,v\n            <jats:sup>\u2192<\/jats:sup>\n            ) is the score (inner-product) of the\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            -th largest projection of P\n            <jats:sub>j<\/jats:sub>\n            on v\n            <jats:sup>\u2192<\/jats:sup>\n            . We first show lower bounds for the Ptile and Pref problems in the centralized setting, showing that we cannot hope for near-linear data structures with polylogarithmic query time. Then we focus on approximate data structures for both problems in both settings. We show \u00d8(N) space data structures with \u00d8(N) preprocessing time, that can answer Ptile and Pref queries in \u00d8(1+OUT) time, where OUT is the output size. The data structures return a set of indexes\n            <jats:italic toggle=\"yes\">J<\/jats:italic>\n            such that: i) for every P\n            <jats:sub>i<\/jats:sub>\n            that satisfies the predicate, i \u2208 J and ii) if j \u2208 J then P\n            <jats:sub>j<\/jats:sub>\n            satisfies the predicate up to an additive error of \u03b5+2\u03b4, where \u03b5 is an arbitrarily small constant and \u03b4 is the error of the synopses.\n          <\/jats:p>","DOI":"10.1145\/3725227","type":"journal-article","created":{"date-parts":[[2025,6,9]],"date-time":"2025-06-09T15:20:31Z","timestamp":1749482431000},"page":"1-26","source":"Crossref","is-referenced-by-count":0,"title":["A Theoretical Framework for Distribution-Aware Dataset Search"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-3798-9578","authenticated-orcid":false,"given":"Aryan","family":"Esmailpour","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Illinois Chicago, Chicago, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2529-4036","authenticated-orcid":false,"given":"Sainyam","family":"Galhotra","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Cornell University, Ithaca, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-6610-4404","authenticated-orcid":false,"given":"Rahul","family":"Raychaudhury","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2114-8886","authenticated-orcid":false,"given":"Stavros","family":"Sintos","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois Chicago, Chicago, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2261250.2261301"},{"key":"e_1_2_1_2_1","volume-title":"50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)","author":"Afshani P.","year":"2023","unstructured":"P. Afshani, P. Cheng, A. Basu Roy, and Z. Wei. On range summary queries. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), 2023."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/3116660.3117000"},{"key":"e_1_2_1_4_1","volume-title":"48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)","author":"Agarwal P. K.","year":"2021","unstructured":"P. K. Agarwal, X. Hu, S. Sintos, and J. Yang. Dynamic enumeration of similarity joins. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), 2021."},{"key":"e_1_2_1_5_1","volume-title":"16th International Symposium on Experimental Algorithms (SEA 2017)","author":"Agarwal P. K.","year":"2017","unstructured":"P. K. Agarwal, N. Kumar, S. Sintos, and S. Suri. Efficient algorithms for k-regret minimizing sets. In 16th International Symposium on Experimental Algorithms (SEA 2017), 2017."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551858"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74915-8_18"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3681954.3681999"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1751-5823.2010.00112.x"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3457390.3457403"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00067"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313685"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476346"},{"key":"e_1_2_1_14_1","first-page":"28","volume-title":"36th International Symposium on Computational Geometry (SoCG 2020","author":"Chan T. M.","year":"2020","unstructured":"T. M. Chan, Q. He, and Y. Nekrich. Further results on colored range searching. In 36th International Symposium on Computational Geometry (SoCG 2020), pages 28--1, 2020."},{"issue":"2","key":"e_1_2_1_15_1","first-page":"45","article-title":"Dynamic orthogonal range searching on the ram, revisited","volume":"9","author":"Chan T. M.","year":"2018","unstructured":"T. M. Chan and K. Tsakalidis. Dynamic orthogonal range searching on the ram, revisited. Journal of Computational Geometry, 9(2):45--66, 2018.","journal-title":"Journal of Computational Geometry"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511626371"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781601985170"},{"key":"e_1_2_1_18_1","volume-title":"Joint Statistical Meetings (JSM). American Statistical Association","author":"Culotta A.","year":"2014","unstructured":"A. Culotta. Reducing sampling bias in social media data for county health inference. In Joint Statistical Meetings (JSM). American Statistical Association, 2014."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1201\/9781003278290-44"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529353"},{"key":"e_1_2_1_22_1","volume-title":"A theoretical framework for distribution-aware dataset search. arXiv preprint arXiv:2503.21235","author":"Esmailpour A.","year":"2025","unstructured":"A. Esmailpour, S. Galhotra, R. Raychaudhury, and S. Sintos. A theoretical framework for distribution-aware dataset search. arXiv preprint arXiv:2503.21235, 2025."},{"key":"e_1_2_1_23_1","volume-title":"Range (R\u00e9nyi) entropy queries and partitioning. arXiv preprint arXiv:2312.15959","author":"Esmailpour A.","year":"2024","unstructured":"A. Esmailpour, S. Krishnan, and S. Sintos. Range (R\u00e9nyi) entropy queries and partitioning. arXiv preprint arXiv:2312.15959, 2024."},{"key":"e_1_2_1_24_1","first-page":"1001","volume-title":"IEEE 34th International Conference on Data Engineering (ICDE)","author":"Fernandez R. C.","year":"2018","unstructured":"R. C. Fernandez, Z. Abedjan, F. Koko, G. Yuan, S. Madden, and M. Stonebraker. Aurum: A data discovery system. In IEEE 34th International Conference on Data Engineering (ICDE), pages 1001--1012. IEEE, 2018."},{"key":"e_1_2_1_25_1","first-page":"2780","volume-title":"39th IEEE International Conference on Data Engineering, ICDE '23","author":"Galhotra S.","unstructured":"S. Galhotra, Y. Gong, and R. C. Fernandez. Metam: Goal-oriented data discovery. In 39th IEEE International Conference on Data Engineering, ICDE '23, pages 2780--2793."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654970"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-62127-2_36"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654957"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00045"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.4236\/ojs.2016.63035"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1038"},{"key":"e_1_2_1_32_1","volume-title":"American Mathematical Soc.","author":"Har-Peled S.","year":"2011","unstructured":"S. Har-Peled. Geometric approximation algorithms. Number 173. American Mathematical Soc., 2011."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594560"},{"key":"e_1_2_1_34_1","first-page":"785","volume-title":"SODA","author":"Kaplan H.","year":"2007","unstructured":"H. Kaplan, N. Rubin, M. Sharir, and E. Verbin. Counting colors in boxes. In SODA, pages 785--794, 2007."},{"key":"e_1_2_1_35_1","first-page":"468","volume-title":"37th IEEE International Conference on Data Engineering, ICDE '21","author":"Koutras C.","unstructured":"C. Koutras, G. Siachamis, A. Ionescu, K. Psarakis, J. Brons, M. Fragkoulis, C. Lofi, A. Bonifati, and A. Katsifodimos. Valentine: Evaluating matching techniques for dataset discovery. In 37th IEEE International Conference on Data Engineering, ICDE '21, pages 468--479."},{"key":"e_1_2_1_36_1","volume-title":"27th International Conference on Database Theory (ICDT 2024)","author":"Krishnan S.","year":"2024","unstructured":"S. Krishnan and S. Sintos. Range entropy queries and partitioning. In 27th International Conference on Database Theory (ICDT 2024), 2024."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975055.6"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588663"},{"issue":"2","key":"e_1_2_1_39_1","first-page":"59","article-title":"Making open data transparent: Data discovery on open data","volume":"41","author":"Miller R. J.","year":"2018","unstructured":"R. J. Miller, F. Nargesian, E. Zhu, C. Christodoulakis, K. Q. Pu, and P. Andritsos. Making open data transparent: Data discovery on open data. IEEE Data Eng. Bull., 41(2):59--70, 2018.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_40_1","unstructured":"M. Mulshine. A major flaw in google's algorithm allegedly tagged two black people's faces with the word 'gorillas'. https:\/\/www.businessinsider.com\/google-tags-black-people-as-gorillas-2015--7."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476299"},{"volume-title":"Conference Name: IEEE Transactions on Knowledge and Data Engineering.","author":"Nargesian F.","key":"e_1_2_1_42_1","unstructured":"F. Nargesian, K. Pu, B. Ghadiri-Bashardoost, E. Zhu, and R. J. Miller. Data lake organization. 35(1):237--250. Conference Name: IEEE Transactions on Knowledge and Data Engineering."},{"key":"e_1_2_1_43_1","first-page":"1939","volume-title":"ACM International Conference on Management of Data, SIGMOD '20","author":"Nargesian F.","unstructured":"F. Nargesian, K. Q. Pu, E. Zhu, B. Ghadiri Bashardoost, and R. J. Miller. Organizing data lakes for navigation. In ACM International Conference on Management of Data, SIGMOD '20, pages 1939--1950."},{"key":"e_1_2_1_44_1","volume-title":"ACM Transactions on Database Systems (TODS), 39(1):1--21","author":"Nekrich Y.","year":"2014","unstructured":"Y. Nekrich. Efficient range searching for categorical and plain data. ACM Transactions on Database Systems (TODS), 39(1):1--21, 2014."},{"key":"e_1_2_1_45_1","first-page":"1365","volume-title":"World Wide Web Conference, WWW '19","author":"Noy N.","unstructured":"N. Noy, M. Burgess, and D. Brickley. Google dataset search: Building a search engine for datasets in an open web ecosystem. In World Wide Web Conference, WWW '19, pages 1365--1375."},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","unstructured":"P. Ouellette A. Sciortino F. Nargesian B. G. Bashardoost E. Zhu K. Q. Pu and R. J. Miller. RONIN: Data lake exploration. 14(12):2863--2866.","DOI":"10.14778\/3476311.3476364"},{"key":"e_1_2_1_47_1","volume-title":"The design of dynamic data structures","author":"Overmars M. H.","year":"1983","unstructured":"M. H. Overmars. The design of dynamic data structures, volume 156. Springer Science & Business Media, 1983."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90093-4"},{"key":"e_1_2_1_49_1","volume-title":"33rd International Symposium on Computational Geometry","author":"Rahul S.","year":"2017","unstructured":"S. Rahul. Approximate range counting revisited. In 33rd International Symposium on Computational Geometry, 2017."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2424321.2424406"},{"key":"e_1_2_1_51_1","unstructured":"A. Rose. Are face-detection cameras racist? https:\/\/time.com\/archive\/6906847\/are-face-detection-cameras-racist\/."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00264"},{"key":"e_1_2_1_53_1","unstructured":"T. Townsend. Most engineers are white - and so are the faces they use to train software. https:\/\/www.vox.com\/2017\/1\/18\/14304964\/data-facial-recognition-trouble-recognizing-black-white-faces-diversity."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3329145"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213882"},{"key":"e_1_2_1_57_1","first-page":"2527","volume-title":"30th ACM International Conference on Information & Knowledge Management, CIKM '21","author":"Zhang H.","unstructured":"H. Zhang, A. Santos, and J. Freire. DSDD: Domain-specific dataset discovery on the web. In 30th ACM International Conference on Information & Knowledge Management, CIKM '21, pages 2527--2536. ACM Press. event-place:."},{"key":"e_1_2_1_58_1","first-page":"1951","volume-title":"ACM International Conference on Management of Data, SIGMOD '20","author":"Zhang Y.","unstructured":"Y. Zhang and Z. G. Ives. Finding related tables in data lakes for interactive data science. In ACM International Conference on Management of Data, SIGMOD '20, pages 1951--1966."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588675"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611479.3611498"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725227","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T23:18:24Z","timestamp":1755904704000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725227"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,9]]},"references-count":60,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,9]]}},"alternative-id":["10.1145\/3725227"],"URL":"https:\/\/doi.org\/10.1145\/3725227","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2025,6,9]]}}}