Motivated by the needs for efficient indexing structures adapted to real applications in video database, we present a new indexing structure named Kpyr. In Kpyr, we use a clustering algorithm to partition the data space into sub spaces on which we apply Pyramid Technique [1]. We thus reduce the search space concerned by a query and improve the performances. We show that our approach provides interesting and performing experimental results for both K-Nearest Neighbors and Window queries.