On the hardness of learning queries from tree structured data

Xianmin Liu () and Jianzhong Li ()
Additional contact information
Xianmin Liu: Harbin Institute of Technology
Jianzhong Li: Harbin Institute of Technology

Journal of Combinatorial Optimization, 2015, vol. 29, issue 3, No 9, 670-684

Abstract: Abstract The problem of learning queries from tree structured data is studied by this paper. A tree structured data is modeled as a node-labeled tree $$T$$ T , and applying a query $$q$$ q on $$T$$ T will return a set $$q(T)$$ q ( T ) which is a subset of nodes in $$T$$ T . For a tree-node pair $$(T,t)$$ ( T , t ) where $$t$$ t is a node in $$T$$ T , $$q$$ q is called to accept the pair if $$t\in {q(T)}$$ t ∈ q ( T ) , and reject the pair if $$t\notin {q(T)}$$ t ∉ q ( T ) . For some query class $$\mathcal{L }$$ L , given tree-node pair sets $$E_p$$ E p and $$E_n$$ E n , the tree query learning problem is to find a query $$q\in \mathcal{L }$$ q ∈ L such that (1) $$q$$ q rejects all pairs in $$E_n$$ E n , and (2) the size of pairs in $$E_p$$ E p accepted by $$q$$ q is maximized. On four different query classes $$\mathcal Q ^{\tiny /}$$ Q / , $$\mathcal Q ^{\tiny /,*}$$ Q / , ∗ , $$\mathcal Q ^{\tiny /,//}$$ Q / , / / and $$\mathcal Q ^{\tiny /,[]}$$ Q / , [ ] , this paper studies the hardness of the corresponding tree query learning problems. For $$\mathcal Q ^{\tiny /}$$ Q / , a PTime algorithm is given. For $$\mathcal Q ^{\tiny /,*}$$ Q / , ∗ and $$\mathcal Q ^{\tiny /,//}$$ Q / , / / , the NP-complete results are shown. For $$\mathcal Q ^{\tiny /,[]}$$ Q / , [ ] , the problem is shown to be NP-hard by considering two constrained fragments of $$\mathcal Q ^{\tiny /,[]}$$ Q / , [ ] . Also, for $$\mathcal Q ^{\tiny /,*}$$ Q / , ∗ , $$\mathcal Q ^{\tiny /,[]}$$ Q / , [ ] and $$\mathcal Q ^{\tiny /,//}$$ Q / , / / , it is shown that there are no $$n^{1-\epsilon }$$ n 1 − ϵ -approximation algorithms for any $$\epsilon >0$$ ϵ > 0 .

Keywords: Tree Query Learning; Hardness; Inapproximability (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9609-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:29:y:2015:i:3:d:10.1007_s10878-013-9609-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9609-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().