Grant: Discovery Grants Program - Individual

Querying for "approximate matches" is very common in document and multimedia retrieval systems.  In search engines, for example, users specify a set of keywords and expect in return a ranking of relevant pages or documents related to the keywords.  In contrast, the querying methods available in relational database management systems (RDBMSs) are designed to return only results found within specified selection conditions.  Due to this, users of online business applications such as product recommendation systems, price comparison and shopping agents routinely face the challenge of specifying value ranges of attributes in search of relevant results.  Often, they get either too few or too many results that are of limited relevance to their request.  This conventional querying process is very frustrating for the user and extremely inefficient for the system.          Alternatively, users of the above applications should be able to specify target values of attributes and expect to obtain a ranked set of a desired number of results that best match the specified values across all the attributes (e.g., the top 10 best matches).  In this type of querying, also known as top-k querying, results are not limited to exact matches but include close matches around the target values of interest.  This research studies cost-based strategies for efficient support of this class of queries in RDBMSs.  The objective is to provide methods that work within the technical constraints of the existing design of RDBMSs but avoid a full sequential scan of the database to obtain the top-k set.  In particular, the proposed research introduces techniques that systematically incorporate the relevant performance cost factors and their underlying trade-offs for efficient top-k retrieval.  The methodology encompasses analytical modelling and extensive computational and experimental analyses using real and synthetic data sets over a wide range of experimental settings.