public class VPPrefixTree
extends java.lang.Object
Modifier and Type | Class and Description |
---|---|
protected class |
VPPrefixTree.HeapItem |
protected class |
VPPrefixTree.VPPrefixNode |
Modifier and Type | Field and Description |
---|---|
protected java.util.List<VPPoint> |
points |
protected VPPrefixTree.VPPrefixNode |
root |
protected double |
tau |
Constructor and Description |
---|
VPPrefixTree(java.util.List<VPPoint> points) |
Modifier and Type | Method and Description |
---|---|
long |
add(VPPoint newNode)
TODO
Adds a single node to an existing vp-tree and returns the prefix of the
node.
|
void |
buildTree()
Constructs the vantage-point prefix tree from the list of points stored in
points . |
protected int |
nth_element(int lower,
int median,
int upper,
VPPoint vp)
Primitive implementation of the C++ std::nth_element algorithm.
|
void |
search(VPPoint target,
int k,
java.util.List<VPPoint> results,
java.util.List<java.lang.Integer> distances,
java.util.List<java.lang.Long> prefixes)
Conducts a nearest neighbor search over the vpp-tree with the specified
target . |
protected void |
search(VPPrefixTree.VPPrefixNode node,
VPPoint target,
int k,
java.util.PriorityQueue<VPPrefixTree.HeapItem> heap) |
protected VPPrefixTree.VPPrefixNode root
protected java.util.List<VPPoint> points
protected double tau
public VPPrefixTree(java.util.List<VPPoint> points)
public void buildTree()
points
.public void search(VPPoint target, int k, java.util.List<VPPoint> results, java.util.List<java.lang.Integer> distances, java.util.List<java.lang.Long> prefixes)
target
. The top k
results will be stored in
results
and their distances in distances
.target
- the query value to search fork
- the number of nearest neighborsresults
- a list the results will be stored indistances
- a list the distances will be stored inprotected void search(VPPrefixTree.VPPrefixNode node, VPPoint target, int k, java.util.PriorityQueue<VPPrefixTree.HeapItem> heap)
public long add(VPPoint newNode)
newNode
- node to be added to the vp-prefix-treejava.lang.IllegalArgumentException
- if newNode is nullprotected int nth_element(int lower, int median, int upper, VPPoint vp)