EUVIMEDEUVIMED entdecken
Crossref

Enabling Index-Free Adjacency in Oblivious Graph Processing with Delayed Duplications

Weiqi Feng, Xinle Cao*, Adam O'Neill, Chuanhui Yang

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →