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: 1953
Venue: PODS
Year: 2024
Pagerank: 4.4893996e-05
Overall Rank: 8,521 | 40.78%
DOI: 10.1145/3695835

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,002	Clustering with Set Outliers and Applications in Relational Clustering	2026	PODS	4.1905499e-05
10,007	Query Answering Under Volume-Based Diversity Functions	2026	PODS	4.1905499e-05
10,928	Improved Approximation Algorithms for Relational Clustering	2024	PODS	4.1905499e-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
18	On Random Sampling over Joins	1999	SIGMOD	0.00092569117
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036655704
325	The History of Histograms (abridged)	2003	VLDB	0.00027398081
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.0002737538
398	Mergeable Summaries	2012	PODS	0.00024383201
1,372	Random Sampling over Joins Revisited	2018	SIGMOD	0.0001233325
1,400	Wavelet Synopses with Error Guarantees	2002	SIGMOD	0.0001219602
1,717	Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates	2012	PODS	0.00010768447
4,926	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	5.8184457e-05
5,085	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	5.7040225e-05
5,128	Efficient Join Synopsis Maintenance for Data Warehouse	2020	SIGMOD	5.6728511e-05
6,724	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	4.9449472e-05
7,145	Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue	2024	PODS	4.8139975e-05
7,165	Ranked Enumeration of Join Queries with Projections	2022	VLDB	4.807833e-05
8,921	Efficient Indexes for Diverse Top-k Range Queries	2020	PODS	4.4229886e-05
10,928	Improved Approximation Algorithms for Relational Clustering	2024	PODS	4.1905499e-05
10,964	Faster Algorithms for Fair Max-Min Diversification in Rd	2024	SIGMOD	4.1905499e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,989	Beyond Simple Aggregates: Indexing for Summary Queries	2011	PODS	6.5545373e-05
11,909	Compact Summaries over Large Datasets	2015	PODS	4.1905499e-05
4,060	On the Complexity of Query Result Diversification	2013	VLDB	6.4840236e-05
1,506	Summarizing Relational Databases	2009	VLDB	0.0001159691
8,065	Efficient Computation of Quantiles over Joins	2023	PODS	4.5899218e-05
3,292	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.2598265e-05
8,602	Structure-Aware Sampling: Flexible and Accurate Summarization	2011	VLDB	4.4822166e-05
8,850	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4324268e-05
10,007	Query Answering Under Volume-Based Diversity Functions	2026	PODS	4.1905499e-05
10,928	Improved Approximation Algorithms for Relational Clustering	2024	PODS	4.1905499e-05