15. The medium of claim 13 wherein the document is an unknown document and the signature is a query signature, the computer program further comprising instructions for causing a computer to compare the query signature to known signatures generated from a set of known documents to determine whether the unknown document is a duplicate of one of the set of known documents.
13. A computer-usable medium storing a computer program used in detecting a duplicate document, the computer program comprising instructions for causing a computer to perform the following operations: generate at least a first and second lexicon of attributes, the second lexicon being generated by eliminating a random fraction of attributes from the first lexicon independently of a characteristic of the attributes in the first lexicon; determine unique attributes in a document; determine a first set of intersection attributes based on an intersection between the unique attributes in the document and the first lexicon; determine a second set of intersection attributes based on an intersection between the unique attributes in the document and the second lexicon; calculate a first sub-signature based on the first set of intersection attributes; calculate a second sub-signature based on the second set of intersection attributions; set a signature of the document to include the first and second sub-signatures; and access a second signature associated with a second document, the second signature including a third sub-signature calculated based on an intersection between unique attributes in the second document and the first lexicon, and a fourth sub-signature calculated based on an intersection between unique attributes in the second document and the second lexicon; and if the first sub-signature matches the third sub-signature or if the second sub-signature matches the fourth sub-signature, determine that the document and the second document are duplicates.