TY - JOUR
T1 - Continuous prefetch for interactive data applications
AU - Mohammed, Haneen
AU - Wei, Ziyun
AU - Wu, Eugene
AU - Netravali, Ravi
N1 - Funding Information:
Thanks to Dan Rubensein, Adam Elmachtoub for advice on the ILP formulation; Thibault Sellam, Mengyang Liu on early system versions; NSF IIS 1845638, 1564049, 1527765, and CNS-1943621.
Publisher Copyright:
© 2020, VLDB Endowment.
PY - 2020/7/1
Y1 - 2020/7/1
N2 - Interactive data visualization and exploration (DVE) applications are often network-bottlenecked due to bursty request patterns, large response sizes, and heterogeneous deployments over a range of networks and devices. This makes it difficult to ensure consistently low response times (< 100ms). Khameleon is a framework for DVE applications that uses a novel combination of prefetching and response tuning to dynamically trade-off response quality for low latency. Khameleon exploits DVE's approximation tolerance: immediate lower-quality responses are preferable to waiting for complete results. To this end, Khameleon progressively encodes responses, and runs a server-side scheduler that proactively streams portions of responses using available bandwidth to maximize user-perceived interactivity. The scheduler involves a complex optimization based on available resources, predicted user interactions, and response quality levels; yet, decisions must also be made in real-time. To overcome this, Khameleon uses a fast greedy heuristic that closely approximates the optimal approach. Using image exploration and visualization applications with real user interaction traces, we show that across a wide range of network and client resource conditions, Khameleon outperforms existing prefetching approaches that benefit from perfect prediction models: Khameleon always lowers response latencies (typically by 2-3 orders of magnitude) while keeping response quality within 50-80%.
AB - Interactive data visualization and exploration (DVE) applications are often network-bottlenecked due to bursty request patterns, large response sizes, and heterogeneous deployments over a range of networks and devices. This makes it difficult to ensure consistently low response times (< 100ms). Khameleon is a framework for DVE applications that uses a novel combination of prefetching and response tuning to dynamically trade-off response quality for low latency. Khameleon exploits DVE's approximation tolerance: immediate lower-quality responses are preferable to waiting for complete results. To this end, Khameleon progressively encodes responses, and runs a server-side scheduler that proactively streams portions of responses using available bandwidth to maximize user-perceived interactivity. The scheduler involves a complex optimization based on available resources, predicted user interactions, and response quality levels; yet, decisions must also be made in real-time. To overcome this, Khameleon uses a fast greedy heuristic that closely approximates the optimal approach. Using image exploration and visualization applications with real user interaction traces, we show that across a wide range of network and client resource conditions, Khameleon outperforms existing prefetching approaches that benefit from perfect prediction models: Khameleon always lowers response latencies (typically by 2-3 orders of magnitude) while keeping response quality within 50-80%.
UR - http://www.scopus.com/inward/record.url?scp=85091117110&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85091117110&partnerID=8YFLogxK
U2 - 10.14778/3407790.3407826
DO - 10.14778/3407790.3407826
M3 - Article
AN - SCOPUS:85091117110
SN - 2150-8097
VL - 13
SP - 2297
EP - 2311
JO - Proceedings of the VLDB Endowment
JF - Proceedings of the VLDB Endowment
IS - 11
ER -