{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T16:55:58Z","timestamp":1759683358903,"version":"3.40.5"},"reference-count":58,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,12,9]],"date-time":"2014-12-09T00:00:00Z","timestamp":1418083200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2015,4]]},"DOI":"10.1007\/s00778-014-0373-y","type":"journal-article","created":{"date-parts":[[2014,12,8]],"date-time":"2014-12-08T13:48:16Z","timestamp":1418046496000},"page":"271-296","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":27,"title":["Graph similarity search on large uncertain graph databases"],"prefix":"10.1007","volume":"24","author":[{"given":"Ye","family":"Yuan","sequence":"first","affiliation":[]},{"given":"Guoren","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Lei","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Haixun","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,12,9]]},"reference":[{"key":"373_CR1","unstructured":"Abadi, D.J., Marcus, A., Madden, S.R., Hollenbach, K.: Scalable semantic web data management using vertical partitioning. In: Proceedings of VLDB, pp. 411\u2013422 (2007)"},{"issue":"2","key":"373_CR2","first-page":"15","volume":"30","author":"E Adar","year":"2007","unstructured":"Adar, E., Re, C.: Managing uncertainty in social networks. IEEE Data Eng. Bull. 30(2), 15\u201322 (2007)","journal-title":"IEEE Data Eng. Bull."},{"key":"373_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-09690-2","volume-title":"Managing and Mining Uncertain Data","author":"C Aggarwal","year":"2009","unstructured":"Aggarwal, C.: Managing and Mining Uncertain Data. Springer, Berlin (2009)"},{"key":"373_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4419-6045-0","volume-title":"Managing and Mining Graph Data","author":"C Aggarwal","year":"2010","unstructured":"Aggarwal, C., Wang, H.: Managing and Mining Graph Data. Springer, Berlin (2010)"},{"issue":"6","key":"373_CR5","doi-asserted-by":"crossref","first-page":"1170","DOI":"10.1101\/gr.2203804","volume":"14","author":"S Asthana","year":"2004","unstructured":"Asthana, S., King, O., Gibbons, F., Roth, F.: Predicting protein complex membership using probabilistic network reliability. Genome Res. 14(6), 1170\u20131175 (2004)","journal-title":"Genome Res."},{"issue":"1","key":"373_CR6","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1038\/nbt924","volume":"22","author":"JS Bader","year":"2003","unstructured":"Bader, J.S., Chaudhuri, A., Rothberg, J.M., Chant, J.: Gaining confidence in high-throughput protein interaction networks. Nat. Biotechnol. 22(1), 78\u201385 (2003)","journal-title":"Nat. Biotechnol."},{"key":"373_CR7","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1007\/BF01955041","volume":"15","author":"E Balas","year":"1996","unstructured":"Balas, E., Xue, J.: Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring. Algorithmica 15, 397\u2013412 (1996)","journal-title":"Algorithmica"},{"key":"373_CR8","doi-asserted-by":"crossref","unstructured":"Biswas, S., Morris, R.: Exor: opportunistic multi-hop routing for wireless networks. In: Proceedings of SIGCOMM, pp. 133\u2013144 (2005)","DOI":"10.1145\/1090191.1080108"},{"issue":"suppl 1","key":"373_CR9","doi-asserted-by":"crossref","first-page":"D572","DOI":"10.1093\/nar\/gkl950","volume":"35","author":"A Chatr-Aryamontri","year":"2007","unstructured":"Chatr-Aryamontri, A., Ceol, A.E.A.: Mint: the molecular interaction database. Nucleic Acids Res. 35(suppl 1), D572\u2013D574 (2007)","journal-title":"Nucleic Acids Res."},{"key":"373_CR10","unstructured":"Chui, H., Sung, W.-K., Wong, L.: Exploiting indirect neighbours and topological weight to predict protein function from protein\u2013protein interactions. Bioinformatics 22(13), 47\u201358 (2007)"},{"key":"373_CR11","doi-asserted-by":"crossref","DOI":"10.1002\/9781118033142","volume-title":"Combinatorial Optimization","author":"WJ Cook","year":"1997","unstructured":"Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A.: Combinatorial Optimization. Wiley-Interscience, London (1997)"},{"issue":"10","key":"373_CR12","doi-asserted-by":"crossref","first-page":"1367","DOI":"10.1109\/TPAMI.2004.75","volume":"38","author":"LP Cordellaand","year":"2004","unstructured":"Cordellaand, L.P., Foggia, P., Sansone, C.: A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans. Pattern Anal. Mach. Intell. 38(10), 1367\u20131372 (2004)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"373_CR13","doi-asserted-by":"crossref","unstructured":"Dalvi, N.N., Suciu, D.: Management of probabilistic data: foundations and challenges. In: Proceedings of PODS, pp. 1\u201312 (2007)","DOI":"10.1145\/1265530.1265531"},{"key":"373_CR14","doi-asserted-by":"crossref","unstructured":"Hochbaum, D. (ed.): Approximation algorithms for NP-Hard problems. PWS, Boston (1997)","DOI":"10.1145\/261342.571216"},{"key":"373_CR15","doi-asserted-by":"crossref","unstructured":"Fishman, G.S.: A monte carlo sampling plan based on product form estimation. In: Proceedings of the 23rd Conference on Winter Simulation, pp. 1012\u20131017. IEEE Computer Society (1991)","DOI":"10.1109\/WSC.1991.185717"},{"key":"373_CR16","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco (1979)"},{"key":"373_CR17","doi-asserted-by":"crossref","unstructured":"Guha, R., Kumar, R., Tomkins, A.: Propagation of trust and distrust. In: Proceedings of WWW, pp. 403\u2013412 (2004)","DOI":"10.1145\/988672.988727"},{"key":"373_CR18","unstructured":"He, H., Singh, A.K.: Closure-tree: an index structure for graph queries. In: Proceedings of ICDE, pp. 27\u201338 (2006)"},{"key":"373_CR19","doi-asserted-by":"crossref","unstructured":"Hua, M., Pei, J.: Probabilistic path queries in road networks: traffic uncertainty aware path selection. In: Proceedings of EDBT, pp. 347\u2013358 (2010)","DOI":"10.1145\/1739041.1739084"},{"issue":"3","key":"373_CR20","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/S0888-613X(96)00069-2","volume":"15","author":"C Huang","year":"1996","unstructured":"Huang, C., Darwiche, A.: Inference in belief networks: a procedural guide. Int. J. Approx. Reason. 15(3), 225\u2013263 (1996)","journal-title":"Int. J. Approx. Reason."},{"key":"373_CR21","doi-asserted-by":"crossref","unstructured":"Huang, H., Liu, C.: Query evaluation on probabilistic rdf databases. In: Proceedings of WISE, pp. 307\u2013320 (2009)","DOI":"10.1007\/978-3-642-04409-0_32"},{"key":"373_CR22","doi-asserted-by":"crossref","unstructured":"Jiang, H., Wang, H., Yu, P.S., Zhou, S.: Gstring: a novel approach for efficient search in graph databases. In: Proceedings of ICDE, pp. 566\u2013575 (2007)","DOI":"10.1109\/ICDE.2007.367902"},{"issue":"25","key":"373_CR23","doi-asserted-by":"crossref","first-page":"9404","DOI":"10.1073\/pnas.0507841103","volume":"103","author":"R Jiang","year":"2006","unstructured":"Jiang, R., Tu, Z., Chen, T., Sun, F.: Network motif identification in stochastic networks. PNAS 103(25), 9404\u20139409 (2006)","journal-title":"PNAS"},{"key":"373_CR24","doi-asserted-by":"crossref","unstructured":"Jin, R., Liu, L., Ding, B., Wang, H.: Distance-constraint reachability computation in uncertain graphs. In: Proceedings of VLDB, pp. 551\u2013562 (2011)","DOI":"10.14778\/2002938.2002941"},{"issue":"2","key":"373_CR25","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1007\/BF01074775","volume":"22","author":"AV Karzanov","year":"1986","unstructured":"Karzanov, A.V., Timofeev, E.A.: Efficient algorithm for finding all minimal edge cuts of a nonoriented graph. Cybern. Syst. Anal. 22(2), 156\u2013162 (1986)","journal-title":"Cybern. Syst. Anal."},{"issue":"1","key":"373_CR26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(00)00286-3","volume":"250","author":"I Koch","year":"2001","unstructured":"Koch, I.: Enumerating all connected maximal common subgraphs in two graphs. Theor. Comput. Sci. 250(1), 1\u201330 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"373_CR27","doi-asserted-by":"crossref","unstructured":"Kollios, G., Potamias, M., Terzi, E.: Clustering large probabilistic graphs. TKDE 25(2), 325\u2013336 (2013)","DOI":"10.1109\/TKDE.2011.243"},{"key":"373_CR28","first-page":"1108","volume":"20","author":"M Kozlov","year":"1979","unstructured":"Kozlov, M., Tarasov, S., Hacijan, L.: Polynomial solvability of convex quadratic programming. Math. Dokl. 20, 1108\u20131111 (1979)","journal-title":"Math. Dokl."},{"key":"373_CR29","doi-asserted-by":"crossref","unstructured":"Thompson, S.K.: Sampling the Third Edition. Wiley Series in Probability and Statistics. Wiley, London (2012)","DOI":"10.1002\/9781118162934"},{"key":"373_CR30","unstructured":"Chen, L., Lian, X.: Efficient query answering in probabilistic rdf graphs. In: Proceedings of SIGMOD, pp. 157\u2013168 (2011)"},{"key":"373_CR31","doi-asserted-by":"crossref","unstructured":"Liben-Nowell, D., Kleinberg, J.: The link prediction problem for social networks. In: Proceedings of CIKM, pp. 556\u2013569 (2003)","DOI":"10.1145\/956863.956972"},{"key":"373_CR32","doi-asserted-by":"crossref","unstructured":"Liu, L., Jin, R., Aggrawal, C., Shen, Y.: Reliable clustering on uncertain graphs. In: Proceedings of ICDM, pp. 459\u2013468. IEEE (2012)","DOI":"10.1109\/ICDM.2012.11"},{"key":"373_CR33","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"M Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005)"},{"key":"373_CR34","doi-asserted-by":"crossref","unstructured":"Moustafa, W.E., Kimmig, A., Deshpande, A., Getoor, L.: Subgraph pattern matching over uncertain graphs with identity linkage uncertainty. In: ICDE, pp. 904\u2013915 (2014)","DOI":"10.1109\/ICDE.2014.6816710"},{"key":"373_CR35","doi-asserted-by":"crossref","unstructured":"Potamias, M., Bonchi, F., Gionis, A., Kollios, G.: k-nearest neighbors in uncertain graphs. In: Proceedings of VLDB, pp. 997\u20131008 (2010)","DOI":"10.14778\/1920841.1920967"},{"issue":"5","key":"373_CR36","doi-asserted-by":"crossref","first-page":"1163","DOI":"10.1093\/nar\/30.5.1163","volume":"30","author":"S Rintaro","year":"2002","unstructured":"Rintaro, S., Harukazu, S., Yoshihide, H.: Interaction generality: a measurement to assess the reliability of a protein\u2013protein interaction. Nucleic Acids Res. 30(5), 1163\u20131168 (2002)","journal-title":"Nucleic Acids Res."},{"key":"373_CR37","doi-asserted-by":"crossref","unstructured":"Seshadri, P., Swami, A.N.: Generalized partial indexes. In: Proceedings of ICDE (1995)","DOI":"10.1109\/ICDE.1995.380355"},{"key":"373_CR38","doi-asserted-by":"crossref","unstructured":"Shang, H., Zhang, Y., Lin, X., Yu, J.X.: Taming verification hardness: an efficient algorithm for testing subgraph isomorphism. In: Proceedings of VLDB, pp. 364\u2013375 (2008)","DOI":"10.14778\/1453856.1453899"},{"key":"373_CR39","doi-asserted-by":"crossref","unstructured":"Shang, H., Zhu, K., Lin, X., Zhang, Y., Ichise, R.: Similarity search on supergraph containment. In: Proceedings of ICDE, pp. 637\u2013648 (2010)","DOI":"10.1109\/ICDE.2010.5447846"},{"issue":"11","key":"373_CR40","doi-asserted-by":"crossref","first-page":"1251","DOI":"10.1038\/nbt1346","volume":"25","author":"B Smith","year":"2007","unstructured":"Smith, B., Ashburner, M.E.A.: The obo foundry: coordinated evolution of ontologies to support biomedical data integration. Nat. Biotechnol. 25(11), 1251\u20131255 (2007)","journal-title":"Nat. Biotechnol."},{"key":"373_CR41","doi-asserted-by":"crossref","unstructured":"Stonebraker, M.: The case for partial indexes. SIGMOD Rec. 18(4), 4\u201311 (1989)","DOI":"10.1145\/74120.74121"},{"key":"373_CR42","doi-asserted-by":"crossref","unstructured":"Suciu, D., Dalvi, N.N.: Foundations of probabilistic answers to queries. In: Proceedings of SIGMOD, p. 963 (2005)","DOI":"10.1145\/1066157.1066303"},{"issue":"1","key":"373_CR43","first-page":"360","volume":"7","author":"S Suthram","year":"2006","unstructured":"Suthram, S., Shlomi, T., Ruppin, E., Sharan, R., Ideker, T.: A direct comparison of protein interaction confidence assignment schemes. Bioinformatics 7(1), 360 (2006)","journal-title":"Bioinformatics"},{"key":"373_CR44","doi-asserted-by":"crossref","unstructured":"Szklarczyk, D., Franceschini, A., et al.: The string database in 2011: functional interaction networks of proteins, globally integrated and scored. Nucleic Acids Res. 39(8), 561\u2013568 (2011)","DOI":"10.1093\/nar\/gkq973"},{"key":"373_CR45","doi-asserted-by":"crossref","unstructured":"Wang, X., Ding, X., Tung, A.K.H., Ying, S., Jin, H.: An efficient graph indexing method. In: Proceedings of ICDE, pp. 805\u2013916 (2012)","DOI":"10.1109\/ICDE.2012.28"},{"key":"373_CR46","doi-asserted-by":"crossref","unstructured":"Williams, D.W., Huan, J., Wang, W.: Graph database indexing using structured graph decomposition. In: Proceedings of ICDE, pp. 976\u2013985 (2007)","DOI":"10.1109\/ICDE.2007.368956"},{"key":"373_CR47","doi-asserted-by":"crossref","unstructured":"Yan, X., Han, J.: Closegraph: mining closed frequent graph patterns. In: Proceedings of KDD, pp. 286\u2013295 (2003)","DOI":"10.1145\/956755.956784"},{"key":"373_CR48","doi-asserted-by":"crossref","unstructured":"Yan, X., Yu, P.S., Han, J.: Graph indexing: a frequent structurebased approach. In: Proceedings of SIGMOD, pp. 335\u2013346 (2004)","DOI":"10.1145\/1007568.1007607"},{"key":"373_CR49","doi-asserted-by":"crossref","unstructured":"Yan, X., Yu, P.S., Han, J.: Substructure similarity search in graph databases. In: Proceedings of SIGMOD, pp. 766\u2013777 (2005)","DOI":"10.1145\/1066157.1066244"},{"key":"373_CR50","doi-asserted-by":"crossref","unstructured":"Yuan, Y., Chen, L., Wang, G.: Efficiently answering probability threshold-based shortest path queries over uncertain graphs. In: Proceedings of DASFAA, pp. 155\u2013170 (2010)","DOI":"10.1007\/978-3-642-12026-8_14"},{"key":"373_CR51","doi-asserted-by":"crossref","unstructured":"Yuan, Y., Wang, G., Chen, L., Wang, H.: Efficient subgraph similarity search on large probabilistic graph databases. In: Proceedings of VLDB, pp. 800\u2013811 (2012)","DOI":"10.14778\/2311906.2311908"},{"issue":"12","key":"373_CR52","first-page":"2767","volume":"25","author":"Y Yuan","year":"2013","unstructured":"Yuan, Y., Wang, G., Chen, L., Wang, H.: Efficient keyword search on uncertain graph data. TKDE 25(12), 2767\u20132779 (2013)","journal-title":"TKDE"},{"key":"373_CR53","doi-asserted-by":"crossref","unstructured":"Yuan, Y., Wang, G., Wang, H., Chen, L.: Efficient subgraph search over large uncertain graphs. In: Proceedings of VLDB, pp. 876\u2013886 (2011)","DOI":"10.14778\/3402707.3402726"},{"key":"373_CR54","doi-asserted-by":"crossref","unstructured":"Zeng, Z., Tung, A.K.H., Wang, J., Zhou, L., Feng, J.: Comparing stars: on approximating graph edit distance. In: Proceedings of VLDB, pp. 25\u201336 (2009)","DOI":"10.14778\/1687627.1687631"},{"key":"373_CR55","doi-asserted-by":"crossref","unstructured":"Zhang, S., Yang, J., Jin, W.: Sapper: subgraph indexing and approximate matching in large graphs. In: VLDB (2010)","DOI":"10.14778\/1920841.1920988"},{"key":"373_CR56","doi-asserted-by":"crossref","unstructured":"Zhu, G., Lin, X., Zhu, K., Zhang, W., Yu, J.X.: Treespan: efficiently computing similarity all-matching. In: SIGMOD (2012)","DOI":"10.1145\/2213836.2213896"},{"key":"373_CR57","doi-asserted-by":"crossref","unstructured":"Zou, Z., Gao, H., Li, J.: Discovering frequent subgraphs over uncertain graph databases under probabilistic semantics. In: Proceedings of KDD, pp. 633\u2013642 (2010)","DOI":"10.1145\/1835804.1835885"},{"issue":"9","key":"373_CR58","first-page":"1203","volume":"22","author":"Z Zou","year":"2010","unstructured":"Zou, Z., Gao, H., Li, J.: Mining frequent subgraph patterns from uncertain graph data. TKDE 22(9), 1203\u20131218 (2010)","journal-title":"TKDE"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-014-0373-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00778-014-0373-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-014-0373-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T23:38:42Z","timestamp":1747179522000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00778-014-0373-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,9]]},"references-count":58,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,4]]}},"alternative-id":["373"],"URL":"https:\/\/doi.org\/10.1007\/s00778-014-0373-y","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"type":"print","value":"1066-8888"},{"type":"electronic","value":"0949-877X"}],"subject":[],"published":{"date-parts":[[2014,12,9]]}}}