# Knee Point Search Using Cascading Top-k Sorting with Minimized Time Complexity

Authors: Zheng Wang; Shian-Shyong Tseng
Journal: The Scientific World Journal
 (2013)

---

## Abstract

Anomaly detection systems and many other applications are frequently confronted with the problem of finding the largest knee point in the sorted curve for a set of unsorted points. This paper proposes an efficient knee point search algorithm with minimized time complexity using the cascading top-k sorting when a priori probability distribution of the knee point is known. First, a top-k sort algorithm is proposed based on a quicksort variation. We divide the knee point search problem into multiple steps. And in each step an optimization problem of the selection number k is solved, where the objective function is defined as the expected time cost. Because the expected time cost in one step is dependent on that of the afterwards steps, we simplify the optimization problem by minimizing the maximum expected time cost. The posterior probability of the largest knee point distribution and the other parameters are updated before solving the optimization problem in each step. An example of source detection of DNS DoS flooding attacks is provided to illustrate the applications of the proposed algorithm.


---

## Body

## 1. Introduction

Anomaly detection system and many other applications often rely on finding the largest knee point in the sorted curve to perform clustering, classification, anomaly identification, and so forth [1–6].  Here the largest knee point is targeted because the particular interests lie in finding the cluster of the largest points whose values differ significantly from their lower neighbors in the sorted curve.Knee point is defined as the point whose value is close to its upper neighbor while far from its lower neighbor in the sorted curve and thereby taken as the boundary of the cluster of upper points. For an unsorted list, it is necessary to sort it to facilitate the knee point search. Due to time and space efficiency considerations, the method of first completely sorting and then searching the sorted list is often not the optimal one. An alternative approach is to perform search on the partially sorted, namely, top-k, list, hoping to save the cost of sort.  Therefore the top-k sort algorithm is introduced to help minimize the time complexity of the knee point search in this paper. There have been many efforts for bounding and evaluating the time and space complexity of sort algorithms [7–12]. These works provide component algorithms for our work. But the problem of knee point search via top-k sorting has not been addressed by any of the previous works. We present in this paper a knee point search algorithm using top-k sorting with minimized time complexity.This paper is organized as follows: some basic concepts and definitions on knee point search and top-k sorting are presented in Section 2; Section 3 will design a knee point search algorithm, including basic idea, top-k sort algorithm, time complexity, parameter updating, cascading top-k sorting with minimized time complexity, the knee point search algorithm, and the solution of the optimization problem; Section 4 will introduce source detection of DNS DoS flooding attacks as an application example of the proposed algorithm; Section 5 will conclude this paper.


## 2. Knee Point Search and Selection Sort

