edu.umn.cs.spatialHadoop.core

Class KdTreePartitioner

java.lang.Object

edu.umn.cs.spatialHadoop.core.Partitioner

edu.umn.cs.spatialHadoop.core.KdTreePartitioner

public class KdTreePartitioner
extends Partitioner

A partitioner that partitioner data using a K-d tree-based partitioner.

Author:

Ahmed Eldawy

Constructor Summary

Constructors

Constructor and Description
KdTreePartitioner() A default constructor to be able to dynamically instantiate it and deserialize it

Method Summary

Methods

Modifier and Type	Method and Description
void	createFromPoints(Rectangle mbr, Point[] points, int numPartitions) Populate this partitioner for a set of points and number of partitions
static int	getNumberOfSignificantBits(int x) Get number of significant bits.
CellInfo	getPartition(int id) Returns the details of a specific partition given its ID.
CellInfo	getPartitionAt(int index) Returns the detail of a partition given its position starting from zero and ending at partitionCount() - 1
int	getPartitionCount() Returns total number of partitions
static void	main(java.lang.String[] args)
int	overlapPartition(Shape shape) Returns only one overlapping partition.
void	overlapPartitions(Shape shape, ResultCollector<java.lang.Integer> matcher) Overlap a shape with partitions and calls a matcher for each overlapping partition.
static <T> void	partialQuickSort(T[] a, int fromIndex, int toIndex, int desiredIndex, java.util.Comparator<T> c) Reorders the given subrange of the array so that the element at the desiredIndex is at its correct position.
void	readFields(java.io.DataInput in)
void	write(java.io.DataOutput out)

Methods inherited from class edu.umn.cs.spatialHadoop.core.Partitioner

getPartitioner, setPartitioner

Methods inherited from class java.lang.Object

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

Constructor Detail

KdTreePartitioner

public KdTreePartitioner()

A default constructor to be able to dynamically instantiate it and deserialize it

Method Detail

createFromPoints

public void createFromPoints(Rectangle mbr,
                    Point[] points,
                    int numPartitions)

Description copied from class: Partitioner

Populate this partitioner for a set of points and number of partitions

Specified by:

createFromPoints in class Partitioner

partialQuickSort

public static <T> void partialQuickSort(T[] a,
                        int fromIndex,
                        int toIndex,
                        int desiredIndex,
                        java.util.Comparator<T> c)

Reorders the given subrange of the array so that the element at the desiredIndex is at its correct position. Upon return of this function, the element at the desired index is greater than or equal all previous values in the subrange and less than or equal to all following items in the subrange.

Parameters:

a - - the array to sort

fromIndex - - the index of the first element in the subrange

toIndex - - the index after the last element in the subrange

desiredIndex - - the index which needs to be adjusted

c - - the comparator used to compare array elements

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

getPartitionCount

public int getPartitionCount()

Description copied from class: Partitioner

Returns total number of partitions

Specified by:

getPartitionCount in class Partitioner

Returns:

overlapPartitions

public void overlapPartitions(Shape shape,
                     ResultCollector<java.lang.Integer> matcher)

Description copied from class: Partitioner

Overlap a shape with partitions and calls a matcher for each overlapping partition.

Specified by:

overlapPartitions in class Partitioner

overlapPartition

public int overlapPartition(Shape shape)

Description copied from class: Partitioner

Returns only one overlapping partition. If the given shape overlaps more than one partitions, the partitioner returns only one of them according to its own criteria. If it does not overlap any partition, it returns -1 which is an invalid partition ID.

Specified by:

overlapPartition in class Partitioner

Parameters:

shape -

Returns:

getPartitionAt

public CellInfo getPartitionAt(int index)

Description copied from class: Partitioner

Returns the detail of a partition given its position starting from zero and ending at partitionCount() - 1

Specified by:

getPartitionAt in class Partitioner

Returns:

getPartition

public CellInfo getPartition(int id)

Description copied from class: Partitioner

Returns the details of a specific partition given its ID.

Specified by:

getPartition in class Partitioner

Returns:

getNumberOfSignificantBits

public static int getNumberOfSignificantBits(int x)

Get number of significant bits. In other words, get the highest position of a bit that is set to 1 and add 1 to that position. For the value zero, number of significant bits is zero.

Parameters:

x -

Returns:

main

public static void main(java.lang.String[] args)
                 throws java.io.IOException

Throws:

java.io.IOException