GeoSearch

gistfile1.aw

<?php
include("init.php");

ob_implicit_flush(true);
set_time_limit(0);
ini_set('memory_limit', '256M');

$t_start = microtime(true);

function msg($msg) {
	echo "\n{$msg}\t\t".getETA();
	flush();
	ob_flush();
}

function getETA() {
	global $processedPoints;
	global $avgTimePerPoint;
	global $expectedWorkload;

	$seconds = (($avgTimePerPoint * ($expectedWorkload - $processedPoints)));
	$percent = sprintf("%.1f",(($processedPoints * 100) / $expectedWorkload));

	$mins = floor($seconds / 60);
	$secs = $seconds % 60;

	return " (ETA {$mins}m{$secs}, ".sprintf("%.2f", $avgTimePerPoint)."sec per point, {$processedPoints}/{$expectedWorkload}, {$percent}% done)";
}

$processedPoints = 0;
$clustersCreated = 0;
$pointsAssigned = 0;
$orphanClusters = 0;

$clusterRadius = 3;
$expectedWorkload = 5000;

echo "<script>var scrollInterval = setInterval(function() {
	window.scrollTo(0, document.body.scrollHeight);
},100);</script>";

echo "<pre>";

$pdo = new PDO("mysql:host=localhost;port=3306;dbname=geosearch", "geosearch", "liquidi", array(
	PDO::MYSQL_ATTR_USE_BUFFERED_QUERY => 1, 
	PDO::ATTR_ERRMODE => PDO::ERRMODE_EXCEPTION
));
$mysqli = new MySQLI('localhost','geosearch','liquidi','geosearch');


$pdo->exec("TRUNCATE TABLE clusters");

$points = $pdo->query("SELECT * FROM points")->fetchAll();

// ---------------------------------------------------
// First pass: assign points to clusters, creating them when no existing ones are found nearby
// ---------------------------------------------------

// For each point in our graph
foreach($points as $point) {

	$ts_start = microtime(true);
	
	// Check if point belongs to a nearby cluster
	$clustersQuery = $mysqli->query("CALL get_nearby_clusters('{$point['lat']}','{$point['lng']}',{$clusterRadius});");

	if($clustersQuery) {
		$cluster = $clustersQuery->fetch_assoc();
	}
	
	// If no nearby clusters are found, we create a new cluster and assign the point to it
	// (this is done further down below)
	if(!$clustersQuery || !$cluster) {

		$pdo->exec("INSERT INTO clusters ( lat, lng, numPoints ) VALUES ( '{$point['lat']}', '{$point['lng']}', 1)");
		$clusterID = $pdo->lastInsertId();

		msg("Created new cluster {$clusterID} @\t {$point['lat']}, \t{$point['lng']}\t for point {$point['id']}");
		$clustersCreated++;
	
	// If we do find a cluster, we raise the point count for it and assign it to the found cluster 
	// (this is done further down below)
	} else {
		
		$clusterID = $cluster['id'];

		$pdo->exec("UPDATE clusters SET numPoints = numPoints + 1 WHERE id = {$clusterID}");

		msg("Assigned point {$point['id']} @ \t{$point['lat']}, \t{$point['lng']} \t to cluster {$cluster['id']} @ \t {$cluster['lat']}, \t{$cluster['lng']}");

		$pointsAssigned++;
	}	

	// Free extra result sets from the stored procedure (MySQL little glitch)
	$clustersQuery->free();
	while ($mysqli->next_result()) { 
		$result = $mysqli->use_result();
		if ($result instanceof mysqli_result) {
			$result->free();
		}
	}

	// Assign the point to the created/found cluster
	$pdo->exec("UPDATE points SET clusterID = {$clusterID} WHERE id = {$point['id']}");

	$processedPoints++;

	$ts_end = microtime(true);
	$avgTimePerPoint = round($ts_end - $ts_start, 2);

}

$orphanClusters = intval($pdo->query("SELECT COUNT(*) FROM clusters WHERE numPoints <= 1")->fetchColumn());

// ---------------------------------------------------
// Second pass: now we correct the clusters position to better suit the middle of the cluster
// ---------------------------------------------------

$clusters = $pdo->query("SELECT * FROM clusters")->fetchAll();

// For each cluster in our graph
foreach($clusters as $cluster) {
	
	// Get all points in the cluster
	$clusterPoints = $pdo->query("SELECT * FROM points WHERE clusterID = {$cluster['id']}")->fetchAll();
	
	$avgLat = 0;
	$avgLng = 0;

	// Add up their lats and lngs
	foreach($clusterPoints as $point) {
		$avgLat += $point['lat'];
		$avgLng += $point['lng'];
	}

	// Calculate the average to identify the center
	// This method is only works because the points are sure to be close by, and we're aiming for
	// performance instead of precision
	$avgLat /= sizeof($clusterPoints);
	$avgLng /= sizeof($clusterPoints);

	// Update the cluster position
	$pdo->exec("UPDATE clusters SET lat = '{$avgLat}', lng = '{$avgLng}' WHERE id = {$cluster['id']}");

	msg("Corrected coords from cluster #{$cluster['id']}, \t from {$cluster['lat']},\t{$cluster['lng']}\t\t to {$avgLat},\t{$avgLng}");


}

$t_end = microtime(true);

$t_total = $t_end - $t_start;
$timeElapsed = sprintf("%.4f",$t_total / 1000);

msg("[!!] Finished processing {$numPoints} - process took {$timeElapsed} seconds");
msg("Processed {$processedPoints} of {$numPoints}");
msg("Created {$clustersCreated} clusters (avg. ".round($processedPoints / $clustersCreated)." points per cluster)");
msg("Assigned a total of {$pointsAssigned} to found clusters");
msg("Found {$orphanClusters} orphan clusters (clusters with only 1 point)");

echo "<script>window.scrollTo(0, document.body.scrollHeight); clearInterval(scrollInterval);</script>";