src/main/java/org/jboss/pressgang/ccms/model/utils/TopicUtilities.java
public static List<Integer> getMatchingMinHash(final EntityManager entityManager, final Map<Integer, Integer> minhashes, final Float threshold) {
        try {

            if (minhashes.size() == 0) {
                /*
                    If the source does not have a minhash signature, force the search query to
                    match a non existent topic id so no results are returned.
                 */
                return new ArrayList<Integer>(){{add(-1);}};
            }

            Float fixedThreshold = Constants.MIN_DOCUMENT_SIMILARITY;
            if (threshold > Constants.MAX_DOCUMENT_SIMILARITY) {
                fixedThreshold = Constants.MAX_DOCUMENT_SIMILARITY;
            } else if (threshold >= Constants.MIN_DOCUMENT_SIMILARITY) {
                fixedThreshold = threshold;
            }

            final CriteriaBuilder criteriaBuilder = entityManager.getCriteriaBuilder();
            final CriteriaQuery<Integer> criteriaQuery = criteriaBuilder.createQuery(Integer.class);
            final Root<MinHash> minHashRoot = criteriaQuery.from(MinHash.class);

            final Set<Integer> candidates = new HashSet<Integer>();

            /*
                Note to self - It may be possible to perform these band queries as one big query through something like
                cb.having(cb.equal(cb.toInteger(cb.prod(minHashRoot.<Integer>get("minHashFuncID"), 1.0/lhsRows), band).
                However, unless lhsRows * bands exactly equals Constants.NUM_MIN_HASHES there needs to be some additional
                logic for the last band, which will have less than lhsRows rows in it.
             */

            for (int band = 0; band < Constants.MIN_HASH_BANDS; ++band) {
                final List<Predicate> rowMatches = new ArrayList<Predicate>();
                for (int row = band * Constants.MIN_HASH_ROWS; row < (band * Constants.MIN_HASH_ROWS) + Constants.MIN_HASH_ROWS; ++row) {
                    Integer sourceMinHash = null;
                    if (minhashes.containsKey(row)) {
                        sourceMinHash = minhashes.get(row);
                    } else {
                        throw new IllegalArgumentException("minhashes did not contain a minhash for function " + row);
                    }

                    rowMatches.add(criteriaBuilder.and(
                            criteriaBuilder.equal(minHashRoot.<Integer>get("minHashFuncID"), row),
                            criteriaBuilder.equal(minHashRoot.<Integer>get("minHash"), sourceMinHash)
                    ));
                }

                final Predicate minHashOrs = criteriaBuilder.or(rowMatches.toArray(new Predicate[]{}));

                final CriteriaQuery<Integer> query = criteriaQuery
                        .select(minHashRoot.<Topic>get("topic").<Integer>get("topicId"))
                        .distinct(true)
                        .where(minHashOrs)
                        .groupBy(minHashRoot.<Integer>get("topic").<Integer>get("topicId"))
                        .having(criteriaBuilder.equal(criteriaBuilder.count(minHashRoot.<Integer>get("topic").<Integer>get("topicId")), rowMatches.size()));

                candidates.addAll(entityManager.createQuery(query).getResultList());
            }

            final List<Integer> matchingTopics = new ArrayList<Integer>();

            if (candidates.size() != 0) {
                // at this point candidates should now list topic ids that are a potential match to the source topic.
                final CriteriaQuery<Topic> topicCQ = criteriaBuilder.createQuery(Topic.class);
                final Root<Topic> topicRoot = topicCQ.from(Topic.class);
                final CriteriaBuilder.In<Integer> in = criteriaBuilder.in(topicRoot.<Integer>get("topicId"));
                for (final Integer candidate : candidates) {
                    in.value(candidate);
                }
                final CriteriaQuery<Topic> topicQuery = topicCQ.select(topicRoot).where(in);
                final List<Topic> topics = entityManager.createQuery(topicQuery).getResultList();

                // we now have a list of topics that are possible candidates for a match. Now we compare the minhash values
                // to see what the similarity actually is.

                for (final Topic topic : topics) {
                    int matches = 0;

                    for (final MinHash otherMinHash : topic.getMinHashes()) {
                        if (minhashes.containsKey(otherMinHash.getMinHashFuncID())) {
                            if (minhashes.get(otherMinHash.getMinHashFuncID()).equals(otherMinHash.getMinHash())) {
                                ++matches;
                            }
                        } else {
                            throw new IllegalArgumentException("minhashes did not contain a minhash for function " + otherMinHash.getMinHashFuncID());
                        }
                    }


                    if ((float)matches / Constants.NUM_MIN_HASHES >= fixedThreshold) {
                        matchingTopics.add(topic.getId());
                    }
                }

                if (matchingTopics.size() != 0) {
                    return matchingTopics;
                }
            }

            return Arrays.asList(-1);
        } catch (final Exception ex) {
            return null;
        }
    }
