What is the meaning of rank in the context of change-detection? In a technique that uses CUSUM for change-point detection in this paper, the first step is given below:

Let $x_1, x_2,..., x_n$ be the $n$
  samples in an event-series. The
  samples are ranked in increasing order
  and the rank $r_i$ for each sample is
  calculated. In case of ties, we assign
  average rank to each sample. The
  cumulative sums are computed as: $S_i = S_{i-1} + (r_i - \bar{r})$.
  If the ranks are randomly distributed, then
  there is no change-point. However, if
  there is indeed a change-point in the
  event-series, then higher ranks should
  dominate in either the earlier or
  later part of the event-series.

I am not quite sure I understand the meaning of rank in this context. For instance, if n=10 and my data points are: 5, 2, 4, 1, 9, 2, 9, 2, 10, 1 can someone please clarify what is really being done here?


*

*Sort in increasing order: 1, 1, 2, 2, 2, 4, 5, 9, 9, 10

*Assign Average Ranks to break ties: What does this step mean?

*Assign Final Ranks: What does this step mean?

 A: Given your data:
cp <- c(5, 2, 4, 1, 9, 2, 9, 2, 10, 1)

then the ranks, with ties being given average of the ranks, are:
> rank(cp)
 [1]  7.0  4.0  6.0  1.5  8.5  4.0  8.5  4.0 10.0  1.5

What is being done here? If you sort the data in increasing order, then we have a 1 in both rank order positions 1 and 2. We could assign rank 1 to both 1s, or rank 2, or as stated above, the average of the rank orders (1/2) / 2 = 1.5. This is why the two 1s have been given rank of 1.5 in the above output from R.
Now look at the next values in the rank order, the 2s. The 2's are in rank order positions 3, 4, and 5, therefore they all get rank 4 from (3+4+5) / 3 = 4, as this is the average of the tied ranks for these values.
If we initiate $S_0 = 0$, i.e. the zeroth cumulative sum is 0, we compute the $i$th cumulative sum ($S_i$) as the previous cumulative sum ($S_{i-1}$) plus the difference between the rank of the $i$th data point ($r_i$) and the average over all ranks $\bar{r}$.
For the above data, the average rank is:
> rcp <- rank(cp)
> mean(rcp)
[1] 5.5

The values $r_i - \bar{r}$ for this set of data are:
> rcp - mean(rcp)
 [1]  1.5 -1.5  0.5 -4.0  3.0 -1.5  3.0 -1.5  4.5 -4.0

and the cumulative sums are:
> cumsum(rcp - mean(rcp))
 [1]  1.5  0.0  0.5 -3.5 -0.5 -2.0  1.0 -0.5  4.0  0.0

