@Test public void testKnn() { System.out.println("knn"); int[] recall = new int[testx.length]; for (int i = 0; i < testx.length; i++) { int k = 7; Neighbor[] n1 = lsh.knn(testx[i], k); Neighbor[] n2 = naive.knn(testx[i], k); for (Neighbor m2 : n2) { for (Neighbor m1 : n1) { if (m1.index == m2.index) { recall[i]++; break; } } } } System.out.format("q1 of recall is %d%n", MathEx.q1(recall)); System.out.format("median of recall is %d%n", MathEx.median(recall)); System.out.format("q3 of recall is %d%n", MathEx.q3(recall)); }
@Override @SuppressWarnings("unchecked") public Neighbor<double[], E>[] knn(double[] q, int k) { if (k < 1) { throw new IllegalArgumentException("Invalid k: " + k); } Set<Integer> candidates = getCandidates(q); k = Math.min(k, candidates.size()); HeapSelect<Neighbor<double[], E>> heap = new HeapSelect<>(new Neighbor[k]); for (int index : candidates) { double[] key = keys.get(index); if (q != key) { double distance = MathEx.distance(q, key); heap.add(new Neighbor<>(key, data.get(index), index, distance)); } } heap.sort(); return heap.toArray(); }
LSH implements NearestNeighborSearch<double[], E>, KNNSearch<double[], E>, RNNSearch<double[], E>, Serializable { @Override @SuppressWarnings("unchecked") public Neighbor<double[], E>[] knn(double[] q, int k) { if (k < 1) { throw new IllegalArgumentException("Invalid k: " + k); } Set<Integer> candidates = getCandidates(q); k = Math.min(k, candidates.size()); HeapSelect<Neighbor<double[], E>> heap = new HeapSelect<>(new Neighbor[k]); for (int index : candidates) { double[] key = keys.get(index); if (q != key) { double distance = MathEx.distance(q, key); heap.add(new Neighbor<>(key, data.get(index), index, distance)); } } heap.sort(); return heap.toArray(); } }
LSH implements NearestNeighborSearch<double[], E>, KNNSearch<double[], E>, RNNSearch<double[], E>, Serializable { @Override @SuppressWarnings("unchecked") public Neighbor<double[], E>[] knn(double[] q, int k) { if (k < 1) { throw new IllegalArgumentException("Invalid k: " + k); } Set<Integer> candidates = getCandidates(q); k = Math.min(k, candidates.size()); HeapSelect<Neighbor<double[], E>> heap = new HeapSelect<>(new Neighbor[k]); for (int index : candidates) { double[] key = keys.get(index); if (q != key) { double distance = MathEx.distance(q, key); heap.add(new Neighbor<>(key, data.get(index), index, distance)); } } heap.sort(); return heap.toArray(); } LSH(double[][] keys, E[] data, double w);  LSH(double[][] keys, E[] data, double w, int H);  LSH(int d, int L, int k, double w);  LSH(int d, int L, int k, double w, int H); }
LSH implements NearestNeighborSearch<double[], E>, KNNSearch<double[], E>, RNNSearch<double[], E>, Serializable { @Override @SuppressWarnings("unchecked") public Neighbor<double[], E>[] knn(double[] q, int k) { if (k < 1) { throw new IllegalArgumentException("Invalid k: " + k); } Set<Integer> candidates = getCandidates(q); k = Math.min(k, candidates.size()); HeapSelect<Neighbor<double[], E>> heap = new HeapSelect<>(new Neighbor[k]); for (int index : candidates) { double[] key = keys.get(index); if (q != key) { double distance = MathEx.distance(q, key); heap.add(new Neighbor<>(key, data.get(index), index, distance)); } } heap.sort(); return heap.toArray(); } LSH(double[][] keys, E[] data, double w);  LSH(double[][] keys, E[] data, double w, int H);  LSH(int d, int L, int k, double w);  LSH(int d, int L, int k, double w, int H); @Override String toString(); void put(double[] key, E value); @Override Neighbor<double[], E> nearest(double[] q); @Override @SuppressWarnings("unchecked") Neighbor<double[], E>[] knn(double[] q, int k); @Override void range(double[] q, double radius, List<Neighbor<double[], E>> neighbors); }
LSH implements NearestNeighborSearch<double[], E>, KNNSearch<double[], E>, RNNSearch<double[], E>, Serializable { @Override @SuppressWarnings("unchecked") public Neighbor<double[], E>[] knn(double[] q, int k) { if (k < 1) { throw new IllegalArgumentException("Invalid k: " + k); } Set<Integer> candidates = getCandidates(q); k = Math.min(k, candidates.size()); HeapSelect<Neighbor<double[], E>> heap = new HeapSelect<>(new Neighbor[k]); for (int index : candidates) { double[] key = keys.get(index); if (q != key) { double distance = MathEx.distance(q, key); heap.add(new Neighbor<>(key, data.get(index), index, distance)); } } heap.sort(); return heap.toArray(); } LSH(double[][] keys, E[] data, double w);  LSH(double[][] keys, E[] data, double w, int H);  LSH(int d, int L, int k, double w);  LSH(int d, int L, int k, double w, int H); @Override String toString(); void put(double[] key, E value); @Override Neighbor<double[], E> nearest(double[] q); @Override @SuppressWarnings("unchecked") Neighbor<double[], E>[] knn(double[] q, int k); @Override void range(double[] q, double radius, List<Neighbor<double[], E>> neighbors);  }