With the advance of digital photographing technology, large amount of personal photos are created and stored online or in personal computers. To save storage space and transmission bandwidth, we proposed a new photo album compression scheme by using both intra prediction and inter prediction to reduce spatial and temporal redundancy. Specifically, we first cluster the images so that each cluster containing a set of similar images is a group of pictures (GOP) with variable length. A graph framework is proposed then, in which an optimal “IPPP…P” GOP structure is derived from every cluster by finding the minimum spanning tree (MST) at a minimum prediction cost. Finally, the photo album is compressed as a whole like a video sequence, by High Efficiency Video Coding (HEVC), according to the predictive order of the optimal structures. The experimental results show that our scheme achieves around 60% improvement over only using JPEG compression.