Multimedia retrieval task is faced with increasingly large datasets and variously changing preferences of users in every query. We realize that the high dimensional representation of physical data which previously challenges search algorithms now brings chances to cope with dynamic contexts. In this paper, we introduce a method of building a large-scale video frame retrieval environment with a fast search algorithm that handles user's dynamic contexts of querying by imagination and controlling response time. The search algorithm quickly finds an initial candidate, which has highest-match possibility, and then iteratively traverses along feature indexes to find other neighbor candidates until the input time bound is elapsed. The experimental studies based on the video frame retrieval system show the feasibility and effectiveness of our proposed search algorithm that can return results in a fraction of a second with a high success rate and small deviation to the expected ones. Moreover, its potential is clear that it can scale to large dataset while preserving its search performance.