Several promising techniques have been recently proposed to bind an image or video to its source acquisition device. These techniques have been intensively studied to address performance issues, but the computational efficiency aspect has not been given due consideration. Considering very large databases, in this paper, we focus on the efficiency of the sensor fingerprint based source device identification technique.1 We propose a novel scheme based on tree structured vector quantization that offers logarithmic improvements in the search complexity as compared to conventional approach. To demonstrate the effectiveness of the proposed approach several experiments are conducted. Our results show that with the proposed scheme major improvement in search time can be achieved.