[KYLIN-943] Approximate TopN supported by Cube

• Type: New Feature
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: v1.4.0
• Assignee: Shao Feng Shi
• Reporter: Hongbin Ma
• Created: 11/Aug/15 09:03
• Updated: 17/Mar/16 07:37
• Resolved: 09/Feb/16 07:23

Description

SpaceSaving (TopN algorithm) code could copy from https://github.com/addthis/stream-lib/blob/master/src/main/java/com/clearspring/analytics/stream/StreamSummary.java
We don’t need the whole stream-lib, but just one (or two) classes is enough. Make sure you give credit to stream-lib in class comment.

In order to run SpaceSaving in parallel, the TopN has to be merged using http://arxiv.org/pdf/1401.0702.pdf. No existing impl as I searched, we have to implement ourselves.

Cheers
Yang

From: Li, Yang
Sent: 2015年8月7日 12:43
To: DL-eBay-Kylin
Subject: Distributed TopN papers

The basic algorithm
[1] https://icmi.cs.ucsb.edu/research/tech_reports/reports/2005-23.pdf

Its application in distributed system
[2] http://www.cs.utah.edu/~jeffp/papers/merge-summ-TODS.pdf
[3] http://www.crm.umontreal.ca/pub/Rapports/3300-3399/3322.pdf

Cheers
Yang

Issue Links

• relates to: KYLIN-1178 Build dictionary in Hadoop cluster
• requires: KYLIN-942 Cube parallel scan on Hbase

Sub-Tasks

• Support fixedLength encoding for TopN measure: Closed