Determines the one-dimensional dense subspace candidates by making a pass
over the database.

@param database the database to run the algorithm on
@return the one-dimensional dense subspace candidates reverse ordered by
their coverage
760483
private List<CLIQUESubspace> findOneDimensionalDenseSubspaceCandidates(Relation<? extends NumberVector> database) {
    Collection<CLIQUEUnit> units = initOneDimensionalUnits(database);
    // identify dense units
    double total = database.size();
    for(DBIDIter it = database.iterDBIDs(); it.valid(); it.advance()) {
      NumberVector featureVector = database.get(it);
      // FIXME: rather than repeatedly testing, use a clever data structure?
      for(CLIQUEUnit unit : units) {
        unit.addFeatureVector(it, featureVector);
      }
    }

    int dimensionality = RelationUtil.dimensionality(database);
    Collection<CLIQUEUnit> denseUnits = new ArrayList<>();
    CLIQUESubspace[] denseSubspaces = new CLIQUESubspace[dimensionality];
    for(CLIQUEUnit unit : units) {
      // unit is a dense unit
      if(unit.selectivity(total) >= tau) {
        denseUnits.add(unit);
        // add the one-dimensional dense unit to its subspace
        int dim = unit.getDimension(0);
        CLIQUESubspace subspace_d = denseSubspaces[dim];
        if(subspace_d == null) {
          denseSubspaces[dim] = subspace_d = new CLIQUESubspace(dim);
        }
        subspace_d.addDenseUnit(unit);
      }
    }
    // Omit null values where no dense unit was found:
    List<CLIQUESubspace> subspaceCandidates = new ArrayList<>(dimensionality);
    for(CLIQUESubspace s : denseSubspaces) {
      if(s != null) {
        subspaceCandidates.add(s);
      }
    }
    Collections.sort(subspaceCandidates, CLIQUESubspace.BY_COVERAGE);

    if(LOG.isDebugging()) {
      LOG.debugFine(new StringBuilder().append("   number of 1-dim dense units: ").append(denseUnits.size()) //
          .append("\n   number of 1-dim dense subspace candidates: ").append(subspaceCandidates.size()).toString());
    }
    return subspaceCandidates;
  }
1343575
@NonNull
    public static As database(@NonNull com.couchbase.lite.Database database) {
        if (database == null) {
            throw new IllegalArgumentException("database cannot be null.");
        }
        return new As(database);
    }
