Comparison among different partitioning approaches (IMAGE)
Caption
Given a sequence of input data belonging to the same hierarchical level, performing a number-balanced partition (a) ensures that the number of nodes in the subsets is balanced and that the temporal coherence is well preserved. However, because the total values of the two subsets vary dramatically (8+9 vs. 1+2), the corresponding rectangles have poor aspect ratios. A greedy searching algorithm for the sizebalanced partition problem (b) sorts all nodes by their sizes in descending order and assigns large nodes first. Even though the two subsets at the first level are perfectly balanced in size, the split at the second level cannot be balanced because of node size variation within the subsets. Like the greedy strategy, the proposed size-balanced partition (c) also orders the input nodes according to their sizes, however, instead of alternatively assigning nodes to the two subsets, the small nodes are kept in the same subset and thus reduce size variation within subsets. This allows for balanced partitions at all hierarchical levels. When there is a need to maintain the order of nodes in the input sequence, the proposed sequence-balanced partition (d) divides the sequence directly without attempting to achieve better temporal coherence when handling dynamic datasets.
Credit
Beijing Zhongke Journal Publising Co. Ltd.
Usage Restrictions
Credit must be given to the creator.
License
CC BY