각 algorithm을 사용하기 위해서는 사전에 몇 가지가 가정되어야 한다.
TA는 현재 읽은 값을 통해 그 다음에 올 값의 한계를 정해 top-k(k등수 이내)를 구하는 방법이다. F가 monotone 이고 각 항목은 정렬되어 있으므로 큰 값부터 순서대로 읽어 다음에 올 값들의 최대값을 한정할 수 있다. 이 값이 현재 top-k에 속해 있는 값보다 작을경우 더 이상 top-k에 들어 갈 수 있는 값이 나오지 못하므로 전체를 다 읽어보지 않더라도 top-k를 구할 수 있다.
구하는 방법은 다음과 같다.
1. 각 정렬된 목록에서 아직 확인하지 않은 가장 큰 값을 가지는 ID들을 찾는다.
2. 각 대상을 aggregation function F를 통해 평가한다.
3. 이 들의 값이 top-k(k등수 이내)이면 기억한다.
4. 각 목록에서 1에서 찾은 ID의 다음 순위의 값을 찾는다.
5. 4에서 찾은 값들로 aggregation function을 통해 평가하고 이 값을 t(threshold)라 하자.
6. t가 현재까지의 top-k에 속하면 1부터 반복하고, 그렇지 않으면 tok-k를 반환한다.
이 방법이 최적의 방법이라 알려져 있지만, 문제점은 2에서 F를 통해 평가할 때 DB에 random access를 한다는 점이다. DB에 따라서 randon access가 허용되지 않는 경우도 있기 때문이다. 다음에 알아볼 NRA algorithm은 random access를 하지 않고 top-k를 구할 수 있다.
NRA(no random access) algorithm
NRA 방식은 TA에 비해 random access를 하지 않지만 memory를 더 필요로 한다. top-k를 저장하기 위한 T와 tok-k가 될 가능성이 있는 ID를 저장하기 위한 C가 필요하다.
1. 각 정렬된 목록에서 순차적으로 읽는다(X).
2. 각 ID마다 F를 통해 최대값(B(X))과 최소값(W(X))을 계산한다.
4. C에 있는 모든 원소들(X1, X2, ... , Xi)의 최대값(B(Y))을 구한다.
5. C에 원소가 아무것도 없으면 T를 리턴하고 끝내고 아니면 1부터 반복한다.
1. 각각의 대상(차량)은 고유한 ID와 각각의 기준(가격, 연비)과 그 값을 가지고 있다.
2. 각 값은 0~1까지의 값을 가진다. (꼭 필요하지는 않지만 설명의 편의상 가정 한다)
3. 각각의 기준에 의해 정렬된 목록들을 가지고 있다.
다른 가정들의 경우 문제를 간단하게 인식하기 위한 것이고 성능이나 비용에 영향을 미치지 않지만 3의 경우 정렬은 큰 비용이 필요하다. 하지만 대체로 DB(database)에서 정렬이 많이 사용되고, 한 번 정렬해 놓으면 다른 명령에서 쓰이는 경우가 많아 꼭 비용이크다고만 볼 수 없다.
가격 연비 ID 값 ID 값 17 0.9936 1581 0.9998 153 0.9825 1551 0.9965 ... ... ... ... 1581 0.8859 153 0.5548 995 0.3548 559 0.2254 [표 1] 예제
4. 각각의 기준을 평가해 순위를 매기는 aggregation function을 가진다. 이 함수는
monotone 함수여야 한다. 즉, aggregation function F가 있고,모든 i에 대해 xi ≤ x'i 이면
F(x1, ... , xm) ≤ F(x'1, ... , xm)을 만족한다.
TA(threshold algorithm)
TA는 현재 읽은 값을 통해 그 다음에 올 값의 한계를 정해 top-k(k등수 이내)를 구하는 방법이다. F가 monotone 이고 각 항목은 정렬되어 있으므로 큰 값부터 순서대로 읽어 다음에 올 값들의 최대값을 한정할 수 있다. 이 값이 현재 top-k에 속해 있는 값보다 작을경우 더 이상 top-k에 들어 갈 수 있는 값이 나오지 못하므로 전체를 다 읽어보지 않더라도 top-k를 구할 수 있다.
구하는 방법은 다음과 같다.
1. 각 정렬된 목록에서 아직 확인하지 않은 가장 큰 값을 가지는 ID들을 찾는다.
2. 각 대상을 aggregation function F를 통해 평가한다.
3. 이 들의 값이 top-k(k등수 이내)이면 기억한다.
4. 각 목록에서 1에서 찾은 ID의 다음 순위의 값을 찾는다.
5. 4에서 찾은 값들로 aggregation function을 통해 평가하고 이 값을 t(threshold)라 하자.
6. t가 현재까지의 top-k에 속하면 1부터 반복하고, 그렇지 않으면 tok-k를 반환한다.
이 방법이 최적의 방법이라 알려져 있지만, 문제점은 2에서 F를 통해 평가할 때 DB에 random access를 한다는 점이다. DB에 따라서 randon access가 허용되지 않는 경우도 있기 때문이다. 다음에 알아볼 NRA algorithm은 random access를 하지 않고 top-k를 구할 수 있다.
NRA(no random access) algorithm
NRA 방식은 TA에 비해 random access를 하지 않지만 memory를 더 필요로 한다. top-k를 저장하기 위한 T와 tok-k가 될 가능성이 있는 ID를 저장하기 위한 C가 필요하다.
1. 각 정렬된 목록에서 순차적으로 읽는다(X).
2. 각 ID마다 F를 통해 최대값(B(X))과 최소값(W(X))을 계산한다.
예를 들어 [표 1]의 경우 ID 17을 읽는다. ID 17의 연비는 1을 넘을 수 없으므로 최대값은 연비가 1일 때의 값이고, 최소값은 연비가 0일 때의 값이다. 마찬가지로 다음에 ID 1581을 읽을 경우 최대값은 가격이 0.9936일 때의 값(ID 17 의 연비가 0.9936이므로 이보다 정렬위치가 낮은 ID 1581의 연비는 이를 넘을 수 없다.) 이고 최소값은 가격이 0일 때의 값이다.3. T의 개수가 k보다 작으면 각 ID를 추가하고 1부터 반복한다.
그렇지 않으면 W(X)와 W(Tk)를 비교한다(Tk는 T에 속한 ID중 최소값이 가장 작은 ID).
W(X) > W(Tk) 이면 X를 T에 넣고 Tk는 C로 옮긴다.
W(X) ≤ W(Tk) 이면 X를 C에 넣는다.
4. C에 있는 모든 원소들(X1, X2, ... , Xi)의 최대값(B(Y))을 구한다.
B(Y) ≤ W(Tk) 이면 C에서 Y를 지운다.
5. C에 원소가 아무것도 없으면 T를 리턴하고 끝내고 아니면 1부터 반복한다.
최근 덧글