786485
public Clustering<MedoidModel> run(Database database, Relation<V> relation) {
    DistanceQuery<V> distQ = DatabaseUtil.precomputedDistanceQuery(database, relation, getDistanceFunction(), LOG);
    // Choose initial medoids
    if(LOG.isStatistics()) {
      LOG.statistics(new StringStatistic(KEY + ".initialization", initializer.toString()));
    }
    ArrayModifiableDBIDs medoids = DBIDUtil.newArray(initializer.chooseInitialMedoids(k, relation.getDBIDs(), distQ));
    DBIDArrayMIter miter = medoids.iter();
    double[] mdists = new double[k];
    // Setup cluster assignment store
    List<ModifiableDBIDs> clusters = new ArrayList<>();
    for(int i = 0; i < k; i++) {
      HashSetModifiableDBIDs set = DBIDUtil.newHashSet(relation.size() / k);
      set.add(miter.seek(i)); // Add medoids.
      clusters.add(set);
    }

    // Initial assignment to nearest medoids
    // TODO: reuse this information, from the build phase, when possible?
    double tc = assignToNearestCluster(miter, mdists, clusters, distQ);
    if(LOG.isStatistics()) {
      LOG.statistics(new DoubleStatistic(KEY + ".iteration-" + 0 + ".cost", tc));
    }

    IndefiniteProgress prog = LOG.isVerbose() ? new IndefiniteProgress("K-Medoids EM iteration", LOG) : null;
    // Swap phase
    int iteration = 0;
    DBIDVar best = DBIDUtil.newVar();
    while(true) {
      boolean changed = false;
      // Try to swap the medoid with a better cluster member:
      int i = 0;
      for(miter.seek(0); miter.valid(); miter.advance(), i++) {
        best.unset();
        double bestm = mdists[i];
        for(DBIDIter iter = clusters.get(i).iter(); iter.valid(); iter.advance()) {
          if(DBIDUtil.equal(miter, iter)) {
            continue;
          }
          double sum = 0;
          for(DBIDIter iter2 = clusters.get(i).iter(); iter2.valid(); iter2.advance()) {
            if(DBIDUtil.equal(iter, iter2)) {
              continue;
            }
            sum += distQ.distance(iter, iter2);
          }
          if(sum < bestm) {
            best.set(iter);
            bestm = sum;
          }
        }
        if(best.isSet() && !DBIDUtil.equal(miter, best)) {
          changed = true;
          assert (clusters.get(i).contains(best));
          medoids.set(i, best);
          mdists[i] = bestm;
        }
      }
      if(!changed) {
        break; // Converged
      }
      // Reassign
      double nc = assignToNearestCluster(miter, mdists, clusters, distQ);
      ++iteration;
      if(LOG.isStatistics()) {
        LOG.statistics(new DoubleStatistic(KEY + ".iteration-" + iteration + ".cost", nc));
      }
      LOG.incrementProcessed(prog);
    }
    LOG.setCompleted(prog);
    if(LOG.isStatistics()) {
      LOG.statistics(new LongStatistic(KEY + ".iterations", iteration));
    }

    // Wrap result
    Clustering<MedoidModel> result = new Clustering<>("k-Medoids Clustering", "kmedoids-clustering");
    for(DBIDArrayIter it = medoids.iter(); it.valid(); it.advance()) {
      result.addToplevelCluster(new Cluster<>(clusters.get(it.getOffset()), new MedoidModel(DBIDUtil.deref(it))));
    }
    return result;
  }