public static List<Integer> getMatchingMinHash(final EntityManager entityManager, final Map<Integer, Integer> minhashes, final Float threshold) {
        try {

            if (minhashes.size() == 0) {
                /*
                    If the source does not have a minhash signature, force the search query to
                    match a non existent topic id so no results are returned.
                 */
                return new ArrayList<Integer>(){{add(-1);}};
            }

            Float fixedThreshold = Constants.MIN_DOCUMENT_SIMILARITY;
            if (threshold > Constants.MAX_DOCUMENT_SIMILARITY) {
                fixedThreshold = Constants.MAX_DOCUMENT_SIMILARITY;
            } else if (threshold >= Constants.MIN_DOCUMENT_SIMILARITY) {
                fixedThreshold = threshold;
            }

            final CriteriaBuilder criteriaBuilder = entityManager.getCriteriaBuilder();
            final CriteriaQuery<Integer> criteriaQuery = criteriaBuilder.createQuery(Integer.class);
            final Root<MinHash> minHashRoot = criteriaQuery.from(MinHash.class);

            final Set<Integer> candidates = new HashSet<Integer>();

            /*
                Note to self - It may be possible to perform these band queries as one big query through something like
                cb.having(cb.equal(cb.toInteger(cb.prod(minHashRoot.<Integer>get("minHashFuncID"), 1.0/lhsRows), band).
                However, unless lhsRows * bands exactly equals Constants.NUM_MIN_HASHES there needs to be some additional
                logic for the last band, which will have less than lhsRows rows in it.
             */

            for (int band = 0; band < Constants.MIN_HASH_BANDS; ++band) {
                final List<Predicate> rowMatches = new ArrayList<Predicate>();
                for (int row = band * Constants.MIN_HASH_ROWS; row < (band * Constants.MIN_HASH_ROWS) + Constants.MIN_HASH_ROWS; ++row) {
                    Integer sourceMinHash = null;
                    if (minhashes.containsKey(row)) {
                        sourceMinHash = minhashes.get(row);
                    } else {
                        throw new IllegalArgumentException("minhashes did not contain a minhash for function " + row);
                    }

                    rowMatches.add(criteriaBuilder.and(
                            criteriaBuilder.equal(minHashRoot.<Integer>get("minHashFuncID"), row),
                            criteriaBuilder.equal(minHashRoot.<Integer>get("minHash"), sourceMinHash)
                    ));
                }

                final Predicate minHashOrs = criteriaBuilder.or(rowMatches.toArray(new Predicate[]{}));

                final CriteriaQuery<Integer> query = criteriaQuery
                        .select(minHashRoot.<Topic>get("topic").<Integer>get("topicId"))
                        .distinct(true)
                        .where(minHashOrs)
                        .groupBy(minHashRoot.<Integer>get("topic").<Integer>get("topicId"))
                        .having(criteriaBuilder.equal(criteriaBuilder.count(minHashRoot.<Integer>get("topic").<Integer>get("topicId")), rowMatches.size()));

                candidates.addAll(entityManager.createQuery(query).getResultList());
            }

            final List<Integer> matchingTopics = new ArrayList<Integer>();

            if (candidates.size() != 0) {
                // at this point candidates should now list topic ids that are a potential match to the source topic.
                final CriteriaQuery<Topic> topicCQ = criteriaBuilder.createQuery(Topic.class);
                final Root<Topic> topicRoot = topicCQ.from(Topic.class);
                final CriteriaBuilder.In<Integer> in = criteriaBuilder.in(topicRoot.<Integer>get("topicId"));
                for (final Integer candidate : candidates) {
                    in.value(candidate);
                }
                final CriteriaQuery<Topic> topicQuery = topicCQ.select(topicRoot).where(in);
                final List<Topic> topics = entityManager.createQuery(topicQuery).getResultList();

                // we now have a list of topics that are possible candidates for a match. Now we compare the minhash values
                // to see what the similarity actually is.

                for (final Topic topic : topics) {
                    int matches = 0;

                    for (final MinHash otherMinHash : topic.getMinHashes()) {
                        if (minhashes.containsKey(otherMinHash.getMinHashFuncID())) {
                            if (minhashes.get(otherMinHash.getMinHashFuncID()).equals(otherMinHash.getMinHash())) {
                                ++matches;
                            }
                        } else {
                            throw new IllegalArgumentException("minhashes did not contain a minhash for function " + otherMinHash.getMinHashFuncID());
                        }
                    }


                    if ((float)matches / Constants.NUM_MIN_HASHES >= fixedThreshold) {
                        matchingTopics.add(topic.getId());
                    }
                }

                if (matchingTopics.size() != 0) {
                    return matchingTopics;
                }
            }

            return Arrays.asList(-1);
        } catch (final Exception ex) {
            return null;
        }
    }
