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: 13299
Venue: VLDB
Year: 2023
Pagerank: 5.300937e-05
Overall Rank: 5,851 | 59.30%
DOI: 10.14778/3625054.3625067

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,367	Aster: Enhancing LSM-structures for Scalable Graph Database	2025	SIGMOD	4.1945683e-05
10,672	Sectric: Towards Accurate, Privacy-preserving and Efficient Triangle Counting	2025	VLDB	4.1945683e-05
10,689	GORAM: Graph-oriented ORAM for Efficient Ego-centric Queries on Federated Graphs	2025	VLDB	4.1945683e-05
10,869	Towards Practical Oblivious Map	2025	VLDB	4.1945683e-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.00061639801
459	Processing Analytical Queries over Encrypted Data	2013	VLDB	0.00022627746
534	TrustedDB: A Trusted Hardware based Database with Privacy and Data Confidentiality	2011	SIGMOD	0.00020729713
558	Trinity: A Distributed Graph Engine on a Memory Cloud	2013	SIGMOD	0.00020168032
1,807	H2O: A Hands-free Adaptive Store	2014	SIGMOD	0.00010487796
2,363	Merging What’s Cracked, Cracking What’s Merged: Adaptive Indexing in Main-Memory Column-Stores	2011	VLDB	8.9580928e-05
2,529	Pregelix: Big(ger) Graph Analytics on A Dataflow Engine	2015	VLDB	8.5940768e-05
2,709	Vertexica: Your Relational Friend for Graph Analytics!	2014	VLDB	8.2530203e-05
3,143	Extracting and Analyzing Hidden Graphs from Relational Databases	2017	SIGMOD	7.4804326e-05
4,799	Practical Private Range Search Revisited	2016	SIGMOD	5.9119553e-05
5,519	IncShrink: Architecting Efficient Outsourced Databases using Incremental MPC and Differential Privacy	2022	SIGMOD	5.4619886e-05
8,539	Efficient Searchable Encryption Through Compression	2018	VLDB	4.4937074e-05
11,792	Fast Searchable Encryption With Tunable Locality	2017	SIGMOD	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,746	OasisDB: An Oblivious and Scalable System for Relational Data	2025	VLDB	4.1945683e-05
8,396	Optimizing Declarative Graph Queries at Large Scale	2019	SIGMOD	4.5276541e-05
4,012	Columnar Storage and List-based Processing for Graph Database Management Systems	2021	VLDB	6.5335884e-05
3,143	Extracting and Analyzing Hidden Graphs from Relational Databases	2017	SIGMOD	7.4804326e-05
461	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022499343
11,548	Parallel Traversal of Graphs Stored in RDBMSs	2020	CIDR	4.1945683e-05
4,940	Privacy Preserving Subgraph Matching on Large Graphs in Cloud	2016	SIGMOD	5.8180285e-05
8,490	A Framework for Privacy Preserving Localized Graph Pattern Query Processing	2023	SIGMOD	4.499438e-05
2,670	Efficient Oblivious Database Joins	2020	VLDB	8.3379158e-05
10,869	Towards Practical Oblivious Map	2025	VLDB	4.1945683e-05