Enabling Index-Free Adjacency in Oblivious Graph Processing with Delayed Duplications
Proceedings of the VLDB Endowment · 01.04.2026 · 19 (8) · 1826-1839
DOI: 10.14778/3811243.3811255 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 15.07.2026. Verfasst von Weiqi Feng und 3 weiteren Autor:innen. Die Arbeit nennt 86 Literaturangaben.
Abstract (Originalsprache)
Obliviousness has been regarded as an essential property in encrypted databases (EDBs) for mitigating leakage from access patterns. Yet despite decades of work, practical oblivious graph processing remains an open problem. In particular, all existing approaches fail to enable the design of index-free adjacency (IFA), i.e., each vertex preserves the physical positions of its neighbors. However, IFA has been widely recognized as necessary for efficient graph processing and is fundamental in native graph databases (e.g., Neo4j). In this work, we propose a core technique named delayed duplication to resolve the conflict between IFA and obliviousness. To the best of our knowledge, we are the first to address this conflict with both practicality and strict security. Based on the new technique, we utilize elaborate data structures to develop a new EDB named Grove for processing expressive graph queries. The experimental results demonstrate that incorporating IFA makes Grove impressively outperform the state-of-the-art work across multiple graph-processing tasks, such as neighbor query and t -hop query.
Zitieren
APA
Feng, W., Cao*, X., O'Neill, A., & Yang, C. (2026). Enabling Index-Free Adjacency in Oblivious Graph Processing with Delayed Duplications. Proceedings of the VLDB Endowment, 19(8), 1826-1839. https://doi.org/10.14778/3811243.3811255
Vancouver
Feng W, Cao* X, O'Neill A, Yang C. Enabling Index-Free Adjacency in Oblivious Graph Processing with Delayed Duplications. Proceedings of the VLDB Endowment. 2026;19(8):1826-1839. doi:10.14778/3811243.3811255
BibTeX
@article{Feng2026,
author = {Feng, Weiqi and Cao*, Xinle and O'Neill, Adam and Yang, Chuanhui},
title = {Enabling Index-Free Adjacency in Oblivious Graph Processing with Delayed Duplications},
journal = {Proceedings of the VLDB Endowment},
year = {2026},
volume = {19},
number = {8},
pages = {1826--1839},
doi = {10.14778/3811243.3811255}
}
EUVIMED