DBScholar

Back to papers

Rapid Sampling for Visualizations with Ordering Guarantees

Summary: Proposes sampling algorithms that preserve visual orderings to rapidly generate approximate visualizations (e.g., bar charts) with provable ordering guarantees. Shows optimal sample complexity and practical speedups - orders of magnitude fewer samples and run time than conventional methods, with broad applicability to related visual properties. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h3ed4c72423107070
Venue
VLDB
Year
2015
Pagerank
9.9502569e-05
Overall Rank
1,662 | 88.84%
DOI
10.14778/2735479.2735486
PDF
Download (CC BY-NC-ND 3.0)

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{kim_vldb15,
        title = {{Rapid Sampling for Visualizations with Ordering Guarantees}},
        author = {Kim, Albert and Blais, Eric and Parameswaran, Aditya and Indyk, Piotr and Madden, Sam and Rubinfeld, Ronitt},
        journal = {PVLDB},
        series = {{VLDB} '15},
        volume = {8},
        number = {5},
        pages = {521--532},
        doi = {10.14778/2735479.2735486},
        url = {https://doi.org/10.14778/2735479.2735486},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 31 of 31 citing papers.

Rank Citing Paper Year Venue Pagerank
395 SeeDB: Efficient Data-Driven Visualization Recommendations to Support Visual Analytics 2015 VLDB 0.00019156481
596 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00015782051
1,061 Approximate Query Processing: No Silver Bullet 2017 SIGMOD 0.00012208639
1,216 Overview of Data Exploration Techniques 2015 SIGMOD 0.00011487268
1,370 Towards Scalable Dataframe Systems 2020 VLDB 0.00010895207
2,003 Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee 2016 SIGMOD 9.2071735e-05
2,028 Database Learning: Toward a Database that Becomes Smarter Every Time 2017 SIGMOD 9.1584244e-05
3,100 Lux: Always-on Visualization Recommendations for Exploratory Dataframe Workflows 2022 VLDB 7.64814e-05
3,341 I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making 2017 VLDB 7.4028264e-05
3,417 Revisiting Reuse for Approximate Query Processing 2017 VLDB 7.3184905e-05
3,956 Smile: A System to Support Machine Learning on EEG Data at Scale 2019 VLDB 6.8992907e-05
4,211 Efficient Selection of Geospatial Data on Maps for Interactive and Visualized Exploration 2018 SIGMOD 6.7290558e-05
5,025 Adaptive Sampling for Rapidly Matching Histograms 2018 VLDB 6.3078009e-05
5,930 Hillview: A trillion-cell spreadsheet for big data 2019 VLDB 5.9410245e-05
6,136 OM3: An Ordered Multi-level Min-Max Representation for Interactive Progressive Visualization of Time Series 2023 SIGMOD 5.8738296e-05
6,319 Visualization-aware Time Series Min-Max Caching with Error Bound Guarantees 2024 VLDB 5.8133264e-05
6,519 Fast-Forwarding to Desired Visualizations with zenvisage 2017 CIDR 5.755832e-05
6,857 SpareLLM: Automatically Selecting Task-Specific Minimum-Cost Large Language Models under Equivalence Constraint 2025 SIGMOD 5.6621524e-05
6,878 Towards Democratizing Relational Data Visualization 2019 SIGMOD 5.6563449e-05
7,106 Data Vocalization with CiceroDB 2019 CIDR 5.5991152e-05
7,424 Efficient Evaluation of Object-Centric Exploration Queries for Visualization 2015 VLDB 5.5298149e-05
8,336 LAQy: Efficient and Reusable Query Approximations via Lazy Sampling 2023 SIGMOD 5.3508072e-05
9,583 A Step Toward Deep Online Aggregation 2023 SIGMOD 5.154741e-05
9,972 Secure Sampling for Approximate Multi-party Query Processing 2023 SIGMOD 5.1014161e-05
10,617 Visualization-Oriented Progressive Time Series Transformation 2026 SIGMOD 4.9769913e-05
11,331 LakeVisage: Towards Scalable, Flexible and Interactive Visualization Recommendation for Data Discovery over Data Lakes 2025 VLDB 4.9769913e-05
11,672 Cache-Efficient Top-k Aggregation over High Cardinality Large Datasets 2024 VLDB 4.9769913e-05
11,985 Exploring Ratings in Subjective Databases 2021 SIGMOD 4.9769913e-05
12,148 A Holistic Approach for Query Evaluation and Result Vocalization in Voice-Based OLAP 2019 SIGMOD 4.9769913e-05
12,192 Enabling Data Science for the Majority 2019 VLDB 4.9769913e-05
12,237 Vocalizing Large Time Series Efficiently 2018 VLDB 4.9769913e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 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.00076265429
58 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00040025054
181 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00026384065
267 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00022713652
309 Approximate Query Processing Using Wavelets 2000 VLDB 0.00021376597
335 The Aqua Approximate Query Answering System 1999 SIGMOD 0.000206533
372 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.0001971778
448 Histogram-Based Approximation of Set-Valued Query Answers 1999 VLDB 0.00018121533
564 Congressional Samples for Approximate Answering of Group-By Queries 2000 SIGMOD 0.00016297598
930 Dynamic Sample Selection for Approximate Query Processing 2003 SIGMOD 0.00013009255
1,090 Scalable Approximate Query Processing With The DBO Engine 2007 SIGMOD 0.00012074369
1,112 Google Fusion Tables: Web-Centered Data Management and Collaboration 2010 SIGMOD 0.00011975206
1,951 VizDeck: Self-Organizing Dashboards for Visual Analytics 2012 SIGMOD 9.3168416e-05
2,141 Analytic Database Technologies for a New Kind of User - The Data Enthusiast 2012 SIGMOD 8.9694203e-05
2,650 DEVise: Integrated Querying and Visual Exploration of Large Datasets 1997 SIGMOD 8.1706208e-05
5,459 SeeDB: Visualizing Database Queries Efficiently 2014 VLDB 6.1211089e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 253 Approximate Medians and other Quantiles in One Pass and with Limited Memory 1998 SIGMOD
2 175 Simple Random Sampling from Relational Databases 1986 VLDB
3 2,808 Sampling Time-Based Sliding Windows in Bounded Space 2008 SIGMOD
4 9,941 Faster Visual Analytics through Pixel-Perfect Aggregation 2014 VLDB
5 5,025 Adaptive Sampling for Rapidly Matching Histograms 2018 VLDB
6 450 Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets 1999 SIGMOD
7 6,319 Visualization-aware Time Series Min-Max Caching with Error Bound Guarantees 2024 VLDB
8 8,560 Sampling Big Ideas in Query Optimization 2023 PODS
9 153 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD
10 3,341 I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making 2017 VLDB