In one embodiment, a method includes analyzing characteristics of a media program to label parts of the media program with a plurality of labels where parts of the media program that are determined to be substantially similar are labeled with a same label. The method then analyzes different partitionings of a sequence of the labels to determine partitions for the media program based on a weighting function that is configured to weight the different partitionings based on portions created from the partitions in the different partitionings. Then, a partitioning for the media program is outputted based on comparing the different partitionings of the sequence of labels using the weighting function. The outputted partitioning partitions the media program into a set of portions and provides points for insertion of information for a service in the media program.