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: 4441
Venue: SIGMOD
Year: 2011
Pagerank: 5.3483178e-05
Overall Rank: 8,935 | 38.70%
DOI: 10.1145/1989323.1989341

Incoming Non-self Citations Over Time

Authors

1. Xiang Lian (Hong Kong University of Science and Technology)
2. Lei Chen (Hong Kong University of Science and Technology)

BibTeX Citation

@inproceedings{lian_sigmod11,
        title = {{Efficient Query Answering in Probabilistic RDF Graphs}},
        author = {Lian, Xiang and Chen, Lei},
        series = {{SIGMOD} '11},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1989323.1989341},
        url = {https://dl.acm.org/doi/10.1145/1989323.1989341},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,548	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB	7.3214417e-05
6,037	On Uncertain Graphs Modeling and Queries	2015	VLDB	5.9990983e-05
6,149	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	5.9581422e-05
11,463	Approximating Probabilistic Group Steiner Trees in Graphs	2023	VLDB	5.093636e-05
11,974	Efficient Ad-Hoc Graph Inference and Matching in Biological Databases	2017	SIGMOD	5.093636e-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
12	C-Store: A Column-oriented DBMS	2005	VLDB	0.00069513174
78	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00036571789
238	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.0002369322
352	On Graph Query Optimization in Large Networks	2010	VLDB	0.00020375193
366	Scalable Semantic Web Data Management Using Vertical Partitioning	2007	VLDB	0.00020039981
542	Hexastore: Sextuple Indexing for Semantic Web Data Management	2008	VLDB	0.00016838296
683	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00015005338
699	Data Integration with Uncertainty	2007	VLDB	0.0001487423
820	BayesStore: Managing Large, Uncertain Data Repositories with Probabilistic Graphical Models	2008	VLDB	0.00013814535
890	Integrating Conflicting Data: The Role of Source Dependence	2009	VLDB	0.00013382697
944	RDF-3X: a RISC-style Engine for RDF	2008	VLDB	0.00013067088
1,049	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.00012415522
1,327	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB	0.00011141552
1,565	Column-Store Support for RDF Data Management: not all swans are white	2008	VLDB	0.00010349261
1,638	U-DBMS: A Database System for Managing Constantly-Evolving Data	2005	VLDB	0.00010155338
2,569	ProTDB: Probabilistic Data in XML	2002	VLDB	8.4090027e-05
4,935	Querying Probabilistic Information Extraction	2010	VLDB	6.4357418e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,994	Reformulation-based query answering in RDF: alternatives and performance	2015	VLDB
2	4,853	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB
3	1,774	gStore: Answering SPARQL Queries via Subgraph Matching	2011	VLDB
4	50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB
5	12,287	Probabilistic Query Rewriting for Efficient and Effective Keyword Search on Graph Data	2013	VLDB
6	9,149	Semantic SPARQL Similarity Search Over RDF Knowledge Graphs	2016	VLDB
7	5,168	How to Build Templates for RDF Question/Answering —An Uncertain Graph Similarity Join Approach	2015	SIGMOD
8	9,339	Efficient Exploration of Interesting Aggregates in RDF Graphs	2021	SIGMOD
9	3,981	Natural Language Question Answering over RDF — A Graph Data Driven Approach	2014	SIGMOD
10	3,548	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB