@Test public void testStrings() { System.out.println("----- Strings -----"); String[] words = IndexNoun.words; CoverTree<String> cover = new CoverTree<>(words, new EditDistance(50, true)); long start = System.currentTimeMillis(); List<Neighbor<String, String>> neighbors = new ArrayList<>(); for (int i = 1000; i < 1100; i++) { cover.range(words[i], 1, neighbors); neighbors.clear(); } double time = (System.currentTimeMillis() - start) / 1000.0; System.out.format("String search: %.2fs%n", time); }
@Override public void range(E q, double radius, List<Neighbor<E, E>> neighbors) { if (radius <= 0.0) { throw new IllegalArgumentException("Invalid radius: " + radius); } ArrayList<DistanceNode> currentCoverSet = new ArrayList<>(); ArrayList<DistanceNode> zeroSet = new ArrayList<>(); double d = distance.d(root.getObject(), q); currentCoverSet.add(new DistanceNode(d, root)); while (!currentCoverSet.isEmpty()) { ArrayList<DistanceNode> nextCoverSet = new ArrayList<>(); for (int i = 0; i < currentCoverSet.size(); i++) { DistanceNode par = currentCoverSet.get(i); Node parent = currentCoverSet.get(i).node; for (int c = 0; c < parent.children.size(); c++) { Node child = parent.children.get(c); if (c == 0) { d = par.dist; } else { d = distance.d(child.getObject(), q); } if (d <= (radius + child.maxDist)) { if (child.children != null) { nextCoverSet.add(new DistanceNode(d, child)); } else if (d <= radius) { zeroSet.add(new DistanceNode(d, child)); } } } } currentCoverSet = nextCoverSet; } for (int i = 0; i < zeroSet.size(); i++) { DistanceNode ds = zeroSet.get(i); if (ds.node.getObject() != q) { neighbors.add(new Neighbor<>(ds.node.getObject(), ds.node.getObject(), ds.node.idx, ds.dist)); } } }
CoverTree implements NearestNeighborSearch<E, E>, KNNSearch<E, E>, RNNSearch<E, E>, Serializable { @Override public void range(E q, double radius, List<Neighbor<E, E>> neighbors) { if (radius <= 0.0) { throw new IllegalArgumentException("Invalid radius: " + radius); } ArrayList<DistanceNode> currentCoverSet = new ArrayList<>(); ArrayList<DistanceNode> zeroSet = new ArrayList<>(); double d = distance.d(root.getObject(), q); currentCoverSet.add(new DistanceNode(d, root)); while (!currentCoverSet.isEmpty()) { ArrayList<DistanceNode> nextCoverSet = new ArrayList<>(); for (int i = 0; i < currentCoverSet.size(); i++) { DistanceNode par = currentCoverSet.get(i); Node parent = currentCoverSet.get(i).node; for (int c = 0; c < parent.children.size(); c++) { Node child = parent.children.get(c); if (c == 0) { d = par.dist; } else { d = distance.d(child.getObject(), q); } if (d <= (radius + child.maxDist)) { if (child.children != null) { nextCoverSet.add(new DistanceNode(d, child)); } else if (d <= radius) { zeroSet.add(new DistanceNode(d, child)); } } } } currentCoverSet = nextCoverSet; } for (int i = 0; i < zeroSet.size(); i++) { DistanceNode ds = zeroSet.get(i); if (ds.node.getObject() != q) { neighbors.add(new Neighbor<>(ds.node.getObject(), ds.node.getObject(), ds.node.idx, ds.dist)); } } } }
CoverTree implements NearestNeighborSearch<E, E>, KNNSearch<E, E>, RNNSearch<E, E>, Serializable { @Override public void range(E q, double radius, List<Neighbor<E, E>> neighbors) { if (radius <= 0.0) { throw new IllegalArgumentException("Invalid radius: " + radius); } ArrayList<DistanceNode> currentCoverSet = new ArrayList<>(); ArrayList<DistanceNode> zeroSet = new ArrayList<>(); double d = distance.d(root.getObject(), q); currentCoverSet.add(new DistanceNode(d, root)); while (!currentCoverSet.isEmpty()) { ArrayList<DistanceNode> nextCoverSet = new ArrayList<>(); for (int i = 0; i < currentCoverSet.size(); i++) { DistanceNode par = currentCoverSet.get(i); Node parent = currentCoverSet.get(i).node; for (int c = 0; c < parent.children.size(); c++) { Node child = parent.children.get(c); if (c == 0) { d = par.dist; } else { d = distance.d(child.getObject(), q); } if (d <= (radius + child.maxDist)) { if (child.children != null) { nextCoverSet.add(new DistanceNode(d, child)); } else if (d <= radius) { zeroSet.add(new DistanceNode(d, child)); } } } } currentCoverSet = nextCoverSet; } for (int i = 0; i < zeroSet.size(); i++) { DistanceNode ds = zeroSet.get(i); if (ds.node.getObject() != q) { neighbors.add(new Neighbor<>(ds.node.getObject(), ds.node.getObject(), ds.node.idx, ds.dist)); } } } CoverTree(E[] dataset, Metric<E> distance);  CoverTree(E[] dataset, Metric<E> distance, double base); }
CoverTree implements NearestNeighborSearch<E, E>, KNNSearch<E, E>, RNNSearch<E, E>, Serializable { @Override public void range(E q, double radius, List<Neighbor<E, E>> neighbors) { if (radius <= 0.0) { throw new IllegalArgumentException("Invalid radius: " + radius); } ArrayList<DistanceNode> currentCoverSet = new ArrayList<>(); ArrayList<DistanceNode> zeroSet = new ArrayList<>(); double d = distance.d(root.getObject(), q); currentCoverSet.add(new DistanceNode(d, root)); while (!currentCoverSet.isEmpty()) { ArrayList<DistanceNode> nextCoverSet = new ArrayList<>(); for (int i = 0; i < currentCoverSet.size(); i++) { DistanceNode par = currentCoverSet.get(i); Node parent = currentCoverSet.get(i).node; for (int c = 0; c < parent.children.size(); c++) { Node child = parent.children.get(c); if (c == 0) { d = par.dist; } else { d = distance.d(child.getObject(), q); } if (d <= (radius + child.maxDist)) { if (child.children != null) { nextCoverSet.add(new DistanceNode(d, child)); } else if (d <= radius) { zeroSet.add(new DistanceNode(d, child)); } } } } currentCoverSet = nextCoverSet; } for (int i = 0; i < zeroSet.size(); i++) { DistanceNode ds = zeroSet.get(i); if (ds.node.getObject() != q) { neighbors.add(new Neighbor<>(ds.node.getObject(), ds.node.getObject(), ds.node.idx, ds.dist)); } } } CoverTree(E[] dataset, Metric<E> distance);  CoverTree(E[] dataset, Metric<E> distance, double base); @Override String toString(); @Override Neighbor<E, E> nearest(E q); @Override Neighbor<E, E>[] knn(E q, int k); @Override void range(E q, double radius, List<Neighbor<E, E>> neighbors); }
CoverTree implements NearestNeighborSearch<E, E>, KNNSearch<E, E>, RNNSearch<E, E>, Serializable { @Override public void range(E q, double radius, List<Neighbor<E, E>> neighbors) { if (radius <= 0.0) { throw new IllegalArgumentException("Invalid radius: " + radius); } ArrayList<DistanceNode> currentCoverSet = new ArrayList<>(); ArrayList<DistanceNode> zeroSet = new ArrayList<>(); double d = distance.d(root.getObject(), q); currentCoverSet.add(new DistanceNode(d, root)); while (!currentCoverSet.isEmpty()) { ArrayList<DistanceNode> nextCoverSet = new ArrayList<>(); for (int i = 0; i < currentCoverSet.size(); i++) { DistanceNode par = currentCoverSet.get(i); Node parent = currentCoverSet.get(i).node; for (int c = 0; c < parent.children.size(); c++) { Node child = parent.children.get(c); if (c == 0) { d = par.dist; } else { d = distance.d(child.getObject(), q); } if (d <= (radius + child.maxDist)) { if (child.children != null) { nextCoverSet.add(new DistanceNode(d, child)); } else if (d <= radius) { zeroSet.add(new DistanceNode(d, child)); } } } } currentCoverSet = nextCoverSet; } for (int i = 0; i < zeroSet.size(); i++) { DistanceNode ds = zeroSet.get(i); if (ds.node.getObject() != q) { neighbors.add(new Neighbor<>(ds.node.getObject(), ds.node.getObject(), ds.node.idx, ds.dist)); } } } CoverTree(E[] dataset, Metric<E> distance);  CoverTree(E[] dataset, Metric<E> distance, double base); @Override String toString(); @Override Neighbor<E, E> nearest(E q); @Override Neighbor<E, E>[] knn(E q, int k); @Override void range(E q, double radius, List<Neighbor<E, E>> neighbors);  }