Adaptive Algorithms for Weighted Queries on Weighted Binary Relations and Labeled Trees

Simple keyword queries are extremely easy for a user to use. They only require him to indicate the words that are, as he believes, relevant to the information he is looking for. This type of queries does not assume any additional knowledge from users, which is especially important nowadays when most of them are laypersons. However, while simple keyword queries do not impose any structural constraints on the information retrieved, the quality of the search is often very poor. Moreover, it is hardly possible to improve the situation without changing the way the queries are asked and the information is stored. Here, we extend simple keyword queries and existing ways of organizing information in the database by adding weights to improve the quality of information retrieval. We consider weighted queries on weighted binary relations and weighted multi-labeled trees. We propose adaptive algorithms to solve these queries and measures of their complexity in terms of the number of high-level operations. We describe how these algorithms can be implemented and derive the exact upper bounds for them.