document: Machine learning for online query relaxation In this paper we provide a fast , data-driven solution to the failing query problem : given a query that returns an empty answer , how can one relax the query 's constraints so that it returns a non-empty set of tuples ? We introduce a novel algorithm , loqr , which is designed to relax queries that are in the disjunctive normal form and contain a mixture of discrete and continuous attributes . loqr discovers the implicit relationships that exist among the various domain attributes and then uses this knowledge to relax the constraints from the failing query . In a first step , loqr uses a small , randomly-chosen subset of the target database to learn a set of decision rules that predict whether an attribute 's value satisfies the constraints in the failing query ; this query-driven operation is performed online for each failing query . In the second step , loqr uses nearest-neighbor techniques to find the learned rule that is the most similar to the failing query ; then it uses the attributes ' values from this rule to relax the failing query 's constraints . Our experiments on six application domains show that loqr is both robust and fast : it successfully relaxes more than 95 % of the failing queries , and it takes under a second for processing queries that consist of up to 20 attributes ( larger queries of up to 93 attributes are processed in several seconds ) .
doc_bio_tags: O B O B I I O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O