tzaeschke / tinspin-indexes Goto Github PK

Hi, I noticed yoy wrote that section in ReadMe.md under "performance" header.
"For kD-trees, try disabling defensive copy via IndexConfig..."
But there is no way to create IndexConfig externally as constructor has a package level of visability and there is no any factory method for creating it.
Could you check it?

The different iterators always return hasNext()=false when a key has a 'null' value assigned.

m0/m1 computation in the quadtree iterators could be improved by replacing

for (int d = 0; d < center.length; d++) {
	m0 <<= 1;
	m1 <<= 1;
	if (max[d] >= center[d]) {
		m1 |= 1;
		if (min[d] >= center[d]) {
			m0 |= 1;
		}
	}
}

with

for (int d = 0; d < center.length; d++) {
	m0 <<= 1;
	m1 <<= 1;
	//Extract signum bit
	m1 |= (Double.doubleToRawLongBits(center[d] - max[d]) >>> 63) & 1;
	m0 |= (Double.doubleToRawLongBits(center[d] - min[d]) >>> 63) & 1;
}

Hello, I believe I encountered a bug in QuadTreeKD2. It's not present in QuadTreeKD or QuadTreeKD0.

reproducer (data.txt):

package bug;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;

import org.tinspin.index.qthypercube.QuadTreeKD;
import org.tinspin.index.qthypercube2.QuadTreeKD2;
import org.tinspin.index.qtplain.QuadTreeKD0;

public class HelloWorld {
  public static void main(String[] args) {
    try {
      t();
    } catch (Exception e) {
    }
  }

 public static void t() throws Exception {
    BufferedReader reader = new BufferedReader(new FileReader("data.txt"));
    int n = Integer.parseInt(reader.readLine());
    QuadTreeKD2<Integer> tree = QuadTreeKD2.create(2);
    for (int i = 0; i < n; i++) {
      String[] sp = reader.readLine().split(" ");
      double d1 = Double.parseDouble(sp[0]), d2 = Double.parseDouble(sp[1]);

      tree.insert(new double[]{d1, d2}, i);
    }
    int k = Integer.parseInt(reader.readLine());
    for (int i = 0; i < k; i++) {
      String[] sp = reader.readLine().split(" ");
      double d1 = Double.parseDouble(sp[0]), d2 = Double.parseDouble(sp[1]);

      tree.remove(new double[]{d1, d2});
    }
    {
      String[] sp = reader.readLine().split(" ");
      double d1 = Double.parseDouble(sp[0]), d2 = Double.parseDouble(sp[1]);
      var node = tree.query1nn(new double[]{d1, d2});
      boolean has = tree.contains(node.point());
      System.out.println(n);

      System.out.println(has); // Should print true, but prints false with QuadTreeKD2
    }
  }
}

CritBitKD may rarely return wrong results of data is dense, i.e. if two data points differ exactly at a depth of 64 bit. CritBit would then store unnecessarily the first identical 64bit a infix, which would confuse the query iterator when rebuilding the keys during traversal.

See TestCritBitKD.test64_3_10000_queries.

Using the last version (2.0.0) in a Java 20 app breaks as follows:

Exception in thread "main" java.lang.NoClassDefFoundError: ch/ethz/globis/phtree/PhTreeF
at org.tinspin.index.phtree.PHTreeP.(PHTreeP.java:34)
at org.tinspin.index.phtree.PHTreeP.create(PHTreeP.java:38)
...
Caused by: java.lang.ClassNotFoundException: ch.ethz.globis.phtree.PhTreeF
at java.base/jdk.internal.loader.BuiltinClassLoader.loadClass(BuiltinClassLoader.java:641)
at java.base/jdk.internal.loader.ClassLoaders$AppClassLoader.loadClass(ClassLoaders.java:188)
Caused by: java.lang.ClassNotFoundException: ch.ethz.globis.phtree.PhTreeF

at java.base/java.lang.ClassLoader.loadClass(ClassLoader.java:521)
... 6 more

The dependency to tinspin is made via Gradle:

implementation 'org.tinspin:tinspin-indexes:2.0.0'

To reproduce, this simple code snippet is enough:

PHTreeP.create(2);

Adding the following dependency fixes the issue:

implementation 'ch.ethz.globis.phtree:phtree:2.8.0'

queryKD should not recheck the prefix when checking for a match. This is already done in the other query() classes.

This was done because the currentDepth parameter was not always correct.
To fix:

• Correct all implementations of checkMatch()
• Correct all calls to checkMatch, in particular, call it with n.posDIff-1 in constructors because the bit at n.posDepth is not set.

Can Tinspin support an indefinite nearest neighbor search, where I can iteratively query for the next nearest neighbor without a predetermined 'k' value?

Is it possible to simulate this by setting k to something like Integer.MAX_VALUE, or does Tinspin first search for and gather all points AND THEN provide an iterator on these, which would be less efficient?

Try using the MinMaxHeapPool from phtree-2.8.0 for reducing GC.

Hi, good evening.
I'm revisiting issue #33 and I noticed that the create factory method of org.tinspin.index.IndexConfig is no static.
Could you please clarify if this change is intentional?