title: Implementing a fast DBSCAN in C#
body: <p>I tried to implement a DBSCAN in C# using kd-trees. I followed the implementation from: 
  <a href="http://www.yzuzun.com/2015/07/dbscan-clustering-algorithm-and-c-implementation/" rel="nofollow">http://www.yzuzun.com/2015/07/dbscan-clustering-algorithm-and-c-implementation/</a></p>
  
  <pre><code>public class DBSCANAlgorithm
  {
      private readonly Func&lt;PointD, PointD, double&gt; _metricFunc;
  
  
      public DBSCANAlgorithm(Func&lt;PointD, PointD, double&gt; metricFunc)
      {
          _metricFunc = metricFunc;
      }
  
      public void ComputeClusterDbscan(ScanPoint[] allPoints, double epsilon, int minPts, out HashSet&lt;ScanPoint[]&gt; clusters)
      {
          clusters = null;
          var allPointsDbscan = allPoints.Select(x =&gt; new DbscanPoint(x)).ToArray();
  
          var tree = new KDTree.KDTree&lt;DbscanPoint&gt;(2);
          for (var i = 0; i &lt; allPointsDbscan.Length; ++i)
          {
              tree.AddPoint(new double[] { allPointsDbscan[i].ClusterPoint.point.X, allPointsDbscan[i].ClusterPoint.point.Y }, allPointsDbscan[i]);
          }
  
          var C = 0;
          for (int i = 0; i &lt; allPointsDbscan.Length; i++)
          {
              var p = allPointsDbscan[i];
              if (p.IsVisited)
                  continue;
              p.IsVisited = true;
  
              DbscanPoint[] neighborPts = null;
              RegionQuery(tree, p.ClusterPoint.point, epsilon, out neighborPts);
              if (neighborPts.Length &lt; minPts)
                  p.ClusterId = (int)ClusterIds.NOISE;
              else
              {
                  C++;
                  ExpandCluster(tree, p, neighborPts, C, epsilon, minPts);
              }
          }
          clusters = new HashSet&lt;ScanPoint[]&gt;(
              allPointsDbscan
                  .Where(x =&gt; x.ClusterId &gt; 0)
                  .GroupBy(x =&gt; x.ClusterId)
                  .Select(x =&gt; x.Select(y =&gt; y.ClusterPoint).ToArray())
              );
  
          return;
      }
  
      private void ExpandCluster(KDTree.KDTree&lt;DbscanPoint&gt; tree, DbscanPoint p, DbscanPoint[] neighborPts, int c, double epsilon, int minPts)
      {
          p.ClusterId = c;
          for (int i = 0; i &lt; neighborPts.Length; i++)
          {
              var pn = neighborPts[i];
              if (!pn.IsVisited)
              {
                  pn.IsVisited = true;
                  DbscanPoint[] neighborPts2 = null;
                  RegionQuery(tree, pn.ClusterPoint.point, epsilon, out neighborPts2);
                  if (neighborPts2.Length &gt;= minPts)
                  {
                      neighborPts = neighborPts.Union(neighborPts2).ToArray();
                  }
              }
              if (pn.ClusterId == (int)ClusterIds.UNCLASSIFIED)
                  pn.ClusterId = c;
          }
      }
  
      private void RegionQuery(KDTree.KDTree&lt;DbscanPoint&gt; tree, PointD p, double epsilon, out DbscanPoint[] neighborPts)
      {
          int totalCount = 0;
          var pIter = tree.NearestNeighbors(new double[] { p.X, p.Y }, 10, epsilon);
          while (pIter.MoveNext())
          {
              totalCount++;
          }
          neighborPts = new DbscanPoint[totalCount];
          int currCount = 0;
          pIter.Reset();
          while (pIter.MoveNext())
          {
              neighborPts[currCount] = pIter.Current;
              currCount++;
          }
  
          return;
      }
  }
  
  //Dbscan clustering identifiers
  public enum ClusterIds
  {
      UNCLASSIFIED = 0,
      NOISE = -1
  }
  
  //Point container for Dbscan clustering
  public class DbscanPoint
  {
      public bool IsVisited;
      public ScanPoint ClusterPoint;
      public int ClusterId;
  
      public DbscanPoint(ScanPoint point)
      {
          ClusterPoint = point;
          IsVisited = false;
          ClusterId = (int)ClusterIds.UNCLASSIFIED;
      }
  }
  </code></pre>
  
  <p>, and modifying the <code>regionQuery(P, eps)</code> to invoke the nearest neighbour function of a kd-tree. To do so, I used the <code>kd-sharp</code> library for C#, which is one of the fastest kd-tree implementations out there.</p>
  
  <p>However, when given a dataset of about 20000 2d points, its performance is in the region of 40s, as compared to the <code>scikit-learn</code> python implementation of DBSCAN, which given the same parameters, takes about 2s.</p>
  
  <p>Since this algorithm is for a C# program that I am writing, I am stuck using C#. As such, I would like to find out what am I still missing out in terms of optimization of the algorithm?</p>