{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T11:58:29Z","timestamp":1742385509024,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642201486"},{"type":"electronic","value":"9783642201493"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-20149-3_32","type":"book-chapter","created":{"date-parts":[[2011,4,8]],"date-time":"2011-04-08T22:41:56Z","timestamp":1302302516000},"page":"434-449","source":"Crossref","is-referenced-by-count":7,"title":["BMC: An Efficient Method to Evaluate Probabilistic Reachability Queries"],"prefix":"10.1007","author":[{"given":"Ke","family":"Zhu","sequence":"first","affiliation":[]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Gaoping","family":"Zhu","sequence":"additional","affiliation":[]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"32_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, R., Borgida, A., Jagadish, H.V.: Efficient management of transitive relationships in large data and knowledge bases. In: SIGMOD, pp. 253\u2013262 (1989)","DOI":"10.1145\/66926.66950"},{"key":"32_CR2","unstructured":"Chen, L., Gupta, A., Kurul, M.E.: Stack-based algorithms for pattern matching on dags. In: VLDB, pp. 493\u2013504 (2005)"},{"key":"32_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"961","DOI":"10.1007\/11687238_56","volume-title":"Advances in Database Technology - EDBT 2006","author":"J. Cheng","year":"2006","unstructured":"Cheng, J., Yu, J.X., Lin, X., Wang, H., Yu, P.S.: Fast computation of reachability labeling for large graphs. In: Ioannidis, Y., Scholl, M.H., Schmidt, J.W., Matthes, F., Hatzopoulos, M., B\u00f6hm, K., Kemper, A., Grust, T., B\u00f6hm, C. (eds.) EDBT 2006. LNCS, vol.\u00a03896, pp. 961\u2013979. Springer, Heidelberg (2006)"},{"key":"32_CR4","unstructured":"Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 937\u2013946 (2002)"},{"issue":"4","key":"32_CR5","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1145\/99935.99944","volume":"15","author":"H.V. Jagadish","year":"1990","unstructured":"Jagadish, H.V.: A compression technique to materialize transitive closure. ACM Trans. Database Syst.\u00a015(4), 558\u2013598 (1990)","journal-title":"ACM Trans. Database Syst."},{"key":"32_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/978-3-540-24741-8_15","volume-title":"Advances in Database Technology - EDBT 2004","author":"R. Schenkel","year":"2004","unstructured":"Schenkel, R., Theobald, A., Weikum, G.: HOPI: An efficient connection index for complex XML document collections. In: Hwang, J., Christodoulakis, S., Plexousakis, D., Christophides, V., Koubarakis, M., B\u00f6hm, K. (eds.) EDBT 2004. LNCS, vol.\u00a02992, pp. 237\u2013255. Springer, Heidelberg (2004)"},{"issue":"1-3","key":"32_CR7","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/0304-3975(88)90032-1","volume":"58","author":"K. Simon","year":"1988","unstructured":"Simon, K.: An improved algorithm for transitive closure on acyclic digraphs. Theor. Comput. Sci.\u00a058(1-3), 325\u2013346 (1988)","journal-title":"Theor. Comput. Sci."},{"key":"32_CR8","doi-asserted-by":"crossref","unstructured":"Tribl, S., Leser, U.: Fast and practical indexing and querying of very large graphs. In: SIGMOD 2007: Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data, pp. 845\u2013846 (2007)","DOI":"10.1145\/1247480.1247573"},{"key":"32_CR9","doi-asserted-by":"crossref","unstructured":"Wang, H., He, H., Yang, J., Yu, P.S., Yu, J.X.: Dual labeling: Answering graph reachability queries in constant time. In: ICDE, p. 75 (2006)","DOI":"10.1109\/ICDE.2006.53"},{"key":"32_CR10","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Compt.\u00a08, 410\u2013421 (1979)","journal-title":"SIAM J. Compt."},{"key":"32_CR11","doi-asserted-by":"crossref","unstructured":"Jiang, B., Pei, J., Lin, X., Cheung, D.W., Han, J.: Mining preferences from superior and inferior examples. In: KDD, pp. 390\u2013398 (2008)","DOI":"10.1145\/1401890.1401940"},{"issue":"3","key":"32_CR12","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1287\/opre.32.3.516","volume":"32","author":"J.S. Provan","year":"1984","unstructured":"Provan, J.S., Ball, M.O.: Computing Network Reliability in Time Polynomial in the Number of Cuts. Operations Research, Reliability and Maintainability\u00a032(3), 516\u2013526 (1984)","journal-title":"Operations Research, Reliability and Maintainability"},{"issue":"5","key":"32_CR13","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1057\/jors.1992.79","volume":"43","author":"D.R. Shier","year":"1992","unstructured":"Shier, D.R., Liu, N.: Bounding the Reliability of Networks. The Journal of the Operational Research Society, Mathematical Programming in Honour of Ailsa Land\u00a043(5), 539\u2013548 (1992)","journal-title":"The Journal of the Operational Research Society, Mathematical Programming in Honour of Ailsa Land"},{"key":"32_CR14","doi-asserted-by":"crossref","unstructured":"Jin, R., Xiang, Y., Ruan, N., Wang, H.: Efficiently Answering Reachability Queries on Very Large Directed Graphs. In: SIGMOD (2008)","DOI":"10.1145\/1376616.1376677"},{"key":"32_CR15","first-page":"191","volume":"29","author":"M.C. Easton","year":"1980","unstructured":"Easton, M.C., Wong, C.K.: Sequential Destruction Method for Monte Carlo Evaluation of System Reliability. IEEE, Reliability\u00a029, 191\u2013209 (1980)","journal-title":"IEEE, Reliability"},{"issue":"4","key":"32_CR16","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1287\/opre.34.4.581","volume":"34","author":"G.S. Fishman","year":"1986","unstructured":"Fishman, G.S.: A Monte Carlo Sampling Plan for Estimating Network Reliability. Operational Research\u00a034(4), 581\u2013594 (1986)","journal-title":"Operational Research"},{"key":"32_CR17","volume-title":"Computer Science Division","author":"R. Karp","year":"1983","unstructured":"Karp, R., Luby, M.G.: A New Monte Carlo Method for Estimating the Failure Probability of An N-component System. In: Computer Science Division. University of Carlifornia, Berkley (1983)"},{"key":"32_CR18","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/BF02883985","volume":"10","author":"M. Okamoto","year":"1958","unstructured":"Okamoto, M.: Some Inequalities Relating To the Partial Sum of Binomial Probabilities. Annals Inst. Statistical Mathematics\u00a010, 29\u201335 (1958)","journal-title":"Annals Inst. Statistical Mathematics"},{"key":"32_CR19","doi-asserted-by":"crossref","unstructured":"Fishman, G.S.: A Comparison of Four Monte Carlo Methods for Estimating the Probability of s-t Connectedness. IEEE, Trans. Reliability\u00a035(2) (1986)","DOI":"10.1109\/TR.1986.4335388"},{"issue":"3","key":"32_CR20","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/s00778-005-0177-1","volume":"16","author":"E.P. Chan","year":"2007","unstructured":"Chan, E.P., Lim, H.: Optimization and Evaluation of Shortest Path Queries. VLDB Journal\u00a016(3), 343\u2013369 (2007)","journal-title":"VLDB Journal"},{"key":"32_CR21","doi-asserted-by":"crossref","unstructured":"Meester, R.: A Natural Introduction to Probability Theory (2004)","DOI":"10.1007\/978-3-0348-7786-2"},{"issue":"2","key":"32_CR22","first-page":"23","volume":"30","author":"E. Adar","year":"2007","unstructured":"Adar, E., R\u00e9, C.: Managing Uncertainty in Social Networks. Data Engineering Bulletin\u00a030(2), 23\u201331 (2007)","journal-title":"Data Engineering Bulletin"},{"key":"32_CR23","doi-asserted-by":"crossref","unstructured":"Zou, Z., Gao, H., Li, J.: Discovering Frequent Subgraphs over Uncertain Graph Databases under Probablistic Semantics. In: KDD (2010)","DOI":"10.1145\/1835804.1835885"},{"issue":"9","key":"32_CR24","first-page":"1203","volume":"22","author":"Z. Zou","year":"2010","unstructured":"Zou, Z., Li, J., Gao, H., Zhang, S.: Mining Frequent Subgraph Patterns from Uncertain Graph Data. TKDE\u00a022(9), 1203\u20131218 (2010)","journal-title":"TKDE"},{"key":"32_CR25","doi-asserted-by":"crossref","unstructured":"Zou, Z., Gao, H., Li, J.: Discovering Frequent Subgraphs over Uncertain Graph Databases under Probabilistic Semantics. In: SIGKDD, pp. 633\u2013642 (2010)","DOI":"10.1145\/1835804.1835885"},{"key":"32_CR26","doi-asserted-by":"crossref","unstructured":"Zou, Z., Li, J., Gao, H., Zhang, S.: Finding Top-k Maximal Cliques in an Uncertain Graph. In: ICDE, pp. 649\u2013652 (2010)","DOI":"10.1109\/ICDE.2010.5447891"}],"container-title":["Lecture Notes in Computer Science","Database Systems for Advanced Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-20149-3_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T23:57:18Z","timestamp":1741132638000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-20149-3_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642201486","9783642201493"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-20149-3_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}