private Set<HiCSSubspace> calculateSubspaces(Relation<? extends NumberVector> relation,ArrayList<ArrayDBIDs> subspaceIndex,Random random){
  final int dbdim=RelationUtil.dimensionality(relation);
  FiniteProgress dprog=LOG.isVerbose() ? new FiniteProgress("Subspace dimensionality",dbdim,LOG) : null;
  if (dprog != null) {
    dprog.setProcessed(2,LOG);
  }
  TreeSet<HiCSSubspace> subspaceList=new TreeSet<>(HiCSSubspace.SORT_BY_SUBSPACE);
  TopBoundedHeap<HiCSSubspace> dDimensionalList=new TopBoundedHeap<>(cutoff,HiCSSubspace.SORT_BY_CONTRAST_ASC);
  FiniteProgress prog=LOG.isVerbose() ? new FiniteProgress("Generating two-element subsets",(dbdim * (dbdim - 1)) >> 1,LOG) : null;
  for (int i=0; i < dbdim; i++) {
    for (int j=i + 1; j < dbdim; j++) {
      HiCSSubspace ts=new HiCSSubspace();
      ts.set(i);
      ts.set(j);
      calculateContrast(relation,ts,subspaceIndex,random);
      dDimensionalList.add(ts);
      LOG.incrementProcessed(prog);
    }
  }
  LOG.ensureCompleted(prog);
  IndefiniteProgress qprog=LOG.isVerbose() ? new IndefiniteProgress("Testing subspace candidates",LOG) : null;
  for (int d=3; !dDimensionalList.isEmpty(); d++) {
    if (dprog != null) {
      dprog.setProcessed(d,LOG);
    }
    ArrayList<HiCSSubspace> candidateList=new ArrayList<>(dDimensionalList.size());
    for (Heap<HiCSSubspace>.UnorderedIter it=dDimensionalList.unorderedIter(); it.valid(); it.advance()) {
      subspaceList.add(it.get());
      candidateList.add(it.get());
    }
    dDimensionalList.clear();
    Collections.sort(candidateList,HiCSSubspace.SORT_BY_SUBSPACE);
    for (int i=0; i < candidateList.size() - 1; i++) {
      for (int j=i + 1; j < candidateList.size(); j++) {
        HiCSSubspace set1=candidateList.get(i);
        HiCSSubspace set2=candidateList.get(j);
        HiCSSubspace joinedSet=new HiCSSubspace();
        joinedSet.or(set1);
        joinedSet.or(set2);
        if (joinedSet.cardinality() != d) {
          continue;
        }
        calculateContrast(relation,joinedSet,subspaceIndex,random);
        dDimensionalList.add(joinedSet);
        LOG.incrementProcessed(qprog);
      }
    }
    for (    HiCSSubspace cand : candidateList) {
      for (Heap<HiCSSubspace>.UnorderedIter it=dDimensionalList.unorderedIter(); it.valid(); it.advance()) {
        if (it.get().contrast > cand.contrast) {
          subspaceList.remove(cand);
          break;
        }
      }
    }
  }
  LOG.setCompleted(qprog);
  if (dprog != null) {
    dprog.setProcessed(dbdim,LOG);
    dprog.ensureCompleted(LOG);
  }
  return subspaceList;
}

private Set < HiCSSubspace > calculateSubspaces ( Relation < ? extends NumberVector > relation , ArrayList < ArrayDBIDs > subspaceIndex , Random random ) { final int dbdim = RelationUtil . dimensionality ( relation ) ; FiniteProgress dprog = LOG . isVerbose ( ) ? new FiniteProgress ( "Subspace dimensionality" , dbdim , LOG ) : null ; if ( dprog != null ) { dprog . setProcessed ( 2 , LOG ) ; } TreeSet < HiCSSubspace > subspaceList = new TreeSet < > ( HiCSSubspace . SORT_BY_SUBSPACE ) ; TopBoundedHeap < HiCSSubspace > dDimensionalList = new TopBoundedHeap < > ( cutoff , HiCSSubspace . SORT_BY_CONTRAST_ASC ) ; FiniteProgress prog = LOG . isVerbose ( ) ? new FiniteProgress ( "Generating two-element subsets" , ( dbdim * ( dbdim - 1 ) ) > > 1 , LOG ) : null ; for ( int i = 0 ; i < dbdim ; i ++ ) { for ( int j = i + 1 ; j < dbdim ; j ++ ) { HiCSSubspace ts = new HiCSSubspace ( ) ; ts . set ( i ) ; ts . set ( j ) ; calculateContrast ( relation , ts , subspaceIndex , random ) ; dDimensionalList . add ( ts ) ; LOG . incrementProcessed ( prog ) ; } } LOG . ensureCompleted ( prog ) ; IndefiniteProgress qprog = LOG . isVerbose ( ) ? new IndefiniteProgress ( "Testing subspace candidates" , LOG ) : null ; for ( int d = 3 ; ! dDimensionalList . isEmpty ( ) ; d ++ ) { if ( dprog != null ) { dprog . setProcessed ( d , LOG ) ; } ArrayList < HiCSSubspace > candidateList = new ArrayList < > ( dDimensionalList . size ( ) ) ; for ( Heap < HiCSSubspace > . UnorderedIter it = dDimensionalList . unorderedIter ( ) ; it . valid ( ) ; it . advance ( ) ) { subspaceList . add ( it . get ( ) ) ; candidateList . add ( it . get ( ) ) ; } dDimensionalList . clear ( ) ; Collections . sort ( candidateList , HiCSSubspace . SORT_BY_SUBSPACE ) ; for ( int i = 0 ; i < candidateList . size ( ) - 1 ; i ++ ) { for ( int j = i + 1 ; j < candidateList . size ( ) ; j ++ ) { HiCSSubspace set1 = candidateList . get ( i ) ; HiCSSubspace set2 = candidateList . get ( j ) ; HiCSSubspace joinedSet = new HiCSSubspace ( ) ; joinedSet . or ( set1 ) ; joinedSet . or ( set2 ) ; if ( joinedSet . cardinality ( ) != d ) { continue ; } calculateContrast ( relation , joinedSet , subspaceIndex , random ) ; dDimensionalList . add ( joinedSet ) ; LOG . incrementProcessed ( qprog ) ; } } for ( HiCSSubspace cand : candidateList ) { for ( Heap < HiCSSubspace > . UnorderedIter it = dDimensionalList . unorderedIter ( ) ; it . valid ( ) ; it . advance ( ) ) { if ( it . get ( ) . contrast > cand . contrast ) { subspaceList . remove ( cand ) ; break ; } } } } LOG . setCompleted ( qprog ) ; if ( dprog != null ) { dprog . setProcessed ( dbdim , LOG ) ; dprog . ensureCompleted ( LOG ) ; } return subspaceList ; }
identifies high contrast subspaces in a given full - dimensional database .
