edu.umn.cs.spatialHadoop.operations

Class Skyline

java.lang.Object

edu.umn.cs.spatialHadoop.operations.Skyline

public class Skyline
extends java.lang.Object

Computes the skyline of a set of points

Author:

Ahmed Eldawy

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	Skyline.IdentityMapper An identity map function that returns values as-is with a null key.
static class	Skyline.SkylineFilter
static class	Skyline.SkylineReducer

Constructor Summary

Constructors

Constructor and Description
Skyline()

Method Summary

Methods

Modifier and Type	Method and Description
static void	main(java.lang.String[] args)
static void	skyline(Path inFile, Path outFile, OperationsParams params)
static Point[]	skyline(Point[] points, OperationsParams.Direction dir) Computes the skyline of a set of points using a divided and conquer in-memory algorithm.
static boolean	skylineDominate(Rectangle r1, Rectangle r2, OperationsParams.Direction dir, boolean compact) Returns true if r1 dominates r2 in the given direction.
static void	skylineLocal(Path inFile, Path outFile, OperationsParams params) Computes the skyline of an input file using a single machine algorithm.

Methods inherited from class java.lang.Object

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

Constructor Detail

Skyline

public Skyline()

Method Detail

skyline

public static Point[] skyline(Point[] points,
              OperationsParams.Direction dir)

Computes the skyline of a set of points using a divided and conquer in-memory algorithm. The algorithm recursively splits the points into half, computes the skyline of each half, and finally combines the two skylines.

Parameters:

points -

dir -

Returns:

skylineDominate

public static boolean skylineDominate(Rectangle r1,
                      Rectangle r2,
                      OperationsParams.Direction dir,
                      boolean compact)

Returns true if r1 dominates r2 in the given direction. r1 dominates r2 if one point in r1 dominates all points in r2. There are two rules for rectangle domination. We will describe them here in terms of MaxMax skyline but they can be expanded to cover all other skylines. 1- If the lowest corner of r1 dominates the highest corner of r2. 2- If the semi-lowest corner of r1 dominates the highest corner of r2. The lowest (highest) corner of a rectangle is the point inside this rectangle with the minimum (maximum) coordinates in all dimensions. The semi-lowest corner of a rectangle is a point inside the rectangle with the minimum coordinates in all dimensions except for one dimension which is the maximum coordinate. Rule 2 is applied only if rectangles are compact which means they are minimal bounding rectangles around contained points.

Parameters:

r1 -

r2 -

dir -

compact - - whether the input rectangles are compact or not

Returns:

skylineLocal

public static void skylineLocal(Path inFile,
                Path outFile,
                OperationsParams params)
                         throws java.io.IOException

Computes the skyline of an input file using a single machine algorithm. The output is written to the output file. If output file is null, the output is just thrown away.

Parameters:

inFile -

outFile -

dir -

overwrite -

Throws:

java.io.IOException

skyline

public static void skyline(Path inFile,
           Path outFile,
           OperationsParams params)
                    throws java.io.IOException

Throws:

java.io.IOException

main

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

Throws:

java.io.IOException