Approximate nearest neighbor (ANN) search provides computationally viable option for retrieval from large document collection. Hashing based techniques are widely regarded as most efficient methods for ANN based retrieval. It has been established that by combination of multiple features in a multiple kernel learning setup can significantly improve the effectiveness of hash codes. The paper presents a novel image indexing method based on multiple kernel learning, which combines multiple features by combinatorial optimization of time and search complexity. The framework is built upon distance based hashing, where the existing kernel distance based hashing formulation adopts linear combination of kernels in tune with optimum search accuracy. In this direction, a novel multiobjective formulation for optimizing the search time as well as accuracy is proposed which is subsequently solved in Genetic algorithm based solution framework for obtaining the pareto-optimal solutions. We have performed extensive experimental evaluation of proposed concepts on different datasets showing improvement in comparison with the existing methods. © 2014 IEEE.