summaryrefslogtreecommitdiff
path: root/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTree.java
diff options
context:
space:
mode:
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTree.java')
-rw-r--r--src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTree.java211
1 files changed, 108 insertions, 103 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTree.java
index b98d6821..126013b1 100644
--- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTree.java
+++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTree.java
@@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkcop;
This file is part of ELKI:
Environment for Developing KDD-Applications Supported by Index-Structures
- Copyright (C) 2013
+ Copyright (C) 2014
Ludwig-Maximilians-Universität München
Lehr- und Forschungseinheit für Datenbanksysteme
ELKI Development Team
@@ -31,21 +31,20 @@ import de.lmu.ifi.dbs.elki.database.ids.DBID;
import de.lmu.ifi.dbs.elki.database.ids.DBIDIter;
import de.lmu.ifi.dbs.elki.database.ids.DBIDRef;
import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil;
+import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDList;
+import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDListIter;
+import de.lmu.ifi.dbs.elki.database.ids.KNNList;
import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs;
-import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDList;
-import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDListIter;
-import de.lmu.ifi.dbs.elki.database.ids.distance.KNNList;
-import de.lmu.ifi.dbs.elki.database.ids.generic.GenericDistanceDBIDList;
+import de.lmu.ifi.dbs.elki.database.ids.ModifiableDoubleDBIDList;
import de.lmu.ifi.dbs.elki.database.relation.Relation;
-import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance;
import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree;
import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.MkTreeSettings;
import de.lmu.ifi.dbs.elki.index.tree.query.GenericMTreeDistanceSearchCandidate;
import de.lmu.ifi.dbs.elki.logging.Logging;
-import de.lmu.ifi.dbs.elki.persistent.ByteArrayUtil;
import de.lmu.ifi.dbs.elki.persistent.PageFile;
import de.lmu.ifi.dbs.elki.utilities.FormatUtil;
import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.ComparableMinHeap;
+import de.lmu.ifi.dbs.elki.utilities.io.ByteArrayUtil;
/**
* MkCopTree is a metrical index structure based on the concepts of the M-Tree
@@ -58,9 +57,8 @@ import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.ComparableMinHeap;
* @apiviz.has ConvexHull
*
* @param <O> Object type
- * @param <D> Distance type
*/
-public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree<O, D, MkCoPTreeNode<O, D>, MkCoPEntry, MkTreeSettings<O, D, MkCoPTreeNode<O, D>, MkCoPEntry>> {
+public class MkCoPTree<O> extends AbstractMkTree<O, MkCoPTreeNode<O>, MkCoPEntry, MkTreeSettings<O, MkCoPTreeNode<O>, MkCoPEntry>> {
/**
* The logger for this class.
*/
@@ -78,11 +76,11 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
* @param pagefile Page file
* @param settings Tree settings
*/
- public MkCoPTree(Relation<O> relation, PageFile<MkCoPTreeNode<O, D>> pagefile, MkTreeSettings<O, D, MkCoPTreeNode<O, D>, MkCoPEntry> settings) {
+ public MkCoPTree(Relation<O> relation, PageFile<MkCoPTreeNode<O>> pagefile, MkTreeSettings<O, MkCoPTreeNode<O>, MkCoPEntry> settings) {
super(relation, pagefile, settings);
// init log k
log_k = new double[settings.k_max];
- for (int k = 1; k <= settings.k_max; k++) {
+ for(int k = 1; k <= settings.k_max; k++) {
log_k[k - 1] = Math.log(k);
}
}
@@ -105,34 +103,34 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
@Override
public void insertAll(List<MkCoPEntry> entries) {
- if (entries.isEmpty()) {
+ if(entries.isEmpty()) {
return;
}
- if (LOG.isDebugging()) {
+ if(LOG.isDebugging()) {
LOG.debugFine("insert " + entries + "\n");
}
- if (!initialized) {
+ if(!initialized) {
initialize(entries.get(0));
}
ModifiableDBIDs ids = DBIDUtil.newArray(entries.size());
// insert
- for (MkCoPEntry entry : entries) {
+ for(MkCoPEntry entry : entries) {
ids.add(entry.getRoutingObjectID());
// insert the object
super.insert(entry, false);
}
// perform nearest neighbor queries
- Map<DBID, KNNList<D>> knnLists = batchNN(getRoot(), ids, settings.k_max);
+ Map<DBID, KNNList> knnLists = batchNN(getRoot(), ids, settings.k_max);
// adjust the knn distances
adjustApproximatedKNNDistances(getRootEntry(), knnLists);
- if (EXTRA_INTEGRITY_CHECKS) {
+ if(EXTRA_INTEGRITY_CHECKS) {
getRoot().integrityCheck(this, getRootEntry());
}
}
@@ -146,17 +144,17 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
* @return a List of the query results
*/
@Override
- public DistanceDBIDList<D> reverseKNNQuery(DBIDRef id, int k) {
- if (k > settings.k_max) {
+ public DoubleDBIDList reverseKNNQuery(DBIDRef id, int k) {
+ if(k > settings.k_max) {
throw new IllegalArgumentException("Parameter k has to be less or equal than " + "parameter kmax of the MCop-Tree!");
}
- GenericDistanceDBIDList<D> result = new GenericDistanceDBIDList<>();
+ ModifiableDoubleDBIDList result = DBIDUtil.newDistanceDBIDList();
ModifiableDBIDs candidates = DBIDUtil.newArray();
doReverseKNNQuery(k, id, result, candidates);
// refinement of candidates
- Map<DBID, KNNList<D>> knnLists = batchNN(getRoot(), candidates, k);
+ Map<DBID, KNNList> knnLists = batchNN(getRoot(), candidates, k);
result.sort();
// Collections.sort(candidates);
@@ -165,12 +163,12 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
// rkNNStatistics.addCandidates(candidates.size());
// rkNNStatistics.addTrueHits(result.size());
- for (DBIDIter iter = candidates.iter(); iter.valid(); iter.advance()) {
+ for(DBIDIter iter = candidates.iter(); iter.valid(); iter.advance()) {
DBID cid = DBIDUtil.deref(iter);
- KNNList<D> cands = knnLists.get(cid);
- for (DistanceDBIDListIter<D> iter2 = cands.iter(); iter2.valid(); iter2.advance()) {
- if (DBIDUtil.equal(id, iter2)) {
- result.add(iter2.getDistance(), cid);
+ KNNList cands = knnLists.get(cid);
+ for(DoubleDBIDListIter iter2 = cands.iter(); iter2.valid(); iter2.advance()) {
+ if(DBIDUtil.equal(id, iter2)) {
+ result.add(iter2.doubleValue(), cid);
break;
}
}
@@ -200,7 +198,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
// overhead = index(4), numEntries(4), id(4), isLeaf(0.125)
double overhead = 12.125;
- if (getPageSize() - overhead < 0) {
+ if(getPageSize() - overhead < 0) {
throw new RuntimeException("Node size of " + getPageSize() + " Bytes is chosen too small!");
}
@@ -208,11 +206,11 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
// coveringRadius + parentDistance + consApprox) + 1
dirCapacity = (int) (getPageSize() - overhead) / (4 + 4 + distanceSize + distanceSize + 10) + 1;
- if (dirCapacity <= 1) {
+ if(dirCapacity <= 1) {
throw new RuntimeException("Node size of " + getPageSize() + " Bytes is chosen too small!");
}
- if (dirCapacity < 10) {
+ if(dirCapacity < 10) {
LOG.warning("Page size is choosen too small! Maximum number of entries " + "in a directory node = " + (dirCapacity - 1));
}
@@ -221,17 +219,17 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
// consApprox + progrApprox) + 1
leafCapacity = (int) (getPageSize() - overhead) / (4 + distanceSize + 2 * 10) + 1;
- if (leafCapacity <= 1) {
+ if(leafCapacity <= 1) {
throw new RuntimeException("Node size of " + getPageSize() + " Bytes is chosen too small!");
}
- if (leafCapacity < 10) {
+ if(leafCapacity < 10) {
LOG.warning("Page size is choosen too small! Maximum number of entries " + "in a leaf node = " + (leafCapacity - 1));
}
initialized = true;
- if (LOG.isVerbose()) {
+ if(LOG.isVerbose()) {
LOG.verbose("Directory Capacity: " + (dirCapacity - 1) + "\nLeaf Capacity: " + (leafCapacity - 1));
}
}
@@ -245,45 +243,46 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
* @param candidates holds possible candidates for the result (they need a
* refinement)
*/
- private void doReverseKNNQuery(int k, DBIDRef q, GenericDistanceDBIDList<D> result, ModifiableDBIDs candidates) {
+ private void doReverseKNNQuery(int k, DBIDRef q, ModifiableDoubleDBIDList result, ModifiableDBIDs candidates) {
final ComparableMinHeap<GenericMTreeDistanceSearchCandidate> pq = new ComparableMinHeap<>();
// push root
pq.add(new GenericMTreeDistanceSearchCandidate(0., getRootID(), null));
// search in tree
- while (!pq.isEmpty()) {
+ while(!pq.isEmpty()) {
GenericMTreeDistanceSearchCandidate pqNode = pq.poll();
// FIXME: cache the distance to the routing object in the queue node!
- MkCoPTreeNode<O, D> node = getNode(pqNode.nodeID);
+ MkCoPTreeNode<O> node = getNode(pqNode.nodeID);
// directory node
- if (!node.isLeaf()) {
- for (int i = 0; i < node.getNumEntries(); i++) {
+ if(!node.isLeaf()) {
+ for(int i = 0; i < node.getNumEntries(); i++) {
MkCoPEntry entry = node.getEntry(i);
- double distance = distance(entry.getRoutingObjectID(), q).doubleValue();
+ double distance = distance(entry.getRoutingObjectID(), q);
double minDist = entry.getCoveringRadius() > distance ? 0. : distance - entry.getCoveringRadius();
double approximatedKnnDist_cons = entry.approximateConservativeKnnDistance(k);
- if (minDist <= approximatedKnnDist_cons) {
+ if(minDist <= approximatedKnnDist_cons) {
pq.add(new GenericMTreeDistanceSearchCandidate(minDist, getPageID(entry), entry.getRoutingObjectID()));
}
}
}
// data node
else {
- for (int i = 0; i < node.getNumEntries(); i++) {
+ for(int i = 0; i < node.getNumEntries(); i++) {
MkCoPLeafEntry entry = (MkCoPLeafEntry) node.getEntry(i);
- D distance = distance(entry.getRoutingObjectID(), q);
+ double distance = distance(entry.getRoutingObjectID(), q);
double approximatedKnnDist_prog = entry.approximateProgressiveKnnDistance(k);
- if (distance.doubleValue() <= approximatedKnnDist_prog) {
+ if(distance <= approximatedKnnDist_prog) {
result.add(distance, entry.getRoutingObjectID());
- } else {
+ }
+ else {
double approximatedKnnDist_cons = entry.approximateConservativeKnnDistance(k);
- double diff = distance.doubleValue() - approximatedKnnDist_cons;
- if (diff <= 1E-10) {
+ double diff = distance - approximatedKnnDist_cons;
+ if(diff <= 1E-10) {
candidates.add(entry.getRoutingObjectID());
}
}
@@ -298,16 +297,17 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
* @param entry the root entry of the current subtree
* @param knnLists a map of knn lists for each leaf entry
*/
- private void adjustApproximatedKNNDistances(MkCoPEntry entry, Map<DBID, KNNList<D>> knnLists) {
- MkCoPTreeNode<O, D> node = getNode(entry);
+ private void adjustApproximatedKNNDistances(MkCoPEntry entry, Map<DBID, KNNList> knnLists) {
+ MkCoPTreeNode<O> node = getNode(entry);
- if (node.isLeaf()) {
- for (int i = 0; i < node.getNumEntries(); i++) {
+ if(node.isLeaf()) {
+ for(int i = 0; i < node.getNumEntries(); i++) {
MkCoPLeafEntry leafEntry = (MkCoPLeafEntry) node.getEntry(i);
approximateKnnDistances(leafEntry, knnLists.get(leafEntry.getRoutingObjectID()));
}
- } else {
- for (int i = 0; i < node.getNumEntries(); i++) {
+ }
+ else {
+ for(int i = 0; i < node.getNumEntries(); i++) {
MkCoPEntry dirEntry = node.getEntry(i);
adjustApproximatedKNNDistances(dirEntry, knnLists);
}
@@ -323,7 +323,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
private double ssqerr(int k0, int kmax, double[] logk, double[] log_kDist, double m, double t) {
int k = kmax - k0;
double result = 0;
- for (int i = 0; i < k; i++) {
+ for(int i = 0; i < k; i++) {
// double h = log_kDist[i] - (m * (logk[i] - logk[0]) + t); ???
double h = log_kDist[i] - m * logk[i] - t;
result += h * h;
@@ -349,19 +349,20 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
* @param knnDistances TODO: Spezialbehandlung fuer identische Punkte in DB
* (insbes. Distanz 0)
*/
- private void approximateKnnDistances(MkCoPLeafEntry entry, KNNList<D> knnDistances) {
+ private void approximateKnnDistances(MkCoPLeafEntry entry, KNNList knnDistances) {
StringBuilder msg = LOG.isDebugging() ? new StringBuilder() : null;
- if (msg != null) {
+ if(msg != null) {
msg.append("\nknnDistances ").append(knnDistances);
}
// count the zero distances
int k_0 = 0;
- for (int i = 0; i < settings.k_max; i++) {
- double dist = knnDistances.get(i).getDistance().doubleValue();
- if (dist == 0) {
+ for(int i = 0; i < settings.k_max; i++) {
+ double dist = knnDistances.get(i).doubleValue();
+ if(dist == 0) {
k_0++;
- } else {
+ }
+ else {
break;
}
}
@@ -374,8 +375,8 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
double sum_log_k_kDist = 0;
double[] log_kDist = new double[settings.k_max - k_0];
- for (int i = 0; i < settings.k_max - k_0; i++) {
- double dist = knnDistances.get(i + k_0).getDistance().doubleValue();
+ for(int i = 0; i < settings.k_max - k_0; i++) {
+ double dist = knnDistances.get(i + k_0).doubleValue();
log_kDist[i] = Math.log(dist);
sum_log_kDist += log_kDist[i];
sum_log_k_kDist += log_kDist[i] * log_k[i];
@@ -384,12 +385,12 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
double sum_log_k = 0;
double sum_log_k2 = 0;
// noinspection ForLoopReplaceableByForEach
- for (int i = 0; i < log_k.length; i++) {
+ for(int i = 0; i < log_k.length; i++) {
sum_log_k += log_k[i];
sum_log_k2 += (log_k[i] * log_k[i]);
}
- if (msg != null) {
+ if(msg != null) {
msg.append("\nk_0 ").append(k_0);
msg.append("\nk_max ").append(settings.k_max);
msg.append("\nlog_k(").append(log_k.length).append(") ").append(FormatUtil.format(log_k));
@@ -412,12 +413,12 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
double err1 = ssqerr(k_0, settings.k_max, log_k, log_kDist, conservative.getM(), conservative.getT());
double err2 = ssqerr(k_0, settings.k_max, log_k, log_kDist, c2.getM(), c2.getT());
- if (msg != null) {
+ if(msg != null) {
msg.append("err1 ").append(err1);
msg.append("err2 ").append(err2);
}
- if (err1 > err2 && err1 - err2 > 0.000000001) {
+ if(err1 > err2 && err1 - err2 > 0.000000001) {
// if (err1 > err2) {
StringBuilder warning = new StringBuilder();
@@ -431,7 +432,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
warning.append("\nconservative1 ").append(conservative);
warning.append("\nconservative2 ").append(c2);
- for (int i = 0; i < u; i++) {
+ for(int i = 0; i < u; i++) {
warning.append("\nlog_k[").append(upperHull[i]).append("] = ").append(log_k[upperHull[i]]);
warning.append("\nlog_kDist[").append(upperHull[i]).append("] = ").append(log_kDist[upperHull[i]]);
}
@@ -444,7 +445,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
entry.setConservativeKnnDistanceApproximation(conservative);
entry.setProgressiveKnnDistanceApproximation(progressive);
- if (msg != null) {
+ if(msg != null) {
LOG.debugFine(msg.toString());
}
}
@@ -470,12 +471,12 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
double low_m = 0.0;
double low_t = 0.0;
- for (int i = 1; i < l; i++) {
+ for(int i = 1; i < l; i++) {
double cur_m = (log_kDist[lowerHull[i]] - log_kDist[lowerHull[i - 1]]) / (log_k[lowerHull[i]] - log_k[lowerHull[i - 1]]);
double cur_t = log_kDist[lowerHull[i]] - cur_m * log_k[lowerHull[i]];
double cur_error = ssqerr(k_0, settings.k_max, log_k, log_kDist, cur_m, cur_t);
msg.append(" Segment = ").append(i).append(" m = ").append(cur_m).append(" t = ").append(cur_t).append(" lowerror = ").append(cur_error).append("\n");
- if (cur_error < low_error) {
+ if(cur_error < low_error) {
low_error = cur_error;
low_m = cur_m;
low_t = cur_t;
@@ -484,13 +485,13 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
// linear search on all points of the lower convex hull
boolean is_right = true; // NEEDED FOR PROOF CHECK
- for (int i = 0; i < l; i++) {
+ for(int i = 0; i < l; i++) {
double cur_m = optimize(k_0, settings.k_max, sum_log_k, sum_log_k2, log_k[lowerHull[i]], log_kDist[lowerHull[i]], sum_log_k_kDist, sum_log_kDist);
double cur_t = log_kDist[lowerHull[i]] - cur_m * log_k[lowerHull[i]];
// only valid if both neighboring points are underneath y=mx+t
- if ((i == 0 || log_kDist[lowerHull[i - 1]] >= log_kDist[lowerHull[i]] - cur_m * (log_k[lowerHull[i]] - log_k[lowerHull[i - 1]])) && (i == l - 1 || log_kDist[lowerHull[i + 1]] >= log_kDist[lowerHull[i]] + cur_m * (log_k[lowerHull[i + 1]] - log_k[lowerHull[i]]))) {
+ if((i == 0 || log_kDist[lowerHull[i - 1]] >= log_kDist[lowerHull[i]] - cur_m * (log_k[lowerHull[i]] - log_k[lowerHull[i - 1]])) && (i == l - 1 || log_kDist[lowerHull[i + 1]] >= log_kDist[lowerHull[i]] + cur_m * (log_k[lowerHull[i + 1]] - log_k[lowerHull[i]]))) {
double cur_error = ssqerr(k_0, settings.k_max, log_k, log_kDist, cur_m, cur_t);
- if (cur_error < low_error) {
+ if(cur_error < low_error) {
low_error = cur_error;
low_m = cur_m;
low_t = cur_t;
@@ -498,9 +499,9 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
}
// check proof of bisection search
- if (!(i > 0 && log_kDist[lowerHull[i - 1]] < log_kDist[lowerHull[i]] - cur_m * (log_k[lowerHull[i]] - log_k[lowerHull[i - 1]])) && !is_right) {
+ if(!(i > 0 && log_kDist[lowerHull[i - 1]] < log_kDist[lowerHull[i]] - cur_m * (log_k[lowerHull[i]] - log_k[lowerHull[i - 1]])) && !is_right) {
// warning("ERROR lower: The bisection search will not work properly !");
- if (!(i < l - 1 && log_kDist[lowerHull[i + 1]] < log_kDist[lowerHull[i]] + cur_m * (log_k[lowerHull[i + 1]] - log_k[lowerHull[i]]))) {
+ if(!(i < l - 1 && log_kDist[lowerHull[i + 1]] < log_kDist[lowerHull[i]] + cur_m * (log_k[lowerHull[i + 1]] - log_k[lowerHull[i]]))) {
is_right = false;
}
}
@@ -519,14 +520,14 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
ApproximationLine approx = null;
double error = Double.POSITIVE_INFINITY;
- for (int i = 0; i < u - 1; i++) {
+ for(int i = 0; i < u - 1; i++) {
int ii = upperHull[i];
int jj = upperHull[i + 1];
double current_m = (log_kDist[jj] - log_kDist[ii]) / (log_k[jj] - log_k[ii]);
double current_t = log_kDist[ii] - current_m * log_k[ii];
ApproximationLine current_approx = new ApproximationLine(k_0, current_m, current_t);
- if (LOG.isDebugging()) {
+ if(LOG.isDebugging()) {
msg.append("\nlog_kDist[").append(jj).append("] ").append(log_kDist[jj]);
msg.append("\nlog_kDist[").append(ii).append("] ").append(log_kDist[ii]);
msg.append("\nlog_k[").append(jj).append("] ").append(log_k[jj]);
@@ -537,22 +538,22 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
boolean ok = true;
double currentError = 0;
- for (int k = k_0; k <= settings.k_max; k++) {
+ for(int k = k_0; k <= settings.k_max; k++) {
double appDist = current_approx.getValueAt(k);
- if (appDist < log_kDist[k - k_0] && log_kDist[k - k_0] - appDist > 0.000000001) {
+ if(appDist < log_kDist[k - k_0] && log_kDist[k - k_0] - appDist > 0.000000001) {
ok = false;
break;
}
currentError += (appDist - log_kDist[k - k_0]);
}
- if (ok && currentError < error) {
+ if(ok && currentError < error) {
approx = current_approx;
error = currentError;
}
}
- if (LOG.isDebugging()) {
+ if(LOG.isDebugging()) {
msg.append("\nupper Approx ").append(approx);
LOG.debugFine(msg.toString());
}
@@ -570,7 +571,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
int k_0 = settings.k_max - upperHull.length + 1;
int a = u / 2;
- while (marked.size() != u) {
+ while(marked.size() != u) {
marked.add(a);
double x_a = log_k[upperHull[a]];
double y_a = log_kDist[upperHull[a]];
@@ -578,7 +579,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
double m_a = optimize(k_0, settings.k_max, sum_log_k, sum_log_k2, x_a, y_a, sum_log_k_kDist, sum_log_kDist);
double t_a = y_a - m_a * x_a;
- if (msg != null) {
+ if(msg != null) {
msg.append("\na=").append(a).append(" m_a=").append(m_a).append(", t_a=").append(t_a);
msg.append("\n err ").append(ssqerr(k_0, settings.k_max, log_k, log_kDist, m_a, m_a));
}
@@ -591,23 +592,24 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
boolean lessThanPre = a == 0 || y_p <= m_a * x_p + t_a;
boolean lessThanSuc = a == u || y_s <= m_a * x_s + t_a;
- if (lessThanPre && lessThanSuc) {
+ if(lessThanPre && lessThanSuc) {
ApproximationLine appr = new ApproximationLine(k_0, m_a, t_a);
- if (msg != null) {
+ if(msg != null) {
msg.append("\n1 anchor = ").append(a);
LOG.debugFine(msg.toString());
}
return appr;
- } else if (!lessThanPre) {
- if (marked.contains(a - 1)) {
+ }
+ else if(!lessThanPre) {
+ if(marked.contains(a - 1)) {
m_a = (y_a - y_p) / (x_a - x_p);
- if (y_a == y_p) {
+ if(y_a == y_p) {
m_a = 0;
}
t_a = y_a - m_a * x_a;
ApproximationLine appr = new ApproximationLine(k_0, m_a, t_a);
- if (msg != null) {
+ if(msg != null) {
msg.append("2 anchor = ").append(a);
msg.append(" appr1 ").append(appr);
msg.append(" x_a ").append(x_a).append(", y_a ").append(y_a);
@@ -617,25 +619,28 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
LOG.debugFine(msg.toString());
}
return appr;
- } else {
+ }
+ else {
a = a - 1;
}
- } else {
- if (marked.contains(a + 1)) {
+ }
+ else {
+ if(marked.contains(a + 1)) {
m_a = (y_a - y_s) / (x_a - x_s);
- if (y_a == y_p) {
+ if(y_a == y_p) {
m_a = 0;
}
t_a = y_a - m_a * x_a;
ApproximationLine appr = new ApproximationLine(k_0, m_a, t_a);
- if (msg != null) {
+ if(msg != null) {
msg.append("3 anchor = ").append(a).append(" -- ").append((a + 1));
msg.append(" appr2 ").append(appr);
LOG.debugFine(msg.toString());
}
return appr;
- } else {
+ }
+ else {
a = a + 1;
}
}
@@ -657,11 +662,11 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
double upp_error = Double.MAX_VALUE;
double upp_m = 0.0;
double upp_t = 0.0;
- for (int i = 1; i < u; i++) {
+ for(int i = 1; i < u; i++) {
double cur_m = (log_kDist[upperHull[i]] - log_kDist[upperHull[i - 1]]) / (log_k[upperHull[i]] - log_k[upperHull[i - 1]]);
double cur_t = log_kDist[upperHull[i]] - cur_m * log_k[upperHull[i]];
double cur_error = ssqerr(k_0, settings.k_max, log_k, log_kDist, cur_m, cur_t);
- if (cur_error < upp_error) {
+ if(cur_error < upp_error) {
upp_error = cur_error;
upp_m = cur_m;
upp_t = cur_t;
@@ -669,13 +674,13 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
}
// linear search on all points of the upper convex hull
boolean is_left = true; // NEEDED FOR PROOF CHECK
- for (int i = 0; i < u; i++) {
+ for(int i = 0; i < u; i++) {
double cur_m = optimize(k_0, settings.k_max, sum_log_k, sum_log_k2, log_k[upperHull[i]], log_kDist[upperHull[i]], sum_log_k_kDist, sum_log_kDist);
double cur_t = log_kDist[upperHull[i]] - cur_m * log_k[upperHull[i]];
// only valid if both neighboring points are underneath y=mx+t
- if ((i == 0 || log_kDist[upperHull[i - 1]] <= log_kDist[upperHull[i]] - cur_m * (log_k[upperHull[i]] - log_k[upperHull[i - 1]])) && (i == u - 1 || log_kDist[upperHull[i + 1]] <= log_kDist[upperHull[i]] + cur_m * (log_k[upperHull[i + 1]] - log_k[upperHull[i]]))) {
+ if((i == 0 || log_kDist[upperHull[i - 1]] <= log_kDist[upperHull[i]] - cur_m * (log_k[upperHull[i]] - log_k[upperHull[i - 1]])) && (i == u - 1 || log_kDist[upperHull[i + 1]] <= log_kDist[upperHull[i]] + cur_m * (log_k[upperHull[i + 1]] - log_k[upperHull[i]]))) {
double cur_error = ssqerr(k_0, settings.k_max, log_k, log_kDist, cur_m, cur_t);
- if (cur_error < upp_error) {
+ if(cur_error < upp_error) {
upp_error = cur_error;
upp_m = cur_m;
upp_t = cur_t;
@@ -683,12 +688,12 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
}
// check proof of bisection search
- if (!(i > 0 && log_kDist[upperHull[i - 1]] > log_kDist[upperHull[i]] - cur_m * (log_k[upperHull[i]] - log_k[upperHull[i - 1]])) && !is_left) {
+ if(!(i > 0 && log_kDist[upperHull[i - 1]] > log_kDist[upperHull[i]] - cur_m * (log_k[upperHull[i]] - log_k[upperHull[i - 1]])) && !is_left) {
// warning("ERROR upper: The bisection search will not work properly !"
// +
// "\n" + Util.format(log_kDist));
}
- if (!(i < u - 1 && log_kDist[upperHull[i + 1]] > log_kDist[upperHull[i]] + cur_m * (log_k[upperHull[i + 1]] - log_k[upperHull[i]]))) {
+ if(!(i < u - 1 && log_kDist[upperHull[i + 1]] > log_kDist[upperHull[i]] + cur_m * (log_k[upperHull[i + 1]] - log_k[upperHull[i]]))) {
is_left = false;
}
}
@@ -703,7 +708,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
* @return a new leaf node
*/
@Override
- protected MkCoPTreeNode<O, D> createNewLeafNode() {
+ protected MkCoPTreeNode<O> createNewLeafNode() {
return new MkCoPTreeNode<>(leafCapacity, true);
}
@@ -713,7 +718,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
* @return a new directory node
*/
@Override
- protected MkCoPTreeNode<O, D> createNewDirectoryNode() {
+ protected MkCoPTreeNode<O> createNewDirectoryNode() {
return new MkCoPTreeNode<>(dirCapacity, false);
}
@@ -726,7 +731,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree
* the routing object of the parent node
*/
@Override
- protected MkCoPEntry createNewDirectoryEntry(MkCoPTreeNode<O, D> node, DBID routingObjectID, double parentDistance) {
+ protected MkCoPEntry createNewDirectoryEntry(MkCoPTreeNode<O> node, DBID routingObjectID, double parentDistance) {
return new MkCoPDirectoryEntry(routingObjectID, parentDistance, node.getPageID(), node.coveringRadius(routingObjectID, this), null);
// node.conservativeKnnDistanceApproximation(k_max));
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-08 05:00:28 +0000