{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T18:17:01Z","timestamp":1790965021397,"version":"4.1.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2011,6]]},"abstract":"<jats:p>\n            Driven by the emerging network applications, querying and mining uncertain graphs has become increasingly important. In this paper, we investigate a fundamental problem concerning uncertain graphs, which we call the\n            <jats:italic>distance-constraint reachability (DCR)<\/jats:italic>\n            problem:\n            <jats:italic>Given two vertices s and t, what is the probability that the distance from s to t is less than or equal to a user-defined threshold d in the uncertain graph?<\/jats:italic>\n            Since this problem is #P-Complete, we focus on efficiently and accurately approximating DCR online. Our main results include two new estimators for the probabilistic reachability. One is a\n            <jats:italic>Horvitz-Thomson<\/jats:italic>\n            type estimator based on the unequal probabilistic sampling scheme, and the other is a novel\n            <jats:italic>recursive sampling<\/jats:italic>\n            estimator, which effectively combines a deterministic recursive computational procedure with a sampling process to boost the estimation accuracy. Both estimators can produce much smaller variance than the direct sampling estimator, which considers each trial to be either 1 or 0. We also present methods to make these estimators more computationally efficient. The comprehensive experiment evaluation on both real and synthetic datasets demonstrates the efficiency and accuracy of our new estimators.\n          <\/jats:p>","DOI":"10.14778\/2002938.2002941","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"551-562","source":"Crossref","is-referenced-by-count":123,"title":["Distance-constraint reachability computation in uncertain graphs"],"prefix":"10.14778","volume":"4","author":[{"given":"Ruoming","family":"Jin","sequence":"first","affiliation":[{"name":"Kent State University, Kent, OH"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lin","family":"Liu","sequence":"additional","affiliation":[{"name":"UIUC Urbana, IL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bolin","family":"Ding","sequence":"additional","affiliation":[{"name":"UIUC Urbana, IL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haixun","family":"Wang","sequence":"additional","affiliation":[{"name":"Microsoft Research Asia, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1513922"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TR.1986.4335422"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/371931.371977"},{"key":"e_1_2_1_5_1","volume-title":"The Combinatorics of Network Reliability","author":"Colbourn C. J.","year":"1987","unstructured":"C. J. Colbourn . The Combinatorics of Network Reliability . Oxford University Press, Inc. , 1987 . C. J. Colbourn. The Combinatorics of Network Reliability. Oxford University Press, Inc., 1987."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TR.1986.4335388"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739084"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559930"},{"key":"e_1_2_1_9_1","volume-title":"USA","author":"Karp R. M.","year":"1983","unstructured":"R. M. Karp and M. G. Luby . A new monte-carlo method for estimating the failure probability of an n-component system. Technical report, Berkeley, CA , USA , 1983 . R. M. Karp and M. G. Luby. A new monte-carlo method for estimating the failure probability of an n-component system. Technical report, Berkeley, CA, USA, 1983."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TR.1980.5220749"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875584"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1415804.1415865"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920967"},{"key":"e_1_2_1_14_1","first-page":"275","volume-title":"Network reliability evaluation","author":"Rubino G.","year":"1999","unstructured":"G. Rubino . Network reliability evaluation , pages 275 -- 302 . Gordon and Breach Science Publishers, Inc. , Newark, NJ, USA , 1999 . G. Rubino. Network reliability evaluation, pages 275--302. Gordon and Breach Science Publishers, Inc., Newark, NJ, USA, 1999."},{"key":"e_1_2_1_15_1","volume-title":"Pearson Education","author":"Russell S. J.","year":"2003","unstructured":"S. J. Russell and P. Norvig . Artificial Intelligence: A Modern Approach . Pearson Education , 2003 . S. J. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Pearson Education, 2003."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214057"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1397735.1397737"},{"key":"e_1_2_1_18_1","volume-title":"Sampling","author":"Thompson S.","year":"2002","unstructured":"S. Thompson . Sampling , Second Edition. New York : Wiley ., 2002 . S. Thompson. Sampling, Second Edition. New York: Wiley., 2002."},{"key":"e_1_2_1_19_1","unstructured":"http:\/\/mips.helmholtz-muenchen.de\/genre\/proj\/mpact\/.  http:\/\/mips.helmholtz-muenchen.de\/genre\/proj\/mpact\/."},{"key":"e_1_2_1_20_1","unstructured":"http:\/\/thebiogrid.org\/.  http:\/\/thebiogrid.org\/."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"issue":"1","key":"e_1_2_1_22_1","first-page":"276","article-title":"Grail: Scalable reachability index for large graphs","volume":"3","author":"Yildirim H.","year":"2010","unstructured":"H. Yildirim , V. Chaoji , and M. J. Zaki . Grail: Scalable reachability index for large graphs . PVLDB , 3 ( 1 ): 276 -- 284 , 2010 . H. Yildirim, V. Chaoji, and M. J. Zaki. Grail: Scalable reachability index for large graphs. PVLDB, 3(1):276--284, 2010.","journal-title":"PVLDB"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12026-8_14"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835885"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447891"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2002938.2002941","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:47:04Z","timestamp":1672224424000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2002938.2002941"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6]]},"references-count":25,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2011,6]]}},"alternative-id":["10.14778\/2002938.2002941"],"URL":"https:\/\/doi.org\/10.14778\/2002938.2002941","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2011,6]]}}}