Author Description

This dissertation, "Ranking and Similarity Queries on Complex Data Types" by Yilun, Cai,, was obtained from The University of Hong Kong (Pokfulam, Hong Kong) and is being sold pursuant to Creative Commons: Attribution 3.0 Hong Kong License. The content of this dissertation has not been altered in any way. We have altered the formatting in order to facilitate the ease of printing and reading of the dissertation. All rights not granted by the above license are retained by the author. Abstract: Ranking queries and similarity queries are elementary operations with many important applications. There are lots of research works investigating efficient evaluation of various ranking and similarity queries in databases over the past few decades. In this thesis, ranking and similarity queries on three interesting complex data types are studied, namely, multidimensional cube, object summary and tree. Efficient and effective solutions are proposed to solve their related applications. First, the evaluation of ranking queries on multidimensional cubes is studied. In exploratory data analysis, a relation can be considered as a multidimensional cube to investigate the relationship among its attributes. Given a relation with records that can be ranked, an interesting problem is to identify selection conditions for the relation, which result in sub-relations qualified by an input record and render the ranking of the input record as high as possible among the qualifying tuples. The ranking of the input record in a sub-relation measures the quality of the corresponding multidimensional cube of this sub-relation. In this thesis, a standing maximization problem, which aims to identify a multidimensional cube of high quality, is extensively studied. As an immediate consequence of its NP-hardness, three greedy methods are proposed to explore the search space only partially, while striving to identify sub-optimal solutions of high quality. Next, the efficient evaluation of r