Invention Grant
- Patent Title: Using hierarchical reservoir sampling to compute percentiles at scale
-
Application No.: US14664043Application Date: 2015-03-20
-
Publication No.: US09756122B2Publication Date: 2017-09-05
- Inventor: Mike Wexler , Robert Ames , Ian Flint
- Applicant: Yahoo! Inc.
- Applicant Address: US CA Sunnyvale
- Assignee: Yahoo Holdings, Inc.
- Current Assignee: Yahoo Holdings, Inc.
- Current Assignee Address: US CA Sunnyvale
- Agency: Weaver Austin Villeneuve & Sampson LLP
- Main IPC: G06F15/173
- IPC: G06F15/173 ; H04L29/08 ; H04L12/26 ; H04L12/24

Abstract:
In one embodiment, in a hierarchy of nodes, a master node having two or more child nodes obtains from the two or more child nodes two or more sets of data samples or summaries associated therewith, the two or more sets of data samples being representative of traffic processed via two or more sets of servers corresponding to the two or more child nodes, wherein a size of each of the two or more sets of data samples is proportional to an allocation of traffic among the two or more sets of servers corresponding to the two or more child nodes. Each of the two or more sets of data samples is obtained from a different one of the two or more child nodes and represents traffic processed by a corresponding one of the two or more sets of servers. The master node combines the two or more sets of data samples or summaries associated therewith such that a combined set of data is generated. The master node ascertains a numerical value from the combined set of data.
Public/Granted literature
- US20160277490A1 USING HIERARCHICAL RESERVOIR SAMPLING TO COMPUTE PERCENTILES AT SCALE Public/Granted day:2016-09-22
Information query