I was experimenting with gc() in different ways. I was callling it
after processing 1000 elements. However, that didn't help and the
problem remained the same: after processing 1334 (or 1335) elements I
received the OutOfMemory error.

Don't know, how much is that an SSCCE, but I am posting you my example:

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Example {

    private class ArrElem {

        private String id;
        private BitSet fp;

        public BitSet getFp() { return fp; }
        public void setFp(BitSet fp) { this.fp = fp; }
        public String getId() {    return id; }
        public void setId(String id) { this.id = id;}
    }

    private List<ArrElem> arr = new ArrayList<ArrElem>();

    private Map<ArrElem, Collection<ArrElem>> rez = new HashMap<ArrElem,
Collection<ArrElem>>();

    public void processArr() {
        //fillArr(10000);
        for (int i = 0; i < 10000-1; i++) {
            for (int j = i+1; j < 10000; j++) {
                compareElements(arr.get(i), arr.get(j));
            }
        }
    }

    private void compareElements(ArrElem elem1, ArrElem elem2) {
        int bitM = elem1.getFp().cardinality();
        int bitN = elem2.getFp().cardinality();

        BitSet commonBits = elem1.getFp();
        commonBits.and(elem2.getFp());
        int bitCommon = commonBits.cardinality();

        double index = bitCommon/(bitM+bitN+bitCommon);
        if (index < 0.8) {
            if (! rez.containsKey(elem1))
                rez.put(elem1, new ArrayList<ArrElem>());
            rez.get(elem1).add(elem2);
        }
    }
}