{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T08:23:53Z","timestamp":1760171033780,"version":"3.41.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,5,10]],"date-time":"2017-05-10T00:00:00Z","timestamp":1494374400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee","doi-asserted-by":"publisher","award":["17205115"],"award-info":[{"award-number":["17205115"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003803","name":"University of Hong Kong","doi-asserted-by":"publisher","award":["102009508"],"award-info":[{"award-number":["102009508"]}],"id":[{"id":"10.13039\/501100003803","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2017,6,30]]},"abstract":"<jats:p>\n            Information in many applications, such as mobile wireless systems, social networks, and road networks, is captured by graphs. In many cases, such information is uncertain. We study the problem of querying a probabilistic graph, in which vertices are connected to each other probabilistically. In particular, we examine \u201csource-to-target\u201d queries (ST-queries), such as computing the shortest path between two vertices. The major difference with the deterministic setting is that query answers are enriched with probabilistic annotations. Evaluating ST-queries over probabilistic graphs is #P-hard, as it requires examining an exponential number of \u201cpossible worlds\u201d\u2014database instances generated from the probabilistic graph. Existing solutions to the ST-query problem, which sample possible worlds, have two downsides: (i) a possible world can be very large and (ii) many samples are needed for reasonable accuracy. To tackle these issues, we study the\n            <jats:italic>ProbTree<\/jats:italic>\n            , a data structure that stores a succinct, or\n            <jats:italic>indexed<\/jats:italic>\n            , version of the possible worlds of the graph. Existing ST-query solutions are executed on top of this structure, with the number of samples and sizes of the possible worlds reduced. We examine lossless and lossy methods for generating the ProbTree, which reflect the tradeoff between the accuracy and efficiency of query evaluation. We analyze the correctness and complexity of these approaches. Our extensive experiments on real datasets show that the ProbTree is fast to generate and small in size. It also enhances the accuracy and efficiency of existing ST-query algorithms significantly.\n          <\/jats:p>","DOI":"10.1145\/3044713","type":"journal-article","created":{"date-parts":[[2017,5,10]],"date-time":"2017-05-10T18:08:53Z","timestamp":1494439733000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["An Indexing Framework for Queries on Probabilistic Graphs"],"prefix":"10.1145","volume":"42","author":[{"given":"Silviu","family":"Maniu","sequence":"first","affiliation":[{"name":"Universit\u00e9 Paris-Sud, Universit\u00e9 Paris-Saclay, Orsay, France"}]},{"given":"Reynold","family":"Cheng","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Hong Kong"}]},{"given":"Pierre","family":"Senellart","sequence":"additional","affiliation":[{"name":"\u00c9cole normale sup\u00e9rieure, PSL Research University and Inria Paris, France; Inria Paris"}]}],"member":"320","published-online":{"date-parts":[[2017,5,10]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Tom\u00e1s De La Barra, and Beatnz P\u00e9rez","author":"A\u00f1ez Juancarlo","year":"1996","unstructured":"Juancarlo A\u00f1ez , Tom\u00e1s De La Barra, and Beatnz P\u00e9rez . 1996 . Dual graph representation of transport networks. Transport. Res. B: Method . 30, 3 (1996), 8 pages. Juancarlo A\u00f1ez, Tom\u00e1s De La Barra, and Beatnz P\u00e9rez. 1996. Dual graph representation of transport networks. Transport. Res. B: Method. 30, 3 (1996), 8 pages."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043652.2043658"},{"key":"e_1_2_1_3_1","volume-title":"Werneck","author":"Abraham Ittai","year":"2010","unstructured":"Ittai Abraham , Amos Fiat , Andrew V. Goldberg , and Renato F . Werneck . 2010 . Highway dimension, shortest paths, and provably efficient algorithms. In SODA. Ittai Abraham, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck. 2010. Highway dimension, shortest paths, and provably efficient algorithms. In SODA."},{"key":"e_1_2_1_4_1","volume-title":"Managing uncertainty in social networks","author":"Adar Eytan","year":"2007","unstructured":"Eytan Adar and Christopher Re. 2007. Managing uncertainty in social networks . IEEE Data Eng. Bull . 30, 2 ( 2007 ), 8 pages. Eytan Adar and Christopher Re. 2007. Managing uncertainty in social networks. IEEE Data Eng. Bull. 30, 2 (2007), 8 pages."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247614"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_5"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902301"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90031-0"},{"key":"e_1_2_1_10_1","volume-title":"Dol\u00e9ans","author":"Ash Robert B.","year":"1999","unstructured":"Robert B. Ash and Catherine A . Dol\u00e9ans . 1999 . Probability 8 Measure Theory (2nd ed.). Academic Press . Robert B. Ash and Catherine A. Dol\u00e9ans. 1999. Probability 8 Measure Theory (2nd ed.). Academic Press."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1101\/gr.2203804"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TR.1986.4335422"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2559905"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557049"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0004-3"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Giuseppe Di Battista and Roberto Tamassia. 1990. On-line graph algorithms with SPQR-trees. In ICALP.   Giuseppe Di Battista and Roberto Tamassia. 1990. On-line graph algorithms with SPQR-trees. In ICALP.","DOI":"10.1007\/BFb0032061"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502525"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213855"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TR.1986.4335388"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2007.201"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Carsten Gutwenger and Petra Mutzel. 2000. A linear time implementation of SPQR-trees. In Graph Drawing.   Carsten Gutwenger and Petra Mutzel. 2000. A linear time implementation of SPQR-trees. In Graph Drawing.","DOI":"10.1007\/3-540-44541-2_8"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1099554.1099708"},{"key":"e_1_2_1_26_1","volume-title":"Hopcroft and Robert Endre Tarjan","author":"John","year":"1973","unstructured":"John E. Hopcroft and Robert Endre Tarjan . 1973 a. Dividing a graph into triconnected components. SIAM J. Comput . 2, 3 (1973), 24 pages. John E. Hopcroft and Robert Endre Tarjan. 1973a. Dividing a graph into triconnected components. SIAM J. Comput. 2, 3 (1973), 24 pages."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/362248.362272"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739084"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002941"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807241"},{"key":"e_1_2_1_31_1","unstructured":"Arijit Khan Francesco Bonchi Aristides Gionis and Francesco Gullo. 2014. Fast reliability search in uncertain graphs. In EDBT.  Arijit Khan Francesco Bonchi Aristides Gionis and Francesco Gullo. 2014. Fast reliability search in uncertain graphs. In EDBT."},{"key":"e_1_2_1_32_1","unstructured":"Michihiro Kuramochi and George Karypis. 2001. Frequent subgraph discovery. In ICDM.   Michihiro Kuramochi and George Karypis. 2001. Frequent subgraph discovery. In ICDM."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.v58:7"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1996413.1996417"},{"key":"e_1_2_1_35_1","volume-title":"Proc. BUDA.","author":"Maniu Silviu","year":"2014","unstructured":"Silviu Maniu , Reynold Cheng , and Pierre Senellart . 2014 . ProbTree: A query-efficient representation of probabilistic graphs . In Proc. BUDA. Silviu Maniu, Reynold Cheng, and Pierre Senellart. 2014. ProbTree: A query-efficient representation of probabilistic graphs. In Proc. BUDA."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.64.026118"},{"volume-title":"Computational Complexity","author":"Papadimitriou Christos H.","key":"e_1_2_1_37_1","unstructured":"Christos H. Papadimitriou . 1994. Computational Complexity . Addison Wesley Pub . Co., Reading, MA. Christos H. Papadimitriou. 1994. Computational Complexity. Addison Wesley Pub. Co., Reading, MA."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1951365.1951408"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920967"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/11549345_64"},{"key":"e_1_2_1_42_1","unstructured":"Prithviraj Sen and Amol Deshpande. 2007. Representing and querying correlated tuples in probabilistic databases. In ICDE.  Prithviraj Sen and Amol Deshpande. 2007. Representing and querying correlated tuples in probabilistic databases. In ICDE."},{"key":"e_1_2_1_43_1","volume-title":"FERRARI: Flexible and efficient reachability range assignment for graph indexing. In ICDE.","author":"Seufert Stephan","year":"2013","unstructured":"Stephan Seufert , Avishek Anand , Srikanta Bedathur , and Gerhard Weikum . 2013 . FERRARI: Flexible and efficient reachability range assignment for graph indexing. In ICDE. Stephan Seufert, Avishek Anand, Srikanta Bedathur, and Gerhard Weikum. 2013. FERRARI: Flexible and efficient reachability range assignment for graph indexing. In ICDE."},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Asma Souihli and Pierre Senellart. 2013. Optimizing approximations of DNF query lineage in probabilistic XML. In ICDE.  Asma Souihli and Pierre Senellart. 2013. Optimizing approximations of DNF query lineage in probabilistic XML. In ICDE.","DOI":"10.1109\/ICDE.2013.6544869"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.3138\/9781487584863"},{"key":"e_1_2_1_46_1","series-title":"SIAM J. Comput. 8, 3","volume-title":"The complexity of enumeration and reliability problems","author":"Valiant Leslie G.","year":"1979","unstructured":"Leslie G. Valiant . 1979. The complexity of enumeration and reliability problems . SIAM J. Comput. 8, 3 ( 1979 ), 12 pages. Leslie G. Valiant. 1979. The complexity of enumeration and reliability problems. SIAM J. Comput. 8, 3 (1979), 12 pages."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807181"},{"key":"e_1_2_1_48_1","first-page":"11","volume-title":"Proc. VLDB 4","author":"Yuan Ye","year":"2011","unstructured":"Ye Yuan , Guoren Wang , Haixun Wang , and Lei Chen . 2011 . Efficient subgraph search over large uncertain graphs . Proc. VLDB 4 , 11 (2011), 12 pages. Ye Yuan, Guoren Wang, Haixun Wang, and Lei Chen. 2011. Efficient subgraph search over large uncertain graphs. Proc. VLDB 4, 11 (2011), 12 pages."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835885"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3044713","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3044713","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:07:27Z","timestamp":1750273647000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3044713"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,10]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,6,30]]}},"alternative-id":["10.1145\/3044713"],"URL":"https:\/\/doi.org\/10.1145\/3044713","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2017,5,10]]},"assertion":[{"value":"2015-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-05-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}