Adaptive Sampling for Rapidly Matching Histograms

Summary: FastMatch interactively retrieves top-k histograms nearest a user-specified distribution under L1 distance. HistSim combines theoretically sound adaptive sampling with asynchronous, block-based execution, achieving near-perfect accuracy and up to 35× speedups. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h2ba2ba4452778072
Venue: VLDB
Year: 2018
Pagerank: 6.3106761e-05
Overall Rank: 5,021 | 66.25%
DOI: 10.14778/3231751.3231753

Incoming Non-self Citations Over Time

Authors

1. Stephen Macke (University of Illinois Urbana-Champaign)
2. Yiming Zhang (Shanghai Jiao Tong University)
3. Silu Huang (University of Illinois Urbana-Champaign)
4. Aditya Parameswaran (University of Illinois Urbana-Champaign)

BibTeX Citation

@article{macke_vldb18,
        title = {{Adaptive Sampling for Rapidly Matching Histograms}},
        author = {Macke, Stephen and Zhang, Yiming and Huang, Silu and Parameswaran, Aditya},
        journal = {PVLDB},
        series = {{VLDB} '18},
        volume = {11},
        number = {10},
        pages = {1262--1275},
        doi = {10.14778/3231751.3231753},
        url = {https://doi.org/10.14778/3231751.3231753},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,369	Towards Scalable Dataframe Systems	2020	VLDB	0.00010899832
1,409	Northstar: An Interactive Data Science System	2018	VLDB	0.00010743451
3,815	Comprehensive and Efficient Workload Compression	2021	VLDB	7.0075744e-05
3,955	Smile: A System to Support Machine Learning on EEG Data at Scale	2019	VLDB	6.9025583e-05
10,189	COMPARE: Accelerating Groupwise Comparison in Relational Databases for Data Analytics	2021	VLDB	5.0651993e-05
11,323	LakeVisage: Towards Scalable, Flexible and Interactive Visualization Recommendation for Data Discovery over Data Lakes	2025	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 26 of 26 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
9	Online Aggregation	1997	SIGMOD	0.00076195956
79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00036487763
181	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00026389403
275	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022413521
283	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022214789
309	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021384073
336	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00020657819
395	SeeDB: Efficient Data-Driven Visualization Recommendations to Support Visual Analytics	2015	VLDB	0.00019165452
448	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.00018129161
519	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00016942879
564	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00016296665
773	Bitmap Index Design and Evaluation	1998	SIGMOD	0.00014084831
924	Effortless Data Exploration with zenvisage: An Expressive and Interactive Visual Analytics System	2017	VLDB	0.00013057136
931	Dynamic Sample Selection for Approximate Query Processing	2003	SIGMOD	0.00013011667
1,183	ICICLES: Self-tuning Samples for Approximate Query Answering	2000	VLDB	0.00011616705
1,500	M4: A Visualization-Oriented Time Series Data Aggregation	2014	VLDB	0.0001046347
1,635	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00010017067
1,661	Rapid Sampling for Visualizations with Ordering Guarantees	2015	VLDB	9.9535453e-05
1,678	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.9088372e-05
1,868	G-OLA: Generalized On-Line Aggregation for Interactive Analysis on Big Data	2015	SIGMOD	9.4754064e-05
2,000	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	9.2112617e-05
2,139	Analytic Database Technologies for a New Kind of User - The Data Enthusiast	2012	SIGMOD	8.973568e-05
3,087	Continuous Sampling for Online Aggregation Over Multiple Queries	2010	SIGMOD	7.6624333e-05
3,341	I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making	2017	VLDB	7.4063139e-05
6,004	Approximate Query Engines: Commercial Challenges and Research Opportunities	2017	SIGMOD	5.9166815e-05
7,421	Efficient Evaluation of Object-Centric Exploration Queries for Visualization	2015	VLDB	5.5324308e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,339	Extensible and Robust Evaluation of Similarity Queries	2025	VLDB
2	866	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD
3	1,826	Effective Use of Block-Level Sampling in Statistics Estimation	2004	SIGMOD
4	5,004	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS
5	488	FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets	1995	SIGMOD
6	242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB
7	448	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB
8	742	Dynamic Multidimensional Histograms	2002	SIGMOD
9	1,661	Rapid Sampling for Visualizations with Ordering Guarantees	2015	VLDB
10	5,534	Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms	2015	PODS