1. A system comprising: one or more computers configured to perform operations comprising: storing a plurality of constrained training examples, a plurality of first training examples, and a plurality of constraints for the constrained training examples, wherein, for each constrained training example, there is at least one constraint in the plurality of constraints, and the constraint either identifies a particular other constrained training example as a neighbor of the constrained training example or identifies a particular other constrained training example as a non-neighbor of the constrained training example, wherein the plurality of first training examples is initialized to include the constrained training examples and one or more non-constrained training examples for which there is no constraint in the plurality of constraints; generating an adjusted covariance matrix from the plurality of constrained training examples, the plurality of first training examples, and the plurality of constraints, wherein the adjusted covariance matrix is generated by adding an accuracy term and a regularizer term, wherein the accuracy term is derived from the constrained training examples and the constraints, and wherein the regularizer term represents variance in projections that result from applying a weight vector to the first training examples; and generating an ordered sequence of hash functions from the adjusted covariance matrix, wherein each hash function defines a mapping of features of an item to a corresponding bit in an ordered sequence of bits, wherein the hash function for a particular bit determines a value of the particular bit according to a respective weight vector for the hash function.