Neighborhood-Privacy Protected Shortest Distance Computing in Cloud

Summary: Neighborhood-privacy for cloud-based shortest-distance queries by splitting a graph G into a local link graph Gl and outsourced graphs Go under a novel 1-neighborhood-d-radius model, preventing neighborhood attacks while preserving distances. Greedy Gl/Go construction minimizes client storage for exact answers; plus an efficient transformation supports additive-error approximate distances, with empirical validation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h9f06889eb1b03425
Venue: SIGMOD
Year: 2011
Pagerank: 6.076839e-05
Overall Rank: 5,581 | 62.48%
DOI: 10.1145/1989323.1989367

Incoming Non-self Citations Over Time

Authors

1. Jun Gao (Peking University)
2. Jeffery Yu Xu (Chinese University of Hong Kong)
3. Ruoming Jin (Kent State University)
4. Jiashuai Zhou (Peking University)
5. Tengjiao Wang (Peking University)
6. Dongqing Yang (Peking University)

BibTeX Citation

@inproceedings{gao_sigmod11,
        title = {{Neighborhood-Privacy Protected Shortest Distance Computing in Cloud}},
        author = {Gao, Jun and Xu, Jeffery Yu and Jin, Ruoming and Zhou, Jiashuai and Wang, Tengjiao and Yang, Dongqing},
        series = {{SIGMOD} '11},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1989323.1989367},
        url = {https://dl.acm.org/doi/10.1145/1989323.1989367},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,789	iBFS: Concurrent Breadth-First Search on GPUs	2016	SIGMOD	8.0116036e-05
5,017	Privacy Preserving Subgraph Matching on Large Graphs in Cloud	2016	SIGMOD	6.3125608e-05
7,980	Shortest Path Computation with No Information Leakage	2012	VLDB	5.4134849e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
625	Optimizing Linear Counting Queries Under Differential Privacy	2010	PODS	0.00015478765
783	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00014021799
1,008	Towards Identity Anonymization on Graphs	2008	SIGMOD	0.00012551244
1,367	Resisting Structural Re-identification in Anonymized Social Networks	2008	VLDB	0.00010911008
2,486	Anonymizing Bipartite Graph Data using Safe Groupings	2008	VLDB	8.3991285e-05
2,963	K-Automorphism: A General Framework for Privacy Preserving Network Publication	2009	VLDB	7.8060151e-05
4,210	Class-based graph anonymization for social network data	2009	VLDB	6.7332571e-05
5,323	K-Isomorphism: Privacy Preserving Network Publication against Structural Attacks	2010	SIGMOD	6.1801311e-05
5,975	Secure Outsourced Aggregation via One-way Chains	2009	SIGMOD	5.9305225e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,580	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB
2	9,183	Bonding Vertex Sets Over Distributed Graph: A Betweenness Aware Approach	2015	VLDB
3	8,662	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB
4	7,573	A Framework for Privacy Preserving Localized Graph Pattern Query Processing	2023	SIGMOD
5	4,028	Shortest Paths and Distances with Differential Privacy	2016	PODS
6	4,458	Fast Range Query Processing with Strong Privacy Protection for Cloud Computing	2014	VLDB
7	7,980	Shortest Path Computation with No Information Leakage	2012	VLDB
8	12,571	Efficiency and Security in Similarity Cloud Services	2013	VLDB
9	10,685	Scalable Privacy-Preserving Shortest Path Distance Computation via 2-Hop Labeling in MPC	2026	SIGMOD
10	5,017	Privacy Preserving Subgraph Matching on Large Graphs in Cloud	2016	SIGMOD