GraphOS: Towards Oblivious Graph Processing

Summary: GraphOS enables oblivious outsourced graph processing with leakage limited to graph size, query type, and response size, using trusted hardware and doubly-oblivious storage. Omix++ and fixed-trace BFS/DFS, MST, and SSSP yield up to 100× speedups over oblivious relational execution. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 13487
Venue: VLDB
Year: 2023
Pagerank: 6.2767341e-05
Overall Rank: 5,299 | 63.65%
DOI: 10.14778/3625054.3625067

Incoming Non-self Citations Over Time

Authors

1. Javad Ghareh Chamani (Hong Kong University of Science and Technology)
2. Ioannis Demertzis (University of California Santa Cruz)
3. Dimitrios Papadopoulos (Hong Kong University of Science and Technology)
4. Charalampos Papamanthou (Yale University)
5. Rasool Jalili (Sharif University of Technology)

BibTeX Citation

@article{chamani_vldb23,
        title = {{GraphOS: Towards Oblivious Graph Processing}},
        author = {Chamani, Javad Ghareh and Demertzis, Ioannis and Papadopoulos, Dimitrios and Papamanthou, Charalampos and Jalili, Rasool},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {13},
        pages = {4324--4338},
        doi = {10.14778/3625054.3625067},
        url = {https://doi.org/10.14778/3625054.3625067},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,896	Aster: Enhancing LSM-structures for Scalable Graph Database	2025	SIGMOD	5.3495662e-05
10,570	Enabling Index-free Adjacency in Oblivious Graph Processing with Delayed Duplications	2026	VLDB	5.093636e-05
10,921	Sectric: Towards Accurate, Privacy-preserving and Efficient Triangle Counting	2025	VLDB	5.093636e-05
10,936	GORAM: Graph-oriented ORAM for Efficient Ego-centric Queries on Federated Graphs	2025	VLDB	5.093636e-05
11,092	Towards Practical Oblivious Map	2025	VLDB	5.093636e-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
24	Spark SQL: Relational Data Processing in Spark	2015	SIGMOD	0.00054865648
412	Processing Analytical Queries over Encrypted Data	2013	VLDB	0.00018901853
436	Trinity: A Distributed Graph Engine on a Memory Cloud	2013	SIGMOD	0.00018504439
526	TrustedDB: A Trusted Hardware based Database with Privacy and Data Confidentiality	2011	SIGMOD	0.00017112934
1,367	H2O: A Hands-free Adaptive Store	2014	SIGMOD	0.00011014419
1,811	Merging What's Cracked, Cracking What's Merged: Adaptive Indexing in Main-Memory Column-Stores	2011	VLDB	9.698026e-05
1,983	Pregelix: Big(ger) Graph Analytics on A Dataflow Engine	2015	VLDB	9.3544951e-05
2,433	Vertexica: Your Relational Friend for Graph Analytics!	2014	VLDB	8.5869161e-05
2,854	Extracting and Analyzing Hidden Graphs from Relational Databases	2017	SIGMOD	8.0350257e-05
4,625	Practical Private Range Search Revisited	2016	SIGMOD	6.5989597e-05
4,930	IncShrink: Architecting Efficient Outsourced Databases using Incremental MPC and Differential Privacy	2022	SIGMOD	6.4402718e-05
6,797	Efficient Searchable Encryption Through Compression	2018	VLDB	5.7707661e-05
11,996	Fast Searchable Encryption With Tunable Locality	2017	SIGMOD	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,318	Optimizing Declarative Graph Queries at Large Scale	2019	SIGMOD
2	3,357	Columnar Storage and List-based Processing for Graph Database Management Systems	2021	VLDB
3	294	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD
4	2,854	Extracting and Analyzing Hidden Graphs from Relational Databases	2017	SIGMOD
5	11,745	Parallel Traversal of Graphs Stored in RDBMSs	2020	CIDR
6	5,384	Privacy Preserving Subgraph Matching on Large Graphs in Cloud	2016	SIGMOD
7	8,586	A Framework for Privacy Preserving Localized Graph Pattern Query Processing	2023	SIGMOD
8	2,045	Efficient Oblivious Database Joins	2020	VLDB
9	11,092	Towards Practical Oblivious Map	2025	VLDB
10	10,570	Enabling Index-free Adjacency in Oblivious Graph Processing with Delayed Duplications	2026	VLDB