Local descriptors are extracted from digital image information and digital depth information related to digital images. The local descriptors convey appearance description information and shape description information related to the digital images. Global representations of the one or more digital images are generated based on the extracted local descriptors, and are hashed. Visual search queries are generated based on the hashed global representations. The visual search queries include fused appearance description information and shape description information conveyed in the local descriptors. The fusing may occur before the global representations are generated, before the hashing or after the hashing.