title: Different clustering algorithms to cluster timeseries events
body: <p>I have a very large input file with the following format:</p>
  
  <pre><code>ID \t time \t duration \t Description \t status
  </code></pre>
  
  <p>The status column is limited to contain either lower case a,s,i or upper case A,S,I or a mixed of the two (sample element in status col: a,si, I, asi, ASI, aSI, Asi...)</p>
  
  <p>The ultimate purpose is to cluster events that start and end at a "close enough' times in order to recognize that those events contribute to a bigger event. Close  enough here could be determined by a theta, let's say for now is 1 hour (or it could be 2 hours, or more, etc.). If two events that have start times within 1 hour and end times within 1 hour, we cluster them together and say that they are part of a big event.</p>
  
  <p>One other thing is that I only care about events that has all lower case letters in the status</p>
  
  <p>So below is my initial input processing:</p>
  
  <pre><code>I filter the input file so that it only contains rows that have all lower case letters
  This task is already done in Python using MapReduce and Hadoop
  
  Then I take the output file and split it into "boxes" where each box represents a time range (ex: 11am-12pm - box1, 12pm-1pm - box2, 1pm-2pm - box 3, etc...)
  
  Then use MapReduce again to sort each box based on start time (ascending order)
  
  The final output is an ordered list of start time
  </code></pre>
  
  <p>Now I want to develop an algorithm to group "similar events" together in the output above. Similar events are determined by start and end time.</p>
  
  <p>my current algorithm is:</p>
  
  <pre><code>pick the first item in the list
  
  find any event in the list that has start time is within 1 hour with first event start time and duration is +/- 1 hour with first item duration (duration determines the end time). 
  
  Then cluster them together (basically I want to cluster events that happen at the same time frame)
  
  If no other event found, move to the next available event (the one that has not been clustered).
  
  Keep doing this until no more events to be clustered.
  </code></pre>
  
  <p>I'm not sure if my algorithm will work or it's efficient. I'm trying to do an algorithm that is better than O (n^2), so hierarchical clustering won't work. K-means might not work also since I don't know ahead of time how many clusters I will need.</p>
  
  <p>There could be some other clustering algorithms that might fit better in my case. I think I might need some equations in my algorithm to calculate the distance in my cluster in order to determine similarity. I'm pretty new to this field, so any help to direct me to the right path is greatly appreciated.</p>
  
  <p>Thanks a lot in advance.</p>