: Class Tree.Query

Overview

Package

Class

Tree

Deprecated

Index

Help

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: INNER | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

xxl.indexStructures
Class Tree.Query

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

public class Tree.Query
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
`class`	`Tree.Query.Candidate` A Candidate is an entry of the priority queue used for queries.

Field Summary
`protected Queue`	`queue` The (priority-)queue used to store candidates that passed the selection-Function.
`protected int`	`targetLevel` Determines the level, whose nodes TODO: Haeh?

Constructor Summary
`Tree.Query(Queue queue, int targetLevel)` Creates a new QueryIterator.

Method Summary
`protected Tree.Query.Candidate`	`createCandidate(Tree.Query.Candidate parent, java.lang.Object entry, Tree.Descriptor descriptor, int level)`
`protected java.util.Iterator`	`expand(Tree.Query.Candidate parent, Tree.Node node)` Returns an Iterator of Candidate-Objects for all entries of node.
`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

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.Query

public Tree.Query(Queue queue,
                  int targetLevel)

Creates a new QueryIterator.

Method Detail

createCandidate

protected Tree.Query.Candidate createCandidate(Tree.Query.Candidate parent,
                                               java.lang.Object entry,
                                               Tree.Descriptor descriptor,
                                               int level)

expand

protected java.util.Iterator expand(Tree.Query.Candidate parent,
                                    Tree.Node node)

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

hasNext

public boolean hasNext()

Checks whether there exists a next result.

Specified by:: hasNext in interface java.util.Iterator

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