Accurate battery capacity prediction is important to ensure reliable battery operation and reduce the cost. However, the complex nature of battery degradation and the presence of capacity regeneration phenomenon render the prediction task very challenging. To address this problem, this paper proposes a novel and efficient algorithm to predict the battery capacity trajectory in a multi-cell setting. The proposed method is a new variant of Gaussian process regression (GPR) model, and it utilizes similar trajectories in the historical data to enhance the prediction of desired capacity trajectory. More importantly, the proposed method adds no extra computation cost to the standard GPR. To demonstrate the effectiveness of the proposed method, validation tests on two different battery datasets are implemented in the case studies. The prediction results and the computation cost are carefully benchmarked with cutting-edge GPR approaches for battery capacity prediction.