SARP: Synopsis-Based Approximate Request Processing for Low Latency and Small Correctness Loss in Cloud Online Services

doi:10.1007/s10766-016-0406-9

CORC > 计算技术研究所 > 中国科学院计算技术研究所 > 中国科学院计算技术研究所期刊论文 > 英文

	SARP: Synopsis-Based Approximate Request Processing for Low Latency and Small Correctness Loss in Cloud Online Services
	Han, Rui 1; Zhan, Jianfeng 1; Vazquez-Poletti Luis, Jose 2
刊名	INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING
	2016-10-01
卷号	44 期号:5 页码:1054-1077
关键词	Cloud online service Approximate request processing Result correctness Synopsis
ISSN号	0885-7458
DOI	10.1007/s10766-016-0406-9
英文摘要	Despite the importance of providing quick responsiveness to user requests for online services, such request processing is very resource expensive when dealing with large-scale service datasets. These often exceed the service providers' budget when services are deployed on a cloud, in which resources are charged in monetary terms. Providing approximate processing results in request processing is a feasible solution for such problem that trades off result correctness (e.g. prediction or query accuracy) for response time reduction. However, existing techniques in this area either use parts of datasets or skip expensive computations to produce approximate results, thus resulting in large losses in result correctness on a tight resource budget. In this paper, we propose Synopsis-based Approximate Request Processing (SARP), a SARP framework to produce approximate results with small correctness losses even using small amount of resources. To achieve this, SARP conducts computations over synopses, which aggregate the statistical information of the entire service dataset at different approximation levels, based on two key ideas: (1) offline synopsis management that generates and maintains a set of synopses that represent the aggregation information of the dataset at different approximation levels. (2) Online synopsis selection that considers both the current resource allocation and the workload status so as to select the synopsis with the maximal length that can be processed within the required response time. We demonstrate the effectiveness of our approach by testing the recommendation services in e-commerce sites using a large, real-world dataset. Using prediction accuracy as the result correctness metric, the results demonstrate: (i) SARP achieves significant response time reduction with very small correctness losses compared to the exact processing results; (ii) using the same processing time, SARP demonstrates a considerable reduction in correctness loss compared to existing approximation techniques.
资助项目	National Natural Science Foundation of China[61502451] ; Key Project of of Guangdong Province, China[2015B010108006] ; Major Program of National Natural Science Foundation of China[61432006] ; Ministerio de Economia y Competitividad from Spain[TIN2015-65469-P]
WOS研究方向	Computer Science
语种	英语
出版者	SPRINGER/PLENUM PUBLISHERS
WOS记录号	WOS:000381150200007
内容类型	期刊论文
源URL	[http://119.78.100.204/handle/2XEOYT63/8228]
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Han, Rui
作者单位	1.Chinese Acad Sci, Inst Comp Technol, Beijing, Peoples R China 2.Univ Complutense Madrid, Madrid, Spain
推荐引用方式 GB/T 7714	Han, Rui,Zhan, Jianfeng,Vazquez-Poletti Luis, Jose. SARP: Synopsis-Based Approximate Request Processing for Low Latency and Small Correctness Loss in Cloud Online Services[J]. INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING,2016,44(5):1054-1077.
APA	Han, Rui,Zhan, Jianfeng,&Vazquez-Poletti Luis, Jose.(2016).SARP: Synopsis-Based Approximate Request Processing for Low Latency and Small Correctness Loss in Cloud Online Services.INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING,44(5),1054-1077.
MLA	Han, Rui,et al."SARP: Synopsis-Based Approximate Request Processing for Low Latency and Small Correctness Loss in Cloud Online Services".INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING 44.5(2016):1054-1077.