mtree.utils
Class Search

java.lang.Object
  extended by mtree.utils.Search

public class Search
extends java.lang.Object


Constructor Summary
Search()
           
 
Method Summary
static int divideObjectUsingPivots(messif.objects.LocalAbstractObject o, messif.objects.LocalAbstractObject p, float r)
          Decides whether an object o is placed inside a region determined by a pivot p and a radius r on the basis of precomputed distances to pivots without any additional distance computations.
static int divideObjectUsingPivots(messif.objects.LocalAbstractObject o, messif.objects.LocalAbstractObject p1, messif.objects.LocalAbstractObject p2)
          Decides whether the distance of an object o to a pivot p1 is farther than the distance to a pivot p2 on the basis of precomputed distances to pivots without any additional distance computations.
static boolean filterApproxNodeEntry(NodeEntry ne, float oParentDist, messif.objects.LocalAbstractObject q, float qParentDist, float r)
          Decides whether the specified node entry could be filtered.
static boolean filterNodeEntry(NodeEntry ne, float oParentDist, messif.objects.LocalAbstractObject q, float qParentDist, float r)
          Decides whether the specified node entry could be filtered.
static boolean filterNodeEntryUsingPivots(NodeEntry ne, messif.objects.LocalAbstractObject q, float r)
          Decides whether the specified node entry could be filtered in the sense of filtering using HR array.
static java.util.List<InternalNode> findLastInternalNodes(Node n)
          Looks for all internal nodes with node level 1 (descendants are leaves).
static java.util.List<LeafNode> findLeavesByQuery(Node n, messif.objects.LocalAbstractObject q, float r)
          Looks for all leaves which are incident to the region R(q, r).
static java.util.List<LeafNode> findLeavesByQuery(Node n, messif.objects.LocalAbstractObject q, float r, java.util.Map<messif.objects.LocalAbstractObject,java.lang.Float> pd)
          Looks for all leaves which are incident to the region R(q, r).
static void getAllBuckets(Node n, java.util.Collection<messif.buckets.LocalBucket> buckets)
          Looks for all buckets stored in all leaves of the subtree determined by node n.
static void getAllLeaves(Node n, java.util.List<LeafNode> leaves)
          Looks for all leaves of the subtree determined by node n.
static messif.objects.LocalAbstractObject setPrecompDistances(messif.objects.LocalAbstractObject q, messif.objects.LocalAbstractObject[] pivots)
          Creates the parent distance filter and the fixed array of precomputed distances to the pivots (in both cases the filters are created only if they are not presented within the object q).
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

Search

public Search()
Method Detail

setPrecompDistances

public static messif.objects.LocalAbstractObject setPrecompDistances(messif.objects.LocalAbstractObject q,
                                                                     messif.objects.LocalAbstractObject[] pivots)
Creates the parent distance filter and the fixed array of precomputed distances to the pivots (in both cases the filters are created only if they are not presented within the object q).


filterNodeEntry

public static boolean filterNodeEntry(NodeEntry ne,
                                      float oParentDist,
                                      messif.objects.LocalAbstractObject q,
                                      float qParentDist,
                                      float r)
Decides whether the specified node entry could be filtered.

Parameters:
ne - node entry to be filtered
oParentDist - the distance between the object stored in node entry ne and its parent pivot
q - query object
qParentDist - the distance between the query object and its parent pivot
r - query radius
Returns:
true if the node entry is filtered

filterNodeEntryUsingPivots

public static boolean filterNodeEntryUsingPivots(NodeEntry ne,
                                                 messif.objects.LocalAbstractObject q,
                                                 float r)
Decides whether the specified node entry could be filtered in the sense of filtering using HR array.

Returns:
true if the node entry is filtered

divideObjectUsingPivots

public static int divideObjectUsingPivots(messif.objects.LocalAbstractObject o,
                                          messif.objects.LocalAbstractObject p1,
                                          messif.objects.LocalAbstractObject p2)
Decides whether the distance of an object o to a pivot p1 is farther than the distance to a pivot p2 on the basis of precomputed distances to pivots without any additional distance computations.

Returns:
-1 if the distance to the pivot p1 is shorter than to the pivot p2

divideObjectUsingPivots

public static int divideObjectUsingPivots(messif.objects.LocalAbstractObject o,
                                          messif.objects.LocalAbstractObject p,
                                          float r)
Decides whether an object o is placed inside a region determined by a pivot p and a radius r on the basis of precomputed distances to pivots without any additional distance computations.

Returns:
-1 if the object o is placed inside the region

filterApproxNodeEntry

public static boolean filterApproxNodeEntry(NodeEntry ne,
                                            float oParentDist,
                                            messif.objects.LocalAbstractObject q,
                                            float qParentDist,
                                            float r)
Decides whether the specified node entry could be filtered. Note that the filtering is approximative.

Parameters:
oParentDist - the distance between the object stored in node entry ne and its parent pivot
qParentDist - the distance between the query object and its parent pivot
Returns:
true if the node entry is filtered

getAllLeaves

public static void getAllLeaves(Node n,
                                java.util.List<LeafNode> leaves)
Looks for all leaves of the subtree determined by node n.


getAllBuckets

public static void getAllBuckets(Node n,
                                 java.util.Collection<messif.buckets.LocalBucket> buckets)
Looks for all buckets stored in all leaves of the subtree determined by node n.


findLastInternalNodes

public static java.util.List<InternalNode> findLastInternalNodes(Node n)
Looks for all internal nodes with node level 1 (descendants are leaves).

Returns:
a list of internal nodes with node level 1

findLeavesByQuery

public static java.util.List<LeafNode> findLeavesByQuery(Node n,
                                                         messif.objects.LocalAbstractObject q,
                                                         float r)
Looks for all leaves which are incident to the region R(q, r).

Returns:
a list of leaves which are incident to the region R(q, r)

findLeavesByQuery

public static java.util.List<LeafNode> findLeavesByQuery(Node n,
                                                         messif.objects.LocalAbstractObject q,
                                                         float r,
                                                         java.util.Map<messif.objects.LocalAbstractObject,java.lang.Float> pd)
Looks for all leaves which are incident to the region R(q, r).

Returns:
a list of leaves which are incident to the region R(q, r)