@Test public void testKnn() { System.out.println("knn"); double[][] data = Matrix.randn(1000, 10).toArray(); CoverTree<double[]> coverTree = new CoverTree<>(data, new EuclideanDistance()); LinearSearch<double[]> naive = new LinearSearch<>(data, new EuclideanDistance()); for (int i = 0; i < data.length; i++) { Neighbor[] n1 = coverTree.knn(data[i], 10); Neighbor[] n2 = naive.knn(data[i], 10); assertEquals(n1.length, n2.length); for (int j = 0; j < n1.length; j++) { assertEquals(n1[j].index, n2[j].index); assertEquals(n1[j].value, n2[j].value); assertEquals(n1[j].distance, n2[j].distance, 1E-7); } } }
@Override public Neighbor<E, E>[] knn(E q, int k) { if (k <= 0) { throw new IllegalArgumentException("Invalid k: " + k); } if (k > data.length) { throw new IllegalArgumentException("Neighbor array length is larger than the dataset size"); } E e = root.getObject(); double d = distance.d(e, q); Neighbor<E, E> n1 = new Neighbor<>(e, e, root.idx, d); @SuppressWarnings("unchecked") Neighbor<E, E>[] a1 = (Neighbor<E, E>[]) java.lang.reflect.Array.newInstance(n1.getClass(), 1); if (root.children == null) { a1[0] = n1; return a1; } ArrayList<DistanceNode> currentCoverSet = new ArrayList<>(); ArrayList<DistanceNode> zeroSet = new ArrayList<>(); currentCoverSet.add(new DistanceNode(d, root)); DoubleHeapSelect heap = new DoubleHeapSelect(k); heap.add(Double.MAX_VALUE); boolean emptyHeap = true; if (root.getObject() != q) { heap.add(d); emptyHeap = false; } 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); } double upperBound = emptyHeap ? Double.MAX_VALUE : heap.peek(); if (d <= (upperBound + child.maxDist)) { if (c > 0 && d < upperBound) { if (child.getObject() != q) { heap.add(d); } } if (child.children != null) { nextCoverSet.add(new DistanceNode(d, child)); } else if (d <= upperBound) { zeroSet.add(new DistanceNode(d, child)); } } } } currentCoverSet = nextCoverSet; } ArrayList<Neighbor<E, E>> list = new ArrayList<>(); double upperBound = heap.peek(); for (int i = 0; i < zeroSet.size(); i++) { DistanceNode ds = zeroSet.get(i); if (ds.dist <= upperBound) { if (ds.node.getObject() != q) { e = ds.node.getObject(); list.add(new Neighbor<>(e, e, ds.node.idx, ds.dist)); } } } Neighbor<E, E>[] neighbors = list.toArray(a1); if (neighbors.length < k) { logger.warn(String.format("CoverTree.knn(%d) returns only %d neighbors", k, neighbors.length)); } Arrays.sort(neighbors); MathEx.reverse(neighbors); if (neighbors.length > k) { neighbors = Arrays.copyOf(neighbors, k); } return neighbors; }
CoverTree implements NearestNeighborSearch<E, E>, KNNSearch<E, E>, RNNSearch<E, E>, Serializable { @Override public Neighbor<E, E>[] knn(E q, int k) { if (k <= 0) { throw new IllegalArgumentException("Invalid k: " + k); } if (k > data.length) { throw new IllegalArgumentException("Neighbor array length is larger than the dataset size"); } E e = root.getObject(); double d = distance.d(e, q); Neighbor<E, E> n1 = new Neighbor<>(e, e, root.idx, d); @SuppressWarnings("unchecked") Neighbor<E, E>[] a1 = (Neighbor<E, E>[]) java.lang.reflect.Array.newInstance(n1.getClass(), 1); if (root.children == null) { a1[0] = n1; return a1; } ArrayList<DistanceNode> currentCoverSet = new ArrayList<>(); ArrayList<DistanceNode> zeroSet = new ArrayList<>(); currentCoverSet.add(new DistanceNode(d, root)); DoubleHeapSelect heap = new DoubleHeapSelect(k); heap.add(Double.MAX_VALUE); boolean emptyHeap = true; if (root.getObject() != q) { heap.add(d); emptyHeap = false; } 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); } double upperBound = emptyHeap ? Double.MAX_VALUE : heap.peek(); if (d <= (upperBound + child.maxDist)) { if (c > 0 && d < upperBound) { if (child.getObject() != q) { heap.add(d); } } if (child.children != null) { nextCoverSet.add(new DistanceNode(d, child)); } else if (d <= upperBound) { zeroSet.add(new DistanceNode(d, child)); } } } } currentCoverSet = nextCoverSet; } ArrayList<Neighbor<E, E>> list = new ArrayList<>(); double upperBound = heap.peek(); for (int i = 0; i < zeroSet.size(); i++) { DistanceNode ds = zeroSet.get(i); if (ds.dist <= upperBound) { if (ds.node.getObject() != q) { e = ds.node.getObject(); list.add(new Neighbor<>(e, e, ds.node.idx, ds.dist)); } } } Neighbor<E, E>[] neighbors = list.toArray(a1); if (neighbors.length < k) { logger.warn(String.format("CoverTree.knn(%d) returns only %d neighbors", k, neighbors.length)); } Arrays.sort(neighbors); MathEx.reverse(neighbors); if (neighbors.length > k) { neighbors = Arrays.copyOf(neighbors, k); } return neighbors; } }
CoverTree implements NearestNeighborSearch<E, E>, KNNSearch<E, E>, RNNSearch<E, E>, Serializable { @Override public Neighbor<E, E>[] knn(E q, int k) { if (k <= 0) { throw new IllegalArgumentException("Invalid k: " + k); } if (k > data.length) { throw new IllegalArgumentException("Neighbor array length is larger than the dataset size"); } E e = root.getObject(); double d = distance.d(e, q); Neighbor<E, E> n1 = new Neighbor<>(e, e, root.idx, d); @SuppressWarnings("unchecked") Neighbor<E, E>[] a1 = (Neighbor<E, E>[]) java.lang.reflect.Array.newInstance(n1.getClass(), 1); if (root.children == null) { a1[0] = n1; return a1; } ArrayList<DistanceNode> currentCoverSet = new ArrayList<>(); ArrayList<DistanceNode> zeroSet = new ArrayList<>(); currentCoverSet.add(new DistanceNode(d, root)); DoubleHeapSelect heap = new DoubleHeapSelect(k); heap.add(Double.MAX_VALUE); boolean emptyHeap = true; if (root.getObject() != q) { heap.add(d); emptyHeap = false; } 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); } double upperBound = emptyHeap ? Double.MAX_VALUE : heap.peek(); if (d <= (upperBound + child.maxDist)) { if (c > 0 && d < upperBound) { if (child.getObject() != q) { heap.add(d); } } if (child.children != null) { nextCoverSet.add(new DistanceNode(d, child)); } else if (d <= upperBound) { zeroSet.add(new DistanceNode(d, child)); } } } } currentCoverSet = nextCoverSet; } ArrayList<Neighbor<E, E>> list = new ArrayList<>(); double upperBound = heap.peek(); for (int i = 0; i < zeroSet.size(); i++) { DistanceNode ds = zeroSet.get(i); if (ds.dist <= upperBound) { if (ds.node.getObject() != q) { e = ds.node.getObject(); list.add(new Neighbor<>(e, e, ds.node.idx, ds.dist)); } } } Neighbor<E, E>[] neighbors = list.toArray(a1); if (neighbors.length < k) { logger.warn(String.format("CoverTree.knn(%d) returns only %d neighbors", k, neighbors.length)); } Arrays.sort(neighbors); MathEx.reverse(neighbors); if (neighbors.length > k) { neighbors = Arrays.copyOf(neighbors, k); } return neighbors; } 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 Neighbor<E, E>[] knn(E q, int k) { if (k <= 0) { throw new IllegalArgumentException("Invalid k: " + k); } if (k > data.length) { throw new IllegalArgumentException("Neighbor array length is larger than the dataset size"); } E e = root.getObject(); double d = distance.d(e, q); Neighbor<E, E> n1 = new Neighbor<>(e, e, root.idx, d); @SuppressWarnings("unchecked") Neighbor<E, E>[] a1 = (Neighbor<E, E>[]) java.lang.reflect.Array.newInstance(n1.getClass(), 1); if (root.children == null) { a1[0] = n1; return a1; } ArrayList<DistanceNode> currentCoverSet = new ArrayList<>(); ArrayList<DistanceNode> zeroSet = new ArrayList<>(); currentCoverSet.add(new DistanceNode(d, root)); DoubleHeapSelect heap = new DoubleHeapSelect(k); heap.add(Double.MAX_VALUE); boolean emptyHeap = true; if (root.getObject() != q) { heap.add(d); emptyHeap = false; } 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); } double upperBound = emptyHeap ? Double.MAX_VALUE : heap.peek(); if (d <= (upperBound + child.maxDist)) { if (c > 0 && d < upperBound) { if (child.getObject() != q) { heap.add(d); } } if (child.children != null) { nextCoverSet.add(new DistanceNode(d, child)); } else if (d <= upperBound) { zeroSet.add(new DistanceNode(d, child)); } } } } currentCoverSet = nextCoverSet; } ArrayList<Neighbor<E, E>> list = new ArrayList<>(); double upperBound = heap.peek(); for (int i = 0; i < zeroSet.size(); i++) { DistanceNode ds = zeroSet.get(i); if (ds.dist <= upperBound) { if (ds.node.getObject() != q) { e = ds.node.getObject(); list.add(new Neighbor<>(e, e, ds.node.idx, ds.dist)); } } } Neighbor<E, E>[] neighbors = list.toArray(a1); if (neighbors.length < k) { logger.warn(String.format("CoverTree.knn(%d) returns only %d neighbors", k, neighbors.length)); } Arrays.sort(neighbors); MathEx.reverse(neighbors); if (neighbors.length > k) { neighbors = Arrays.copyOf(neighbors, k); } return neighbors; } 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 Neighbor<E, E>[] knn(E q, int k) { if (k <= 0) { throw new IllegalArgumentException("Invalid k: " + k); } if (k > data.length) { throw new IllegalArgumentException("Neighbor array length is larger than the dataset size"); } E e = root.getObject(); double d = distance.d(e, q); Neighbor<E, E> n1 = new Neighbor<>(e, e, root.idx, d); @SuppressWarnings("unchecked") Neighbor<E, E>[] a1 = (Neighbor<E, E>[]) java.lang.reflect.Array.newInstance(n1.getClass(), 1); if (root.children == null) { a1[0] = n1; return a1; } ArrayList<DistanceNode> currentCoverSet = new ArrayList<>(); ArrayList<DistanceNode> zeroSet = new ArrayList<>(); currentCoverSet.add(new DistanceNode(d, root)); DoubleHeapSelect heap = new DoubleHeapSelect(k); heap.add(Double.MAX_VALUE); boolean emptyHeap = true; if (root.getObject() != q) { heap.add(d); emptyHeap = false; } 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); } double upperBound = emptyHeap ? Double.MAX_VALUE : heap.peek(); if (d <= (upperBound + child.maxDist)) { if (c > 0 && d < upperBound) { if (child.getObject() != q) { heap.add(d); } } if (child.children != null) { nextCoverSet.add(new DistanceNode(d, child)); } else if (d <= upperBound) { zeroSet.add(new DistanceNode(d, child)); } } } } currentCoverSet = nextCoverSet; } ArrayList<Neighbor<E, E>> list = new ArrayList<>(); double upperBound = heap.peek(); for (int i = 0; i < zeroSet.size(); i++) { DistanceNode ds = zeroSet.get(i); if (ds.dist <= upperBound) { if (ds.node.getObject() != q) { e = ds.node.getObject(); list.add(new Neighbor<>(e, e, ds.node.idx, ds.dist)); } } } Neighbor<E, E>[] neighbors = list.toArray(a1); if (neighbors.length < k) { logger.warn(String.format("CoverTree.knn(%d) returns only %d neighbors", k, neighbors.length)); } Arrays.sort(neighbors); MathEx.reverse(neighbors); if (neighbors.length > k) { neighbors = Arrays.copyOf(neighbors, k); } return neighbors; } 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);  }