tzaeschke / phtree Goto Github PK
View Code? Open in Web Editor NEWPH-Tree
License: Apache License 2.0
PH-Tree
License: Apache License 2.0
Hello Mr. Zäschke,
I am a student of Information Technology and Communication in Brazil and currently work on a project titled Metric Indexing in Space Junctions at LNCC with Doctor Fábio Porto. In my research I worked on comparisons between data indexing methods like PH-tree, Slim-tree, Quatree. In these comparisons I observed the tree creation time and the search times to the neighbors in Range Queries. In short, I could see that PH-tree does not return all neighbors in their queries. I performed precision and recall calculations, and Slim-tree did better. Can you tell if the fact that PH-tree does not return all the neighbors is something normal of PH-tree's structure? It has something to do with the 'worst cases' mentioned in your article in '3.4 Spacial efficiency' or '3.5 Query efficiency'.
Thank you in advance.
André Muniz Demori - LNCC
Look at the new API and see whether it may improve performance.
Java already vectorizes code, so there may or may not be any benefit from using the new API.
Hello, another question I am studying that I did not find in the article is how binary conversion occurs on PH-tree with negative numbers. In the case of my project, I work with spatial positions, being right ascension and declination. Declination can have negative values. Can this affect something in the insertion and search in the PH-tree or does it come naturally with bit insertion?
Thank you in advance.
Add more tests for IEEE converter
See TinSpin tests using v16
Hi, i am trying to compile PH-tree C++ version for implement in another project. I'm trying to run the project on Clion. Do you have the CMakeList file? How you compile that? I'm trying to compile just the main file on terminal, but it's not working.
Best regards.
Hi there, I apologize if this has an obvious answer, but I couldn't find it from reading the code or searching the papers. Is it possible to do a near-neighbours query in a PH-tree that omits some number of dimensions, but can still do a pseudo-table scan in the dimensions that are provided?
The APIs take longs/doubles so I guess the first thing I'd try would be to pass infinities for the doubles, or min/max values for longs. Do you think this would work? :)
The update()
function for the new multimap could be more efficient.
When running TinSpin, the update()
test appears to cause a LOT of garbage collections.
Great library, thank you!
I've got 2 3d point clouds of a few thousand points each. There are no correlated "pairs of points", so to find the minimum offset between the two clouds I have to run through 1 cloud, get the single nearest neighbor from the other cloud, and sum up all the distances.
This is slower than expected, I think partially because the phtree search is optimized for returning a series of nodes sorted by distance, rather than "the one closest output node for each input node"
My question: Is there a better way to call this library that reduces overhead, and get the closest node for a whole bunch of starting location nodes?
My code:
fun averageNeighborDistance(other: OrientedCloud) = getNearestNeighbors(other).entries.sumByDouble {
it.key.distance(it.value)
} / size
fun getNearestNeighbors(other: OrientedCloud): Map<Vector3D, Vector3D> {
val result = mutableMapOf<Vector3D, Vector3D>()
oriented.forEach { myPoint ->
result[myPoint] = other.tree.nearestNeighbour(1, *myPoint.toArray()).next()!!
}
return result
}
Those repeated calls to nearestNeighbour(1,
is where my profiler says most of the time is spent. My uneducated guess is that some bulk function of "here is a a list of points from cloud0, please return the single nearest neighbor in cloud1 for each one" would possibly be faster.
However, maybe I am doing it the best way, and what looks like overhead with the NodeIteratorFullToList.init
call is where the sort-by-distance happens, and isn't something that can be optimized around.
Fix spurious error messages:
[ERROR] Array too large: 7 - 4 = 3
[ERROR] Array too large: 7 - 4 = 3
Consider porting the algorithm for min/max mask in window queries from phtree-cpp. The algorithm is more vectorization friendly.
Thanks for your work! I am just wondering how well it works on high dimensional data, such as SIFT or various deep features. Comparing with Hilbert curve, does it hold similar property in preserving the locality of the high dimensional points. That is, when two points a, b \in R^d are neighbors, they will be neighbors as well when they have been converted to one-dimensional values.
First of all, thanks for sharing the source code of your research work, which I think demonstrates, in combination with your papers, an exemplary attitude for conducting and publishing research work!
My question: As far as I understand, this implementation is not thread-safe. Is this correct? If so, what's the best way to use this library in concurrent applications, e.g., global lock or is this data structure kind of reactive and enables transactional modifications?
Further, is the library's implementation of iterators thread-safe? If iterators are thread-safe, I would use a fine-grained synchronization like this (pseudo)-code:
public Set<T> query(...) {
Iterator<T> it = null;
Set<T> result = new HashSet<T>();
synchronized (tree) {
it = tree.query(...);
}
while (it.hasNext()) {
result.add(it.next());
}
return result;
}
... otherwise this: (... which must, by the way, be similar to what would be required in the implementation of the iterators for storing a snapshot of the query result, if they are thread-safe but the data structure is not. The questions is just, what can I presume?)
public class ThreadsafeTree {
private PHTree tree = new PHTree(...);
public synchronized Set<T> query(...) {
Iterator<T> it = tree.query(...);
Set<T> result = new HashSet<T>();
while (it.hasNext()) {
result.add(it.next());
}
return result;
}
...
}
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.