Method to efficiently partition large hyperlinked databases by hyperlink structure

A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for partitioning a database containing a plurality of documents into desired and undesired type documents, the plurality of documents containing text and/or links to and from other documents in the database, the method comprising the steps of:

• providing a source document of the desired type, the source document including a collection of seed documents linked to more similar documents of the desired type than to dissimilar documents of the undesired type;
• providing a sink document for providing access to the database, the sink document is generic and representative of the database;
• identifying a cut-set of links which is the smallest set of links such that removing them from the database completely disconnects the source document and its linked documents from the sink document and its linked documents into first and second subsets of documents, respectively;
• and
• defining the first subset of documents as desired type documents and the remaining documents as undesired type documents.

A computer program product embodied in a computer-readable medium for partitioning a database containing a plurality of documents into desired and undesired type documents, the plurality of documents containing text and/or links to and from other documents in the database, the computer program product comprising:

• computer readable program code means for providing a source document of the desired type, the source document including a collection of seed documents linked to more similar documents of the desired type than to dissimilar documents of the undesired type;
• computer readable program code means for providing a sink document for providing access to the database, the sink document is generic and representative of the database;
• computer readable program code means for identifying a cut-set of links which is the smallest set of links such that removing them from the database completely disconnects the source document and its linked documents from the sink document and its linked documents into first and second subsets of documents, respectively;
• and
• computer readable program code means for defining the first subset of documents as desired type documents and the remaining documents as undesired type documents.