A method of segmenting a compressed video containing a plurality of frames into a multi-level hierarchy of video segments. The method comprises the steps of determining differences between the size of successive compressed frames in media time. The method then groups the frames to create a hierarchy of clusters of successive frames as video segments using a clustering process. The clustering process uses the size differences to determine boundaries between clusters at each level of the hierarchy.