{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T19:41:14Z","timestamp":1725478874698},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>\n            Multi-relation graphs intuitively capture the heterogeneous correlations among real-world entities by allowing multiple types of relationships to be represented as entity-connecting edges, i.e., two entities could be correlated with more than one type of relationship. This is important in various applications such as social network analysis, ecology, and bio-informatics. Existing studies on these graphs usually consider an edge label constraint perspective, where each edge contains only one label and each edge is considered independently. For example, there are lines of research focusing on reachability between two vertices under a set of edge label constraints, or finding paths whose consecutive edge labels satisfy a user-specified logical expression. This is too restricted in real graphs, and in this work, we define a generic correlation constraint on multi-relation graphs from the perspective of vertex correlations, where a correlation can be defined recursively. Specifically, we formalize and investigate the shortest path problem over large multi-relation graphs in the presence of both necessity and denial constraints, which have various real applications. We show that it is nontrivial to apply conventional graph traversal algorithms (e.g., BFS or DFS) to address the challenge. To effectively reduce the search space, we propose a\n            <jats:italic>Hybrid Relation Encoding<\/jats:italic>\n            method, a.k.a. HyRE, to encode both topological and relation information in a compact way. We conduct extensive experiments over large real-world graphs to validate the effectiveness and efficiency of the proposed solution.\n          <\/jats:p>","DOI":"10.14778\/3303753.3303756","type":"journal-article","created":{"date-parts":[[2019,2,27]],"date-time":"2019-02-27T14:57:56Z","timestamp":1551279476000},"page":"488-501","source":"Crossref","is-referenced-by-count":10,"title":["Correlation constraint shortest path over large multi-relation graphs"],"prefix":"10.14778","volume":"12","author":[{"given":"Xiaofei","family":"Zhang","sequence":"first","affiliation":[{"name":"University of Memphis"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. Tamer","family":"\u00d6zsu","sequence":"additional","affiliation":[{"name":"University of Waterloo"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_4"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_3_1","volume-title":"Synthesis Lectures on Data Management","author":"Angela Bonifati H. V. N. Y.","year":"2018"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 12th Alberto Mendelzon International Workshop on Foundations of Data Management","author":"Angles R.","year":"2018"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the Hadoop Summit. Santa Clara","author":"Avery C.","year":"2011"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-7-55"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807089"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/647912.740806"},{"key":"e_1_2_1_9_1","volume-title":"Proc. 9th workshop on algorithm eng. and experiments. In Proceedings of the Nine Workshop on Algorithm Engineering and Experiments","author":"Bast H.","year":"2007"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1155\/2013\/702694"},{"key":"e_1_2_1_11_1","first-page":"547","volume-title":"Proc. 17th Int. Conf. on Extending Database Technology","author":"Bonchi F.","year":"2014"},{"key":"e_1_2_1_12_1","first-page":"176","volume-title":"KR","author":"Calvanese D.","year":"2000"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"A. Cardillo J. G\u00f3mez-Garde\u00f1es M. Zanin M. Romance D. Papo F. del Pozo and S. Boccaletti. Emergence of network features from multiplexity. CoRR abs\/1212.2153 2012.  A. Cardillo J. G\u00f3mez-Garde\u00f1es M. Zanin M. Romance D. Papo F. del Pozo and S. Boccaletti. Emergence of network features from multiplexity. CoRR abs\/1212.2153 2012.","DOI":"10.1038\/srep01344"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492517.2492537"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699886"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-012-1312-y"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275503"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2133803.2133805"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1788888.1788912"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1871437.1871503"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882933"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875499"},{"key":"e_1_2_1_25_1","unstructured":"Janusgraph: Distributed graph database. http:\/\/janusgraph.org\/ 2018.  Janusgraph: Distributed graph database. http:\/\/janusgraph.org\/ 2018."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87881-0_10"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2013.50"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.129"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2531667"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCYB.2016.2595620"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33765-9_59"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979122370X"},{"key":"e_1_2_1_34_1","unstructured":"Microsoft academic graph. https:\/\/www.openacademic.ai\/oag\/ 2015.  Microsoft academic graph. https:\/\/www.openacademic.ai\/oag\/ 2015."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544813"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/1921071.1921074"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376623"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902291"},{"key":"e_1_2_1_39_1","first-page":"149","volume-title":"Proc. 18th Int. Conf. on Extending Database Technology","author":"Selmer P.","year":"2015"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2037676.2037679"},{"issue":"3","key":"e_1_2_1_41_1","first-page":"486","article-title":"Parasite spreading in spatial ecological multiplex networks","volume":"5","author":"Stella M.","year":"2017","journal-title":"J. Complex Networks"},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"D. Szklarczyk A. Franceschini S. Wyder K. Forslund D. Heller J. Huerta-Cepas M. Simonovic A. Roth A. Santos K. P. Tsafou M. Kuhn P. Bork L. J. Jensen and C. von Mering. String v10: protein-protein interaction networks integrated over the tree of life. Nucleic Acids Research 43(D1):D447 2014.  D. Szklarczyk A. Franceschini S. Wyder K. Forslund D. Heller J. Huerta-Cepas M. Simonovic A. Roth A. Santos K. P. Tsafou M. Kuhn P. Bork L. J. Jensen and C. von Mering. String v10: protein-protein interaction networks integrated over the tree of life. Nucleic Acids Research 43(D1):D447 2014.","DOI":"10.1093\/nar\/gku1003"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"D. Szklarczyk J. H. Morris H. Cook M. Kuhn S. Wyder M. Simonovic A. Santos N. T. Doncheva A. Roth P. Bork L. J. Jensen and C. von Mering. The STRING database in 2017: quality-controlled protein-protein association networks made broadly accessible. Nucleic Acids Research 45(Database-Issue):D362--D368 2017.  D. Szklarczyk J. H. Morris H. Cook M. Kuhn S. Wyder M. Simonovic A. Santos N. T. Doncheva A. Roth P. Bork L. J. Jensen and C. von Mering. The STRING database in 2017: quality-controlled protein-protein association networks made broadly accessible. Nucleic Acids Research 45(Database-Issue):D362--D368 2017.","DOI":"10.1093\/nar\/gkw937"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-011-0231-0"},{"key":"e_1_2_1_45_1","unstructured":"The neo4j graph platform. https:\/\/neo4j.com\/ 2018.  The neo4j graph platform. https:\/\/neo4j.com\/ 2018."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035955"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00500-016-2032-2"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/1997166.1997181"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807181"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807181"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733103"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3303753.3303756","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:26:57Z","timestamp":1672219617000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3303753.3303756"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":51,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.14778\/3303753.3303756"],"URL":"https:\/\/doi.org\/10.14778\/3303753.3303756","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}