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,602 | Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks | 2023 | SIGMOD | 5.4868396e-05 |
| 8,659 | ShadowAQP: Efficient Approximate Group-by and Join Query via Attribute-oriented Sample Size Allocation and Data Generation | 2023 | VLDB | 5.2930951e-05 |
| 9,013 | Learning-based Property Estimation with Polynomials | 2024 | SIGMOD | 5.2375369e-05 |
| 10,165 | Cents: A Flexible and Cost-Effective Framework for LLM-Based Table Understanding | 2025 | VLDB | 5.0682654e-05 |
| 10,542 | Aegis: A Correlation-Based Data Masking Advisor for Data-Sharing Ecosystems | 2026 | SIGMOD | 4.9793485e-05 |
| 11,732 | Efficient Approximation Framework for Attribute Recommendation | 2023 | SIGMOD | 4.9793485e-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 |
|---|---|---|---|---|
| 909 | Finding Frequent Items in Data Streams | 2008 | VLDB | 0.00013125647 |
| 2,258 | HubPPR: Effective Indexing for Approximate Personalized PageRank | 2017 | VLDB | 8.7385422e-05 |
| 5,859 | Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks | 2018 | SIGMOD | 5.9682458e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 2,354 | Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries | 2008 | VLDB |
| 2 | 10,402 | Accelerating Approximate Analytical Join Queries over Unstructured Data with Statistical Guarantees | 2026 | SIGMOD |
| 3 | 12,467 | Resource-oriented Approximation for Frequent Itemset Mining from Bursty Data Streams | 2014 | SIGMOD |
| 4 | 2,655 | A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries | 2001 | SIGMOD |
| 5 | 51 | Efficient Query Evaluation on Probabilistic Databases | 2004 | VLDB |
| 6 | 6,252 | Finding Frequent Items in Probabilistic Data | 2008 | SIGMOD |
| 7 | 7,810 | Mining Frequent Itemsets over Uncertain Databases | 2012 | VLDB |
| 8 | 11,732 | Efficient Approximation Framework for Attribute Recommendation | 2023 | SIGMOD |
| 9 | 1,635 | Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases | 2008 | VLDB |
| 10 | 8,363 | Probabilistic Database Summarization for Interactive Data Exploration | 2017 | VLDB |