1. A computer-implemented method of segmenting a compressed video, containing a plurality of frames, into a multi-level hierarchy of video segments, said method comprising: determining differences between the size of successive compressed frames in media time; sorting successive pairs of the frames in increasing order of the determined size difference; using a successive pair of the frames as a seed for a new cluster; selecting a neighboring frame at one boundary of the new cluster; grouping the frames to create a hierarchy of clusters of successive frames as video segments using a clustering process operative upon at least one said seed, wherein: (a) if the selected neighboring frame does not belong to an existing cluster, then the selected neighboring frame is included in the new cluster if the selected neighboring frame meets a predetermined set of clustering criteria for frames; and (b) if the selected neighboring frame belongs to an existing cluster, then the existing cluster is included as a child cluster of the new cluster if the existing cluster meets a predetermined set of clustering criteria for child clusters; and storing at least a representation of the segments.