Rajat Khandelwal created LENS-1452:
--------------------------------------
Summary: 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
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)