826390
public OutlierResult run(Database database, Relation<O> relation) {
    StepProgress stepprog = LOG.isVerbose() ? new StepProgress("LDF", 3) : null;
    final int dim = RelationUtil.dimensionality(relation);
    DBIDs ids = relation.getDBIDs();

    LOG.beginStep(stepprog, 1, "Materializing neighborhoods w.r.t. distance function.");
    KNNQuery<O> knnq = DatabaseUtil.precomputedKNNQuery(database, relation, getDistanceFunction(), k);

    // Compute LDEs
    LOG.beginStep(stepprog, 2, "Computing LDEs.");
    WritableDoubleDataStore ldes = DataStoreUtil.makeDoubleStorage(ids, DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_TEMP);
    FiniteProgress densProgress = LOG.isVerbose() ? new FiniteProgress("Densities", ids.size(), LOG) : null;
    for(DBIDIter it = ids.iter(); it.valid(); it.advance()) {
      final KNNList neighbors = knnq.getKNNForDBID(it, k);
      double sum = 0.0;
      int count = 0;
      // Fast version for double distances
      for(DoubleDBIDListIter neighbor = neighbors.iter(); neighbor.valid(); neighbor.advance()) {
        if(DBIDUtil.equal(neighbor, it)) {
          continue;
        }
        final double nkdist = knnq.getKNNForDBID(neighbor, k).getKNNDistance();
        if(!(nkdist > 0.) || nkdist == Double.POSITIVE_INFINITY) {
          sum = Double.POSITIVE_INFINITY;
          count++;
          break;
        }
        final double v = MathUtil.max(nkdist, neighbor.doubleValue()) / (h * nkdist);
        sum += kernel.density(v) / MathUtil.powi(h * nkdist, dim);
        count++;
      }
      ldes.putDouble(it, sum / count);
      LOG.incrementProcessed(densProgress);
    }
    LOG.ensureCompleted(densProgress);

    // Compute local density factors.
    LOG.beginStep(stepprog, 3, "Computing LDFs.");
    WritableDoubleDataStore ldfs = DataStoreUtil.makeDoubleStorage(ids, DataStoreFactory.HINT_STATIC);
    // track the maximum value for normalization.
    DoubleMinMax lofminmax = new DoubleMinMax();

    FiniteProgress progressLOFs = LOG.isVerbose() ? new FiniteProgress("Local Density Factors", ids.size(), LOG) : null;
    for(DBIDIter it = ids.iter(); it.valid(); it.advance()) {
      final double lrdp = ldes.doubleValue(it);
      final KNNList neighbors = knnq.getKNNForDBID(it, k);
      double sum = 0.0;
      int count = 0;
      for(DBIDIter neighbor = neighbors.iter(); neighbor.valid(); neighbor.advance()) {
        // skip the point itself
        if(DBIDUtil.equal(neighbor, it)) {
          continue;
        }
        sum += ldes.doubleValue(neighbor);
        count++;
      }
      sum /= count;
      final double div = lrdp + c * sum;
      double ldf = div == Double.POSITIVE_INFINITY ? (sum < Double.POSITIVE_INFINITY ? 0. : 1) : (div > 0) ? sum / div : 0;
      ldfs.putDouble(it, ldf);
      // update minimum and maximum
      lofminmax.put(ldf);

      LOG.incrementProcessed(progressLOFs);
    }
    LOG.ensureCompleted(progressLOFs);

    LOG.setCompleted(stepprog);

    // Build result representation.
    DoubleRelation scoreResult = new MaterializedDoubleRelation("Local Density Factor", "ldf-outlier", ldfs, ids);
    OutlierScoreMeta scoreMeta = new BasicOutlierScoreMeta(lofminmax.getMin(), lofminmax.getMax(), 0.0, 1. / c, 1 / (1 + c));
    OutlierResult result = new OutlierResult(scoreMeta, scoreResult);

    return result;
  }
173101
public DatabaseObject getExample(final Database database, final String tableName) {
      final Schema schema = new Schema(getCatalogName(), getSchemaName());
      final DatabaseObject example;

      // For GeoDB, the index is another table.
      if (database instanceof DerbyDatabase || database instanceof H2Database) {
         final String correctedTableName = database.correctObjectName(getHatboxTableName(),
               Table.class);
         example = new Table().setName(correctedTableName).setSchema(schema);
      } else {
         example = getIndexExample(database, schema, tableName);
      }
      return example;
   }
154361
public OutlierResult run(Database database, Relation<O> relation) {
    StepProgress stepprog = LOG.isVerbose() ? new StepProgress("LOF", 3) : null;
    DBIDs ids = relation.getDBIDs();

    LOG.beginStep(stepprog, 1, "Materializing nearest-neighbor sets.");
    KNNQuery<O> knnq = DatabaseUtil.precomputedKNNQuery(database, relation, getDistanceFunction(), k);

    // Compute LRDs
    LOG.beginStep(stepprog, 2, "Computing Local Reachability Densities (LRD).");
    WritableDoubleDataStore lrds = DataStoreUtil.makeDoubleStorage(ids, DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_TEMP);
    computeLRDs(knnq, ids, lrds);

    // compute LOF_SCORE of each db object
    LOG.beginStep(stepprog, 3, "Computing Local Outlier Factors (LOF).");
    WritableDoubleDataStore lofs = DataStoreUtil.makeDoubleStorage(ids, DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_DB);
    // track the maximum value for normalization.
    DoubleMinMax lofminmax = new DoubleMinMax();
    computeLOFScores(knnq, ids, lrds, lofs, lofminmax);

    LOG.setCompleted(stepprog);

    // Build result representation.
    DoubleRelation scoreResult = new MaterializedDoubleRelation("Local Outlier Factor", "lof-outlier", lofs, ids);
    OutlierScoreMeta scoreMeta = new QuotientOutlierScoreMeta(lofminmax.getMin(), lofminmax.getMax(), 0.0, Double.POSITIVE_INFINITY, 1.0);
    return new OutlierResult(scoreMeta, scoreResult);
  }
