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 unconstrained training examples for which there is no constraint in the plurality of constraints; generating an ordered sequence of hash functions, 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, wherein generating the sequence of hash functions comprises sequentially determining the weight vector for each hash function, and wherein determining the weight vector for a current hash function in the sequence comprises: determining the weight vector for the current hash function, wherein the determined weight vector for the current hash function maximizes an accuracy measure derived from a number of constraints satisfied by the weight vector and a number of constraints not satisfied by the weight vector, and wherein the weight vector for the current hash function maximizes a variance of values generated by the hash function when the hash function is applied to the first training examples; identifying one or more first training examples to remove from the plurality of first training examples according to the determined weight vector; and updating the plurality of first training examples for use in calculating the weight vector for the next hash function in the sequence, wherein the updating comprises calculating a residual of the first training examples according to the determined weight vector; and storing the determined weight vectors in a data store.