摘要: Large graph databases are commonly collected and analyzed in numerous domains. For reasons related to either space efficiency or for privacy protection (e.g., the case of social network graphs), it sometimes makes sense replace original with a summary, which removes certain details about topology. However, this summarization process leaves database owner challenge processing queries that expressed terms graph, but answered using summary. In paper, we propose formal semantics answering on summaries structures. At its core, our formulation is based random worlds model. We show important graph-structure adjacency, degree, eigenvector centrality) can be efficiently closed form these semantics. Further, approach query answering, formulate three novel partitioning/compression problems. develop algorithms finding summary least affects accuracy results, evaluate proposed both real synthetic data.
参考文章(37)
Raghu Ramakrishnan, Kristen LeFevre, Bee-Chung Chen, Privacy skyline: privacy with multidimensional adversarial knowledge very large data bases. pp. 770- 781 ,(2007)
P. Samarati, Protecting respondents identities in microdata release IEEE Transactions on Knowledge and Data Engineering. ,vol. 13, pp. 1010- 1027 ,(2001) , 10.1109/69.971193
Michael Hay, Gerome Miklau, David Jensen, Don Towsley, Philipp Weis, Resisting structural re-identification in anonymized social networks very large data bases. ,vol. 1, pp. 102- 114 ,(2008) , 10.14778/1453856.1453873
Yuanyuan Tian, Richard A. Hankins, Jignesh M. Patel, Efficient aggregation for graph summarization Proceedings of the 2008 ACM SIGMOD international conference on Management of data - SIGMOD '08. pp. 567- 580 ,(2008) , 10.1145/1376616.1376675
Ashwin Machanavajjhala, Daniel Kifer, Johannes Gehrke, Muthuramakrishnan Venkitasubramaniam, L-diversity: Privacy beyond k-anonymity ACM Transactions on Knowledge Discovery From Data. ,vol. 1, pp. 3- ,(2007) , 10.1145/1217299.1217302
A. Machanavajjhala, J. Gehrke, D. Kifer, M. Venkitasubramaniam, L-diversity: privacy beyond k-anonymity international conference on data engineering. pp. 24- 24 ,(2006) , 10.1109/ICDE.2006.1
Lyublena Antova, Christoph Koch, Dan Olteanu, 10106Worlds and Beyond: Efficient Representation and Processing of Incomplete Information international conference on data engineering. pp. 606- 615 ,(2007) , 10.1109/ICDE.2007.367906
LATANYA SWEENEY, k -anonymity: a model for protecting privacy International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems. ,vol. 10, pp. 557- 570 ,(2002) , 10.1142/S0218488502001648
Vitaly Shmatikov, Arvind Narayanan, De-anonymizing Social Networks ieee symposium on security and privacy. pp. 173- 187 ,(2009) , 10.1109/SP.2009.22
Lars Backstrom, Cynthia Dwork, Jon Kleinberg, Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography the web conference. pp. 181- 190 ,(2007) , 10.1145/1242572.1242598