337475
public Clustering<SubspaceModel> run(Database db, Relation<V> relation) {
    if(mu >= relation.size()) {
      throw new AbortException("Parameter mu is chosen unreasonably large. This won't yield meaningful results.");
    }
    DiSHClusterOrder opticsResult = new Instance(db, relation).run();

    if(LOG.isVerbose()) {
      LOG.verbose("Compute Clusters.");
    }
    return computeClusters(relation, opticsResult);
  }
244623
private double evaluateClusters(ArrayList<PROCLUSCluster> clusters, long[][] dimensions, Relation<V> database) {
    double result = 0;
    for(int i = 0; i < dimensions.length; i++) {
      PROCLUSCluster c_i = clusters.get(i);
      double[] centroid_i = c_i.centroid;

      long[] dims_i = dimensions[i];
      double w_i = 0;
      for(int d = BitsUtil.nextSetBit(dims_i, 0); d >= 0; d = BitsUtil.nextSetBit(dims_i, d + 1)) {
        w_i += avgDistance(centroid_i, c_i.objectIDs, database, d);
      }

      w_i /= dimensions.length;
      result += c_i.objectIDs.size() * w_i;
    }

    return result / database.size();
  }
1286187
public int removeShapesNotWithinMap(BoundingBox boundingBox, String database) {

        int count = 0;

        Map<String, Map<Long, FeatureShape>> tables = getTables(database);

        if (tables != null) {

            for (String table : tables.keySet()) {
                count += removeShapesNotWithinMap(boundingBox, database, table);
            }
        }

        return count;
    }
1367732
private boolean isNamespace(String database) {
    Collection<String> tables = getMetaStoreUtil().getAllTables(database);
    for (String name : tables) {
      if (isReadable(database, name)) {
        return true;
      }
    }
    return false;
  }
1010237
public boolean removeDatabase(Database database)
    {
        database = (BaseDatabase)this.getDatabaseList((database.getDatabaseType() & DBConstants.TABLE_MASK)).remove(database.getDatabaseName(false));
        if (database == null)
            return false;
        return true;
    }
1033529
public PCAResult processQueryResult(DoubleDBIDList results, Relation<? extends NumberVector> database) {
    return processCovarMatrix(covarianceMatrixBuilder.processQueryResults(results, database));
  }
1111518
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;
    // compute two-element sets of subspaces
    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);
      }
      // result now contains all d-dimensional sets of subspaces

      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();
      // candidateList now contains the *m* best d-dimensional sets
      Collections.sort(candidateList, HiCSSubspace.SORT_BY_SUBSPACE);

      // TODO: optimize APRIORI style, by not even computing the bit set or?
      for(int i = 0; i < candidateList.size() - 1; i++) {
        for(int j = i + 1; j < candidateList.size(); j++) {
          HiCSSubspace set1 = candidateList.get(i), 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);
        }
      }
      // Prune
      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;
  }
37105
public static String loadOracleSrid(final String srid, final Database database) {
      final String oracleSrid;
      final JdbcConnection jdbcConnection = (JdbcConnection) database.getConnection();
      final Connection connection = jdbcConnection.getUnderlyingConnection();
      Statement statement = null;
      try {
         statement = connection.createStatement();
         final ResultSet resultSet = statement.executeQuery("SELECT " + EPSG_TO_ORACLE_FUNCTION
               + "(" + srid + ") FROM dual");
         resultSet.next();
         oracleSrid = resultSet.getString(1);
      } catch (final SQLException e) {
         throw new UnexpectedLiquibaseException("Failed to find the Oracle SRID for EPSG:" + srid,
               e);
      } finally {
         try {
            statement.close();
         } catch (final SQLException ignore) {
         }
      }
      return oracleSrid;
   }
