The multimodal neighborhood signature (MNS) method has given acceptable results both for the color-based image retrieval and the object recognition task. Invariant features computed from neighborhoods with multimodal color density function concisely represent local color content. In this paper, efficiency related issues regarding the MNS algorithm are investigated. Its performance, speed, sensitivity to internal parameters and storage requirements are tested on a standard color object recognition experiment. Very good recognition rate (99.9%) was achieved in real time (0.28 seconds per match). MNS signature size is a few hundred bytes on average - an important property for retrieval from large databases. The algorithmic complexity of signature computation and matching are analyzed and efficient implementations are proposed.