Difference between revisions of "Parallel Enclosing Circle Algorithm"
| Line 36: | Line 36: | ||
<nowiki> | <nowiki> | ||
| − | $ python vc_circles.py --infile E:/McNair/Projects/OliverLovesCircles/CoLevelForCirclesNotRunGTE200.txt</nowiki> | + | $ python vc_circles.py --infile E:/McNair/Projects/OliverLovesCircles/CoLevelForCirclesNotRunGTE200.txt |
| + | $ python outjoiner.py</nowiki> | ||
where <code>CoLevelForCirclesNotRunGTE200.txt</code> is a tab-separated values file with the columns | where <code>CoLevelForCirclesNotRunGTE200.txt</code> is a tab-separated values file with the columns | ||
<code>placestate, place, statecode, year, latitude, longitude, coname, datefirstinv, placens, geoid, city</code> | <code>placestate, place, statecode, year, latitude, longitude, coname, datefirstinv, placens, geoid, city</code> | ||
Revision as of 11:52, 6 October 2017
| Parallel Enclosing Circle Algorithm | |
|---|---|
| Project Information | |
| Project Title | Parallel Enclosing Circle Algorithm |
| Owner | Oliver Chang |
| Start Date | July 31, 2017 |
| Deadline | October 4, 2017 |
| Primary Billing | |
| Notes | |
| Has project status | Complete |
| Is dependent on | Enclosing Circle Algorithm |
| Copyright © 2016 edegan.com. All Rights Reserved. | |
A thin-wrapper around the enclosing circle algorithm which allows for instance-level parallelization.
This project consists of the python files in E:\McNair\Projects\OliverLovesCircles\src\python.
Parallelization is implemented via Python2's subprocess.open() which is non-blocking and available in the standard library.
The Problem
Note that this is not the classical enclosing circle algorithm.
Rather, we seek to minimize the sum of enclosing circles containing at least n points.
Thus, multiple circles are allowed and inclusion in multiple circles is possible.
This algorithm has terrible time-performance characteristics, so we make the assumption that we can divide a large number of points with k-means and then solve those subproblems. In other words, we make the simplifying assumption that the Enclosing Circle Algorithm has Optimal Substructure.
Parameters
- in
circles.py:ITERATIONS: the number of iterations to attempt for eachkto find minimum for thatkMIN_POINTS_PER_CIRCLE(AKAn): the minimum number of data points that must be included in a circle
- in
vc_circles.pyNUMBER_INSTANCES: number of parallel instances to run; assume no data-races between instancesSWEEP_CYCLE_SECONDS: amount of time before removing completed jobs from the current job and adding new jobs if any files are left to processTIMEOUT_MINUTES: maximum running time of a parallel instance of the algorithmSPLIT_THRESHOLD: if a dataset has more than this threshold of data points, it will be split via k-means
Example Usage
$ python vc_circles.py --infile E:/McNair/Projects/OliverLovesCircles/CoLevelForCirclesNotRunGTE200.txt $ python outjoiner.py
where CoLevelForCirclesNotRunGTE200.txt is a tab-separated values file with the columns
placestate, place, statecode, year, latitude, longitude, coname, datefirstinv, placens, geoid, city
This command will populate (and overwrite) any files in data/. The format of the filenames in this directory are {city}{sep}{state}{sep}{year}{sep}{num}.tsv where num is a 0-indexed integer of a split city/state/year infile that has greater than SPLIT_THRESHOLD
