{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:16:46Z","timestamp":1763457406993,"version":"3.40.4"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319058122"},{"type":"electronic","value":"9783319058139"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-05813-9_9","type":"book-chapter","created":{"date-parts":[[2014,4,16]],"date-time":"2014-04-16T11:57:50Z","timestamp":1397649470000},"page":"124-140","source":"Crossref","is-referenced-by-count":10,"title":["Efficient Sampling Methods for Shortest Path Query over Uncertain Graphs"],"prefix":"10.1007","author":[{"given":"Yurong","family":"Cheng","sequence":"first","affiliation":[]},{"given":"Ye","family":"Yuan","sequence":"additional","affiliation":[]},{"given":"Guoren","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Baiyou","family":"Qiao","sequence":"additional","affiliation":[]},{"given":"Zhiqiong","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"9_CR1","first-page":"15","volume":"30","author":"E. Adar","year":"2007","unstructured":"Adar, E., R\u00e9, C.: Managing uncertainty in social networks. IEEE Data Eng. Bull.\u00a030(2), 15\u201322 (2007)","journal-title":"IEEE Data Eng. Bull."},{"issue":"6","key":"9_CR2","doi-asserted-by":"publisher","first-page":"1170","DOI":"10.1101\/gr.2203804","volume":"14","author":"S. Asthana","year":"2004","unstructured":"Asthana, S., King, O.D., Gibbons, F.D., Roth, F.P.: Predicting protein complex membership using probabilistic network reliability. Genome Research\u00a014(6), 1170\u20131175 (2004)","journal-title":"Genome Research"},{"key":"9_CR3","unstructured":"Bast, H., Funke, S., Matijevic, D.: Transitultrafast shortest-path queries with linear-time preprocessing. In: 9th DIMACS Implementation Challenge [1] (2006)"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Cheng, J., Ke, Y., Chu, S., Cheng, C.: Efficient processing of distance queries in large graphs: A vertex cover approach. In: SIGMOD, pp. 457\u2013468. ACM (2012)","DOI":"10.1145\/2213836.2213888"},{"issue":"5","key":"9_CR5","doi-asserted-by":"publisher","first-page":"1338","DOI":"10.1137\/S0097539702403098","volume":"32","author":"E. Cohen","year":"2003","unstructured":"Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. SIAM Journal on Comp\u00a032(5), 1338\u20131355 (2003)","journal-title":"SIAM Journal on Comp"},{"key":"9_CR6","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"},{"issue":"11","key":"9_CR7","doi-asserted-by":"publisher","first-page":"3324","DOI":"10.1016\/j.cor.2005.03.027","volume":"33","author":"L. Fu","year":"2006","unstructured":"Fu, L., Sun, D., Rilett, L.R.: Heuristic shortest path algorithms for transportation applications: State of the art. Computers & Operations Research\u00a033(11), 3324\u20133343 (2006)","journal-title":"Computers & Operations Research"},{"issue":"4","key":"9_CR8","first-page":"358","volume":"5","author":"J. Gao","year":"2011","unstructured":"Gao, J., Jin, R., Zhou, J., Yu, J.X., Jiang, X., Wang, T.: Relational approach for shortest path discovery over large graphs. PVLDB\u00a05(4), 358\u2013369 (2011)","journal-title":"PVLDB"},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"Gubichev, A., Bedathur, S., Seufert, S., Weikum, G.: Fast and accurate estimation of shortest paths in large graphs. In: CIKM, pp. 499\u2013508. ACM (2010)","DOI":"10.1145\/1871437.1871503"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Hua, M., Pei, J.: Probabilistic path queries in road networks: Traffic uncertainty aware path selection. In: EDBT, pp. 347\u2013358. ACM (2010)","DOI":"10.1145\/1739041.1739084"},{"issue":"9","key":"9_CR11","first-page":"551","volume":"4","author":"R. Jin","year":"2011","unstructured":"Jin, R., Liu, L., Ding, B., Wang, H.: Distance-constraint reachability computation in uncertain graphs. PVLDB\u00a04(9), 551\u2013562 (2011)","journal-title":"PVLDB"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"Jin, R., Ruan, N., Xiang, Y., Lee, V.: A highway-centric labeling approach for answering distance queries on large sparse graphs. In: SIGMOD, pp. 445\u2013456. ACM (2012)","DOI":"10.1145\/2213836.2213887"},{"issue":"3","key":"9_CR13","first-page":"409","volume":"10","author":"N. Jing","year":"1998","unstructured":"Jing, N., Huang, Y.W., Rundensteiner, E.A.: Hierarchical encoded path views for path query processing: An optimal model and its performance evaluation. TKDE\u00a010(3), 409\u2013432 (1998)","journal-title":"TKDE"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Thompson, S.K.: Sampling the Third Edition. Wiley Series In Probability And Statistics. Wiley (2012)","DOI":"10.1002\/9781118162934"},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"Lian, X., Chen, L.: Efficient query answering in probabilistic rdf graphs. In: SIGMOD, pp. 157\u2013168. ACM (2011)","DOI":"10.1145\/1989323.1989341"},{"issue":"9","key":"9_CR16","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1145\/358172.358406","volume":"26","author":"R.P. Loui","year":"1983","unstructured":"Loui, R.P.: Optimal paths in graphs with stochastic or multidimensional weights. CACM\u00a026(9), 670\u2013676 (1983)","journal-title":"CACM"},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"Nierman, A., Jagadish, H.: Protdb: Probabilistic data in xml. In: Proceedings of the 28th International Conference on Very Large Data Bases, pp. 646\u2013657. VLDB Endowment (2002)","DOI":"10.1016\/B978-155860869-6\/50063-9"},{"issue":"2","key":"9_CR18","first-page":"69","volume":"4","author":"M. Rice","year":"2010","unstructured":"Rice, M., Tsotras, V.J.: Graph indexing of road networks for shortest path queries with label restrictions. PVLDB\u00a04(2), 69\u201380 (2010)","journal-title":"PVLDB"},{"key":"9_CR19","doi-asserted-by":"crossref","unstructured":"Samet, H., Sankaranarayanan, J., Alborzi, H.: Scalable network distance browsing in spatial databases. In: SIGMOD, pp. 43\u201354. ACM (2008)","DOI":"10.1145\/1376616.1376623"},{"issue":"1","key":"9_CR20","first-page":"1210","volume":"2","author":"J. Sankaranarayanan","year":"2009","unstructured":"Sankaranarayanan, J., Samet, H., Alborzi, H.: Path oracles for spatial networks. PVLDB\u00a02(1), 1210\u20131221 (2009)","journal-title":"PVLDB"},{"issue":"11","key":"9_CR21","first-page":"1650","volume":"5","author":"Y. Tong","year":"2012","unstructured":"Tong, Y., Chen, L., Cheng, Y., Yu, P.S.: Mining frequent itemsets over uncertain databases. PVLDB\u00a05(11), 1650\u20131661 (2012)","journal-title":"PVLDB"},{"key":"9_CR22","doi-asserted-by":"crossref","unstructured":"Tong, Y., Chen, L., Ding, B.: Discovering threshold-based frequent closed itemsets over probabilistic data. In: ICDE, pp. 270\u2013281. IEEE (2012)","DOI":"10.1109\/ICDE.2012.51"},{"issue":"3","key":"9_CR23","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 Journal on Comp.\u00a08(3), 410\u2013421 (1979)","journal-title":"SIAM Journal on Comp."},{"key":"9_CR24","doi-asserted-by":"crossref","unstructured":"Wei, F.: Tedi: Efficient shortest path query answering on graphs. In: Proceedings of SIGMOD, pp. 99\u2013110. ACM (2010)","DOI":"10.1145\/1807167.1807181"},{"issue":"5","key":"9_CR25","first-page":"406","volume":"5","author":"L. Wu","year":"2012","unstructured":"Wu, L., Xiao, X., Deng, D., Cong, G., Zhu, A.D., Zhou, S.: Shortest path and distance queries on road networks: an experimental evaluation. PVLDB\u00a05(5), 406\u2013417 (2012)","journal-title":"PVLDB"},{"key":"9_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/978-3-642-12026-8_14","volume-title":"Database Systems for Advanced Applications","author":"Y. Yuan","year":"2010","unstructured":"Yuan, Y., Chen, L., Wang, G.: Efficiently answering probability threshold-based shortest path queries over uncertain graphs. In: Kitagawa, H., Ishikawa, Y., Li, Q., Watanabe, C. (eds.) DASFAA 2010. LNCS, vol.\u00a05981, pp. 155\u2013170. Springer, Heidelberg (2010)"},{"issue":"12","key":"9_CR27","doi-asserted-by":"publisher","first-page":"2767","DOI":"10.1109\/TKDE.2012.222","volume":"25","author":"Y. Yuan","year":"2013","unstructured":"Yuan, Y., Wang, G., Chen, L., Wang, H.: Efficient keyword search on uncertain graph data. IEEE Transactions on Knowledge and Data Engineering\u00a025(12), 2767\u20132779 (2013)","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"9_CR28","doi-asserted-by":"crossref","unstructured":"Yuan, Y., Wang, G., Wang, H., Chen, L.: Efficient subgraph search over large uncertain graphs. In: International Conference on Very Large Data Bases (2011)","DOI":"10.14778\/3402707.3402726"},{"key":"9_CR29","doi-asserted-by":"crossref","unstructured":"Zhang, Z., Yu, J.X., Qin, L., Chang, L., Lin, X.: I\/o efficient: Computing sccs in massive graphs. In: Proceedings of the 2013 International Conference on Management of Data, pp. 181\u2013192. ACM (2013)","DOI":"10.1145\/2463676.2463703"},{"key":"9_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1007\/978-3-642-24434-6_6","volume-title":"Web Information System Engineering \u2013 WISE 2011","author":"L. Zou","year":"2011","unstructured":"Zou, L., Peng, P., Zhao, D.: Top-k possible shortest path query over a large uncertain graph. In: Bouguettaya, A., Hauswirth, M., Liu, L. (eds.) WISE 2011. LNCS, vol.\u00a06997, pp. 72\u201386. Springer, Heidelberg (2011)"}],"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-319-05813-9_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T11:46:19Z","timestamp":1746186379000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-05813-9_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319058122","9783319058139"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-05813-9_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}