Evaluation of top-k queries over structured and semi-structured data
Luis Gravano, Amélie Marian · 2005
This thesis addresses fundamental issues in defining and efficiently processing top-k queries for a variety of scenarios, presenting different query processing challenges. In all these scenarios, our query processing algorithms attempt to focus on the objects that are most likely to be among the top-k matches for a given query, and discard---as early as possible---objects that are guaranteed not to qualify for the top- k answer, thus minimizing query processing time. One important top-k query scenario that we study is web applications where the data objects are only available through remote, autonomous web sources. During query processing, these sources have to be queried repeatedly for a potentially large set of candidate objects. Processing top-k queries efficiently in such a scenario is challenging, as web sources exhibit diverse probing costs and access interfaces, as well as constraints on the degree of concurrency that they support. By considering the peculiarities of the sources and potentially designing object-specific query execution plans, our adaptive algorithms efficiently prune non-top- k answers and produce significantly more efficient query executions than previously existing algorithms, which select global query execution plans and do not fully take advantage of source-access parallelism. As another contribution of this thesis, we extend our query processing algorithms to handle natural variations of the basic top-k query model. Specifically, we develop algorithms for queries that, in addition to fuzzy conditions, include some hard Boolean constraints (e.g., to allow the users to specify a more complex set of preferences). We also study extensions of our algorithms to handle scenarios where individual objects can be combined through joint operations. (Abstract shortened by UMI.)