Efficient Query Answering in Probabilistic RDF Graphs

Summary: Efficient query answering on probabilistic RDF graphs via search over high-probability subgraphs. Introduces synopses-based structural pruning for vertex/edge labels, a cost-model-driven probabilistic pruning to bound answers, and an integrated index combining synopses and statistics, with extensive experiments. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4379
Venue: SIGMOD
Year: 2011
Pagerank: 4.456315e-05
Overall Rank: 8,765 | 39.03%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Xiang Lian
2. Lei Chen

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,873	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB	6.6779082e-05
6,393	On Uncertain Graphs Modeling and Queries	2015	VLDB	5.0837624e-05
6,441	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	5.0603113e-05
11,264	Approximating Probabilistic Group Steiner Trees in Graphs	2023	VLDB	4.1945683e-05
11,769	Efficient Ad-Hoc Graph Inference and Matching in Biological Databases	2017	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
21	C-Store: A Column-oriented DBMS	2005	VLDB	0.00086087497
101	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.0004955674
321	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00027527389
417	Scalable Semantic Web Data Management Using Vertical Partitioning	2007	VLDB	0.00023794574
506	On Graph Query Optimization in Large Networks	2010	VLDB	0.00021475362
624	Hexastore: Sextuple Indexing for Semantic Web Data Management	2008	VLDB	0.00018988711
706	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00017845469
721	Data Integration with Uncertainty	2007	VLDB	0.00017570539
855	Integrating Conflicting Data: The Role of Source Dependence	2009	VLDB	0.00015906735
980	BayesStore: Managing Large, Uncertain Data Repositories with Probabilistic Graphical Models	2008	VLDB	0.00014879747
1,162	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.0001358105
1,213	RDF-3X: a RISC-style Engine for RDF	2008	VLDB	0.0001325231
1,609	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB	0.00011150935
1,705	U-DBMS: A Database System for Managing Constantly-Evolving Data	2005	VLDB	0.00010829958
1,706	Column-Store Support for RDF Data Management: not all swans are white	2008	VLDB	0.00010823026
2,774	ProTDB: Probabilistic Data in XML	2002	VLDB	8.134432e-05
4,983	Querying Probabilistic Information Extraction	2010	VLDB	5.7870787e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,568	Reformulation-based query answering in RDF: alternatives and performance	2015	VLDB	4.3254416e-05
4,958	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	5.8031038e-05
2,196	gStore: Answering SPARQL Queries via Subgraph Matching	2011	VLDB	9.3089621e-05
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057857292
12,090	Probabilistic Query Rewriting for Efficient and Effective Keyword Search on Graph Data	2013	VLDB	4.1945683e-05
9,058	Semantic SPARQL Similarity Search Over RDF Knowledge Graphs	2016	VLDB	4.4039656e-05
4,328	How to Build Templates for RDF Question/Answering —An Uncertain Graph Similarity Join Approach	2015	SIGMOD	6.2866586e-05
9,175	Efficient Exploration of Interesting Aggregates in RDF Graphs	2021	SIGMOD	4.383548e-05
3,211	Natural Language Question Answering over RDF — A Graph Data Driven Approach	2014	SIGMOD	7.3743561e-05
3,873	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB	6.6779082e-05