With the advent of search engines, searching the web is now a lot easier and efficient. In order to satisfy the user base, search engines need to constantly update their index to provide latest information and be inline with the dynamic nature of web. Updating an existing index is an expensive and challenging task, and most search engines do an off-line rebuild of entire index from scratch. Although rebuilding the index from scratch solves the problem of keeping the search engines up to date, it is an inefficient process in the current day scenarios. A more viable solution is to incrementally update the existing index on line. We propose, a variant of on-line index maintenance approach leveraging the frequency pattern of queries observed in query logs to attain better trade off between query performance and index update costs.