Knee Point Search Using Cascading Top-k Sorting with Minimized Time Complexity
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 s...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2013-01-01
|
| Series: | The Scientific World Journal |
| Online Access: | http://dx.doi.org/10.1155/2013/960348 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832558336226099200 |
|---|---|
| author | Zheng Wang Shian-Shyong Tseng |
| author_facet | Zheng Wang Shian-Shyong Tseng |
| author_sort | Zheng Wang |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-a88fb2653c134ad796d87f9c2c76d7b5 |
| institution | Kabale University |
| issn | 1537-744X |
| language | English |
| publishDate | 2013-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | The Scientific World Journal |
| spelling | doaj-art-a88fb2653c134ad796d87f9c2c76d7b52025-02-03T01:32:44ZengWileyThe Scientific World Journal1537-744X2013-01-01201310.1155/2013/960348960348Knee Point Search Using Cascading Top-k Sorting with Minimized Time ComplexityZheng Wang0Shian-Shyong Tseng1Computer Network Information Center, Chinese Academy of Sciences, Beijing 100190, ChinaDepartment of Information Science and Applications, Asia University, Taichung 41354, TaiwanAnomaly 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.http://dx.doi.org/10.1155/2013/960348 |
| spellingShingle | Zheng Wang Shian-Shyong Tseng Knee Point Search Using Cascading Top-k Sorting with Minimized Time Complexity The Scientific World Journal |
| title | Knee Point Search Using Cascading Top-k Sorting with Minimized Time Complexity |
| title_full | Knee Point Search Using Cascading Top-k Sorting with Minimized Time Complexity |
| title_fullStr | Knee Point Search Using Cascading Top-k Sorting with Minimized Time Complexity |
| title_full_unstemmed | Knee Point Search Using Cascading Top-k Sorting with Minimized Time Complexity |
| title_short | Knee Point Search Using Cascading Top-k Sorting with Minimized Time Complexity |
| title_sort | knee point search using cascading top k sorting with minimized time complexity |
| url | http://dx.doi.org/10.1155/2013/960348 |
| work_keys_str_mv | AT zhengwang kneepointsearchusingcascadingtopksortingwithminimizedtimecomplexity AT shianshyongtseng kneepointsearchusingcascadingtopksortingwithminimizedtimecomplexity |