Aryan Esmailpour
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Aryan Esmailpour has a total of 10 co-authors. Here are the top co-authors by number of shared publications:
- Stavros Sintos
Department of Computer Science, University of Illinois Chicago, Chicago, IL, USA
8 shared publications - Xiao Hu
University of Waterloo, Waterloo, Canada
3 shared publications - Boris Glavic
University of Illinois Chicago, Chicago, IL, USA
1 shared publication - Jinchao Huang
The Chinese University of Hong Kong, Hong Kong, Hong Kong
1 shared publication - Jun Yang
Duke University, Durham, NC, USA
1 shared publication - Khoi Le
Department of Computer Science, University of Illinois Chicago, Chicago, IL, USA
1 shared publication
Latest Publications
- Open Access
- 6 November 2026
- Published by Association for Computing Machinery (ACM)
- p. 1141-1152
Compact Representations of Geometric Bipartite Graphs via Weighted Biclique Covers
- 6 November 2026
- Published by Association for Computing Machinery (ACM)
- p. 1141-1152
Open AccessCompact Representations of Geometric Bipartite Graphs via Weighted Biclique Covers
- Open Access
- 18 May 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 4 (3) , 1-25
Weighted Set Multi-Cover on Bounded Universe and Applications in Package Recommendation
The weighted set multi-cover problem is a fundamental generalization of set cover that arises in data-driven applications where one must select a small, low-cost subset from a large collection of candidates under coverage constraints. In data management settings, such problems arise naturally either as expressive database queries or as post-processing steps over query results, for example, when selecting representative or diverse subsets from large relations returned by database queries for decision support, recommendation, fairness-aware data selection, or crowd-sourcing. While the general weighted set multi-cover problem is NP-complete, many practical workloads involve a bounded universe of attributes or items that must be covered, leading to the Weighted Set Multi-Cover with Bounded Universe (WSMC-BU) problem, where the universe size is constant. Despite its relevance in large-scale data processing pipelines, little is known about efficient algorithms for this special case. In this paper, we develop exact and approximation algorithms for WSMC-BU. We first discuss a dynamic programming algorithm that solves WSMC-BU exactly in O ( n ℓ+1 ) time, where n is the number of input sets and ℓ=O(1) is the universe size. We then present a 2-approximation algorithm based on linear programming and rounding, running in O ( ℒ ( n )) time, where ℒ ( n ) denotes the complexity of solving a linear program with O ( n ) variables. To further improve efficiency for large datasets, we propose a faster (2+ε)-approximation algorithm with running time O ( n log n + ℒ (log W )), where W is the ratio of the total weight to the minimum weight, and ε is an arbitrary constant specified by the user. Our results provide the first practical constant-factor approximation algorithms for WSMC-BU, with approximation guarantees independent of the universe size. Extensive experiments on real and synthetic datasets demonstrate that our methods consistently outperform greedy and standard LP-rounding baselines in both solution quality and runtime, making them suitable for data-intensive selection tasks over large query outputs.
- 18 May 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 4 (3) , 1-25
Open AccessWeighted Set Multi-Cover on Bounded Universe and Applications in Package Recommendation
The weighted set multi-cover problem is a fundamental generalization of set cover that arises in data-driven applications where one must select a small, low-cost subset from a large collection of candidates under coverage constraints. In data management settings, such problems arise naturally either as expressive database queries or as post-processing steps over query results, for example, when selecting representative or diverse subsets from large relations returned by database queries for decision support, recommendation, fairness-aware data selection, or crowd-sourcing. While the general weighted set multi-cover problem is NP-complete, many practical workloads involve a bounded universe of attributes or items that must be covered, leading to the Weighted Set Multi-Cover with Bounded Universe (WSMC-BU) problem, where the universe size is constant. Despite its relevance in large-scale data processing pipelines, little is known about efficient algorithms for this special case. In this paper, we develop exact and approximation algorithms for WSMC-BU. We first discuss a dynamic programming algorithm that solves WSMC-BU exactly in O ( n ℓ+1 ) time, where n is the number of input sets and ℓ=O(1) is the universe size. We then present a 2-approximation algorithm based on linear programming and rounding, running in O ( ℒ ( n )) time, where ℒ ( n ) denotes the complexity of solving a linear program with O ( n ) variables. To further improve efficiency for large datasets, we propose a faster (2+ε)-approximation algorithm with running time O ( n log n + ℒ (log W )), where W is the ratio of the total weight to the minimum weight, and ε is an arbitrary constant specified by the user. Our results provide the first practical constant-factor approximation algorithms for WSMC-BU, with approximation guarantees independent of the universe size. Extensive experiments on real and synthetic datasets demonstrate that our methods consistently outperform greedy and standard LP-rounding baselines in both solution quality and runtime, making them suitable for data-intensive selection tasks over large query outputs.
- Open Access
- 12 May 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 4 (2) , 1-27
Faster Relational Algorithms Using Geometric Data Structures
Optimization tasks over relational data, such as clustering, often suffer from the prohibitive cost of join operations, which are necessary to access the full dataset. While geometric data structures like BBD trees yield fast approximation algorithms in the standard computational setting, their application to relational data remains unclear due to the size of the join output. In this paper, we introduce a framework that leverages geometric insights to design faster algorithms when the data is stored as the results of a join query in a relational database. Our core contribution is the development of the RBBD tree, a randomized variant of the BBD tree tailored for relational settings. Instead of completely constructing the RBBD tree, by leveraging efficient sampling and counting techniques over relational joins, we enable on-the-fly efficient expansion of the RBBD tree, maintaining only the necessary parts. This allows us to simulate geometric query procedures without materializing the join result. As an application, we present algorithms that improve the state-of-the-art for relational k -center/means/median clustering by a factor of k in running time while maintaining the same approximation guarantees. Our method is general and can be applied to various optimization problems in the relational setting.
- 12 May 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 4 (2) , 1-27
Open AccessFaster Relational Algorithms Using Geometric Data Structures
Optimization tasks over relational data, such as clustering, often suffer from the prohibitive cost of join operations, which are necessary to access the full dataset. While geometric data structures like BBD trees yield fast approximation algorithms in the standard computational setting, their application to relational data remains unclear due to the size of the join output. In this paper, we introduce a framework that leverages geometric insights to design faster algorithms when the data is stored as the results of a join query in a relational database. Our core contribution is the development of the RBBD tree, a randomized variant of the BBD tree tailored for relational settings. Instead of completely constructing the RBBD tree, by leveraging efficient sampling and counting techniques over relational joins, we enable on-the-fly efficient expansion of the RBBD tree, maintaining only the necessary parts. This allows us to simulate geometric query procedures without materializing the join result. As an application, we present algorithms that improve the state-of-the-art for relational k -center/means/median clustering by a factor of k in running time while maintaining the same approximation guarantees. Our method is general and can be applied to various optimization problems in the relational setting.
- Open Access
- 12 May 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 4 (2) , 1-26
Subset Sampling over Joins
Subset sampling (also known as Poisson sampling), where the decision to include any specific element in the sample is made independently of all others, is a fundamental primitive in data analytics, enabling efficient approximation by processing representative subsets rather than massive datasets. While sampling from explicit lists is well-understood, modern applications-such as machine learning over relational data--often require sampling from a set defined implicitly by a relational join. In this paper, we study the problem of subset sampling over joins : drawing a random subset from the join results, where each join result is included independently with some probability. We address the general setting where the probability is derived from input tuple weights via decomposable functions (e.g., product, sum, min, max). Since the join size can be exponentially larger than the input, the naive approach of materializing all join results to perform subset sampling is computationally infeasible. We propose the first efficient algorithms for subset sampling over acyclic joins: (1) a static index for generating multiple (independent) subset samples over joins; (2) a one-shot algorithm for generating a single subset sample over joins; (3) a dynamic index that can support tuple insertions, while maintaining a one-shot sample or generating multiple (independent) samples. Our techniques achieve near-optimal time and space complexity with respect to the input size and the expected sample size.
- 12 May 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 4 (2) , 1-26
Open AccessSubset Sampling over Joins
Subset sampling (also known as Poisson sampling), where the decision to include any specific element in the sample is made independently of all others, is a fundamental primitive in data analytics, enabling efficient approximation by processing representative subsets rather than massive datasets. While sampling from explicit lists is well-understood, modern applications-such as machine learning over relational data--often require sampling from a set defined implicitly by a relational join. In this paper, we study the problem of subset sampling over joins : drawing a random subset from the join results, where each join result is included independently with some probability. We address the general setting where the probability is derived from input tuple weights via decomposable functions (e.g., product, sum, min, max). Since the join size can be exponentially larger than the input, the naive approach of materializing all join results to perform subset sampling is computationally infeasible. We propose the first efficient algorithms for subset sampling over acyclic joins: (1) a static index for generating multiple (independent) subset samples over joins; (2) a one-shot algorithm for generating a single subset sample over joins; (3) a dynamic index that can support tuple insertions, while maintaining a one-shot sample or generating multiple (independent) samples. Our techniques achieve near-optimal time and space complexity with respect to the input size and the expected sample size.
- Open Access
- 9 June 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (2) , 1-26
A Theoretical Framework for Distribution-Aware Dataset Search
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 ={P 1 ,..., P N } be a repository of N datasets, such that each P i ⊂ ℝ d , where 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 P . In the federated setting we are given a synopsis S P i which is a compressed representation of P i that captures the structure of P i , for every i ∈ [N]. For the Ptile problem, the goal is to construct a data structure such that given a predicate (query rectangle R and an interval θ) report all indexes J such that j ∈ J if and only if |P j ∩ R|/|P j | ∈ [N]. For the Ptile problem, the goal is to construct a data structure such that given a predicate (query vector v → and an interval θ) report all indexes J such that j ∈ J if and only if ω k (P j ,v → )∈ θ, where ω k (p j ,v → ) is the score (inner-product) of the k -th largest projection of P j on 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 Ø(N) space data structures with Ø(N) preprocessing time, that can answer Ptile and Pref queries in Ø(1+OUT) time, where OUT is the output size. The data structures return a set of indexes J such that: i) for every P i that satisfies the predicate, i ∈ J and ii) if j ∈ J then P j satisfies the predicate up to an additive error of ε+2δ, where ε is an arbitrarily small constant and δ is the error of the synopses.
- 9 June 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (2) , 1-26
Open AccessA Theoretical Framework for Distribution-Aware Dataset Search
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 ={P 1 ,..., P N } be a repository of N datasets, such that each P i ⊂ ℝ d , where 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 P . In the federated setting we are given a synopsis S P i which is a compressed representation of P i that captures the structure of P i , for every i ∈ [N]. For the Ptile problem, the goal is to construct a data structure such that given a predicate (query rectangle R and an interval θ) report all indexes J such that j ∈ J if and only if |P j ∩ R|/|P j | ∈ [N]. For the Ptile problem, the goal is to construct a data structure such that given a predicate (query vector v → and an interval θ) report all indexes J such that j ∈ J if and only if ω k (P j ,v → )∈ θ, where ω k (p j ,v → ) is the score (inner-product) of the k -th largest projection of P j on 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 Ø(N) space data structures with Ø(N) preprocessing time, that can answer Ptile and Pref queries in Ø(1+OUT) time, where OUT is the output size. The data structures return a set of indexes J such that: i) for every P i that satisfies the predicate, i ∈ J and ii) if j ∈ J then P j satisfies the predicate up to an additive error of ε+2δ, where ε is an arbitrarily small constant and δ is the error of the synopses.
- Open Access
- 9 June 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (2) , 1-25
Smallest Synthetic Witnesses for Conjunctive Queries
Given a self-join-free conjunctive query Q and a set of tuples S , a synthetic witness D is a database instance such that the result of Q on D is S . In this work, we are interested in two problems. First, the existence problem ESW decides whether any synthetic witness D exists. Second, given that a synthetic witness exists, the minimization problem SSW computes a synthetic witness of minimal size. The SSW problem is related to the smallest witness problem recently studied by Hu and Sintos [22]; however, the objective and the results are inherently different. More specifically, we show that SSW is poly-time solvable for a wider range of queries. Interestingly, in some cases, SSW is related to optimization problems in other domains, such as the role mining problem in data mining and the edge concentration problem in graph drawing. Solutions to ESW and SSW are of practical interest, e.g., for test database generation for applications accessing a database and for data compression by encoding a dataset S as a pair of a query Q and database D . We prove that ESW is in P, presenting a simple algorithm that, given any S , decides whether a synthetic witness exists in polynomial time in the size of S . Next, we focus on the SSW problem. We show an algorithm that computes a minimal synthetic witness in polynomial time with respect to the size of S for any query Q that has the head-domination property. If Q does not have such a property, then SSW is generally hard. More specifically, we show that for the class of path queries (of any constant length), SSW cannot be solved in polynomial time unless P = NP. We then extend this hardness result to the class of Berge-acyclic queries that do not have the head-domination property, obtaining a full dichotomy of SSW for Berge-acyclic queries. Finally, we investigate the hardness of SSW beyond Berge-acyclic queries by showing that SSW cannot be solved in polynomial time for some cyclic queries unless P = NP.
- 9 June 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (2) , 1-25
Open AccessSmallest Synthetic Witnesses for Conjunctive Queries
Given a self-join-free conjunctive query Q and a set of tuples S , a synthetic witness D is a database instance such that the result of Q on D is S . In this work, we are interested in two problems. First, the existence problem ESW decides whether any synthetic witness D exists. Second, given that a synthetic witness exists, the minimization problem SSW computes a synthetic witness of minimal size. The SSW problem is related to the smallest witness problem recently studied by Hu and Sintos [22]; however, the objective and the results are inherently different. More specifically, we show that SSW is poly-time solvable for a wider range of queries. Interestingly, in some cases, SSW is related to optimization problems in other domains, such as the role mining problem in data mining and the edge concentration problem in graph drawing. Solutions to ESW and SSW are of practical interest, e.g., for test database generation for applications accessing a database and for data compression by encoding a dataset S as a pair of a query Q and database D . We prove that ESW is in P, presenting a simple algorithm that, given any S , decides whether a synthetic witness exists in polynomial time in the size of S . Next, we focus on the SSW problem. We show an algorithm that computes a minimal synthetic witness in polynomial time with respect to the size of S for any query Q that has the head-domination property. If Q does not have such a property, then SSW is generally hard. More specifically, we show that for the class of path queries (of any constant length), SSW cannot be solved in polynomial time unless P = NP. We then extend this hardness result to the class of Berge-acyclic queries that do not have the head-domination property, obtaining a full dichotomy of SSW for Berge-acyclic queries. Finally, we investigate the hardness of SSW beyond Berge-acyclic queries by showing that SSW cannot be solved in polynomial time for some cyclic queries unless P = NP.
- Open Access
- 4 November 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (5) , 1-27
Computing A Well-Representative Summary of Conjunctive Query Results
Data summarization is a powerful approach to deal with large-scale data analytics, which has wide applications in web search, recommendation systems, approximate query processing, etc. It computes a small, compact summary that preserves vital properties of the original data. In this paper, we study the data summarization problem of conjunctive query results, i.e., computing a k-size subset of a conjunctive query output, for any given k>0, that optimizes a certain objective. More specifically, we are interested in two commonly studied objectives: cohesion, which measures the maximum distance between a tuple in the query result tuples and its closest tuple in the summary (k-center clustering); and diversity, which measures the pairwise distances between the summary items. A simple approach that computes the entire query output and then applies existing algorithms on top of these materialized tuples suffers from high computational complexity because the query output can be large, e.g., for a relational database of N tuples, the number of result tuples can be N O(1). We propose O(1)-approximation algorithms that compute well-representative summaries of size k in time O(N*k O(1) ), or even O(N+ k O(1) ) in some cases, without computing all result tuples. We also propose the first efficient (2+\eps)-approximation algorithm for the k-center clustering problem over relational data. Our main idea is to formulate a few oracles that enable us to access specific query result tuples with certain properties, to show how these oracles can be implemented efficiently, and to compute desired summaries with few invocations of these oracles.
- 4 November 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (5) , 1-27
Open AccessComputing A Well-Representative Summary of Conjunctive Query Results
Data summarization is a powerful approach to deal with large-scale data analytics, which has wide applications in web search, recommendation systems, approximate query processing, etc. It computes a small, compact summary that preserves vital properties of the original data. In this paper, we study the data summarization problem of conjunctive query results, i.e., computing a k-size subset of a conjunctive query output, for any given k>0, that optimizes a certain objective. More specifically, we are interested in two commonly studied objectives: cohesion, which measures the maximum distance between a tuple in the query result tuples and its closest tuple in the summary (k-center clustering); and diversity, which measures the pairwise distances between the summary items. A simple approach that computes the entire query output and then applies existing algorithms on top of these materialized tuples suffers from high computational complexity because the query output can be large, e.g., for a relational database of N tuples, the number of result tuples can be N O(1). We propose O(1)-approximation algorithms that compute well-representative summaries of size k in time O(N*k O(1) ), or even O(N+ k O(1) ) in some cases, without computing all result tuples. We also propose the first efficient (2+\eps)-approximation algorithm for the k-center clustering problem over relational data. Our main idea is to formulate a few oracles that enable us to access specific query result tuples with certain properties, to show how these oracles can be implemented efficiently, and to compute desired summaries with few invocations of these oracles.
- Open Access
- 4 November 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (5) , 1-27
Improved Approximation Algorithms for Relational Clustering
Clustering plays a crucial role in computer science, facilitating data analysis and problem-solving across numerous fields. By partitioning large datasets into meaningful groups, clustering reveals hidden structures and relationships within the data, aiding tasks such as unsupervised learning, classification, anomaly detection, and recommendation systems. Particularly in relational databases, where data is distributed across multiple tables, efficient clustering is essential yet challenging due to the computational complexity of joining tables. This paper addresses this challenge by introducing efficient algorithms for k-median and k-means clustering on relational data without the need for pre-computing the join query results. For the relational k-median clustering, we propose the first efficient relative approximation algorithm. For the relational k-means clustering, our algorithm significantly improves both the approximation factor and the running time of the known relational k-means clustering algorithms, which suffer either from large constant approximation factors, or expensive running time. Given a join query q and a database instance D of O(N) tuples, for both k-median and k-means clustering on the results of q on D, we propose randomized (1+ε)γ-approximation algorithms that run in roughly O(k 2 N fhw )+T_γ(k 2 ) time, where ε ∈ (0,1) is a constant parameter decided by the user, \fhw is the fractional hyper-tree width of Q, while γ and T_γ(x) represent the approximation factor and the running time, respectively, of a traditional clustering algorithm in the standard computational setting over x points.
- 4 November 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (5) , 1-27
Open AccessImproved Approximation Algorithms for Relational Clustering
Clustering plays a crucial role in computer science, facilitating data analysis and problem-solving across numerous fields. By partitioning large datasets into meaningful groups, clustering reveals hidden structures and relationships within the data, aiding tasks such as unsupervised learning, classification, anomaly detection, and recommendation systems. Particularly in relational databases, where data is distributed across multiple tables, efficient clustering is essential yet challenging due to the computational complexity of joining tables. This paper addresses this challenge by introducing efficient algorithms for k-median and k-means clustering on relational data without the need for pre-computing the join query results. For the relational k-median clustering, we propose the first efficient relative approximation algorithm. For the relational k-means clustering, our algorithm significantly improves both the approximation factor and the running time of the known relational k-means clustering algorithms, which suffer either from large constant approximation factors, or expensive running time. Given a join query q and a database instance D of O(N) tuples, for both k-median and k-means clustering on the results of q on D, we propose randomized (1+ε)γ-approximation algorithms that run in roughly O(k 2 N fhw )+T_γ(k 2 ) time, where ε ∈ (0,1) is a constant parameter decided by the user, \fhw is the fractional hyper-tree width of Q, while γ and T_γ(x) represent the approximation factor and the running time, respectively, of a traditional clustering algorithm in the standard computational setting over x points.