Computing A Well-Representative Summary of Conjunctive Query Results

Summary: Computes k-sized summaries of conjunctive query results under cohesion (k-center) and diversity. Leverages oracle-based access to avoid enumeration, yielding O(1)-approximation in near-linear time (in N, poly(k)) and a 2+ε-approximation for k-center on relational data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 1985
Venue: PODS
Year: 2024
Pagerank: 5.3766157e-05
Overall Rank: 8,728 | 40.12%
DOI: 10.1145/3695835

Incoming Non-self Citations Over Time

Authors

1. Pankaj K. Agarwal (Duke University)
2. Aryan Esmailpour (University of Illinois Chicago)
3. Xiao Hu (University of Waterloo)
4. Stavros Sintos (University of Illinois Chicago)
5. Jun Yang (Duke University)

BibTeX Citation

@inproceedings{agarwal_pods24,
        address = {New York, NY, USA},
        series = {{PODS} '24},
        title = {{Computing A Well-Representative Summary of Conjunctive Query Results}},
        url = {https://dl.acm.org/doi/10.1145/3695835},
        doi = {10.1145/3695835},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Agarwal, Pankaj K. and Esmailpour, Aryan and Hu, Xiao and Sintos, Stavros and Yang, Jun},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,719	Subset Sampling over Joins	2026	PODS	5.2319816e-05
10,153	Faster Relational Algorithms Using Geometric Data Structures	2026	PODS	5.093636e-05
10,176	Clustering with Set Outliers and Applications in Relational Clustering	2026	PODS	5.093636e-05
10,180	Query Answering Under Volume-Based Diversity Functions	2026	PODS	5.093636e-05
11,144	Improved Approximation Algorithms for Relational Clustering	2024	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
54	On Random Sampling over Joins	1999	SIGMOD	0.00040810225
149	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00029226907
257	The History of Histograms (abridged)	2003	VLDB	0.00023154793
267	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022798161
451	Mergeable Summaries	2012	PODS	0.00018151445
802	Random Sampling over Joins Revisited	2018	SIGMOD	0.00013907725
1,156	Wavelet Synopses with Error Guarantees	2002	SIGMOD	0.00011929041
1,908	Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates	2012	PODS	9.5010932e-05
3,453	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	7.4004131e-05
3,941	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	7.0074268e-05
4,630	Efficient Join Synopsis Maintenance for Data Warehouse	2020	SIGMOD	6.5955933e-05
5,918	Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue	2024	PODS	6.0427671e-05
6,206	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	5.9443409e-05
6,412	Ranked Enumeration of Join Queries with Projections	2022	VLDB	5.8836116e-05
9,073	Efficient Indexes for Diverse Top-k Range Queries	2020	PODS	5.3251649e-05
11,144	Improved Approximation Algorithms for Relational Clustering	2024	PODS	5.093636e-05
11,175	Faster Algorithms for Fair Max-Min Diversification in Rd	2024	SIGMOD	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,596	On the Complexity of Query Result Diversification	2013	VLDB
2	1,532	Summarizing Relational Databases	2009	VLDB
3	7,286	Efficient Computation of Quantiles over Joins	2023	PODS
4	3,241	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS
5	10,153	Faster Relational Algorithms Using Geometric Data Structures	2026	PODS
6	7,419	Structure-Aware Sampling: Flexible and Accurate Summarization	2011	VLDB
7	9,009	Efficient Approximations of Conjunctive Queries	2012	PODS
8	5,383	Compressed Representations of Conjunctive Query Results	2018	PODS
9	10,180	Query Answering Under Volume-Based Diversity Functions	2026	PODS
10	11,144	Improved Approximation Algorithms for Relational Clustering	2024	PODS