A computer-implemented method comprising: receiving a query curve as a sketch query input; identifying a first plurality of direction-oriented points based at least in part on the query curve, wherein each direction-oriented point of the first plurality of direction-oriented points specifies a position of a particular point of the sketch query input and a direction from which the query curve passes the position; and using, by a processor (1802, 1902), the first plurality of direction-oriented points to locate at least one image of a plurality of images having a salient curve that includes a second plurality of direction-oriented points that match at least some of the first plurality of direction-oriented points based at least in part on the query curve by employing an index comprising a third plurality of direction-oriented points associated with salient curves detected for a plurality of down-sampled images corresponding to the plurality of images, said third plurality of direction oriented points serving as index entries associating particular direction-oriented points with identifiers of the plurality of images based on whether one or more of the plurality of corresponding down-sampled images contains one or more salient curves containing the particular direction-oriented points, wherein the plurality of corresponding down-sampled images were previously generated by reducing resolution of corresponding images from the plurality of images, and wherein one or more salient curves for a particular down-sampled image are identified by filtering image curves detected for the particular down-sampled image to remove image curves having a length less than a predetermined threshold. receiving a query curve as a sketch query input; identifying a first plurality of direction-oriented points based at least in part on the query curve, wherein each direction-oriented point of the first plurality of direction-oriented points specifies a position of a particular point of the sketch query input and a direction from which the query curve passes the position; and using, by a processor (1802, 1902), the first plurality of direction-oriented points to locate at least one image of a plurality of images having a salient curve that includes a second plurality of direction-oriented points that match at least some of the first plurality of direction-oriented points based at least in part on the query curve by employing an index comprising a third plurality of direction-oriented points associated with salient curves detected for a plurality of down-sampled images corresponding to the plurality of images, said third plurality of direction oriented points serving as index entries associating particular direction-oriented points with identifiers of the plurality of images based on whether one or more of the plurality of corresponding down-sampled images contains one or more salient curves containing the particular direction-oriented points, wherein the plurality of corresponding down-sampled images were previously generated by reducing resolution of corresponding images from the plurality of images, and wherein one or more salient curves for a particular down-sampled image are identified by filtering image curves detected for the particular down-sampled image to remove image curves having a length less than a predetermined threshold.