213283
@Override
  public double[][] processIds(DBIDs ids, Relation<? extends NumberVector> database) {
    return CovarianceMatrix.make(database, ids).destroyToPopulationMatrix();
  }
1191099
public KNNDistanceOrderResult run(Database database, Relation<O> relation) {
    final DistanceQuery<O> distanceQuery = database.getDistanceQuery(relation, getDistanceFunction());
    final KNNQuery<O> knnQuery = database.getKNNQuery(distanceQuery, k + 1);

    final int size = (int) ((sample <= 1.) ? Math.ceil(relation.size() * sample) : sample);
    DBIDs sample = DBIDUtil.randomSample(relation.getDBIDs(), size, rnd);

    FiniteProgress prog = LOG.isVerbose() ? new FiniteProgress("Sampling kNN distances", size, LOG) : null;
    double[] knnDistances = new double[size];
    int i = 0;
    for(DBIDIter iditer = sample.iter(); iditer.valid(); iditer.advance(), i++) {
      final KNNList neighbors = knnQuery.getKNNForDBID(iditer, k + 1);
      knnDistances[i] = neighbors.getKNNDistance();
      LOG.incrementProcessed(prog);
    }
    LOG.ensureCompleted(prog);

    return new KNNDistanceOrderResult(knnDistances, k);
  }
423039
private Collection<CLIQUEUnit> initOneDimensionalUnits(Relation<? extends NumberVector> database) {
    StringBuilder buf = LOG.isDebuggingFiner() ? new StringBuilder(1000) : null;
    int dimensionality = RelationUtil.dimensionality(database);
    // initialize minima and maxima
    double[] minima = new double[dimensionality];
    double[] maxima = new double[dimensionality];
    Arrays.fill(minima, Double.MAX_VALUE);
    Arrays.fill(maxima, -Double.MAX_VALUE);
    // update minima and maxima
    for(DBIDIter it = database.iterDBIDs(); it.valid(); it.advance()) {
      updateMinMax(database.get(it), minima, maxima);
    }
    for(int i = 0; i < maxima.length; i++) {
      maxima[i] += 0.0001;
    }

    // determine the unit length in each dimension
    double[] unit_lengths = new double[dimensionality];
    for(int d = 0; d < dimensionality; d++) {
      unit_lengths[d] = (maxima[d] - minima[d]) / xsi;
    }

    if(buf != null) {
      FormatUtil.formatTo(buf.append("   minima: "), minima, ", ", FormatUtil.NF2);
      FormatUtil.formatTo(buf.append("\n   maxima: "), maxima, ", ", FormatUtil.NF2);
      FormatUtil.formatTo(buf.append("\n   unit lengths: "), unit_lengths, ", ", FormatUtil.NF2);
    }

    // determine the boundaries of the units
    double[][] unit_bounds = new double[xsi + 1][dimensionality];
    for(int x = 0; x <= xsi; x++) {
      for(int d = 0; d < dimensionality; d++) {
        unit_bounds[x][d] = (x < xsi) ? minima[d] + x * unit_lengths[d] : maxima[d];
      }
    }
    if(buf != null) {
      FormatUtil.formatTo(buf.append("   unit bounds "), unit_bounds, "    [", "]\n", ", ", FormatUtil.NF2);
    }

    // build the 1 dimensional units
    List<CLIQUEUnit> units = new ArrayList<>(xsi * dimensionality);
    for(int x = 0; x < xsi; x++) {
      for(int d = 0; d < dimensionality; d++) {
        units.add(new CLIQUEUnit(d, unit_bounds[x][d], unit_bounds[x + 1][d]));
      }
    }

    if(buf != null) {
      LOG.debugFiner(buf.append("   total number of 1-dim units: ").append(units.size()).toString());
    }

    return units;
  }