Efficient Approximate Algorithms for Empirical Entropy and Mutual Information

Summary: Approximate top-k and filtering for empirical entropy and mutual information with tunable accuracy-time trade-offs. Introduces stopping rules and theoretical bounds, yielding large runtime reductions on real datasets while preserving accurate results and outperforming prior approaches. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6146
Venue: SIGMOD
Year: 2021
Pagerank: 4.6179608e-05
Overall Rank: 7,914 | 44.95%
DOI: 10.1145/3448016.3457255

Incoming Non-self Citations Over Time

Authors

1. Xingguang Chen
2. Sibo Wang

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,451	Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks	2023	SIGMOD	4.7263711e-05
8,835	Learning-based Property Estimation with Polynomials	2024	SIGMOD	4.4394021e-05
9,621	ShadowAQP: Efficient Approximate Group-by and Join Query via Attribute-oriented Sample Size Allocation and Data Generation	2023	VLDB	4.3167167e-05
10,046	Aegis: A Correlation-Based Data Masking Advisor for Data-Sharing Ecosystems	2026	SIGMOD	4.1945683e-05
10,753	Cents: A Flexible and Cost-Effective Framework for LLM-Based Table Understanding	2025	VLDB	4.1945683e-05
11,217	Efficient Approximation Framework for Attribute Recommendation	2023	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
835	Finding Frequent Items in Data Streams	2008	VLDB	0.00016109621
2,242	HubPPR: Effective Indexing for Approximate Personalized PageRank	2017	VLDB	9.218875e-05
6,309	Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks	2018	SIGMOD	5.1167347e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,779	Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries	2008	VLDB	8.1320575e-05
760	Creating Probabilistic Databases from Information Extraction Models	2006	VLDB	0.00017053935
11,978	Resource-oriented Approximation for Frequent Itemset Mining from Bursty Data Streams	2014	SIGMOD	4.1945683e-05
2,808	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD	8.0870741e-05
5,796	Finding Frequent Items in Probabilistic Data	2008	SIGMOD	5.3240234e-05
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057857292
7,633	Mining Frequent Itemsets over Uncertain Databases	2012	VLDB	4.6914549e-05
11,217	Efficient Approximation Framework for Attribute Recommendation	2023	SIGMOD	4.1945683e-05
1,542	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011456321
7,872	Probabilistic Database Summarization for Interactive Data Exploration	2017	VLDB	4.6307184e-05