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: 4462
Venue: SIGMOD
Year: 2011
Pagerank: 6.1924452e-05
Overall Rank: 5,507 | 62.22%
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,874	iBFS: Concurrent Breadth-First Search on GPUs	2016	SIGMOD	8.0094569e-05
5,384	Privacy Preserving Subgraph Matching on Large Graphs in Cloud	2016	SIGMOD	6.2370509e-05
7,817	Shortest Path Computation with No Information Leakage	2012	VLDB	5.5377369e-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
611	Optimizing Linear Counting Queries Under Differential Privacy	2010	PODS	0.00015747402
776	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00014110016
985	Towards Identity Anonymization on Graphs	2008	SIGMOD	0.00012818114
1,326	Resisting Structural Re-identification in Anonymized Social Networks	2008	VLDB	0.00011145219
2,430	Anonymizing Bipartite Graph Data using Safe Groupings	2008	VLDB	8.5885381e-05
2,909	K-Automorphism: A General Framework for Privacy Preserving Network Publication	2009	VLDB	7.9708764e-05
4,125	Class-based graph anonymization for social network data	2009	VLDB	6.886347e-05
5,227	K-Isomorphism: Privacy Preserving Network Publication against Structural Attacks	2010	SIGMOD	6.3085805e-05
5,853	Secure Outsourced Aggregation via One-way Chains	2009	SIGMOD	6.0655523e-05

Semantically Similar Papers

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