Abstract Finding typical instances is an effective approach to understand and analyze large data sets. In this paper, we apply the idea of typicality analysis from psychology and cognitive science to database query answering, and study the novel problem of answering top-k typicality queries. We model typicality in large data sets systematically. Three types This paper is a substantial extension of the conference version [32] . The research of Ming Hua and Jian Pei is supported in part by an NSERC Discovery grant and an NSERC Discovery Accelerator Supplements grant. The research of Xuemin Lin is supported in part by the Australian Research Council Discovery Grants DP0987557, DP0881035 and DP0666428 and a Google research award. All opinions, findings, conclusions and recommendations in this paper are those of the authors and do not necessarily reflect the views of the funding agencies. We are grateful to the anonymous reviewers and Dr. Peter Haas, the associate editor, for their constructive comments which help to improve the quality of the paper substantially. Particularly, we thank them for their advice in improving the mathematical exposition and their suggestions about some important related work. of top-k typicality queries are formulated. To answer questions like "Who are the top-k most typical NBA players?", the measure of simple typicality is developed. To answer questions like "Who are the top-k most typical guards distinguishing guards from other players?", the notion of discriminative typicality is proposed. Moreover, to answer questions like "Who are the best k typical guards in whole representing different types of guards?", the notion of representative typicality is used. Computing the exact answer to a top-k typicality query requires quadratic time which is often too costly for online query answering on large databases. We develop a series of approximation methods for various situations: (1) the randomized tournament algorithm has linear complexity though it does not provide a theoretical guarantee on the quality of the answers; (2) the direct local typicality approximation using VP-trees provides an approximation quality guarantee; (3) a local typicality tree data structure can be exploited to index a large set of objects. Then, typicality queries can be answered efficiently with quality guarantees by a tournament method based on a Local Typicality Tree. An extensive performance study using two real data sets and a series of synthetic data sets clearly shows that top-k typicality queries are meaningful and our methods are practical. M. Hua (B)·
Hua et al. REF introduced a novel top-k typicality query, which ranks objects according to their typicality in a data set or a class of objects.
Top-k typicality queries and efficient query answering methods on large databases
The VLDB Journal
The VLDB Journal
Computer Science