DocumentCode :
3302431
Title :
Adaptive Algorithm for Threshold Path Subset Queries
Author :
Barbay, Jérémy ; Veraskouski, Aleh
Author_Institution :
DCC (Dept. de Cienc. de la Comput.), Univ. de Chile, Santiago, Chile
fYear :
2009
fDate :
10-12 Nov. 2009
Firstpage :
3
Lastpage :
10
Abstract :
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.
Keywords :
Adaptive algorithm; Computer science; Costs; Data structures; Encoding; File systems; Indexing; Search engines; Tree data structures; XML; Adaptive; Intersection; Labeled Trees; Threshold;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Chilean Computer Science Society (SCCC), 2009 International Conference of the
Conference_Location :
Santiago, TBD, Chile
ISSN :
1522-4902
Print_ISBN :
978-1-4244-7752-4
Type :
conf
DOI :
10.1109/SCCC.2009.17
Filename :
5532405
Link To Document :
بازگشت