Despite the hierarchical methods performing best, the state of the art hierarchical algorithms have two significant limitations: they require the full video to be loaded into memory, limiting the videos they can process, and the hierarchical output they produce often overwhelms the user with too much data; it is not always clear which level of the hierarchy should be used. The second part of the talk will discuss how we systematically address these two limitations. We have proposed an approximation framework for streaming hierarchical video segmentation motivated by data stream algorithms: each video frame is processed only once and does not change the segmentation of previous frames. We also propose a new criterion for flattening the hierarchy based on the notion of uniform motion entropy; select segments throughout the hierarchy so as to balance the amount of motion entropy within the selected segments. Time permitting, I will present an example of how video understanding can benefit from using the segmentation: for the video label propagation problem, our supervoxel-based propagation method is significantly more capable than the best of the state of the art pixel-based methods.