You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lens.apache.org by "Rajat Khandelwal (JIRA)" <ji...@apache.org> on 2017/07/10 10:34:00 UTC
[jira] [Updated] (LENS-1452) Optimize Time Union candidate
Algorithm
[ https://issues.apache.org/jira/browse/LENS-1452?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Rajat Khandelwal updated LENS-1452:
-----------------------------------
Attachment: LENS-1452.01.patch
> Optimize Time Union candidate Algorithm
> ---------------------------------------
>
> Key: LENS-1452
> URL: https://issues.apache.org/jira/browse/LENS-1452
> Project: Apache Lens
> Issue Type: Task
> Components: cube
> Reporter: Rajat Khandelwal
> Assignee: Rajat Khandelwal
> Attachments: LENS-1452.01.patch
>
>
> Current algorithm:
> * Create bitmap (equivalent to powerset)
> * from the powerset, add sets which can complete all time ranges as candidates
> * Prune sets which are contained in other sets
> Proposed change:
> The following recursion implemented iteratively:
> {code}
> (ignoring cubeql for clarity)
> getCombinations(candidates) = getCombinationsRecursive(emptyList(), candidates)
> getCombinationsRecursive(incompleteCombinations: List<List<Candidate>>, candidates: List<Candidate>) =
> head, tail = head and tail of linked List candidates
> add head to all elements of incompleteCombinations.
> add {{ [head] }} as one incompleteCombination.
> complete = remove now complete combinations from incompleteCombinations
> return {{complete ++ getCombinationsTailRecursive(incompleteCombinations+[head], tail)}}
> {code}
> The improvement is, that redundant union candidates like {a,b,c} won't be generated if {a,b} is already covering time ranges. This will only generate minimal sets that cover time ranges. So the memory footprint isn't O( 2^n ) anymore.
--
This message was sent by Atlassian JIRA
(v6.4.14#64029)