Patent ID: 8510236

Claim:
A system, comprising: one or more computers configured to perform operations comprising: storing a plurality of training examples and a plurality of constraints for the training examples, wherein, for one or more constrained training examples in the plurality of training examples, there is at least one constraint in the plurality of constraints, and the constraint either identifies a particular other training example in the plurality of training examples as a neighbor of the constrained training example or identifies a particular other training example in the plurality of training examples as a non-neighbor of the constrained training example; initializing a current constraint weight for each of the constraints to a respective initial value; generating an ordered sequence of hash functions, wherein each hash function defines a mapping of features of an item to a bit in a corresponding ordered sequence of bits, wherein the hash function for a particular bit determines the 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 maximizes an accuracy measure, wherein the accuracy measure is derived from a number of constraints satisfied by the weight vector and a number of constraints not satisfied by the weight vector and the current constraint weight of each constraint; and updating the current constraint weights for use in calculating a weight vector of a next hash function in the sequence, wherein the current constraint weights are updated to increase a magnitude of the current constraint weight of any constraint not satisfied by the determined weight vector for the current hash function; and storing the determined weight vectors in a data store.