generalpacific / cg-spark

This project aims at implementing and evaluating some common Computation Geometry algorithms on Apache Spark.

CG_Spark - Implementation of Computational Geometry Algorithms in Apache Spark

This project implements some basic computational geometry algorithms in Apache Spark.

Setup

• Setup Scala: http://www.scala-lang.org/download/install.html
• Setup Spark: https://spark.apache.org/docs/latest/

Building

• mvn install

Running CG_Spark

lp - localpath where the jars are located in your system

• Skyline

$ bin/spark-submit --class edu.umn.cs.cgspark.operations.Skyline \
--master local[k] \
--driver-class-path \
lp/cgspark-0.0.1-SNAPSHOT.jar:lp/guava-18.0.jar \
lp/cgspark-0.0.1-SNAPSHOT.jar \
-i lp/<input-filename> -o <output-filename> -l \
-p <partitionsize>

• Closest Pair

$ bin/spark-submit --class \
edu.umn.cs.cgspark.operations.ClosestPair \
--master local[k] \
--driver-class-path \
lp/cgspark-0.0.1-SNAPSHOT.jar:lp/guava-18.0.jar \
lp/cgspark-0.0.1-SNAPSHOT.jar \
-i lp/<input-filename> -o <output-filename> -l \
-p <partitionsize>

• Command for generating datasets

$ java -jar InputCreator.jar \
<outputfile> <number of points> \
<distribution-uni|gaus|cor|anti|circle>

• Usage information:

-i,--input <arg>       Input File
-l,--isLocal           Run locally instead of as spark job
-o,--output <arg>      Output File
-p,--partition <arg>   Partition Size

cg-spark's Issues

Implement sequential convex hull algorithm

Research on optimizing merge step for calculating convex hull algorithm

How to merge the hulls more optimally? Can we use Dynamic Programming (like matrix multiplication)?

Main hindrance in this step is to guess the number of points in the final merged hull.

Initial Commit

Initial commit for README.md and few documentation.

Implement merging step for closest pair algorithm

Write Unit Tests for verifying correctness of convex hull sequential and merge algorithm

Implement Polygon union, farthest pair and skyline

Implement these algorithms following the same procedure as done for closest pair and convex hull.

Add multithreads to inpurcreator

Add steps to run the program in README.md

Test the sequential closest pair on ACM online judge

http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1186

Combine the sequential and merge algorithm for closest pair on Spark and evaluate the performance

Test the sequential and merging Convex algorithm on ACM online judge

Use this probem:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2673

Combine the sequential and merge algorithm for convex hull on Spark and evaluate the performance

Use spatial indices from SpatialHadoop and evaluation/experiment

Write unit test for closest pair algorithm

Implement Skyline in spark

Get results for Convex hull on spark vs CG_hadoop

Add logging to the operations

Use logging instead of system.out.printlln

Implement closest pair sequential algorithm

Document Issues and setting steps for Spark

Merge algorithm for merging to convex hulls

Write a class to create an input of arbitrary size