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)
Incoming Non-self Citations Over Time
Authors
- 1. Xingguang Chen (Chinese University of Hong Kong)
- 2. Sibo Wang (Chinese University of Hong Kong)
BibTeX Citation
@inproceedings{chen_sigmod21,
title = {{Efficient Approximate Algorithms for Empirical Entropy and Mutual Information}},
author = {Chen, Xingguang and Wang, Sibo},
series = {{SIGMOD} '21},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3448016.3457255},
url = {https://dl.acm.org/doi/10.1145/3448016.3457255},
year = {2021}
}Incoming Citations (Sorted by Pagerank)
Showing 6 of 6 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 7,455 | Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks | 2023 | SIGMOD | 5.6127752e-05 |
| 8,492 | ShadowAQP: Efficient Approximate Group-by and Join Query via Attribute-oriented Sample Size Allocation and Data Generation | 2023 | VLDB | 5.4145838e-05 |
| 8,850 | Learning-based Property Estimation with Polynomials | 2024 | SIGMOD | 5.3577504e-05 |
| 9,972 | Cents: A Flexible and Cost-Effective Framework for LLM-Based Table Understanding | 2025 | VLDB | 5.1845938e-05 |
| 10,339 | Aegis: A Correlation-Based Data Masking Advisor for Data-Sharing Ecosystems | 2026 | SIGMOD | 5.093636e-05 |
| 11,418 | Efficient Approximation Framework for Attribute Recommendation | 2023 | SIGMOD | 5.093636e-05 |
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 885 | Finding Frequent Items in Data Streams | 2008 | VLDB | 0.00013419017 |
| 2,225 | HubPPR: Effective Indexing for Approximate Personalized PageRank | 2017 | VLDB | 8.9183159e-05 |
| 5,741 | Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks | 2018 | SIGMOD | 6.1029326e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 680 | Creating Probabilistic Databases from Information Extraction Models | 2006 | VLDB |
| 2 | 10,186 | Accelerating Approximate Analytical Join Queries over Unstructured Data with Statistical Guarantees | 2026 | SIGMOD |
| 3 | 12,176 | Resource-oriented Approximation for Frequent Itemset Mining from Bursty Data Streams | 2014 | SIGMOD |
| 4 | 2,608 | A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries | 2001 | SIGMOD |
| 5 | 50 | Efficient Query Evaluation on Probabilistic Databases | 2004 | VLDB |
| 6 | 6,120 | Finding Frequent Items in Probabilistic Data | 2008 | SIGMOD |
| 7 | 7,657 | Mining Frequent Itemsets over Uncertain Databases | 2012 | VLDB |
| 8 | 11,418 | Efficient Approximation Framework for Attribute Recommendation | 2023 | SIGMOD |
| 9 | 1,605 | Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases | 2008 | VLDB |
| 10 | 8,191 | Probabilistic Database Summarization for Interactive Data Exploration | 2017 | VLDB |