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: h7053bafeff42de8d
Venue: PODS
Year: 2024
Pagerank: 5.5049463e-05
Overall Rank: 7,513 | 49.49%
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 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,279	Subset Sampling over Joins	2026	PODS	5.3637624e-05
10,370	Faster Relational Algorithms Using Geometric Data Structures	2026	PODS	4.9793485e-05
10,393	Clustering with Set Outliers and Applications in Relational Clustering	2026	PODS	4.9793485e-05
10,396	Query Answering Under Volume-Based Diversity Functions	2026	PODS	4.9793485e-05
10,852	Fast and Private Max-Sum Diversification	2026	VLDB	4.9793485e-05
11,492	Improved Approximation Algorithms for Relational Clustering	2024	PODS	4.9793485e-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
57	On Random Sampling over Joins	1999	SIGMOD	0.00040108301
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00028633995
255	The History of Histograms (abridged)	2003	VLDB	0.00022981861
275	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022413521
456	Mergeable Summaries	2012	PODS	0.0001791284
795	Random Sampling over Joins Revisited	2018	SIGMOD	0.00013938779
1,173	Wavelet Synopses with Error Guarantees	2002	SIGMOD	0.00011686985
1,936	Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates	2012	PODS	9.3387282e-05
3,494	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	7.2582926e-05
3,992	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	6.8685334e-05
4,642	Efficient Join Synopsis Maintenance for Data Warehouse	2020	SIGMOD	6.4898745e-05
5,989	Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue	2024	PODS	5.9253439e-05
6,221	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	5.8463347e-05
6,545	Ranked Enumeration of Join Queries with Projections	2022	VLDB	5.7515992e-05
7,776	Efficient Indexes for Diverse Top-k Range Queries	2020	PODS	5.4546499e-05
11,492	Improved Approximation Algorithms for Relational Clustering	2024	PODS	4.9793485e-05
11,520	Faster Algorithms for Fair Max-Min Diversification in Rd	2024	SIGMOD	4.9793485e-05

Semantically Similar Papers

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