Laboratory of Computer and Information Science > Teaching > T-61.5060 > Exercises 2007 > Solutions 4

Solutions for the 4th exercises

1. At least not totally. The counts seem to be quite level and also the occurrence times plot is just noise. But looking at the occurrence distances between event types as defined in Problem 2, there are some non-random behaviour that the differences in the densities can't explain.

   Some Matlab tests for the data.
   Plot of the occurrence times and pauses.





2. Create a matrix A, where A(i,j) will contain a list of distances from the ith event type to the next jth event type. We will traverse the occurrence list in reverse and remember the latest encountered occurrences of all event types in list L. For each event (in reverse) of type i we subtract its occurrence time from L's numbers and append these numbers to the A's ith row's elements. After this we update L_i to be the current time.

   Finally we can just calculate the mean and std for all the matrix elements.

   The complexity of the method is pretty easily seen to be O(Nk), where N is the number of events and k the number of event types.

   The algorithm for Matlab.





3. Say we create an occurrence matrix A from the locations of the points. Now we just want to find the rectangular tiles of A that have at least K ones in them.

   At first, we of course have to have a good way of calculating the number of ones in a rectangle. It can be achieved in constant time with a bit of precalculation. We fill a matrix W (as for [wans]) of size m x n so that W(i,j) gives the amount of ones in the rectangle R(1,i,1,j).

   W = zeros(m+1,n+1);
   for i = 2:m+1,
      for j = 2:n+1,
         W(i,j) = W(i-1,j) + W(i,j-1) - W(i-1,j-1);
         if(A(i,j) > 0)
            W(i,j) = W(i,j)+1;
         end
      end
   end
   W = W(2:,2:);
   

   After this the number of ones in R(a,b,c,d) can be given as W(b,d) - W(a-1,d) - W(b, c-1) + W(a-1,c-1). Now we can start looking for minimal rectangles. The basic solution might be to start with the singleton rectangles and spread them right and down with a breadth-first search. We cut the branch and add the current rectangle to the list whenever we get at least K ones. In the worst case the method will search through all the rectangles in the matrix, so the complexity will be O(m^2n^2), i.e. the size of the matrix squared although depending on K we might usually stop a bit earlier. It's not terrible, but it makes things difficult in practice, especially for memory.

   We can also calculate some upper bound for the number of found rectangles. Suppose we have a matrix filled with ones. For each width of a rectangle there exists a height so that a rectangle of that size is a minimal rectangle. There are naturally K (one to K) different widths to consider. As we can mount these rectangle's upper left corner to any of the matrix elements to get a new minimal rectangle, there are at most mnK minimal rectangles. More precisely the number of minimal rectangles in a filled-up matrix is mnK - O(max(m,n)K).

   Naturally we can do all sorts of optimizations to the method described above. We can for example start from the minimal rectangles of the filled-up matrix and not from singletons. This will save us O(mnK^2) rectangles at the start.