Matching Twigs in Probabilistic XML

Summary: Twig queries with projection over probabilistic XML: tractable under data complexity; projection intractable in other models. Threshold-based partial answers (maximal by probability) and twig evaluation without projection under query-and-data complexity. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: he90bddd3cb61ca52
Venue: VLDB
Year: 2007
Pagerank: 7.6137556e-05
Overall Rank: 3,132 | 78.95%
DOI: 10.14778/1325851.1325854

Incoming Non-self Citations Over Time

Authors

1. Benny Kimelfeld (Hebrew University)
2. Yehoshua Sagiv (Hebrew University)

BibTeX Citation

@article{kimelfeld_vldb07,
        title = {{Matching Twigs in Probabilistic XML}},
        author = {Kimelfeld, Benny and Sagiv, Yehoshua},
        journal = {PVLDB},
        series = {{VLDB} '07},
        volume = {30},
        number = {2},
        pages = {27--38},
        doi = {10.14778/1325851.1325854},
        url = {https://doi.org/10.14778/1325851.1325854},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
245	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00023258672
5,474	Running Tree Automata on Probabilistic XML	2009	PODS	6.1176063e-05
6,637	Probabilistic XML via Markov Chains	2010	VLDB	5.7262369e-05
6,708	Selective Provenance for Datalog Programs Using Top-K Queries	2015	VLDB	5.7027474e-05
7,057	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	5.6113229e-05
8,923	Incorporating Constraints in Probabilistic XML	2008	PODS	5.2559789e-05
12,701	Certain Answers for XML Queries	2010	PODS	4.9793485e-05
12,761	Navigating in Complex Mashed-Up Applications	2010	VLDB	4.9793485e-05
12,769	Optimal Top-K Query Evaluation for Weighted Business Processes	2010	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00042936299
421	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00018516535
571	The Theory of Probabilistic Databases	1987	VLDB	0.00016210743
658	The Complexity of Query Reliability	1998	PODS	0.00015051203
1,065	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.0001219981
1,198	Outerjoins as Disjunctions	1994	SIGMOD	0.00011565328
2,617	ProTDB: Probabilistic Data in XML	2002	VLDB	8.2219007e-05
2,853	Integrating Information by Outerjoins and Full Disjunctions (Extended Abstract)	1996	PODS	7.9412355e-05
3,378	On the Complexity of Managing Probabilistic XML Data	2007	PODS	7.3569859e-05
4,262	Maximally Joining Probabilistic Data	2007	PODS	6.6984258e-05
6,499	Full Disjunctions: Polynomial-Delay Iterators in Action	2006	VLDB	5.7650247e-05
8,234	An Incremental Algorithm for Computing Ranked Full Disjunctions	2005	PODS	5.3711847e-05
9,789	Computing Full Disjunctions	2003	PODS	5.1265605e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,200	On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques	2005	SIGMOD
2	3,246	Approximate XML Query Answers	2004	SIGMOD
3	2,746	Holistic Twig Joins on Indexed XML Documents	2003	VLDB
4	178	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD
5	9,901	Fast Optimal Twig Joins	2010	VLDB
6	5,474	Running Tree Automata on Probabilistic XML	2009	PODS
7	12,616	Answering Queries using Views over Probabilistic XML: Complexity and Tractability	2012	VLDB
8	5,421	Efficient Processing of XML Twig Queries with OR-Predicates	2004	SIGMOD
9	3,378	On the Complexity of Managing Probabilistic XML Data	2007	PODS
10	7,057	Query Efficiency in Probabilistic XML Models	2008	SIGMOD