1. One or more computer-readable storage media devices storing computer-useable instructions that, when used by one or more computing devices, cause the one or more computing devices to perform a method comprising: accessing a plurality of images; segmenting each of the plurality of images into a respective plurality of segments; creating an edgel-based representation and one or more shape-descriptors for the respective plurality of segments for each of the plurality of images; generating, by a processor, an edgel index comprising image data that describes the respective one or more shape-descriptors; receiving at least a portion of a search query; displaying a search suggestion interface with a plurality of search suggestions based on the edgel index and the at least a portion of a search query, wherein at least one search suggestion of the plurality of search suggestions is a visual query refinement interface suggestion, and wherein each search suggestion of the plurality of search suggestions includes a search suggestion edgel-based representation and one or more search suggestion shape-descriptors; receiving a selection of a search suggestion; and comparing the search suggestion edgel-based representation and the one or more search suggestion shape-descriptors of the selected search suggestion with the edgel-based representation and the respective one or more shape-descriptors of for each image of the plurality of images in the edgel index to identify one or more matching image results.