xxl.indexStructures
Class Tree.QueryIterator

java.lang.Object
  |
  +--xxl.indexStructures.Tree.QueryIterator

Direct Known Subclasses:

BTree.DescriptorQueryIterator

public static class Tree.QueryIterator

extends java.lang.Object

implements java.util.Iterator

Queries on the Tree are evaluated lazily (ONC). This means when query() is called a QueryIterator is returned. No work has yet been done.
Idea: start with the root-node: assess all entries, select those entries that are important for the query and insert them into a priority queue. If the top-element of the priority queue is a data-page an answer has been found else an index entry has been found. In that case the node referenced by that index entry has to be read and its nodes have to be assessed recursively.
This is a generalization of the incremental nearest-neighbor-search algorithm (Henrich 94, Hjaltason and Samet 95) and greatly facilitates the implementation of arbitrary query types on arbitrary trees.
Example: TODO

Inner Class Summary

static class

Tree.QueryIterator.Candidate A Candidate is an entry of the priority queue used for queries.

Field Summary

protected Function	assessment The assessment-function Function Object x Descriptor -> Object
protected Queue	queue The (priority-)queue used to store candidates that passed the selection-Function.
protected Function	selection The selection-Function checks whether the candidate is of interest.
protected int	targetLevel Determines the level, whose nodes TODO: Haeh?
protected Tree	tree The Tree to query.

Constructor Summary

protected

Tree.QueryIterator(Tree tree, Function assessment, Function selection, Queue queue, int targetLevel) Creates a new QueryIterator.

Method Summary

protected java.util.Iterator	expand(Tree.Node node, Tree.Descriptor nodeDescriptor, Function currentAssessment) Returns an Iterator of Candidate-Objects for all entries of node.
protected java.util.Iterator	filter(java.util.Iterator candidates) Removes all elements from the candidate set for which the selection-Function returns a value < 0.
boolean	hasNext() Checks whether there exists a next result.
java.lang.Object	next() Returns the next result of the query.
void	remove() Not supported.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

tree

protected Tree tree

The Tree to query.

assessment

protected Function assessment

The assessment-function
Function Object x Descriptor -> Object

selection

protected Function selection

The selection-Function checks whether the candidate is of interest. If not a value < 0 is returned. If the Candidate is a definite result a value > 0 is returned. Else (value == 0) the entries have to be checked in detail. Only those candidates are inserted into the priority-queue for which this Function returns a value >= 0.
Function Candidate -> Integer

queue

protected Queue queue

The (priority-)queue used to store candidates that passed the selection-Function.

targetLevel

protected int targetLevel

Determines the level, whose nodes TODO: Haeh?

Constructor Detail

Tree.QueryIterator

protected Tree.QueryIterator(Tree tree,
                             Function assessment,
                             Function selection,
                             Queue queue,
                             int targetLevel)

Creates a new QueryIterator.

Method Detail

expand

protected java.util.Iterator expand(Tree.Node node,
                                    Tree.Descriptor nodeDescriptor,
                                    Function currentAssessment)

Returns an Iterator of Candidate-Objects for all entries of node.

Parameters:

node - the node to be expanded

nodeDescriptor - the descriptor of the node

currentAssessment - the assessment that computes the value for each candidate-object

filter

protected java.util.Iterator filter(java.util.Iterator candidates)

Removes all elements from the candidate set for which the selection-Function returns a value < 0.

hasNext

public boolean hasNext()

Checks whether there exists a next result.

Specified by:

hasNext in interface java.util.Iterator

next

public java.lang.Object next()
                      throws java.util.NoSuchElementException

Returns the next result of the query.

Specified by:

next in interface java.util.Iterator

remove

public void remove()
            throws java.lang.UnsupportedOperationException

Not supported.

Specified by:

remove in interface java.util.Iterator