Query Efficiency in Probabilistic XML Models

Summary: Unifies probabilistic XML via p-documents with distributional nodes; analyzes twig queries under value- and object-based semantics. Efficient evaluator for a single tractable family; translations across families and approximate methods for the rest. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hb645bb3a79128e51
Venue: SIGMOD
Year: 2008
Pagerank: 5.6086666e-05
Overall Rank: 7,060 | 52.55%
DOI: 10.1145/1376616.1376687

Incoming Non-self Citations Over Time

Authors

1. Benny Kimelfeld (Hebrew University)
2. Yuri Kosharovsky (Hebrew University)
3. Yehoshua Sagiv (Hebrew University)

BibTeX Citation

@inproceedings{kimelfeld_sigmod08,
        title = {{Query Efficiency in Probabilistic XML Models}},
        author = {Kimelfeld, Benny and Kosharovsky, Yuri and Sagiv, Yehoshua},
        series = {{SIGMOD} '08},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1376616.1376687},
        url = {https://dl.acm.org/doi/10.1145/1376616.1376687},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,971	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	6.3302434e-05
5,293	How to Build Templates for RDF Question/Answering —An Uncertain Graph Similarity Join Approach	2015	SIGMOD	6.1908657e-05
5,478	Running Tree Automata on Probabilistic XML	2009	PODS	6.1147103e-05
8,931	Incorporating Constraints in Probabilistic XML	2008	PODS	5.2534908e-05
12,705	Transducing Markov Sequences	2010	PODS	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 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.00042926566
179	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00026617591
409	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00018859247
660	The Complexity of Query Reliability	1998	PODS	0.00015045167
1,066	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.00012194105
2,619	ProTDB: Probabilistic Data in XML	2002	VLDB	8.2180287e-05
2,883	On the minimization of XPath queries	2003	VLDB	7.9096688e-05
3,133	Matching Twigs in Probabilistic XML	2007	VLDB	7.6103114e-05
3,379	On the Complexity of Managing Probabilistic XML Data	2007	PODS	7.3535108e-05
4,262	Maximally Joining Probabilistic Data	2007	PODS	6.6954238e-05
8,931	Incorporating Constraints in Probabilistic XML	2008	PODS	5.2534908e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,680	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB
2	9,824	ProApproX: A Lightweight Approximation Query Processor over Probabilistic Trees	2011	SIGMOD
3	13,007	An Algebraic Query Model for Effective and Efficient Retrieval of XML Fragments	2006	VLDB
4	6,641	Probabilistic XML via Markov Chains	2010	VLDB
5	3,248	Approximate XML Query Answers	2004	SIGMOD
6	5,425	Efficient Processing of XML Twig Queries with OR-Predicates	2004	SIGMOD
7	5,478	Running Tree Automata on Probabilistic XML	2009	PODS
8	12,622	Answering Queries using Views over Probabilistic XML: Complexity and Tractability	2012	VLDB
9	3,379	On the Complexity of Managing Probabilistic XML Data	2007	PODS
10	3,133	Matching Twigs in Probabilistic XML	2007	VLDB