A Theoretical Framework for Distribution-Aware Dataset Search
Aryan Esmailpour, Sainyam Galhotra, Rahul Raychaudhury, Stavros Sintos · 2025
Read A Theoretical Framework for Distribution-Aware Dataset Search by Aryan Esmailpour, Sainyam Galhotra, Rahul Raychaudhury, Stavros Sintos (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-21235.txt.
Introduction
Aryan Esmailpour and co-authors give dataset search a theory base in a 2025 paper. Hunters of data often want sets with set traits, like a share of rows in a range or a top value along a chosen line. Past search tools lean on rules of thumb with no proof behind them.
Two index tasks anchor the frame: one for percentile shares, one for preference scores. The team shows near linear stores with fast queries are out of reach when data sit in one place. Near linear stores do exist for both tasks in wider setups, with bounds spelled out. The work covers lone and federated stores alike.
Catalog record
| CREATOR | Aryan Esmailpour, Sainyam Galhotra, Rahul Raychaudhury, Stavros Sintos |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 128 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-21235
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Theoretical Framework for Distribution-Aware Dataset Search Aryan Esmailpour, Sainyam Galhotra, Rahul Raychaudhury, Stavros Sintos Abstract . 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. More specifically, let 𝒫 = { P 1 , … , P N } \mathcal{P}=\{P_{1},\ldots,P_{N}\} be a repository of N N datasets, such that each P i ⊂ ℝ d P_{i}\subset\mathbb{R}^{d} , where d d 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 𝒫 \mathcal{P} . In the federated setting we are given a synopsis 𝒮 P i \mathcal{S}_{P_{i}} which is a compressed representation of P i P_{i} that captures the structure of P i P_{i} , for every i ∈ [ N ] i\in[N] . For the Ptile problem, the goal is to construct a data structure such that given a predicate (query rectangle R R and an interval θ \theta ) report all indexes J J such that j ∈ J j\in J if and only if | P j ∩ R | | P j | ∈ θ \frac{|P_{j}\cap R|}{|P_{j}|}\in\theta . For the Pref problem, the goal is to construct a data structure such that given a predicate (query vector v → \vec{v} and an interval θ \theta ) report all indexes J J such that j ∈ J j\in J if and only if ω k ( P j , v → ) ∈ θ \omega_{k}(P_{j},\vec{v})\in\theta , where ω k ( P j , v → ) \omega_{k}(P_{j},\vec{v}) is the score (inner-product) of the k k -th largest projection of P j P_{j} on v → \vec{v} . 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 O ~ ( N ) \tilde{O}(N) space data structures with O ~ ( N ) \tilde{O}(N) preprocessing time, that can answer Ptile and Pref queries in O ~ ( 1 + 𝖮𝖴𝖳 ) \tilde{O}(1+\mathsf{OUT}) time, where 𝖮𝖴𝖳 \mathsf{OUT} is the output size. The data structures return a set of indexes J J such that: i) for every P i P_{i} that satisfies the predicate, i ∈ J i\in J and ii) if j ∈ J j\in J then P j P_{j} satisfies the predicate up to an additive error of ε + 2 δ \varepsilon+2\delta , where ε \varepsilon is an arbitrarily small constant and δ \delta is the error of the synopses. 1. Introduction In today’s data-driven world, efficient and effective data discovery ( 13 , 14 , 25 , 10 , 11 , 22 , 29 , 35 , 39 , 56 , 57 , 28 ) plays a pivotal role in unlocking the true potential of information collected from diverse sources. With the rise of deep learning, organizations increasingly rely on vast and varied datasets to drive innovation and gain competitive advantage. However, existing data discovery systems primarily rely on keyword-based searches or examples to identify relevant datasets ( 13 , 45 ) . While these methods are ubiquitous, they fall short in scenarios where users have a specific distributional requirement. For instance, users developing machine learning models often require datasets that ensure balanced representation across various groups to prevent overfitting or biases in their models. Furthermore, the problem of selection bias (lack of representative samples) often leads to flawed analyses and unreliable outcomes. These shortcomings are particularly pronounced in industrial settings ( 20 , 40 , 51 , 52 ) , where datasets are frequently repurposed or reused in contexts different from their original design ( 9 , 19 , 30 , 59 ) . Therefore, it is important to develop advanced data discovery techniques that allow users to search for datasets that satisfy their distributional needs. We demonstrate this with the following example. Example 1.1. Consider an economist who wants to understand the various reasons behind high crime in Brooklyn, NY (more generally, in any specific neighborhood in the US). To ensure statistical significance of the analysis, the economist searches for data that contain a substantial fraction of the data points (say at least 10%) from Brooklyn. More generally, such support requirement would hold even if they want to analyze crime (or other factors affecting development) across different cities across the United States. Several prior works ( 8 , 28 , 25 , 29 ) on data discovery have considered such queries for data analysis on open data repositories which contain roughly 100K datasets. Additionally, the economist may want to identify cities which have at least k neighborhoods with high or low quality of life, modeled as a linear function of crime, pollution, healthcare and other factors that they are interested to consider. In summary, the economist often faces two types of distributional requirements for data search: (i) The fraction of data points within a specific range (geographical region) must meet or exceed a specified threshold, such as x%. We refer to this query as a percentile-query. (ii) The value (or score) of a specific combination of attributes from at least k data points must exceed a threshold, such as \tau . We formalize this notion as a preference query. The prior work on distribution aware search suffer from two main challenges: First, these techniques cannot handle preference requirements and only support one-sided percentile queries. For example, a query to identify datasets that contain at least 10\% points in a rectangular area (that includes Brooklyn) can not be answered with these tools. Second, all these techniques employ heuristics to identify the best datasets. More generally, prior work on data discovery employs heuristics (for example in keyword based data discovery techniques ( 13 , 45 ) ), which do not guarantee the effectiveness of the search algorithm. This means that the search result may miss certain datasets, even though it satisfies user’s query. Missing any dataset that satisfies user query can percolate biases into the system. Missing datasets is generally unacceptable in data marketplaces, where it is extremely crucial to ensure that all datasets that satisfy the query are available to the user. Therefore, it is important to develop a theoretically rigorous framework for data discovery, which guarantees to return all relevant datasets for the user’s query. In this work, we address these limitations and present the first theoretical framework for data discovery which helps users to identify datasets that satisfy distributional requirements. Next, we describe a new general theoretical framework that is used to formally define various practical problems from distribution-aware dataset search. Later, we show two of the most common subclasses of problems that we