In this Prolog version of the comprehensive project, we focus on the third step of the parallel DBSCAN algorithm (MapReduce) where we merge the intersection clusters from adjacent partitions introduced in the concurrent Go version.
The parallel DBSCAN algorithm extracts the clusters of a set by subdividing the region into a number of overlapping partitions. The fact that these partitions overlap with each other implies that some points (at the periphery of the partitions) might belong to more than one partition. Consequently, some clusters may contain the same point(s) and are then said to intersect.
In this case, these clusters must be merged because they should in fact constitute one large cluster covering more than one partition. The merging can be simply done by changing the label of one of the clusters to the one of the second.
Open the file main.pl in SWI-Prolog and type in the query start. to produce the text file output clusters.txt.
An alternative method is to run the program in SWISH, an online SWI-Prolog compiler.
Make sure the partition##.csv files are also in the same directory.
The parallel DBSCAN algorithm is based on the MapReduce pattern and proceeds as follows:
- Create partitions on the data
- Apply the DBSCAN algorithm over each partition
- Reduce the results by merging the clusters from all partition to create one single result. Intersecting clusters must be merged
In this part of the project, the 3rd step (merging the partitions step) will be implemented.
Suppose we have the 5 points of cluster A and the 8 points of cluster C in current ClusterList. We are now processing the partition containing clusters B and D. We first consider cluster D; it has no intersection with the points in ClusterList so its 4 points will simply be inserted to the list. Now if we consider cluster B, it has 3 points intersecting with cluster A and 4 points intersecting with cluster C. These 7 points will constitute the intersection set I and the labels of I are A and C. Consequently, the cluster label of all points in ClusterList having label A will be changed to B and same for the points having label C. Finally, the points in B are inserted into the ClusterList.
Given the figure above, the steps are illustrated as follows:
- Step 1: Start with an empty ClusterList. Add all the points in cluster A to the empty ClusterList.
- Step 2: Add all the points in cluster B into ClusterList. We see that cluster A (which is being added to ClusterList) and cluster B (which is already inside ClusterList) have at least one overlapping point, so, we convert all the PointIDs in cluster A to the PointIDs in cluster B. Now, cluster A and B are merged into one single cluster B.
- Step 3: Add all the points in cluster C into ClusterList. We see that cluster B created in step 2 and cluster C have at least one overlapping point, so, we convert all the PointIDs in cluster B to the PointIDs in cluster C. Now, the current cluster B and C are merged into one single cluster C.
- Step 4: Add all the points in cluster D into ClusterList as cluster D does not overlap with any other clusters.
Since we are not implementing the DBSCAN algorithm and only merging the results created by DBSCAN (specifically, the concurrent version), the dataset will be CSV files containing extracted clusters in each partition. Sample clustering results of 7 partitions are provided in 7 CSV files in the form partition##.csv. From that, we can create a knowledge base partition using the predicate import.
?- import.
partition(65, 1345, 40.750304, -73.952031, 65000001).
partition(65, 6017, 40.760146, -73.957873, 65000002).
partition(65, 17457, 40.760213, -73.955471, 65000003).
partition(65, 18582, 40.750299, -73.952027, 65000001).
partition(65, 20050, 40.750365, -73.952127, 65000001).
partition(65, 25351, 40.760153, -73.955467, 65000003).
partition(65, 34767, 40.758621, -73.957704, 65000004).
partition(65, 36487, 40.758621, -73.957704, 65000004).
...View Raw Cluster List Output
[[1345,40.750304,-73.952031,65000001],[6017,40.760146,-73.957873,65000002],[17457,40.760213,-73.955471,65000003],[18582,40.750299,-73.952027,65000001],[20050,40.750365,-73.952127,65000001],[25351,40.760153,-73.955467,65000003],[34767,40.758621,-73.957704,65000004],[36487,40.758621,-73.957704,65000004],[45516,40.760213,-73.955471,65000003],[47568,40.760213,-73.955471,65000003],[54926,40.758621,-73.957704,65000004],[62646,40.758621,-73.957704,65000004],[72026,40.760213,-73.955471,65000003],[81600,40.758623,-73.957706,65000004],[96975,40.760213,-73.955471,65000003],[98703,40.758621,-73.957704,65000004],[106539,40.750301,-73.951998,65000001],[110517,40.758621,-73.957704,65000004],[118199,40.76027,-73.958243,65000002],[120090,40.760213,-73.955471,65000003],[129867,40.760287,-73.958005,65000002],[132229,40.760195,-73.958036,65000002],[136126,40.759916,-73.958131,65000002],[138214,40.758623,-73.957706,65000004],[140763,40.750301,-73.951998,65000001],[146427,40.760243,-73.958027,65000002],[156573,40.760144,-73.958017,65000002],[164407,40.758621,-73.957704,65000004],[166384,40.758623,-73.957706,65000004],[166538,40.758623,-73.957706,65000004],[168525,40.760283,-73.958295,65000002],[173487,40.758623,-73.957706,65000004],[175085,40.760213,-73.955471,65000003],[189425,40.750329,-73.952151,65000001],[190220,40.760213,-73.955471,65000003],[193009,40.758621,-73.957704,65000004],[198847,40.760213,-73.955471,65000003],[201426,40.758621,-73.957704,65000004],[203222,40.758621,-73.957704,65000004],[211127,40.758623,-73.957706,65000004],[218717,40.760213,-73.955471,65000003],[224339,40.758621,-73.957704,65000004],[225855,40.760213,-73.955471,65000003],[228909,40.758621,-73.957704,65000004],[3245,40.74501,-73.949245,74000001],[3868,40.744845,-73.948922,74000001],[5894,40.744709,-73.946638,74000002],[6855,40.744919,-73.948974,74000001],[7030,40.749987,-73.94406,85000003],[8976,40.749987,-73.94406,85000003],[14169,40.744499,-73.948995,74000001],[15101,40.749987,-73.94406,85000003],[22106,40.74501,-73.949245,74000001],[33954,40.749987,-73.94406,85000003],[41303,40.74501,-73.949245,74000001],[42438,40.744647,-73.94681,74000002],[47427,40.744934,-73.948774,74000001],[50871,40.74493,-73.94889,74000001],[51019,40.744392,-73.948919,74000001],[52795,40.749987,-73.94406,85000003],[52913,40.744919,-73.948974,74000001],[53916,40.74502,-73.949245,74000001],[54925,40.745012,-73.949247,74000001],[55749,40.74471,-73.94883,74000001],[56191,40.749987,-73.94406,85000003],[62022,40.745012,-73.949247,74000001],[63398,40.749987,-73.94406,85000003],[63433,40.749987,-73.94406,85000003],[68620,40.744657,-73.946757,74000002],[77581,40.74501,-73.949245,74000001],[79259,40.744617,-73.94679,74000002],[84599,40.749987,-73.94406,85000003],[85661,40.744698,-73.948707,74000001],[85837,40.749987,-73.94406,85000003],[93113,40.74502,-73.949245,74000001],[99056,40.749987,-73.94406,85000003],[126318,40.74501,-73.949245,74000001],[126540,40.750168,-73.944085,85000003],[127428,40.749987,-73.94406,85000003],[128839,40.744617,-73.94679,74000002],[130509,40.749987,-73.94406,85000003],[131084,40.74468,-73.948955,74000001],[138689,40.749987,-73.94406,85000003],[144526,40.749987,-73.94406,85000003],[154470,40.745017,-73.949247,74000001],[164203,40.749987,-73.94406,85000003],[164610,40.745012,-73.949247,74000001],[165869,40.749987,-73.94406,85000003],[167109,40.744914,-73.94898,74000001],[169366,40.749987,-73.94406,85000003],[171917,40.745012,-73.949247,74000001],[172529,40.74501,-73.949245,74000001],[174373,40.744873,-73.948913,74000001],[184217,40.745061,-73.948786,74000001],[187138,40.744617,-73.94679,74000002],[188242,40.74501,-73.949245,74000001],[190356,40.744931,-73.948895,74000001],[191803,40.749987,-73.94406,85000003],[193214,40.74501,-73.949245,74000001],[196925,40.745012,-73.949247,74000001],[199960,40.749987,-73.94406,85000003],[202947,40.74501,-73.949245,74000001],[208234,40.749987,-73.94406,85000003],[211266,40.74502,-73.949245,74000001],[216901,40.745017,-73.949247,74000001],[219151,40.749987,-73.94406,85000003],[220761,40.749987,-73.94406,85000003],[224006,40.74501,-73.949245,74000001],[226877,40.749987,-73.94406,85000003],[230390,40.749987,-73.94406,85000003],[8459,40.7528,-73.950483,75000002],[31217,40.750393,-73.943973,85000003],[65507,40.752872,-73.950578,75000002],[79772,40.752711,-73.950531,75000002],[81778,40.752711,-73.950531,75000002],[81813,40.752531,-73.950412,75000002],[85053,40.752603,-73.950483,75000002],[119072,40.752603,-73.950483,75000002],[137428,40.752711,-73.950531,75000002],[144327,40.752711,-73.950531,75000002],[148011,40.752603,-73.950483,75000002],[156187,40.7528,-73.950483,75000002],[164742,40.7528,-73.950483,75000002],[174074,40.752711,-73.950531,75000002],[183447,40.752782,-73.950507,75000002],[186348,40.752711,-73.950531,75000002],[193756,40.752711,-73.950531,75000002],[15689,40.770193,-73.951154,76000001],[19607,40.770132,-73.951132,76000001],[19836,40.769738,-73.950683,76000001],[30997,40.769752,-73.951255,76000001],[33025,40.769979,-73.951293,76000001],[34887,40.769672,-73.950902,76000001],[39383,40.769594,-73.950861,76000001],[41652,40.769777,-73.950802,76000001],[47002,40.768872,-73.949765,76000002],[48864,40.76994,-73.950783,76000001],[55304,40.770248,-73.951275,76000001],[57133,40.769743,-73.950818,76000001],[58828,40.76398,-73.947577,76000004],[61559,40.768513,-73.949755,76000002],[66652,40.769501,-73.950909,76000001],[72371,40.768623,-73.949802,76000002],[74829,40.769528,-73.950827,76000001],[83314,40.767781,-73.949848,76000003],[87023,40.770149,-73.951269,76000001],[89864,40.770128,-73.9513,76000001],[91731,40.768828,-73.95007,76000002],[96095,40.767781,-73.949848,76000003],[100332,40.769641,-73.950809,76000001],[100771,40.76998,-73.951072,76000001],[106900,40.763972,-73.947502,76000004],[115914,40.769722,-73.950886,76000001],[116721,40.770279,-73.951199,76000001],[126088,40.769999,-73.951297,76000001],[134210,40.76994,-73.951277,76000001],[136493,40.77027,-73.9513,76000001],[137809,40.770157,-73.951283,76000001],[151260,40.768818,-73.950283,76000002],[159288,40.769972,-73.950673,76000001],[164215,40.769923,-73.950558,76000001],[166041,40.764107,-73.947575,76000004],[168512,40.769693,-73.950817,76000001],[169527,40.770132,-73.951132,76000001],[174919,40.770051,-73.951266,76000001],[176562,40.768468,-73.949447,76000002],[176760,40.770287,-73.951253,76000001],[177029,40.769732,-73.951202,76000001],[177712,40.768665,-73.949928,76000002],[177746,40.767703,-73.949894,76000003],[180258,40.768584,-73.949936,76000002],[184745,40.767781,-73.949848,76000003],[186953,40.768716,-73.949579,76000002],[188604,40.768502,-73.949802,76000002],[188678,40.770022,-73.951145,76000001],[201813,40.769858,-73.950787,76000001],[202540,40.764083,-73.947688,76000004],[202825,40.769745,-73.950935,76000001],[208551,40.767781,-73.949848,76000003],[210556,40.76863,-73.949765,76000002],[211135,40.77001,-73.951228,76000001],[213731,40.76428,-73.947617,76000004],[213748,40.769902,-73.951055,76000001],[217727,40.768427,-73.949547,76000002],[223021,40.769633,-73.950835,76000001],[226638,40.768735,-73.950092,76000002],[230722,40.769762,-73.950962,76000001],[20430,40.745162,-73.937342,84000003],[35805,40.749365,-73.94245,84000002],[65368,40.749365,-73.94245,84000002],[78338,40.745107,-73.937064,84000003],[83303,40.74513,-73.937215,84000003],[88067,40.749365,-73.94245,84000002],[102333,40.749657,-73.943125,84000004],[105666,40.745173,-73.936955,84000003],[137529,40.745042,-73.937038,84000003],[141580,40.749365,-73.94245,84000002],[142731,40.74957,-73.94288,84000004],[151622,40.749659,-73.943122,84000004],[159057,40.74513,-73.937402,84000003],[165627,40.749874,-73.943283,84000004],[173043,40.749659,-73.943122,84000004],[182196,40.749659,-73.943122,84000004],[183328,40.749365,-73.94245,84000002],[194038,40.749655,-73.943127,84000004],[203657,40.749853,-73.943472,84000004],[210436,40.749365,-73.94245,84000002],[224032,40.749657,-73.943125,84000004],[1311,40.75219,-73.938681,85000004],[3914,40.751392,-73.93988,85000001],[4993,40.751289,-73.940023,85000001],[5258,40.75418,-73.94214,85000002],[6314,40.751998,-73.93927,85000004],[7382,40.75411,-73.942377,85000002],[10188,40.750253,-73.938827,85000007],[14746,40.751418,-73.939917,85000001],[21758,40.750815,-73.940268,85000001],[24309,40.752429,-73.939027,85000004],[29394,40.758232,-73.937337,85000005],[31262,40.752862,-73.938563,85000004],[31340,40.758125,-73.937518,85000005],[34861,40.75261,-73.938698,85000004],[35259,40.750815,-73.940268,85000001],[35578,40.759826,-73.936991,86000001],[41710,40.75818,-73.937482,85000005],[41800,40.754008,-73.942542,85000002],[41911,40.750815,-73.940268,85000001],[42085,40.758183,-73.93758,85000005],[59542,40.758262,-73.937372,85000005],[59775,40.750815,-73.940268,85000001],[59837,40.758217,-73.937862,85000005],[63252,40.758128,-73.93753,85000005],[64641,40.752299,-73.938958,85000004],[64848,40.750815,-73.940268,85000001],[67875,40.758275,-73.937403,85000005],[68095,40.758148,-73.937478,85000005],[69715,40.751292,-73.940075,85000001],[71224,40.754122,-73.942244,85000002],[73531,40.754206,-73.942156,85000002],[74225,40.758112,-73.937528,85000005],[74834,40.759792,-73.936975,86000001],[75128,40.75261,-73.938698,85000004],[78159,40.750524,-73.93934,85000007],[80216,40.753975,-73.942527,85000002],[81135,40.751034,-73.940187,85000001],[82042,40.757922,-73.937453,85000005],[82499,40.751006,-73.940131,85000001],[83222,40.759875,-73.936926,86000001],[86994,40.754179,-73.942183,85000002],[91014,40.75816,-73.937568,85000005],[91835,40.752426,-73.93885,85000004],[93894,40.750909,-73.940572,85000001],[95883,40.754038,-73.942287,85000002],[96435,40.758235,-73.937485,85000005],[97234,40.758457,-73.93744,85000005],[98692,40.751313,-73.939944,85000001],[99541,40.754202,-73.942373,85000002],[100342,40.754235,-73.942097,85000002],[103572,40.758208,-73.9375,85000005],[107783,40.751278,-73.93992,85000001],[109869,40.754007,-73.942328,85000002],[110386,40.750535,-73.939829,85000007],[111927,40.754107,-73.94227,85000002],[112764,40.759808,-73.936956,86000001],[113022,40.750815,-73.940268,85000001],[113613,40.75261,-73.938698,85000004],[114302,40.750477,-73.939508,85000007],[118163,40.751108,-73.940117,85000001],[118428,40.759786,-73.936848,86000001],[118544,40.758168,-73.937817,85000005],[119657,40.758147,-73.93753,85000005],[119710,40.75109,-73.94023,85000001],[123723,40.750618,-73.939878,85000007],[124592,40.750815,-73.940268,85000001],[126602,40.758085,-73.937543,85000005],[126793,40.7582,-73.937397,85000005],[127842,40.754054,-73.942389,85000002],[130947,40.754128,-73.942364,85000002],[134345,40.750524,-73.939636,85000007],[137585,40.753972,-73.942498,85000002],[138202,40.752456,-73.938881,85000004],[139707,40.7512,-73.94025,85000001],[141789,40.750438,-73.939462,85000007],[145368,40.758217,-73.93737,85000005],[150071,40.750044,-73.939373,85000007],[150753,40.754107,-73.942114,85000002],[151434,40.75811,-73.9375,85000005],[151992,40.751126,-73.940126,85000001],[152243,40.751005,-73.940383,85000001],[154308,40.751327,-73.940025,85000001],[154544,40.754105,-73.942358,85000002],[155668,40.753968,-73.94263,85000002],[155865,40.759827,-73.93685,86000001],[157914,40.75447,-73.942128,85000002],[158887,40.751101,-73.940361,85000001],[161410,40.750265,-73.939017,85000007],[166805,40.758198,-73.93785,85000005],[168971,40.750558,-73.939422,85000007],[169530,40.758313,-73.937827,85000005],[171701,40.759658,-73.93683,86000001],[174534,40.758205,-73.937333,85000005],[178245,40.752348,-73.939025,85000004],[178807,40.750426,-73.939389,85000007],[180935,40.750403,-73.939198,85000007],[184521,40.758105,-73.937517,85000005],[188766,40.758067,-73.937582,85000005],[195394,40.750815,-73.940268,85000001],[195601,40.752176,-73.939186,85000004],[200967,40.750193,-73.938922,85000007],[204338,40.750293,-73.939216,85000007],[206190,40.75816,-73.937618,85000005],[207066,40.750542,-73.939373,85000007],[209858,40.758585,-73.937908,85000005],[216349,40.752128,-73.939288,85000004],[216757,40.750815,-73.940268,85000001],[218126,40.75261,-73.938698,85000004],[222167,40.75115,-73.940221,85000001],[225478,40.75827,-73.937582,85000005],[225771,40.750815,-73.940268,85000001],[226759,40.758233,-73.937435,85000005],[227778,40.7542,-73.942152,85000002],[230370,40.750815,-73.940268,85000001]]
Alternatively, view the output in the Ouput folder.
This merge part of the parallel DBSCAN algorithm is also implemented in the Scheme version of the comprehensive project.
I learned that it takes a lot of humility and patience to learn a new programming paradigm such as logic and declarative programming with Prolog. I had to start from scratch and I found that carrying the object-oriented and imperative way of thinking from previous programming languages not only did not help me advance in Prolog but also pulled me backwards. It felt like swimming against the tide and as a result, I had to abandon basic ideas such as the "return" statement or "loops". Once I understood that Prolog is about telling the machine what I want and using recursion to help me with that, the language and paradigm immediately clicked for me.
This project has given me a greater understand of recursion and a greater appreciation for declarative programming. Overall, I now have a strong grasp of Prolog, declarative, and logic programming thanks to this comprehensive DBSCAN project as well as the various assignments, labs, and tutorials I've done in the CSI2520 - Programming Paradigms course at uOttawa.