Assume there aren points a1,a2,…,an whose values are q1,q2,…,qn. Let a1,a2,…,an be sorted by their values and let their differential values be δ1,δ2,…,δn,   where q1≥q2≥⋯≥qn, and
(1)δi={δ1i=1qi-1-qii=2,3,…,n.
As illustrated in Figure 1, there is usually a notable gap of value between points on the upper left side and those on the lower right side of the sorted curve. We define a knee point as the one whose neighboring differential values differ significantly.Figure 1
Sorted graph for first knee point search.Definition 1.
Pointai,i=1,2,…,n-1, is a knee point if it satisfies
(2)δi+1δi>θ,
where θ is the threshold, whose value ranges from 10 to 50 in the practice of anomaly detection.Note that there may be more than one knee point for a list, and the goal of the algorithm is to find the largest one in the sorted curve. For an unsorted list, we should first partially sort the list to find the sorted top-klist and then search the sorted top-klist for the largest knee point.Definition 2.
A top-k sort problem of selection number kfor an unsorted list L is a problem that finds k largest elements of L sorted in descending order.Apparently, total sort is often not optimal for the problem as knee point search may be successful on a partially sorted top-k list if it contains the largest knee point. Therefore it is preferable to selectively sort first using the top-k sort algorithm and then search in each step. The procedure may go through many recursive steps until finding the largest knee point for the search may fail in the previous steps. There is a tradeoff between the time cost and expected hit probability of knee point search in each step, both determined by the selection number and both contributing to the expected overall time cost. In this paper, the optimization problem of the selection number is solved by minimizing the maximum expected time cost.


## 3. The Knee Point Search Algorithm

### 3.1. Basic Idea

The knee point search algorithm is based on cascading top-k sorting. In each step, top-k sorting segments the list left to be searched. The optimal selection number is determined by minimizing the expected time cost on the list left. If the search successfully finds the knee point in the sorted top-k list, the algorithm ends there. Otherwise, the residual list excluding top-k requires further checking. It becomes the objective list for the next step and the function of the expected time cost using top-ksorting should also be updated according to the a priori knowledge that the search fails in the previous step. Thus the new top-k sort problem, likewise, holds for the next step. The algorithm runs in this way recursively until the knee point is found. There are two cases that bring the algorithm to the end.(1)
The knee point is found in the sorted top-k list in a step.(2)
The optimal selection number in one step equals the length of the objective list. This means the optimal option is total sorting. Therefore the knee point is certain to be found in the completely sorted list.


### 3.2. Top-k Sort Algorithm

We design a quicksort variation as the top-k sort algorithm. Quicksort is a very efficient sort algorithm invented by Hoare [7]. Quicksort has two phases: the partition phase and the sort phase, which makes it a good example of the divide and conquer strategy for solving problems.Top-k sorting only aims at treating the largest k elements, and thus it can be facilitated by the divide and conquer strategy. The intermediate results of quicksort, namely, the pivot positions, can be leveraged to possibly cut off one of the smaller problems divided from the bigger problem and to be conquered. For the strategy to be effective, the partition phase runs recursively only for the lower part if the pivot falls below position k, because there is no need to sort the upper part, which only consists of elements larger than top-k. This is the major distinction from the original quicksort algorithm and brings sorting efficiency.At the same time, the pivots located after positiondi (the optimal selection number) at step i in Section 3.6 are potentially useful for the afterwards steps, while they are actually not helpful for the inner top-di sorting. Therefore we record those pivots via a stack. A stack is a data structure featured by last in, first out (LIFO). Recalling that the recursive partitions with their pivots after position k produce their pivots in a sequential descending position order, we push these pivots into the stack resulting in a stack of pivots ordered by their positions. At the afterwards step i+1, if the optimal selection number di+1 is larger than the position of the pivot at the top of the stack, the pivot is popped from the stack used for an inner pivot of top-di+1. Since this pivot is no longer needed for the afterwards steps, it should not be maintained in the stack.  When the stack is empty or the pivot at the top of the stack (so do all of the other pivots) is located after the selection number, the partition has to run by itself to find a pivot without the help of the pivot stack.The top-k sort algorithm, namely, QuickSortTopK,  can be expressed as in Algorithm 1.Algorithm 1:QuickSortTopK(L, FirstIndex, LastIndex, k).
Input:
L: an unsorted list of length n
FirstIndex: the first index ofL to be sorted
LastIndex: the last index ofL to be sorted
k: top-k elements of L are to be sorted
Output:
L
k: Sorted top-k elements of L ranging from FirstIndex to LastIndex
S: a stack of pivot positons useful for the afterwards selection sorts
(1)if FirstIndex < LastIndex then
(2)if !isempty(S) & top(S) < LastIndex then  /* the stack is available */
(3)   pivotpos =pop(S)  /* use the top element of the stack as the pivot */
(4)else
(5)   /* Partition without using pivots from the stack */
(6)   pivotpos=Partition(L, FirstIndex, LastIndex)
(7)if  pivotpos− FirstIndex +1>k  then /* The pivot falls after position k */
(8)   /* The pivot may be useful for the afterwards steps */
(9)push(pivotpos, S)
(10)   /* QuickSort for top-k in the upper part */
(11)QuickSortTopK(L, FirstIndex, pivotpos −1, k)
(12)/* The pivot is located exactly at position k */
(13)elseif(pivotpos− FirstIndex +1==k)
(14)   /* QuickSort for top-k-1 in the upper part */
(15)QuickSortTopK(L, FirstIndex, pivotpos −1, k-1)
(16)else  /* The pivot falls prior to position k */
(17)    /* QuickSort the upper part */
(18)QuickSortTopK(L, FirstIndex, pivotpos −1, pivotpos− FirstIndex)
(19)    /* QuickSort for the residual elements in the lower part */
(20)QuickSortTopK(L, pivotpos +1, FirstIndex, k-pivotpos+ FirstIndex −1)The input of QuickSortTopK is the objective unsorted listL indexed from FirstIndex to LastIndex. For all steps, LastIndex is fixed at n, whereas FirstIndex is progressively increased to exclude the sorted part of L in all previous steps. The output includes the sorted top-k elements of L indexed from FirstIndex to LastIndex and the stack S containing all pivots falling after position k obtained in all previous steps.The termination condition of the recursion is checked in Line 1 of the algorithm. If the stack is nonempty and the top element of the stack falls into the objective range (see Line 2), the top element is used as the pivot for the partition (see Line 3). Otherwise, the pivot is obtained by a partition (see Line 6). Once the pivot is presented, different recursive steps are to be taken depending on the position of the pivot. If the pivot falls after positionk, it should be pushed into the stack and then run further sorting on the original list subtracting the pivot, hoping to help afterwards steps (see Lines 9, 11). If the pivot is located exactly at position k, the pivot itself is the last element of the output and thereafter only top-k-1 sorting on the original list subtracting the pivot is needed (see Line 15).  If the pivot is located prior to position k, both the upper and lower parts should be treated.  The action on the upper part is equivalent to Quicksort, while the action on the lower part is actually the recursive running of QuickSortTopK  with diminished selection number k and the shrinking  objective list (see Lines 18, 20).


### 3.3. Time Complexity

Let totally sorting of a list of lengthn require S(n) time. Calculated by the number of comparisons, the average time complexity of S(n) is O(nlog(n)) following some efficient algorithms, for example, Quicksort [7].Let top-k sorting of selection number k require C(k,n) time, where n is the length of the list. The QuickSortTopK algorithm requires an expected time of O(n+klogk). So C(k,n) equals O(n+klogk).Let the time complexity of finding the knee point in the sorted list of lengthn be D(n).  Recalling (2), D(n) takes  O(n).


### 3.4. Parameter Updating

For a list of lengthn, the algorithm divides the overall procedure into m+1 steps by a sequence of selection numbers, d1,d2,…,dm, 1≤d1<d2<⋯<dm≤n. Additionally, to facilitate the formulation, we let d0=0 and dm+1=n. Let the length of the objective list in step i,  i=1,2,…,m+1 be ni; we have
(3)ni=n-di-1,i=1,2,…,m+1.In the first step,ni=n. Let top-ki sorting for the objective list of length ni be performed in step i,  i=1,2,…,m+1, and we have
(4)ki=di-di-1,i=1,2,…,m+1.Particularly,ki=ni in step m+1. And thus top-ki sorting for the objective list of length ni is actually total sorting of the objective list. If the search of the knee point is successful in step i for the sorted top-ki list, the algorithm ends at step i. Otherwise, the algorithm continues with the next step. The algorithm lasts until step m+1 if the search misses in all of the previous steps during the progressive search. Since step m+1 takes no further selection of the objective list, the algorithm finishes in it.LetA be the position variable of the knee point and A=1,2,…,n. Let p(i) represent the probability that A=i,  i=1,2,…,n, and thus  ∑i=1np(i)=1. The value of p(i) is assumed to be known at the beginning of the algorithm. Let Ai be the position variable of the knee point in step i and Ai=di-1+1, di-1+2,…,n. Let pi(j) represent the probability that Ai=j,  j=di-1+1, di-1+2,…,n, i=1,2,…,m+1, and thus  ∑j=di-1+1npi(j)=1.Lemma 3.
The probability distribution of the knee point in stepi  pi(j) can be written as
(5)pi(j)=p(j)∑k=di-1+1np(k),j=di-1+1,di-1+2,…,n,i=1,2,…,m+1.Proof.
At the first step, all knowledge about the probability distribution of the knee point is only given byp(i). But the search in the afterward steps should make use of the posterior distribution of the knee point for it is confirmed not to exist prior to the selection number in the previous steps; for example, when the algorithm comes to step i, the knee point is already checked to be not present in the top-di-1 list, i=2,3,…,m+1. Therefore pi(j) should be updated in step i as
(6)pi(j)=P(Ai=j)=P(A=j∣A∈{di-1+1,di-1+2,…,n})=P(A=j,j∈{di-1+1,di-1+2,…,n})P(A∈{di-1+1,di-1+2,…,n})=p(j)∑k=di-1+1np(k)j=di-1+1,di-1+2,…,n,i=1,2,…,m+1.Let the hit probability of search in stepi  be Hi.Lemma 4.
The hit probability of search in stepi  Hi can be written as
(7)Hi(di)=∑j=di-1+1dipi(j),i=1,2,…,m+1.Proof.
For the selection numberdi in step i, the search for the knee point is successful if and only if the knee point falls into the interval of position among di-1+1 and di. According to Lemma 3, the probability distribution of the knee point at step i  pi(j) should be updated as (5). Therefore we have
(8)Hi(di)=∑j=di-1+1diP(Ai=j)=∑j=di-1+1dipi(j),i=1,2,…,m+1.


### 3.5. Cascading Top-k Sorting with Minimized Time Complexity

Lemma 5.
Let the expected overall computational time cost in stepi  be  tci;  tci yields
(9)tci=C(di-di-1,n-di-1)+(1-Hi(di))tci+1,i=1,2,…,m.Proof.
When the search succeeds in stepi, tci comes only from top-ki sorting which requires C(ki,ni) time and the search in the top-ki sorted list which requires D(n). However, recalling Section 3.3, the time complexity of D(n) is negligible compared to that of  C(ki,ni), so the summation of them can be approximated by C(ki,ni). For the failure of search in step i, the residual list of length ni-di has to be further checked. Thus the overall computation time cost consists of top-k sort and search in the remaining list. Note that the computation time cost of sort and search in the remaining list is no other than  tci+1. Hence  tci yields
(10)tci=Hi(di)C(ki,ni)+(1-Hi(di))(C(ki,ni)+tci+1)=C(ki,ni)+(1-Hi(di))tci+1,i=1,2,…,m.
Plugging (3) and (4) into (10), we get (9).Lemma5 tells us that the expected computational cost tc1 can be calculated iteratively following (7), until reaching tcm+1 where there is no selection for step m+1. Thus tcm+1 only consists of the time cost of total sorting of the list of length ni and the search in it. As total sorting takes S(ni) and search takes  D(ni), thus we have
(11)tcm+1=S(nm+1)+D(nm+1).LetN(a,b) (a≤b and a, b are integers) denote the set of integers {i∣a≤i≤bandiisinteger}. In every step i, the algorithm calculates the current probability distribution of the knee point which determines the hit probability Hi and chooses di to be the solution of the following optimization problem:
(12)Min:tcis.t.didi∈N(di-1+1,n).We see in (12) that for any fixed di the minimum of  tci  is determined by tci+1 under the optimal selection of di+1 in the next step, di∈N(di-1+1,n). And the optimal tci+1 for any fixed di+1 is also determined by the tci+2 under the optimal selection of  di+2  and so on. This kind of iterative dependency finally extends to the last step which has no further selection. So tci is the function of  di, di+1,…. The variation of any choice of selection in any number of steps makes the search space of optimization very huge, especially for the initial steps. Therefore it is not practical to evaluate all possibilities of selections in all of the afterwards steps when solving the optimization problem in step i. Thus it is necessary to constrain the variable of the objective function tci in (12) as mere di.Theorem 6.
The upper bound of the minimum oftci for a fixed di can be written as substituting tci+1 in (9) by  S(ni+1)+D(ni+1),  such that
(13)mindi+1∈N(di+1,n),di+2∈N(di+1+1,n),…tci≤C(di-di-1,n-di-1)+(1-Hi(di))(S(n-di)+D(n-di)),i=1,2,…,m.Proof.
We only need to prove that(14)mindi+1∈N(di+1,n),di+2∈N(di+1+1,n),…tci+1≤S(n-di)+D(n-di).
As total sort of the list of length ni+1 can be viewed as performing top-ni+1 sorting, their time costs are both S(ni+1)+D(ni+1). This is equivalent to the case when di+1=n. Because the algorithm ends with the total sorting and there are no afterwards steps, we have no definitions for  di+1, di+2,…. Thus we have
(15)tci+1|di+1=n(hencedi+2,di+3…hasnodefinition)=S(ni+1)+D(ni+1).
Hence
(16)mindi+1∈N(di+1,n),di+2∈N(di+1+1,n),…tci+1≤tci+1|di+1=n(hencedi+2,di+3,…hasnodefinition).
Plugging (3) into (15) and then (15) into (16), we have (14), and thereby (13) is proved.Theorem6 manifests that, for a fixed di, tci is definitely bounded by the time cost of total sort of the residual list of length ni+1plus that of search in it. The optimization problem in step i described by (13) can be isolated from all of the possible selections of the afterwards steps and becomes a function of mere di. This minmax technique brings convenience to our analysis, such that (13) can be simplified as
(17)Min:C(di-di-1,n-di-1)Min:+(1-Hi(di))(S(n-di)+D(n-di))s.t.didi∈N(di-1+1,n).
Plugging (5) into (17), we have
(18)Min:C(di-di-1,n-di-1)Min:+(1-∑j=di-1+1dipi(j))(S(n-di)+D(n-di))s.t.didi∈N(di-1+1,n).
Solving (14), we can obtain the optimal di in step i.


### 3.6. The Knee Point Search Algorithm

The knee point search algorithm runs iteratively using cascading top-k sorting. When the optimal selection number di is determined at step i, top-k sorting can be done via running QuickSortTopK  (L,di-1+1,n,di-di-1).  Specifically, the first step starts with QuickSortTopK   (L,1,n,d1).The procedure can be described as follows.Step 1.
(
1
)
According to (5), the probability distribution of the knee point for the optimization problem is initialized as follows
(19)p1(j)=p(j),j=1,2,…,n.
(
2
)
The optimal selection numberd1 is obtained by solving the following optimization problem as (18):
(20)Min:C(d1,n)+(1-∑j=1d1p(j))Min:×(S(n-d1)+D(n-d1))s.t.d1d1∈N(1,n).
(
3
)
Performtop-d1 sorting on the list of length n.
(
4
)
Search for the knee point on the sorted top-d1 list. If successful or d1=n, the algorithm ends. Otherwise, go to Step 2.Step 2.
(
1
)
The probability distribution of the knee point for the optimization problem is updated as follows:(21)p2(j)=p(j)∑k=d1+1np(k),j=d1+1,d1+2,…,n.
(
2
)
d
2 is derived as the solution of the following optimization problem:
(22)Min:C(d2-d1,n-d1)+(1-∑j=d1+1d2p2(j))Min:×(S(n-d2)+D(n-d2))s.t.d2d2∈N(d1+1,n).Note  that d1  is inherited from Step 1.(3)
Perform top-(d2-d1) selection sort on the list of length  n-d1 subtracting top-d1 elements in Step 1.(4)
Search for the knee point on the sorted top-(d2-d1) list. If successful or d2=n, the algorithm ends. Otherwise, go to Step 2.Step i.(1)
The probability distribution of the knee point for the optimization problem is updated according to (5).(2)
di is obtained as the solution of the optimization problem in (18), where di-1 is known from step i-1.(3)
Perform top-(di-di-1) selection sort on the list of length  n-di-1  subtracting top-di-1  elements already sorted in the previous steps.(4)
Search for the knee point on the sorted top-(di-di-1) list. If successful or di=n, the algorithm ends. Otherwise, go to step i+1.The knee point search algorithm can be summarized as  in Algorithm2.Algorithm 2:FindKnee(L, P).
Input: Unsorted list L of length n, probability distribution of the knee point in the sorted
list of lengthn: P
Output: The knee point e or the non-existence of it (e = null).
(1) /* initialize the parameters for the optimization problem */
(2)P1←P, L1←L
(3)i←1
(4)while (true)
(5)solve the optimization problem of list Li in (18) to get di
(6)if  di=ni  then  /* total sorting is the optimal option */
(7) totally sort list Li
(8) /* successful if the knee point exists */
(9) Search the sorted list for the knee point e
(10) break  /* the algorithm is completed */
(11)else  /* top-(di-di-1) sort is the optimal option */
(12) QuickSortTopK(L, di-1 + 1, n, di–di-1)
(13) Search the sorted list for the knee point e
(14) if  e is found then
(15)break
(16) else  /* Update the parameters for the next round of optimization problem */
(17)   updatePi+1 according to (5)  /* the posterior probability */
(18)   updateLi+1 by exluding the top-(di-di-1) item from list Li
(19)i←i+1
(20)return  eThe knee point search algorithm can also be expressed recursively.For each recursive step, we have an unsorted listL of length n and the probability distribution of the knee point in the sorted list of length n:P. Thus we can modify the optimization problem in (18) as follows:
(23)Min:C(d,n)+(1-∑j=1dp(j))(S(n-d)+D(n-d))s.t.d∈d∈N(1,n).Solving (14), we can obtain the optimal d in each recursive step.When the knee point search fails after top-k sorting in each recursive step, the algorithm has to go to the next recursive step. First, we need to update the probability distribution of the knee point as well as the residual unsorted list as two parameters for the recursive function. According to Lemma 3, the update of the probability distribution of the knee point yields
(24)p(j)⟵p(j)∑k=d+1np(k),j=d+1,d+2,…,n.In each recursive step, top-k sorting can be done via running QuickSortTopK(L, 1, length(L), d), where L is the objective list in the current step and length(L) denotes the length ofL.A recursive version of knee point search algorithm can be summarized as in Algorithm3.Algorithm 3:FindKnee(L, P).
Input: Unsorted list L of length n, probability distribution of the knee point in the sorted
list of lengthn: P
Output: The knee point e or the non-existence of it (e = null).
(1)solve the optimization problem of list L in (20) to get d
(2)if  d=n then  /* total sort is the optimal option */
(3) totally sort list L
(4) /* successful if the knee point exists */
(5) Search the sorted list for the knee point e
(6) return e /* the algorithm is completed */
(7)else  /* top-d sorting is the optimal option */
(8) QuickSortTopK(L, 1, length(L), d)
(9) Search the sorted list for the knee point e
(10)if e is found then
(11) return e
(12)else  /* Update the parameters for the next round of optimization problem */
(13)    updateP according to (5)  /* the posterior probability */
(14)update L by exluding the top-d item from list L
(15)FindKnee(L, P)


### 3.7. The Solution of the Optimization Problem

In this section, we will assume two forms of the probability distribution of the knee point and discuss the solutions of (18) under these presumptions.(1) Uniform Distribution. p(i) is equal for all i∈N(1,n), and thus p(i)=1/n. Plugging p(i) into (23), we have
(25)Min:C(d,n)+(1-dn)(S(n-d)+D(n-d))s.t.d∈N(1,n).Let(26)f(d)=C(d,n)+(1-dn)(S(n-d)+D(n-d)).
Although (26) is a discrete function, we still utilize the method of derivation to find the extremum, which can be only applied to the continuous and derivable function. Here we treat the discrete variable d as continuous ones, and thereafter (26) turns into a continuous and derivable function. This is a rational approximation of the problem, which facilitates our analysis and solving. The final solution should be the round-off of d obtained by solving the continuous function.For simplicity, we let(27)C(k,n)=c1(n+klogk)S(n)=c2(nlog(n))D(n)=c3n,
where c1,c2, and c3 are all constants.By choosingd such that  df(d)/d=0, we have the optimal d which satisfies
(28)c1(1+logd)n=(n-d)[2c2log(n-d)+2c3+c2].For largen and d, we have the approximation of (28) as
(29)c1nlogd=2c2(n-d)log(n-d).To get the explicit mathematical expression of the solution of the nonlinearity equation (29), we used a heuristic approach to simplify the problem. We assume that d  is a proportion function of  n, such that
(30)d=pn,0<p<1,
where p decides the optimum of d.Thus (30) yields
(31)c1nlog(pn)=2c2(1-p)nlog[(1-p)n],
then
(32)c1nlog(p)+c1nlog(n)=2c2(1-p)nlog(1-p)+2c2(1-p)nlog(n).Leave out the low order item in both sides of (32), and we get
(33)c1nlog(p)+c1nlog(n)≈c1nlog(n),2c2(1-p)nlog(1-p)+2c2(1-p)nlog(n)≈2c2(1-p)nlog(n).Plugging (33) into (32), the optimum of p yields
(34)p=1-c12c2.We can see that the optimum ofp that takes the form of a proportion function of n exists only when c1<2c2. Particularly, if c1=c2=1, the optimum of p is 1/2, which means that the optimum first selection number is half of the length of the list. As the search algorithm may run recursively if the knee point search misses, the optimal method is the so-called binary search or logarithmic search method.Theorem 7.
If the probability distribution of the knee point follows uniform distribution and the optimal selection number takes the form of (30), the optimal method for the knee point search algorithm is binary search or logarithmic search method.Proof.
We first prove using an inductive method that in each recursive step of the search algorithm,p(i) is equal for all  i∈N(1,n).
We know that for the first recursive step,p(i) is equal for all i∈N(1,n) as the starting point of the induction. Then for the second recursive step, we can derive according to (24) that p(i) is equal for all  i∈N(1,n).
Suppose that for thelth recursive step, p(i) is equal for all i∈N(1,n). Similarly, for the (l+1)th recursive step, p(i) is equal for all i∈N(1,n) following (24).
Therefore we can form the concept inductively that in each recursive step of the knee point search algorithm,p(i) is equal for all i∈N(1,n). So the optimization problem in each recursive step can be written as no other than (25), whose solution of number of selection is half of the length of the list discussed above. Here the list is the one left from previous recursive step. Hence the optimal method for the search algorithm is binary search or logarithmic search method.(2) Inverse Proportion Distribution. p(i) is in direct inverse proportion to i, i∈N(1,n), and thus p(i)=c/i, where c=1/∑i=1n(1/i).As an approximate treatment of the summation∑i=ab(1/i), we consider
(35)∑i=ab1i≈∫ab1xdx.Particularly, fora=1 and a large b, we have
(36)∑i=1b1i=lnb+E.And for a largen, we have
(37)c=1/(lnn+E),
where E is the Euler constant and has the approximate value as 0.5772.Pluggingp(i) and then (36) and (37) into (23), we have
(38)Min:C(d,n)+(1-lnd+Elnn+E)(S(n-d)+D(n-d))s.t.d∈d∈N(1,n).Let(39)g(d)=C(d,n)+(1-lnd+Elnn+E)(S(n-d)+D(n-d)).Theorem 8.
If the probability distribution of the knee pointp(i) is in direct inverse proportion to i,  i∈N(1,n), the optimal top-k sorting for the knee point search algorithm is full sorting of the list for a large length of the list.Proof.
We only need to prove thatg(d) is a monotony increase function of d, and the equivalent condition for it is
(40)dg(d)d=c1(1+logd)-c2(n-d)log(n-d)-c3n(lnn+E)d-c2(lnn-lnd)(1+log(n-d))lnn+E<0,
that is,
(41)c1(1+logd)(lnn+E)d<c2(n-d)log(n-d)+c3n+c2(lnn-lnd)(1+log(n-d))d.
We assume thatd is an exponential function of n, such that
(42)d=nq,0<q<1.
Thus the left and right sides of (41) can be, respectively, written as
(43)c1(1+logd)(lnn+E)d~O((logn)2nq)(44)c2(n-d)log(n-d)+c3n+c2(lnn-lnd)(1+log(n-d))d~O(n).
Comparing (43) and (44), we obtain (41) for a large n. That means the optimal selection number is n for the first step, or the optimal top-k sorting for the knee point search algorithm is full sorting.


## 3.1. Basic Idea

The knee point search algorithm is based on cascading top-k sorting. In each step, top-k sorting segments the list left to be searched. The optimal selection number is determined by minimizing the expected time cost on the list left. If the search successfully finds the knee point in the sorted top-k list, the algorithm ends there. Otherwise, the residual list excluding top-k requires further checking. It becomes the objective list for the next step and the function of the expected time cost using top-ksorting should also be updated according to the a priori knowledge that the search fails in the previous step. Thus the new top-k sort problem, likewise, holds for the next step. The algorithm runs in this way recursively until the knee point is found. There are two cases that bring the algorithm to the end.(1)
The knee point is found in the sorted top-k list in a step.(2)
The optimal selection number in one step equals the length of the objective list. This means the optimal option is total sorting. Therefore the knee point is certain to be found in the completely sorted list.


## 3.2. Top-k Sort Algorithm

We design a quicksort variation as the top-k sort algorithm. Quicksort is a very efficient sort algorithm invented by Hoare [7]. Quicksort has two phases: the partition phase and the sort phase, which makes it a good example of the divide and conquer strategy for solving problems.Top-k sorting only aims at treating the largest k elements, and thus it can be facilitated by the divide and conquer strategy. The intermediate results of quicksort, namely, the pivot positions, can be leveraged to possibly cut off one of the smaller problems divided from the bigger problem and to be conquered. For the strategy to be effective, the partition phase runs recursively only for the lower part if the pivot falls below position k, because there is no need to sort the upper part, which only consists of elements larger than top-k. This is the major distinction from the original quicksort algorithm and brings sorting efficiency.At the same time, the pivots located after positiondi (the optimal selection number) at step i in Section 3.6 are potentially useful for the afterwards steps, while they are actually not helpful for the inner top-di sorting. Therefore we record those pivots via a stack. A stack is a data structure featured by last in, first out (LIFO). Recalling that the recursive partitions with their pivots after position k produce their pivots in a sequential descending position order, we push these pivots into the stack resulting in a stack of pivots ordered by their positions. At the afterwards step i+1, if the optimal selection number di+1 is larger than the position of the pivot at the top of the stack, the pivot is popped from the stack used for an inner pivot of top-di+1. Since this pivot is no longer needed for the afterwards steps, it should not be maintained in the stack.  When the stack is empty or the pivot at the top of the stack (so do all of the other pivots) is located after the selection number, the partition has to run by itself to find a pivot without the help of the pivot stack.The top-k sort algorithm, namely, QuickSortTopK,  can be expressed as in Algorithm 1.Algorithm 1:QuickSortTopK(L, FirstIndex, LastIndex, k).
Input:
L: an unsorted list of length n
FirstIndex: the first index ofL to be sorted
LastIndex: the last index ofL to be sorted
k: top-k elements of L are to be sorted
Output:
L
k: Sorted top-k elements of L ranging from FirstIndex to LastIndex
S: a stack of pivot positons useful for the afterwards selection sorts
(1)if FirstIndex < LastIndex then
(2)if !isempty(S) & top(S) < LastIndex then  /* the stack is available */
(3)   pivotpos =pop(S)  /* use the top element of the stack as the pivot */
(4)else
(5)   /* Partition without using pivots from the stack */
(6)   pivotpos=Partition(L, FirstIndex, LastIndex)
(7)if  pivotpos− FirstIndex +1>k  then /* The pivot falls after position k */
(8)   /* The pivot may be useful for the afterwards steps */
(9)push(pivotpos, S)
(10)   /* QuickSort for top-k in the upper part */
(11)QuickSortTopK(L, FirstIndex, pivotpos −1, k)
(12)/* The pivot is located exactly at position k */
(13)elseif(pivotpos− FirstIndex +1==k)
(14)   /* QuickSort for top-k-1 in the upper part */
(15)QuickSortTopK(L, FirstIndex, pivotpos −1, k-1)
(16)else  /* The pivot falls prior to position k */
(17)    /* QuickSort the upper part */
(18)QuickSortTopK(L, FirstIndex, pivotpos −1, pivotpos− FirstIndex)
(19)    /* QuickSort for the residual elements in the lower part */
(20)QuickSortTopK(L, pivotpos +1, FirstIndex, k-pivotpos+ FirstIndex −1)The input of QuickSortTopK is the objective unsorted listL indexed from FirstIndex to LastIndex. For all steps, LastIndex is fixed at n, whereas FirstIndex is progressively increased to exclude the sorted part of L in all previous steps. The output includes the sorted top-k elements of L indexed from FirstIndex to LastIndex and the stack S containing all pivots falling after position k obtained in all previous steps.The termination condition of the recursion is checked in Line 1 of the algorithm. If the stack is nonempty and the top element of the stack falls into the objective range (see Line 2), the top element is used as the pivot for the partition (see Line 3). Otherwise, the pivot is obtained by a partition (see Line 6). Once the pivot is presented, different recursive steps are to be taken depending on the position of the pivot. If the pivot falls after positionk, it should be pushed into the stack and then run further sorting on the original list subtracting the pivot, hoping to help afterwards steps (see Lines 9, 11). If the pivot is located exactly at position k, the pivot itself is the last element of the output and thereafter only top-k-1 sorting on the original list subtracting the pivot is needed (see Line 15).  If the pivot is located prior to position k, both the upper and lower parts should be treated.  The action on the upper part is equivalent to Quicksort, while the action on the lower part is actually the recursive running of QuickSortTopK  with diminished selection number k and the shrinking  objective list (see Lines 18, 20).


## 3.3. Time Complexity

Let totally sorting of a list of lengthn require S(n) time. Calculated by the number of comparisons, the average time complexity of S(n) is O(nlog(n)) following some efficient algorithms, for example, Quicksort [7].Let top-k sorting of selection number k require C(k,n) time, where n is the length of the list. The QuickSortTopK algorithm requires an expected time of O(n+klogk). So C(k,n) equals O(n+klogk).Let the time complexity of finding the knee point in the sorted list of lengthn be D(n).  Recalling (2), D(n) takes  O(n).


## 3.4. Parameter Updating

For a list of lengthn, the algorithm divides the overall procedure into m+1 steps by a sequence of selection numbers, d1,d2,…,dm, 1≤d1<d2<⋯<dm≤n. Additionally, to facilitate the formulation, we let d0=0 and dm+1=n. Let the length of the objective list in step i,  i=1,2,…,m+1 be ni; we have
(3)ni=n-di-1,i=1,2,…,m+1.In the first step,ni=n. Let top-ki sorting for the objective list of length ni be performed in step i,  i=1,2,…,m+1, and we have
(4)ki=di-di-1,i=1,2,…,m+1.Particularly,ki=ni in step m+1. And thus top-ki sorting for the objective list of length ni is actually total sorting of the objective list. If the search of the knee point is successful in step i for the sorted top-ki list, the algorithm ends at step i. Otherwise, the algorithm continues with the next step. The algorithm lasts until step m+1 if the search misses in all of the previous steps during the progressive search. Since step m+1 takes no further selection of the objective list, the algorithm finishes in it.LetA be the position variable of the knee point and A=1,2,…,n. Let p(i) represent the probability that A=i,  i=1,2,…,n, and thus  ∑i=1np(i)=1. The value of p(i) is assumed to be known at the beginning of the algorithm. Let Ai be the position variable of the knee point in step i and Ai=di-1+1, di-1+2,…,n. Let pi(j) represent the probability that Ai=j,  j=di-1+1, di-1+2,…,n, i=1,2,…,m+1, and thus  ∑j=di-1+1npi(j)=1.Lemma 3.
The probability distribution of the knee point in stepi  pi(j) can be written as
(5)pi(j)=p(j)∑k=di-1+1np(k),j=di-1+1,di-1+2,…,n,i=1,2,…,m+1.Proof.
At the first step, all knowledge about the probability distribution of the knee point is only given byp(i). But the search in the afterward steps should make use of the posterior distribution of the knee point for it is confirmed not to exist prior to the selection number in the previous steps; for example, when the algorithm comes to step i, the knee point is already checked to be not present in the top-di-1 list, i=2,3,…,m+1. Therefore pi(j) should be updated in step i as
(6)pi(j)=P(Ai=j)=P(A=j∣A∈{di-1+1,di-1+2,…,n})=P(A=j,j∈{di-1+1,di-1+2,…,n})P(A∈{di-1+1,di-1+2,…,n})=p(j)∑k=di-1+1np(k)j=di-1+1,di-1+2,…,n,i=1,2,…,m+1.Let the hit probability of search in stepi  be Hi.Lemma 4.
The hit probability of search in stepi  Hi can be written as
(7)Hi(di)=∑j=di-1+1dipi(j),i=1,2,…,m+1.Proof.
For the selection numberdi in step i, the search for the knee point is successful if and only if the knee point falls into the interval of position among di-1+1 and di. According to Lemma 3, the probability distribution of the knee point at step i  pi(j) should be updated as (5). Therefore we have
(8)Hi(di)=∑j=di-1+1diP(Ai=j)=∑j=di-1+1dipi(j),i=1,2,…,m+1.


## 3.5. Cascading Top-k Sorting with Minimized Time Complexity

Lemma 5.
Let the expected overall computational time cost in stepi  be  tci;  tci yields
(9)tci=C(di-di-1,n-di-1)+(1-Hi(di))tci+1,i=1,2,…,m.Proof.
When the search succeeds in stepi, tci comes only from top-ki sorting which requires C(ki,ni) time and the search in the top-ki sorted list which requires D(n). However, recalling Section 3.3, the time complexity of D(n) is negligible compared to that of  C(ki,ni), so the summation of them can be approximated by C(ki,ni). For the failure of search in step i, the residual list of length ni-di has to be further checked. Thus the overall computation time cost consists of top-k sort and search in the remaining list. Note that the computation time cost of sort and search in the remaining list is no other than  tci+1. Hence  tci yields
(10)tci=Hi(di)C(ki,ni)+(1-Hi(di))(C(ki,ni)+tci+1)=C(ki,ni)+(1-Hi(di))tci+1,i=1,2,…,m.
Plugging (3) and (4) into (10), we get (9).Lemma5 tells us that the expected computational cost tc1 can be calculated iteratively following (7), until reaching tcm+1 where there is no selection for step m+1. Thus tcm+1 only consists of the time cost of total sorting of the list of length ni and the search in it. As total sorting takes S(ni) and search takes  D(ni), thus we have
(11)tcm+1=S(nm+1)+D(nm+1).LetN(a,b) (a≤b and a, b are integers) denote the set of integers {i∣a≤i≤bandiisinteger}. In every step i, the algorithm calculates the current probability distribution of the knee point which determines the hit probability Hi and chooses di to be the solution of the following optimization problem:
(12)Min:tcis.t.didi∈N(di-1+1,n).We see in (12) that for any fixed di the minimum of  tci  is determined by tci+1 under the optimal selection of di+1 in the next step, di∈N(di-1+1,n). And the optimal tci+1 for any fixed di+1 is also determined by the tci+2 under the optimal selection of  di+2  and so on. This kind of iterative dependency finally extends to the last step which has no further selection. So tci is the function of  di, di+1,…. The variation of any choice of selection in any number of steps makes the search space of optimization very huge, especially for the initial steps. Therefore it is not practical to evaluate all possibilities of selections in all of the afterwards steps when solving the optimization problem in step i. Thus it is necessary to constrain the variable of the objective function tci in (12) as mere di.Theorem 6.
The upper bound of the minimum oftci for a fixed di can be written as substituting tci+1 in (9) by  S(ni+1)+D(ni+1),  such that
(13)mindi+1∈N(di+1,n),di+2∈N(di+1+1,n),…tci≤C(di-di-1,n-di-1)+(1-Hi(di))(S(n-di)+D(n-di)),i=1,2,…,m.Proof.
We only need to prove that(14)mindi+1∈N(di+1,n),di+2∈N(di+1+1,n),…tci+1≤S(n-di)+D(n-di).
As total sort of the list of length ni+1 can be viewed as performing top-ni+1 sorting, their time costs are both S(ni+1)+D(ni+1). This is equivalent to the case when di+1=n. Because the algorithm ends with the total sorting and there are no afterwards steps, we have no definitions for  di+1, di+2,…. Thus we have
(15)tci+1|di+1=n(hencedi+2,di+3…hasnodefinition)=S(ni+1)+D(ni+1).
Hence
(16)mindi+1∈N(di+1,n),di+2∈N(di+1+1,n),…tci+1≤tci+1|di+1=n(hencedi+2,di+3,…hasnodefinition).
Plugging (3) into (15) and then (15) into (16), we have (14), and thereby (13) is proved.Theorem6 manifests that, for a fixed di, tci is definitely bounded by the time cost of total sort of the residual list of length ni+1plus that of search in it. The optimization problem in step i described by (13) can be isolated from all of the possible selections of the afterwards steps and becomes a function of mere di. This minmax technique brings convenience to our analysis, such that (13) can be simplified as
(17)Min:C(di-di-1,n-di-1)Min:+(1-Hi(di))(S(n-di)+D(n-di))s.t.didi∈N(di-1+1,n).
Plugging (5) into (17), we have
(18)Min:C(di-di-1,n-di-1)Min:+(1-∑j=di-1+1dipi(j))(S(n-di)+D(n-di))s.t.didi∈N(di-1+1,n).
Solving (14), we can obtain the optimal di in step i.


## 3.6. The Knee Point Search Algorithm

The knee point search algorithm runs iteratively using cascading top-k sorting. When the optimal selection number di is determined at step i, top-k sorting can be done via running QuickSortTopK  (L,di-1+1,n,di-di-1).  Specifically, the first step starts with QuickSortTopK   (L,1,n,d1).The procedure can be described as follows.Step 1.
(
1
)
According to (5), the probability distribution of the knee point for the optimization problem is initialized as follows
(19)p1(j)=p(j),j=1,2,…,n.
(
2
)
The optimal selection numberd1 is obtained by solving the following optimization problem as (18):
(20)Min:C(d1,n)+(1-∑j=1d1p(j))Min:×(S(n-d1)+D(n-d1))s.t.d1d1∈N(1,n).
(
3
)
Performtop-d1 sorting on the list of length n.
(
4
)
Search for the knee point on the sorted top-d1 list. If successful or d1=n, the algorithm ends. Otherwise, go to Step 2.Step 2.
(
1
)
The probability distribution of the knee point for the optimization problem is updated as follows:(21)p2(j)=p(j)∑k=d1+1np(k),j=d1+1,d1+2,…,n.
(
2
)
d
2 is derived as the solution of the following optimization problem:
(22)Min:C(d2-d1,n-d1)+(1-∑j=d1+1d2p2(j))Min:×(S(n-d2)+D(n-d2))s.t.d2d2∈N(d1+1,n).Note  that d1  is inherited from Step 1.(3)
Perform top-(d2-d1) selection sort on the list of length  n-d1 subtracting top-d1 elements in Step 1.(4)
Search for the knee point on the sorted top-(d2-d1) list. If successful or d2=n, the algorithm ends. Otherwise, go to Step 2.Step i.(1)
The probability distribution of the knee point for the optimization problem is updated according to (5).(2)
di is obtained as the solution of the optimization problem in (18), where di-1 is known from step i-1.(3)
Perform top-(di-di-1) selection sort on the list of length  n-di-1  subtracting top-di-1  elements already sorted in the previous steps.(4)
Search for the knee point on the sorted top-(di-di-1) list. If successful or di=n, the algorithm ends. Otherwise, go to step i+1.The knee point search algorithm can be summarized as  in Algorithm2.Algorithm 2:FindKnee(L, P).
Input: Unsorted list L of length n, probability distribution of the knee point in the sorted
list of lengthn: P
Output: The knee point e or the non-existence of it (e = null).
(1) /* initialize the parameters for the optimization problem */
(2)P1←P, L1←L
(3)i←1
(4)while (true)
(5)solve the optimization problem of list Li in (18) to get di
(6)if  di=ni  then  /* total sorting is the optimal option */
(7) totally sort list Li
(8) /* successful if the knee point exists */
(9) Search the sorted list for the knee point e
(10) break  /* the algorithm is completed */
(11)else  /* top-(di-di-1) sort is the optimal option */
(12) QuickSortTopK(L, di-1 + 1, n, di–di-1)
(13) Search the sorted list for the knee point e
(14) if  e is found then
(15)break
(16) else  /* Update the parameters for the next round of optimization problem */
(17)   updatePi+1 according to (5)  /* the posterior probability */
(18)   updateLi+1 by exluding the top-(di-di-1) item from list Li
(19)i←i+1
(20)return  eThe knee point search algorithm can also be expressed recursively.For each recursive step, we have an unsorted listL of length n and the probability distribution of the knee point in the sorted list of length n:P. Thus we can modify the optimization problem in (18) as follows:
(23)Min:C(d,n)+(1-∑j=1dp(j))(S(n-d)+D(n-d))s.t.d∈d∈N(1,n).Solving (14), we can obtain the optimal d in each recursive step.When the knee point search fails after top-k sorting in each recursive step, the algorithm has to go to the next recursive step. First, we need to update the probability distribution of the knee point as well as the residual unsorted list as two parameters for the recursive function. According to Lemma 3, the update of the probability distribution of the knee point yields
(24)p(j)⟵p(j)∑k=d+1np(k),j=d+1,d+2,…,n.In each recursive step, top-k sorting can be done via running QuickSortTopK(L, 1, length(L), d), where L is the objective list in the current step and length(L) denotes the length ofL.A recursive version of knee point search algorithm can be summarized as in Algorithm3.Algorithm 3:FindKnee(L, P).
Input: Unsorted list L of length n, probability distribution of the knee point in the sorted
list of lengthn: P
Output: The knee point e or the non-existence of it (e = null).
(1)solve the optimization problem of list L in (20) to get d
(2)if  d=n then  /* total sort is the optimal option */
(3) totally sort list L
(4) /* successful if the knee point exists */
(5) Search the sorted list for the knee point e
(6) return e /* the algorithm is completed */
(7)else  /* top-d sorting is the optimal option */
(8) QuickSortTopK(L, 1, length(L), d)
(9) Search the sorted list for the knee point e
(10)if e is found then
(11) return e
(12)else  /* Update the parameters for the next round of optimization problem */
(13)    updateP according to (5)  /* the posterior probability */
(14)update L by exluding the top-d item from list L
(15)FindKnee(L, P)


## 3.7. The Solution of the Optimization Problem

In this section, we will assume two forms of the probability distribution of the knee point and discuss the solutions of (18) under these presumptions.(1) Uniform Distribution. p(i) is equal for all i∈N(1,n), and thus p(i)=1/n. Plugging p(i) into (23), we have
(25)Min:C(d,n)+(1-dn)(S(n-d)+D(n-d))s.t.d∈N(1,n).Let(26)f(d)=C(d,n)+(1-dn)(S(n-d)+D(n-d)).
Although (26) is a discrete function, we still utilize the method of derivation to find the extremum, which can be only applied to the continuous and derivable function. Here we treat the discrete variable d as continuous ones, and thereafter (26) turns into a continuous and derivable function. This is a rational approximation of the problem, which facilitates our analysis and solving. The final solution should be the round-off of d obtained by solving the continuous function.For simplicity, we let(27)C(k,n)=c1(n+klogk)S(n)=c2(nlog(n))D(n)=c3n,
where c1,c2, and c3 are all constants.By choosingd such that  df(d)/d=0, we have the optimal d which satisfies
(28)c1(1+logd)n=(n-d)[2c2log(n-d)+2c3+c2].For largen and d, we have the approximation of (28) as
(29)c1nlogd=2c2(n-d)log(n-d).To get the explicit mathematical expression of the solution of the nonlinearity equation (29), we used a heuristic approach to simplify the problem. We assume that d  is a proportion function of  n, such that
(30)d=pn,0<p<1,
where p decides the optimum of d.Thus (30) yields
(31)c1nlog(pn)=2c2(1-p)nlog[(1-p)n],
then
(32)c1nlog(p)+c1nlog(n)=2c2(1-p)nlog(1-p)+2c2(1-p)nlog(n).Leave out the low order item in both sides of (32), and we get
(33)c1nlog(p)+c1nlog(n)≈c1nlog(n),2c2(1-p)nlog(1-p)+2c2(1-p)nlog(n)≈2c2(1-p)nlog(n).Plugging (33) into (32), the optimum of p yields
(34)p=1-c12c2.We can see that the optimum ofp that takes the form of a proportion function of n exists only when c1<2c2. Particularly, if c1=c2=1, the optimum of p is 1/2, which means that the optimum first selection number is half of the length of the list. As the search algorithm may run recursively if the knee point search misses, the optimal method is the so-called binary search or logarithmic search method.Theorem 7.
If the probability distribution of the knee point follows uniform distribution and the optimal selection number takes the form of (30), the optimal method for the knee point search algorithm is binary search or logarithmic search method.Proof.
We first prove using an inductive method that in each recursive step of the search algorithm,p(i) is equal for all  i∈N(1,n).
We know that for the first recursive step,p(i) is equal for all i∈N(1,n) as the starting point of the induction. Then for the second recursive step, we can derive according to (24) that p(i) is equal for all  i∈N(1,n).
Suppose that for thelth recursive step, p(i) is equal for all i∈N(1,n). Similarly, for the (l+1)th recursive step, p(i) is equal for all i∈N(1,n) following (24).
Therefore we can form the concept inductively that in each recursive step of the knee point search algorithm,p(i) is equal for all i∈N(1,n). So the optimization problem in each recursive step can be written as no other than (25), whose solution of number of selection is half of the length of the list discussed above. Here the list is the one left from previous recursive step. Hence the optimal method for the search algorithm is binary search or logarithmic search method.(2) Inverse Proportion Distribution. p(i) is in direct inverse proportion to i, i∈N(1,n), and thus p(i)=c/i, where c=1/∑i=1n(1/i).As an approximate treatment of the summation∑i=ab(1/i), we consider
(35)∑i=ab1i≈∫ab1xdx.Particularly, fora=1 and a large b, we have
(36)∑i=1b1i=lnb+E.And for a largen, we have
(37)c=1/(lnn+E),
where E is the Euler constant and has the approximate value as 0.5772.Pluggingp(i) and then (36) and (37) into (23), we have
(38)Min:C(d,n)+(1-lnd+Elnn+E)(S(n-d)+D(n-d))s.t.d∈d∈N(1,n).Let(39)g(d)=C(d,n)+(1-lnd+Elnn+E)(S(n-d)+D(n-d)).Theorem 8.
If the probability distribution of the knee pointp(i) is in direct inverse proportion to i,  i∈N(1,n), the optimal top-k sorting for the knee point search algorithm is full sorting of the list for a large length of the list.Proof.
We only need to prove thatg(d) is a monotony increase function of d, and the equivalent condition for it is
(40)dg(d)d=c1(1+logd)-c2(n-d)log(n-d)-c3n(lnn+E)d-c2(lnn-lnd)(1+log(n-d))lnn+E<0,
that is,
(41)c1(1+logd)(lnn+E)d<c2(n-d)log(n-d)+c3n+c2(lnn-lnd)(1+log(n-d))d.
We assume thatd is an exponential function of n, such that
(42)d=nq,0<q<1.
Thus the left and right sides of (41) can be, respectively, written as
(43)c1(1+logd)(lnn+E)d~O((logn)2nq)(44)c2(n-d)log(n-d)+c3n+c2(lnn-lnd)(1+log(n-d))d~O(n).
Comparing (43) and (44), we obtain (41) for a large n. That means the optimal selection number is n for the first step, or the optimal top-k sorting for the knee point search algorithm is full sorting.


## 4. Source Detection of DNS DoS Flooding Attacks: An Application Example

### 4.1. DNS DoS Flooding Attacks

The Domain Name System is a fundamental and indispensable component of the modern Internet [13, 14]. The availability of the DNS can affect the availability of a large number of Internet applications. Ensuring the DNS data availability is an essential part of providing a robust Internet.In the past few years, some important DNS name servers on the top level of the DNS hierarchical structure were targeted by the DoS or DDoS attackers, and some of these attacks did succeed in disabling the DNS servers and resulted in parts of the Internet experiencing severe name resolution problems [15–18]. Particularly, DNS DoS flooding attacks are the attacks launched by the attackers towards the DNS name servers with an overwhelming traffic flux in order to disrupt the DNS service for the legitimate clients. However, it is usually not easy to efficiently detect and defend the DoS flooding attacks because the attacking traffic is blended with the legitimate ones, which complicates the distinguishing efforts. Moreover, the detection mechanism should be implementable or should not add heavy computational load. Here we focus on the source-based detection method and show that the problem of source detection of DNS DoS flooding attacks can be addressed by the knee point search in the sorted curve discussed in this paper.


### 4.2. Detection Using the Knee Point Search

Generally, DNS name servers may receive queries coming from thousands of DNS clients (mostly DNS cache servers), whose traffic volumes are expected to remain far below those of the DoS flooding attacks. The real-time query rates for all incoming sources can be counted by the traffic monitoring system residing at the border gateway in front of the DNS name server. The goal of the DoS attack defense is to realize real-time attacking source detection and then filter out the attacking traffic from these sources accordingly.  Therefore the detection problem is equivalent to knee point search in the sorted curve, where all points above the largest knee point are identified as the attacking sources. Moreover, time efficiency is also the key requirement for the problem, for timely attacking detection means timely defending action.  Applying the knee point search algorithm proposed in this paper, the expected detection time is minimized.


### 4.3. Leaning the Knee Point Distribution

The assumption on probability distribution of the knee point is the prerequisite for the knee point search algorithm. However, in the initial rounds of detection we have hardly any a priori knowledge about the knee point. But the distribution estimation of the knee point can be learned based on the empirical data obtained in all previous rounds of detection.First, suppose that the knee point largely follows stationary random distribution; hence its distribution exhibits almost the same probability model in all rounds of detection. We can fit a statistical model to data and provide estimates for the model's parameters. Here we apply the method of maximum likelihood for the estimation.Let the count variable of detected knee points so far at positioni in the ordered list of length n be  hi,i=1,2,…,n. Let the value of  hi be  xi, i=1,2,…,n. If the number of rounds of detection is R, we have
(45)∑i=1nxi=R.Let the probability vector of the knee point at different positions beP=(p1,p2,…,pn)′. The likelihood function of  P can be written as
(46)lik(P)=fD(h1=x1,h2=x2,…,hn=xn∣P),
where fD(·) is the density function. To calculate lik(P), we have
(47)lik(P)=fD(h1=x1∣P)fD(h2=x2,…,hn=xn∣h1=x1,P)=fD(h1=x1∣P)fD(h2=x2∣h1=x1,P)fD×(h3=x3,…,hn=xn∣h1=x1,h2=x2,P)⋮=fD(h1=x1∣P)fD(h2=x2∣h1=x1,P)⋯fD(hn-2=xn-2∣h1=x1,h2=x2,…,hn-3=xn-3,P)×fD(hn-1=xn-1,hn=xn∣h1=x1,×fDh2=x2,…,hn-2=xn-2,P)=fD(h1=x1∣P)fD(h2=x2∣h1=x1,P)⋯fD(hn-2=xn-2∣h1=x1,×fDh2=x2,…,hn-3=xn-3,P)×fD(hn-1=xn-1∣h1=x1,×fDh2=x2,…,hn-2=xn-2,P)×fD(hn=xn∣h1=x1,h2=x2,…,hn-1=xn-1,P),
where the last item in (47) is actually not an independent one given that all hi  other than hn  are known due to the constraint in (45), such that
(48)fD(hn=xn∣h1=x1,h2=x2,…,hn-1=xn-1,P)=1.
Plugging (48) into (47), we get
(49)lik(P)=(nx1)p1x1(1-p1)n-x1(n-x1x2)(p21-p1)x2×(1-p21-p1)n-x1-x2⋯(n-∑i=1n-2xixn-1)×(pn-11-∑i=1n-2pi)xn-1(1-pn-11-∑i=1n-2pi)n-∑i=1n-1xi.
Thus let
(50)∂ln(lik(P))∂pi=0,i=1,2,…,n-1.
We obtain the maximum likelihood estimation of  pi,  i=1,2,…,n-1:
(51)p^i=xiR,i=1,2,…,n-1,p^n=1-∑i=1n-1p^i=xnR.At the beginning of each round of detection, if the previous round finds the knee point at positioni*, R and  xi, i=1,2,…,n, are updated as follows:
(52)R⟵R+1,xi*⟵xi*+1,xi⟵xi,i∈N(1,n),i≠i*.The knee point distribution may evolve over time; thus the position of the knee point detected in recent rounds provides more reliable information for the estimation than earlier rounds. Taking the chronological order into consideration, we assign more weight to recent rounds than earlier rounds. This can be done by decreasing the detection results in previous rounds progressively. The deceasing is performed in updatingR and xi, i=1,2,…,n, and sums up the current detection and the previous ones at a discount β, 0<β<1. Formally, the updating of R and xi,  i=1,2,…,n,  can be modified as follows:
(53)R⟵β*R+1,xi*⟵β*xi*+1,xi⟵β*xi,i∈N(1,n),i≠i*.


## 4.1. DNS DoS Flooding Attacks

The Domain Name System is a fundamental and indispensable component of the modern Internet [13, 14]. The availability of the DNS can affect the availability of a large number of Internet applications. Ensuring the DNS data availability is an essential part of providing a robust Internet.In the past few years, some important DNS name servers on the top level of the DNS hierarchical structure were targeted by the DoS or DDoS attackers, and some of these attacks did succeed in disabling the DNS servers and resulted in parts of the Internet experiencing severe name resolution problems [15–18]. Particularly, DNS DoS flooding attacks are the attacks launched by the attackers towards the DNS name servers with an overwhelming traffic flux in order to disrupt the DNS service for the legitimate clients. However, it is usually not easy to efficiently detect and defend the DoS flooding attacks because the attacking traffic is blended with the legitimate ones, which complicates the distinguishing efforts. Moreover, the detection mechanism should be implementable or should not add heavy computational load. Here we focus on the source-based detection method and show that the problem of source detection of DNS DoS flooding attacks can be addressed by the knee point search in the sorted curve discussed in this paper.


## 4.2. Detection Using the Knee Point Search

Generally, DNS name servers may receive queries coming from thousands of DNS clients (mostly DNS cache servers), whose traffic volumes are expected to remain far below those of the DoS flooding attacks. The real-time query rates for all incoming sources can be counted by the traffic monitoring system residing at the border gateway in front of the DNS name server. The goal of the DoS attack defense is to realize real-time attacking source detection and then filter out the attacking traffic from these sources accordingly.  Therefore the detection problem is equivalent to knee point search in the sorted curve, where all points above the largest knee point are identified as the attacking sources. Moreover, time efficiency is also the key requirement for the problem, for timely attacking detection means timely defending action.  Applying the knee point search algorithm proposed in this paper, the expected detection time is minimized.


## 4.3. Leaning the Knee Point Distribution

The assumption on probability distribution of the knee point is the prerequisite for the knee point search algorithm. However, in the initial rounds of detection we have hardly any a priori knowledge about the knee point. But the distribution estimation of the knee point can be learned based on the empirical data obtained in all previous rounds of detection.First, suppose that the knee point largely follows stationary random distribution; hence its distribution exhibits almost the same probability model in all rounds of detection. We can fit a statistical model to data and provide estimates for the model's parameters. Here we apply the method of maximum likelihood for the estimation.Let the count variable of detected knee points so far at positioni in the ordered list of length n be  hi,i=1,2,…,n. Let the value of  hi be  xi, i=1,2,…,n. If the number of rounds of detection is R, we have
(45)∑i=1nxi=R.Let the probability vector of the knee point at different positions beP=(p1,p2,…,pn)′. The likelihood function of  P can be written as
(46)lik(P)=fD(h1=x1,h2=x2,…,hn=xn∣P),
where fD(·) is the density function. To calculate lik(P), we have
(47)lik(P)=fD(h1=x1∣P)fD(h2=x2,…,hn=xn∣h1=x1,P)=fD(h1=x1∣P)fD(h2=x2∣h1=x1,P)fD×(h3=x3,…,hn=xn∣h1=x1,h2=x2,P)⋮=fD(h1=x1∣P)fD(h2=x2∣h1=x1,P)⋯fD(hn-2=xn-2∣h1=x1,h2=x2,…,hn-3=xn-3,P)×fD(hn-1=xn-1,hn=xn∣h1=x1,×fDh2=x2,…,hn-2=xn-2,P)=fD(h1=x1∣P)fD(h2=x2∣h1=x1,P)⋯fD(hn-2=xn-2∣h1=x1,×fDh2=x2,…,hn-3=xn-3,P)×fD(hn-1=xn-1∣h1=x1,×fDh2=x2,…,hn-2=xn-2,P)×fD(hn=xn∣h1=x1,h2=x2,…,hn-1=xn-1,P),
where the last item in (47) is actually not an independent one given that all hi  other than hn  are known due to the constraint in (45), such that
(48)fD(hn=xn∣h1=x1,h2=x2,…,hn-1=xn-1,P)=1.
Plugging (48) into (47), we get
(49)lik(P)=(nx1)p1x1(1-p1)n-x1(n-x1x2)(p21-p1)x2×(1-p21-p1)n-x1-x2⋯(n-∑i=1n-2xixn-1)×(pn-11-∑i=1n-2pi)xn-1(1-pn-11-∑i=1n-2pi)n-∑i=1n-1xi.
Thus let
(50)∂ln(lik(P))∂pi=0,i=1,2,…,n-1.
We obtain the maximum likelihood estimation of  pi,  i=1,2,…,n-1:
(51)p^i=xiR,i=1,2,…,n-1,p^n=1-∑i=1n-1p^i=xnR.At the beginning of each round of detection, if the previous round finds the knee point at positioni*, R and  xi, i=1,2,…,n, are updated as follows:
(52)R⟵R+1,xi*⟵xi*+1,xi⟵xi,i∈N(1,n),i≠i*.The knee point distribution may evolve over time; thus the position of the knee point detected in recent rounds provides more reliable information for the estimation than earlier rounds. Taking the chronological order into consideration, we assign more weight to recent rounds than earlier rounds. This can be done by decreasing the detection results in previous rounds progressively. The deceasing is performed in updatingR and xi, i=1,2,…,n, and sums up the current detection and the previous ones at a discount β, 0<β<1. Formally, the updating of R and xi,  i=1,2,…,n,  can be modified as follows:
(53)R⟵β*R+1,xi*⟵β*xi*+1,xi⟵β*xi,i∈N(1,n),i≠i*.


## 5. Conclusion

Knee point search in the sorted curve is often used in the practice of anomaly detection and many other applications. Due to the inefficiency of total sorting, top-k sorting should be adopted for the knee point search. In this paper, a knee point search algorithm using cascading top-k sorting is proposed. The expected time complexity is minimized via optimizing the selection number k in each step.



---

*Source: 960348-2013-08-27.xml*