The video descriptor generation device includes an each-picture feature extraction unit which extracts a feature from a video for each picture which is a frame or a field, and outputs an each-picture feature; an inter-picture feature difference calculation unit which calculates an inter-picture feature difference, which is a difference between features of pictures, from the each-picture features as a difference feature, and calculates a difference feature information amount indicating an amount of information of the difference feature; an additional feature extraction unit which calculates a feature to be added as an additional feature from the video; and a feature combining unit which, if the volume of the difference feature information amount is smaller than a certain criterion, constitutes a video descriptor by incorporating the additional feature in addition to the difference feature.