Adaptive Algorithm for Threshold Path Subset Queries

摘要

In the context of queries to indexed search engines such as Google, Barbay and Kenyon introduced and solved threshold set queries, answered by the set of references associated with at least $t$ keywords out of the $k$ given as input, for some constant parameter $t$. We slightly generalize those results to the easy case where weights are associated to the keywords of the query, and to the more difficult case where weights are associated to the pairs of the relation between keywords and references. In the context of search queries on indexed file systems, Barbay et al. introduced and solved path-subset queries, answered by the minimum set of subtrees which rooted path match all $k$ keywords given as input. We combine both approaches to define and solve weighted threshold path-subset queries, answered by the minimum set of subtrees which rooted path match at least $t$ keywords out of the $k$ given as input, through the definition of a reduction to threshold queries.