GraphOS: Towards Oblivious Graph Processing

Summary: GraphOS outsources graphs to untrusted servers using doubly‑oblivious storage inside trusted enclaves, leaking only |V|, |E| and each query's type and response size. It presents Omix++ (a doubly‑oblivious map, up to 34× faster) and fixed‑trace BFS/DFS/MST/SSSP to prevent memory and instruction‑fetch leakage, yielding up to two orders‑of‑magnitude speedup vs oblivious RDBMS and eliminating topology leakage. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13300
Venue: VLDB
Year: 2023
Pagerank: 5.4701773e-05
Overall Rank: 5,511 | 61.70%
DOI: 10.14778/3625054.3625067

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,283	Enabling Index-free Adjacency in Oblivious Graph Processing with Delayed Duplications	2026	VLDB	4.1905499e-05
10,379	Aster: Enhancing LSM-structures for Scalable Graph Database	2025	SIGMOD	4.1905499e-05
10,680	Sectric: Towards Accurate, Privacy-preserving and Efficient Triangle Counting	2025	VLDB	4.1905499e-05
10,697	GORAM: Graph-oriented ORAM for Efficient Ego-centric Queries on Federated Graphs	2025	VLDB	4.1905499e-05
10,873	Towards Practical Oblivious Map	2025	VLDB	4.1905499e-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
66	Spark SQL: Relational Data Processing in Spark	2015	SIGMOD	0.00061707583
455	Processing Analytical Queries over Encrypted Data	2013	VLDB	0.00022736946
532	TrustedDB: A Trusted Hardware based Database with Privacy and Data Confidentiality	2011	SIGMOD	0.00020773783
558	Trinity: A Distributed Graph Engine on a Memory Cloud	2013	SIGMOD	0.00020158056
1,801	H2O: A Hands-free Adaptive Store	2014	SIGMOD	0.00010485628
2,361	Merging What’s Cracked, Cracking What’s Merged: Adaptive Indexing in Main-Memory Column-Stores	2011	VLDB	8.9648608e-05
2,528	Pregelix: Big(ger) Graph Analytics on A Dataflow Engine	2015	VLDB	8.5953347e-05
2,711	Vertexica: Your Relational Friend for Graph Analytics!	2014	VLDB	8.2548656e-05
3,147	Extracting and Analyzing Hidden Graphs from Relational Databases	2017	SIGMOD	7.4825501e-05
4,775	Practical Private Range Search Revisited	2016	SIGMOD	5.9275924e-05
5,522	IncShrink: Architecting Efficient Outsourced Databases using Incremental MPC and Differential Privacy	2022	SIGMOD	5.4654207e-05
8,457	Efficient Searchable Encryption Through Compression	2018	VLDB	4.5018004e-05
11,800	Fast Searchable Encryption With Tunable Locality	2017	SIGMOD	4.1905499e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,394	Optimizing Declarative Graph Queries at Large Scale	2019	SIGMOD	4.5233733e-05
4,017	Columnar Storage and List-based Processing for Graph Database Management Systems	2021	VLDB	6.5276062e-05
3,147	Extracting and Analyzing Hidden Graphs from Relational Databases	2017	SIGMOD	7.4825501e-05
460	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022679846
11,552	Parallel Traversal of Graphs Stored in RDBMSs	2020	CIDR	4.1905499e-05
4,942	Privacy Preserving Subgraph Matching on Large Graphs in Cloud	2016	SIGMOD	5.8124358e-05
8,488	A Framework for Privacy Preserving Localized Graph Pattern Query Processing	2023	SIGMOD	4.4951247e-05
2,549	Efficient Oblivious Database Joins	2020	VLDB	8.5572389e-05
10,873	Towards Practical Oblivious Map	2025	VLDB	4.1905499e-05
10,283	Enabling Index-free Adjacency in Oblivious Graph Processing with Delayed Duplications	2026	VLDB	4.1905499e-05