Left Bit Right: For SPARQL Join Queries with OPTIONAL Patterns (Left-outer-joins)

Summary: LBR uses a graph of supernodes to model nested BGP/OPTIONAL patterns, enabling aggressive RDF pruning with compressed indexes. Novel optimizations exploit acyclicity, minimality, and nullification/best-match for left-outer-joins; UNIONs/FILTERs are handled by rewrite; on large RDFs, LBR attains up to 11× speedups over Virtuoso/MonetDB on 8 GB RAM. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5094
Venue: SIGMOD
Year: 2015
Pagerank: 5.093636e-05
Overall Rank: 12,119 | 16.86%
DOI: 10.1145/2723372.2746483

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Medha Atre (Rensselaer Polytechnic Institute; University of Pennsylvania)

BibTeX Citation

@inproceedings{atre_sigmod15,
        title = {{Left Bit Right: For SPARQL Join Queries with OPTIONAL Patterns (Left-outer-joins)}},
        author = {Atre, Medha},
        series = {{SIGMOD} '15},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2723372.2746483},
        url = {https://dl.acm.org/doi/10.1145/2723372.2746483},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

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
500	Scalable SPARQL Querying of Large RDF Graphs	2011	VLDB	0.00017413839
542	Hexastore: Sextuple Indexing for Semantic Web Data Management	2008	VLDB	0.00016838296
1,176	Outerjoins as Disjunctions	1994	SIGMOD	0.00011809075
1,565	Column-Store Support for RDF Data Management: not all swans are white	2008	VLDB	0.00010349261
1,774	gStore: Answering SPARQL Queries via Subgraph Matching	2011	VLDB	9.7870727e-05
1,963	Building an Efficient RDF Store Over a Relational Database	2013	SIGMOD	9.3915212e-05
1,979	Scalable Join Processing on Very Large RDF Graphs	2009	SIGMOD	9.3621296e-05
2,053	TripleBit: a Fast and Compact System for Large Scale RDF Data	2013	VLDB	9.2518674e-05
2,287	TriAD: A Distributed Shared-Nothing RDF Engine based on Asynchronous Message Passing	2014	SIGMOD	8.8034872e-05
2,446	Querying Semantic Web Data with SPARQL	2011	PODS	8.5728114e-05
3,201	Apples and Oranges: A Comparison of RDF Benchmarks and Real RDF Datasets	2011	SIGMOD	7.6419269e-05
3,556	Static Analysis and Optimization of Semantic Web Queries	2012	PODS	7.3113256e-05
3,625	Canonical Abstraction for Outerjoin Optimization	2004	SIGMOD	7.2458252e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,813	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD
2	11,787	SPARQL Rewriting: Towards Desired Results	2020	SIGMOD
3	7,622	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB
4	143	Optimization of Nonrecursive Queries	1986	VLDB
5	11,895	The Tractability Frontier of Well-designed SPARQL Queries	2018	PODS
6	809	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB
7	1,013	Dynamic Programming Strikes Back	2008	SIGMOD
8	2,053	TripleBit: a Fast and Compact System for Large Scale RDF Data	2013	VLDB
9	1,979	Scalable Join Processing on Very Large RDF Graphs	2009	SIGMOD
10	3,556	Static Analysis and Optimization of Semantic Web Queries	2012	PODS