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: 11805
Venue: VLDB
Year: 2018
Pagerank: 6.4428362e-05
Overall Rank: 4,926 | 66.21%
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,392	Northstar: An Interactive Data Science System	2018	VLDB	0.00010936065
1,431	Towards Scalable Dataframe Systems	2020	VLDB	0.00010807221
3,869	Smile: A System to Support Machine Learning on EEG Data at Scale	2019	VLDB	7.0609879e-05
4,084	Comprehensive and Efficient Workload Compression	2021	VLDB	6.9151691e-05
10,002	COMPARE: Accelerating Groupwise Comparison in Relational Databases for Data Analytics	2021	VLDB	5.1814573e-05
10,933	LakeVisage: Towards Scalable, Flexible and Interactive Visualization Recommendation for Data Discovery over Data Lakes	2025	VLDB	5.093636e-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.00077458002
76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00037054261
178	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00026881845
267	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022798161
274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022645621
307	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021792475
327	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00021091539
410	SeeDB: Efficient Data-Driven Visualization Recommendations to Support Visual Analytics	2015	VLDB	0.0001890421
435	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.000185063
508	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00017275873
553	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00016590619
794	Bitmap Index Design and Evaluation	1998	SIGMOD	0.00013969303
909	Dynamic Sample Selection for Approximate Query Processing	2003	SIGMOD	0.00013291205
986	Effortless Data Exploration with zenvisage: An Expressive and Interactive Visual Analytics System	2017	VLDB	0.0001281777
1,166	ICICLES: Self-tuning Samples for Approximate Query Answering	2000	VLDB	0.00011850439
1,472	M4: A Visualization-Oriented Time Series Data Aggregation	2014	VLDB	0.00010668946
1,605	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00010229844
1,634	Rapid Sampling for Visualizations with Ordering Guarantees	2015	VLDB	0.00010163938
1,664	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	0.00010070362
1,827	G-OLA: Generalized On-Line Aggregation for Interactive Analysis on Big Data	2015	SIGMOD	9.6690206e-05
1,962	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	9.3978414e-05
2,109	Analytic Database Technologies for a New Kind of User - The Data Enthusiast	2012	SIGMOD	9.1548967e-05
3,042	Continuous Sampling for Online Aggregation Over Multiple Queries	2010	SIGMOD	7.8231049e-05
3,288	I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making	2017	VLDB	7.5578177e-05
5,906	Approximate Query Engines: Commercial Challenges and Research Opportunities	2017	SIGMOD	6.0457047e-05
7,275	Efficient Evaluation of Object-Centric Exploration Queries for Visualization	2015	VLDB	5.658426e-05

Semantically Similar Papers

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