public static List < Integer > getMatchingMinHash ( final EntityManager entityManager , final Map < Integer , Integer > minhashes , final Float threshold ) { try { if ( minhashes . size ( ) == 0 ) { /*
                    If the source does not have a minhash signature, force the search query to
                    match a non existent topic id so no results are returned.
                 */ return new ArrayList < Integer > ( ) { { add ( - 1 ) ; } } ; } Float fixedThreshold = Constants . MIN_DOCUMENT_SIMILARITY ; if ( threshold > Constants . MAX_DOCUMENT_SIMILARITY ) { fixedThreshold = Constants . MAX_DOCUMENT_SIMILARITY ; } else if ( threshold >= Constants . MIN_DOCUMENT_SIMILARITY ) { fixedThreshold = threshold ; } final CriteriaBuilder criteriaBuilder = entityManager . getCriteriaBuilder ( ) ; final CriteriaQuery < Integer > criteriaQuery = criteriaBuilder . createQuery ( Integer . class ) ; final Root < MinHash > minHashRoot = criteriaQuery . from ( MinHash . class ) ; final Set < Integer > candidates = new HashSet < Integer > ( ) ; /*
                Note to self - It may be possible to perform these band queries as one big query through something like
                cb.having(cb.equal(cb.toInteger(cb.prod(minHashRoot.<Integer>get("minHashFuncID"), 1.0/lhsRows), band).
                However, unless lhsRows * bands exactly equals Constants.NUM_MIN_HASHES there needs to be some additional
                logic for the last band, which will have less than lhsRows rows in it.
             */ for ( int band = 0 ; band < Constants . MIN_HASH_BANDS ; ++ band ) { final List < Predicate > rowMatches = new ArrayList < Predicate > ( ) ; for ( int row = band * Constants . MIN_HASH_ROWS ; row < ( band * Constants . MIN_HASH_ROWS ) + Constants . MIN_HASH_ROWS ; ++ row ) { Integer sourceMinHash = null ; if ( minhashes . containsKey ( row ) ) { sourceMinHash = minhashes . get ( row ) ; } else { throw new IllegalArgumentException ( "minhashes did not contain a minhash for function " + row ) ; } rowMatches . add ( criteriaBuilder . and ( criteriaBuilder . equal ( minHashRoot . < Integer > get ( "minHashFuncID" ) , row ) , criteriaBuilder . equal ( minHashRoot . < Integer > get ( "minHash" ) , sourceMinHash ) ) ) ; } final Predicate minHashOrs = criteriaBuilder . or ( rowMatches . toArray ( new Predicate [ ] { } ) ) ; final CriteriaQuery < Integer > query = criteriaQuery . select ( minHashRoot . < Topic > get ( "topic" ) . < Integer > get ( "topicId" ) ) . distinct ( true ) . where ( minHashOrs ) . groupBy ( minHashRoot . < Integer > get ( "topic" ) . < Integer > get ( "topicId" ) ) . having ( criteriaBuilder . equal ( criteriaBuilder . count ( minHashRoot . < Integer > get ( "topic" ) . < Integer > get ( "topicId" ) ) , rowMatches . size ( ) ) ) ; candidates . addAll ( entityManager . createQuery ( query ) . getResultList ( ) ) ; } final List < Integer > matchingTopics = new ArrayList < Integer > ( ) ; if ( candidates . size ( ) != 0 ) { // at this point candidates should now list topic ids that are a potential match to the source topic. final CriteriaQuery < Topic > topicCQ = criteriaBuilder . createQuery ( Topic . class ) ; final Root < Topic > topicRoot = topicCQ . from ( Topic . class ) ; final CriteriaBuilder . In < Integer > in = criteriaBuilder . in ( topicRoot . < Integer > get ( "topicId" ) ) ; for ( final Integer candidate : candidates ) { in . value ( candidate ) ; } final CriteriaQuery < Topic > topicQuery = topicCQ . select ( topicRoot ) . where ( in ) ; final List < Topic > topics = entityManager . createQuery ( topicQuery ) . getResultList ( ) ; // we now have a list of topics that are possible candidates for a match. Now we compare the minhash values // to see what the similarity actually is. for ( final Topic topic : topics ) { int matches = 0 ; for ( final MinHash otherMinHash : topic . getMinHashes ( ) ) { if ( minhashes . containsKey ( otherMinHash . getMinHashFuncID ( ) ) ) { if ( minhashes . get ( otherMinHash . getMinHashFuncID ( ) ) . equals ( otherMinHash . getMinHash ( ) ) ) { ++ matches ; } } else { throw new IllegalArgumentException ( "minhashes did not contain a minhash for function " + otherMinHash . getMinHashFuncID ( ) ) ; } } if ( ( float ) matches / Constants . NUM_MIN_HASHES >= fixedThreshold ) { matchingTopics . add ( topic . getId ( ) ) ; } } if ( matchingTopics . size ( ) != 0 ) { return matchingTopics ; } } return Arrays . asList ( - 1 ) ; } catch ( final Exception ex ) { return null ; } }
Matching the minhash signature of a document relies on a process known as locality sensitive hashing.
A good explaination of this process can be found at http://infolab.stanford.edu/~ullman/mmds/ch3.pdf.

To implement this feature, we need to group the minhash signatures into bands. When two topics share
the same minhash in a single band, they are considered a candidate pair for further testing.

The documentation above suggests hashing the minhash values that fall into a band, and then comparing
these hashed band values to find candidates. Our implementation will defer this to the database by
finding the number of topics that have matching minhash values in all rows in a band.

The number of rows and bands is calculated such that the threshold is approximately Math.pow(1/b, 1/r). This
formula means that increasing the threshold results in an increased number of rows and a decreased number
of bands. We get a close approximation by running through a bunch of combinations and seeing what fits best.

@param entityManager The entity manager to use for queries
@param minhashes The minhash signature to match topics to
@param threshold How similar we want two documents to be to be considered a match. This will be forced to a value
between 0.6 and 0.9.
@return
Matching the minhash signature of a document relies on a process known as locality sensitive hashing . A good explaination of this process can be found at http : // infolab . stanford . edu / ~ullman / mmds / ch3 . pdf .