Researchers have presented systems for efficiently analysing video data at scale using sampling algorithms. While these systems effectively leverage the temporal redundancy present in videos, they suffer from three limitations. First, they use traditional video storage formats are tailored for human consumption. Second, they load and decode the entire compressed video in memory before applying the sampling algorithm. Third, the sampling algorithms often require labeled training data obtained using a specific deep learning model. These limitations lead to lower accuracy, higher query execution time, and larger memory footprint. In this paper, we present EKO, a storage engine for efficiently managing video data. EKO relies on two optimizations. First, it uses a novel unsupervised, adaptive sampling algorithm for identifying the key frames in a given video. Second, it stores the identified key frames in a compressed representation that is optimized for machine consumption. We show that EKO improves F1-score by up to 9% compared to the next best performing state-of-the-art unsupervised, sampling algorithms by selecting more representative frames. It reduces query execution time by 3X and memory footprint by 10X in comparison to a widely-used, traditional video storage format.