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
1685
Venue
PODS
Year
2016
Pagerank
6.9993183e-05
Overall Rank
3,948 | 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,083 Global and Local Differentially Private Release of Count-Weighted Graphs 2023 SIGMOD 5.9833455e-05
7,976 Correlation Constraint Shortest Path over Large Multi-Relation Graphs 2019 VLDB 5.5152959e-05
9,538 Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation 2025 PODS 5.2528121e-05
10,158 Improved Lower Bounds for Privacy under Continual Release 2026 PODS 5.093636e-05
10,385 N2E: A General Framework to Reduce Node-Differential Privacy to Edge-Differential Privacy for Graph Analytics 2026 SIGMOD 5.093636e-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
596 Private Analysis of Graph Structure 2011 VLDB 0.00015926024
Previous Page 1 / 1 Next

Semantically Similar Papers

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