Abstract
When we explain a new concept to our colleagues, the most formal way is to give its definition and to describe its attributes. However, if our listener is a child, we will normally avoid the formal way as it is difficult to be understood. A better approach in this case is to first give a “typical example” of the concept. A similar case occurs in searching large databases. For instance when we want to search Google by some keywords, As we search the database and receive a set of result, what we desire in general is some “typical” examples from those reported results. We define the top-k typical range representatives query for retrieving the top-most typical data and design the efficient algorithms for the query. In the RAM model, our algorithm will answer the query in O(n log n) time, where we conjecture the bound is optimal. And in the external-memory model, we propose another algorithm which will answer the query in O(SORT(n)) I/O’s, where SORT(n) is the lower bound on the number of I/O’s to sort n data in the model.