The problem to find the kth smallest of n elements has been considered as a significant problem in the combinatorial area. In this thesis, two efficient selection algorithms, pSELECT and HSELECT, are presented. The former has a practical upper bound of average case complexity on the number of pairwise comparisons. The later solves the selection problem through efficient use of a hardware sorter. Based on multiselection, a new join method is proposed where the join operation of the relational database management system is a costly operation and the most important operation due to its frequent uses.
The algorithm pSELECT mainly consists of a determination step of a partitioning element and a partition step to divide elements into two parts. The partitioning element is estimated from the cumulative frequency distribution of a small sample by using the theory of nonparametric statistics. The expected number of comparisons is n + min(k, n-k) + O($n^{2/3}$) where the sample size is approximately $n^{2/3}$. The experimental results show that the performance of the algorithm is improved, compared to the two known selection algorithms, particularly when the selection index is near to the median.
The algorithm HSELECT uses the property of quantiles of each sorted columns which are generated by a special purpose sorter. When a pipeline merge sorter is used, the comparison complexity of the algorithm is 1. 4167n+o(n) in the worst case, provided that the capacity of the sorter is 256 elements. The comparison complexity of the algorithm decreases as the capacity of the sorter increases.
Since relation sizes are usually too large to fit in main memory, the join operation may require more than one scan of all tuples of both relations. A new join algorithm which employs a selection algorithm as a basic part of divide-and-conquer strategy is presented to reduce the number of input/output accesses. The performance of the new algorithm is analyzed on the number of input/outputs, which shows that the proposed algorithm outperforms the hash-partitioned join algorithm which is known as the best method in the join operations. Simulation results agree with the analysis of the algorithm, and the number of input/outputs of the algorithm is less than that of a hash-partitioned join algorithm in the simulation.
주어진 n개의 원소들(elements) 중에서 k번째 작은 원소를 찾는 선택문제는 전산과학의 기본적인 문제이다. 이 논문에서는, 두 개의 선택 알고리즘인 pSELECT와 HSELECT가 제안되었다. 첫번째 알고리즘은 두 개의 원소 비교회수에서 평균 복잡도(average case complexity)의 실제적인 상한값을 가진다. 두번째 알고리즘은 하드웨어 정렬기(hardware sorter)가 보조 프로세서로 사용될 때 이것을 효율적으로 이용하여 선택문제를 푸는 방법이다. 여러 원소들을 선택하는 다중선택을 기본으로, 관계 데이타베이스 시스템의 결합연산을 빠르게 수행하는 알고리즘을 제안하였다. 관계 데이타베이스 관리 시스템의 결합연산은 다른 연산에 비해 시간 복잡도가 크고, 또한 자주 사용되기 때문에 가장 중요한 연산이다.
알고리즘 pSELECT는 분할원소(partitioning element)를 결정하는 과정과 주어진 원소들을 두 부분으로 나누는 분할 과정으로 구성된다. 분할원소는 비모수 통계 이론을 이용하여 작은 샘플의 누적 빈도 분포로 부터 예측된다. 비교회수의 기대치는 $n+min(k,n-k) + O(n^{2/3})$이고 샘플 크기는 $n^{2/3}$이다. 실험결과는 알고리즘의 성능이 다른 두개의 알려진 선택 알고리즘들보다 개선되었음을 보여준다. 특히, 선택지수가 중위수(median)에 가까울때 이 알고리즘의 성능이 좋다.
알고리즘 HSELECT는 하드웨어 정렬기를 사용하여 정렬된 원소들의 대표값을 이용한다. 파이프라인 병합 정렬기(pipeline merge sorter)를 사용하고 이 정렬기가 256개의 원소를 선형시간내에 처리할 때, 이 알고리즘의 비교회수 복잡도는 최악의 경우(in the worst case) 1.4167n+o(n) 이다. 이 알고리즘의 비교회수 복잡도는 정렬기의 용량이 커짐에 따라 작아진다.
관계 데이타베이스 관리 시스템에서 릴레이션(relation)의 크기가 컴퓨터의 주기억장치에 비해서 보통 너무 크므로, 결합 연산은 관련된 두 릴레이션의 모든 튜플(tuple)들을 한번 이상 검색하여야 된다. 제안된 결합 연산 알고리즘은 선택 알고리즘을 분할 및 처리(divide-and-conquer)의 기본 부분으로 이용한다. 이 알고리즘은 컴퓨터의 주 기억 장치와 이차 기억 장치 사이의 입력/출력 회수를 감소시키기 위하여 제안하였다. 새로운 알고리즘의 성능은 입력/출력 회수로 분석하였다. 이 분석은 제안된 알고리즘이 결합연산에서 가장 좋은 방법으로 알려진 해쉬 분할 결합 연산 방법(hash-partitioned join method) 보다 우수함을 보여주었다. 모의 실험 결과는 이 알고리즘의 분석결과와 일치하고, 이 알고리즘의 입력/출력 회수가 해쉬 분할 방법보다 작았다.
