DBScholar

Back to papers

Shortest Paths and Distances with Differential Privacy

Summary: DP model: public topology, private edge weights (neighbors: ℓ1 distance ≤1); studies private release of shortest paths and all-pairs distances. Proves an Ω(|V|) additive lower bound for path release and gives a near-matching algorithm with error scaling with path length; all-pairs: trees O(log^{2.5}|V|) and bounded-weight graphs Õ(|V|M). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
hbc3ea2eebe89ac2c
Venue
PODS
Year
2016
Pagerank
6.8424244e-05
Overall Rank
4,028 | 72.92%
DOI
10.1145/2902251.2902291

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{sealfon_pods16,
        address = {New York, NY, USA},
        series = {{PODS} '16},
        title = {{Shortest Paths and Distances with Differential Privacy}},
        url = {https://dl.acm.org/doi/10.1145/2902251.2902291},
        doi = {10.1145/2902251.2902291},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Sealfon, Adam},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank Citing Paper Year Venue Pagerank
6,210 Global and Local Differentially Private Release of Count-Weighted Graphs 2023 SIGMOD 5.8490953e-05
8,063 Correlation Constraint Shortest Path over Large Multi-Relation Graphs 2019 VLDB 5.3954994e-05
9,721 Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation 2025 PODS 5.1349531e-05
10,375 Improved Lower Bounds for Privacy under Continual Release 2026 PODS 4.9793485e-05
10,581 N2E: A General Framework to Reduce Node-Differential Privacy to Edge-Differential Privacy for Graph Analytics 2026 SIGMOD 4.9793485e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
609 Private Analysis of Graph Structure 2011 VLDB 0.00015591971
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 10,375 Improved Lower Bounds for Privacy under Continual Release 2026 PODS
2 609 Private Analysis of Graph Structure 2011 VLDB
3 6,495 Robust Privacy-Preserving Triangle Counting under Edge Local Differential Privacy 2025 SIGMOD
4 2,009 Private Release of Graph Statistics using Ladder Functions 2015 SIGMOD
5 10,685 Scalable Privacy-Preserving Shortest Path Distance Computation via 2-Hop Labeling in MPC 2026 SIGMOD
6 11,356 Continuous Publication of Weighted Graphs with Local Differential Privacy 2025 VLDB
7 7,980 Shortest Path Computation with No Information Leakage 2012 VLDB
8 11,686 Node-Differentially Private Estimation of the Number of Connected Components 2023 PODS
9 6,210 Global and Local Differentially Private Release of Count-Weighted Graphs 2023 SIGMOD
10 9,721 Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation 2025 PODS