edu.umn.cs.spatialHadoop.core

Class RTree<T extends Shape>

java.lang.Object

edu.umn.cs.spatialHadoop.core.RTree<T>

All Implemented Interfaces:

java.io.Closeable, java.lang.AutoCloseable, java.lang.Iterable<T>

public class RTree<T extends Shape>
extends java.lang.Object
implements java.lang.Iterable<T>, java.io.Closeable

A disk-based R-tree that can be loaded using a bulk loading method and never changed afterwards. It works with any shape given in the generic parameter. To load the tree, use the bulkLoadWrite(byte[], int, int, int, DataOutput, boolean) method. To restore the tree from disk, use the readFields(DataInput) methods. To do queries against the tree, use the search(Shape, ResultCollector), knn(double, double, int, ResultCollector2) or spatialJoin(RTree, RTree, ResultCollector2) methods.

Author:

Ahmed Eldawy

Field Summary

Fields

Modifier and Type	Field and Description
static int	NodeSize Size of a node.
static int	TreeHeaderSize Size of tree header on disk.

Constructor Summary

Constructors

Constructor and Description
RTree()

Method Summary

Methods

Modifier and Type	Method and Description
void	bulkLoadWrite(byte[] element_bytes, int offset, int len, int degree, java.io.DataOutput dataOut, boolean fast_sort) Builds the RTree given a serialized list of elements.
static int	calculateStorageOverhead(int elementCount, int degree) Calculate the storage overhead required to build an RTree for the given number of nodes.
static int	calculateTreeStorage(int elementCount, int degree)
void	close()
static double	fastLog(int x)
static double	fastPow(double a, double b)
static int	findBestDegree(int bytesAvailable, int recordCount) Find the best (minimum) degree that can index the given number of records such that the whole tree structure can be stored in the given bytes available.
static int	getBlockCapacity(long blockSize, int degree, int recordSize) Given a block size, record size and a required tree degree, this function calculates the maximum number of records that can be stored in this block taking into consideration the overhead needed by node structure.
int	getElementCount() Returns total number of elements
static int	getHeaderSize(java.io.DataInput in) Returns the total size of the header (including the index) in bytes.
Rectangle	getMBR() Returns the MBR of the root
java.util.Iterator<T>	iterator()
int	knn(double qx, double qy, int k, ResultCollector2<T,java.lang.Double> output) k nearest neighbor query
static int	log2Floor(int x) Find log to the base 2 quickly
static Rectangle[]	packInRectangles(GridInfo gridInfo, Point[] sample) Create rectangles that together pack all points in sample such that each rectangle contains roughly the same number of points.
static int	powInt(int base, int exponent)
T	readElement(int i) Reads and returns the element with the given index
void	readFields(java.io.DataInput in)
int	search(Shape query, ResultCollector<T> output) Performs a range query over this tree using the given query range.
protected int	search(Shape query_shape, ResultCollector<T> output, int start, int end) Searches the RTree starting from the given start position.
void	setStockObject(T stockObject)
static int	skipHeader(java.io.InputStream in) Reads and skips the header of the tree returning the total number of bytes skipped from the stream.
static int	skipToEOL(byte[] bytes, int startOffset) Skip bytes until the end of line
static <S1 extends Shape,S2 extends Shape> int	spatialJoin(RTree<S1> R, RTree<S2> S, ResultCollector2<S1,S2> output)
protected static <S1 extends Shape,S2 extends Shape> int	spatialJoinDisk(RTree<S1> R, RTree<S2> S, ResultCollector2<S1,S2> output) Performs a spatial join between records in two R-trees
protected static <S1 extends Shape,S2 extends Shape> int	spatialJoinMemory(RTree<S1> R, RTree<S2> S, ResultCollector2<S1,S2> output)
void	write(java.io.DataOutput out)

Methods inherited from class java.lang.Object

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

Field Detail

TreeHeaderSize

public static final int TreeHeaderSize

Size of tree header on disk. Height + Degree + Number of records

See Also:

Constant Field Values

NodeSize

public static final int NodeSize

Size of a node. Offset of first child + dimensions (x, y, width, height)

See Also:

Constant Field Values

Constructor Detail

RTree

public RTree()

Method Detail

bulkLoadWrite

public void bulkLoadWrite(byte[] element_bytes,
                 int offset,
                 int len,
                 int degree,
                 java.io.DataOutput dataOut,
                 boolean fast_sort)

Builds the RTree given a serialized list of elements. It uses the given stockObject to deserialize these elements using TextSerializable.fromText(Text) and build the tree. Also writes the created tree to the disk directly.

Parameters:

element_bytes - - serialization of all elements separated by new lines

offset - - offset of the first byte to use in elements_bytes

len - - number of bytes to use in elements_bytes

degree - - Degree of the R-tree to build in terms of number of children per node

dataOut - - output stream to write the result to.

fast_sort - - setting this to true allows the method to run faster by materializing the offset of each element in the list which speeds up the comparison. However, this requires an additional 16 bytes per element. So, for each 1M elements, the method will require an additional 16 M bytes (approximately).

write

public void write(java.io.DataOutput out)
           throws java.io.IOException

Throws:

java.io.IOException

readFields

public void readFields(java.io.DataInput in)
                throws java.io.IOException

Throws:

java.io.IOException

skipHeader

public static int skipHeader(java.io.InputStream in)
                      throws java.io.IOException

Reads and skips the header of the tree returning the total number of bytes skipped from the stream. This is used as a preparatory function to read all elements in the tree without the index part.

Parameters:

in -

Returns:

- Total number of bytes read and skipped

Throws:

java.io.IOException

getHeaderSize

public static int getHeaderSize(java.io.DataInput in)
                         throws java.io.IOException

Returns the total size of the header (including the index) in bytes. Assume that the input is aligned to the start offset of the tree (header). Note that the part of the header is consumed from the given input to be able to determine header size.

Parameters:

in -

Returns:

Throws:

java.io.IOException

getElementCount

public int getElementCount()

Returns total number of elements

Returns:

getMBR

public Rectangle getMBR()

Returns the MBR of the root

Returns:

readElement

public T readElement(int i)

Reads and returns the element with the given index

Parameters:

i -

Returns:

Throws:

java.io.IOException

setStockObject

public void setStockObject(T stockObject)

packInRectangles

public static Rectangle[] packInRectangles(GridInfo gridInfo,
                           Point[] sample)

Create rectangles that together pack all points in sample such that each rectangle contains roughly the same number of points. In other words it tries to balance number of points in each rectangle. Works similar to the logic of bulkLoad but does only one level of rectangles.

Parameters:

samples -

gridInfo - - Used as a hint for number of rectangles per row or column

Returns:

skipToEOL

public static int skipToEOL(byte[] bytes,
            int startOffset)

Skip bytes until the end of line

Parameters:

bytes -

startOffset -

Returns:

iterator

public java.util.Iterator<T> iterator()

Specified by:

iterator in interface java.lang.Iterable<T extends Shape>

getBlockCapacity

public static int getBlockCapacity(long blockSize,
                   int degree,
                   int recordSize)

Given a block size, record size and a required tree degree, this function calculates the maximum number of records that can be stored in this block taking into consideration the overhead needed by node structure.

Parameters:

blockSize -

degree -

recordSize -

Returns:

search

protected int search(Shape query_shape,
         ResultCollector<T> output,
         int start,
         int end)
              throws java.io.IOException

Searches the RTree starting from the given start position. This is either a node number or offset of an element. If it's a node number, it performs the search in the subtree rooted at this node. If it's an offset number, it searches only the object found there. It is assumed that the openQuery() has been called before this function and that endQuery() will be called afterwards.

Parameters:

query_mbr -

output -

start - - where to start searching

end - - where to end searching. Only used when start is an offset of an object.

Returns:

Throws:

java.io.IOException

search

public int search(Shape query,
         ResultCollector<T> output)

Performs a range query over this tree using the given query range.

Parameters:

query - - The query rectangle to use (TODO make it any shape not just rectangle)

output - - Shapes found are reported to this output. If null, results are not reported

Returns:

- Total number of records found

knn

public int knn(double qx,
      double qy,
      int k,
      ResultCollector2<T,java.lang.Double> output)

k nearest neighbor query

Parameters:

qx -

qy -

k -

output -

spatialJoinMemory

protected static <S1 extends Shape,S2 extends Shape> int spatialJoinMemory(RTree<S1> R,
                                                        RTree<S2> S,
                                                        ResultCollector2<S1,S2> output)
                                throws java.io.IOException

Throws:

java.io.IOException

spatialJoinDisk

protected static <S1 extends Shape,S2 extends Shape> int spatialJoinDisk(RTree<S1> R,
                                                      RTree<S2> S,
                                                      ResultCollector2<S1,S2> output)
                              throws java.io.IOException

Performs a spatial join between records in two R-trees

Parameters:

R -

S -

output -

Returns:

Throws:

java.io.IOException - SuppresWarnings("resource") is used because we create LineReaders on the internal data stream of both R and S. We do not want to close the LineReader because it will subsequently close the internal data stream of R and S which is something we want to avoid because both R and S are not created by this function and it should not free these resources.

spatialJoin

public static <S1 extends Shape,S2 extends Shape> int spatialJoin(RTree<S1> R,
                                                  RTree<S2> S,
                                                  ResultCollector2<S1,S2> output)
                       throws java.io.IOException

Throws:

java.io.IOException

calculateStorageOverhead

public static int calculateStorageOverhead(int elementCount,
                           int degree)

Calculate the storage overhead required to build an RTree for the given number of nodes.

Returns:

- storage overhead in bytes

log2Floor

public static int log2Floor(int x)

Find log to the base 2 quickly

Parameters:

x -

Returns:

powInt

public static int powInt(int base,
         int exponent)

fastLog

public static double fastLog(int x)

fastPow

public static double fastPow(double a,
             double b)

findBestDegree

public static int findBestDegree(int bytesAvailable,
                 int recordCount)

Find the best (minimum) degree that can index the given number of records such that the whole tree structure can be stored in the given bytes available.

Parameters:

bytesAvailable -

recordCount -

Returns:

calculateTreeStorage

public static int calculateTreeStorage(int elementCount,
                       int degree)

close

public void close()
           throws java.io.IOException

Specified by:

close in interface java.io.Closeable

Specified by:

close in interface java.lang.AutoCloseable

Throws:

java.io.IOException