Patent ID: 8296306

Claim:
A Linear-Time Top-k Sort Method that finds k data elements having the largest key values from a dataset of n elements in a time linearly proportional to the size of the dataset so as to process top-k queries that retrieve only the highest-ranked k results arranged in the order of importance in large-scale search systems or distributed systems comprises the following steps; reading k data elements in sequence from a dataset S of n data elements, and removing those k data elements from S so as not to be read again (Step 1 ); initializing a min heap structure topKHeap, which will be returned as the result of the proposed method, as an empty tree, and constructing topKHeap by inserting the k data elements read in Step 1 into topKHeap (Step 2 ); extracting a data element e from the dataset S (Step 3 ); comparing the key value of the element e extracted in Step 3 with the key value of the root node r of topKHeap (Step 4 ); replacing the key value of the root node r with the element e if the key value of e is larger than that of r (Step 5 ); comparing the key value of the root node r that is replaced in Step 5 with key values of its children nodes, and readjusting topKHeap so that the key value of the parent node is no larger than the key values of its children nodes (Step 6 ); removing the element e from the dataset S (Step 7 ); repeating Steps 3 to 7 until the dataset S becomes empty so that there is no element left to be read (Step 8 ); returning topKHeap, which consists of the data elements having the largest key values, as a result when the dataset S becomes empty (Step 9 ), where in Step 9 , returning the k data elements stored in topKHeap in the descending order of those key values 1) by extracting the k data elements from the root node of topKHeap and 2) by reading them in the reverse order of the extraction, wherein the time complexity of the method is represented as a sum of the time for initializing topKHeap using k data elements initially selected (O(k log k)), the time for reconstructing topKHeap with the other (n−k) data elements (O((n−k)log k)), and the time for returning the k data elements in the descending order, resulting in O(c 1 k log k+c 2 k log k+(n−k)log k)=O((n+ck)log k) (c=(c 1 +c 2 −1)) with respect to constants c, c 1 and c 2 , wherein since c and k are constants, the time complexity becomes O((n+ck)log k)=O(n) so that the time complexity of the method is linearly proportional to the number of all data elements (i.e., n) of the dataset.