{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:34:06Z","timestamp":1750221246052,"version":"3.41.0"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,9,27]],"date-time":"2018-09-27T00:00:00Z","timestamp":1538006400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ARO","award":["W911NF1410358"],"award-info":[{"award-number":["W911NF1410358"]}]},{"name":"Start-(H)Open POR","award":["J28C17000380006"],"award-info":[{"award-number":["J28C17000380006"]}]},{"name":"Italian Ministry for Economic Development"},{"name":"ONR","award":["N000141612739, N000141512007, N000141612896 and N000141512742"],"award-info":[{"award-number":["N000141612739, N000141512007, N000141612896 and N000141512742"]}]},{"name":"Calabria Region Administration, and by the NextShop PON","award":["F\/050374\/01-03\/X32"],"award-info":[{"award-number":["F\/050374\/01-03\/X32"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Web"],"published-print":{"date-parts":[[2018,11,30]]},"abstract":"<jats:p>\n            We consider identifying highly ranked vertices in large graph databases such as social networks or the Semantic Web where there are edge labels. There are many applications where users express\n            <jats:italic>scoring queries<\/jats:italic>\n            against such databases that involve two elements: (i) a set of patterns describing relationships that a vertex of interest to the user must satisfy and (ii) a scoring mechanism in which the user may use properties of the vertex to assign a score to that vertex. We define the concept of a partial pattern map query (partial PM-query), which intuitively allows us to prune partial matchings, and show that finding an optimal partial PM-query is NP-hard. We then propose two algorithms, PScore_LP and PScore_NWST, to find the answer to a scoring (top-\n            <jats:italic>k<\/jats:italic>\n            ) query. In PScore_LP, the optimal partial PM-query is found using a list-oriented pruning method. PScore_NWST leverages node-weighted Steiner trees to quickly compute slightly sub-optimal solutions. We conduct detailed experiments comparing our algorithms with (i) an algorithm (PScore_Base) that computes all answers to the query, evaluates them according to the scoring method, and chooses the top-\n            <jats:italic>k<\/jats:italic>\n            , and (ii) two Semantic Web query processing systems (Jena and GraphDB). Our algorithms show better performance than PScore_Base and the Semantic Web query processing systems\u2014moreover, PScore_NWST outperforms PScore_LP on large queries and on queries with a tree structure.\n          <\/jats:p>","DOI":"10.1145\/3213891","type":"journal-article","created":{"date-parts":[[2018,9,28]],"date-time":"2018-09-28T17:47:33Z","timestamp":1538156853000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Top-k User-Defined Vertex Scoring Queries in Edge-Labeled Graph Databases"],"prefix":"10.1145","volume":"12","author":[{"given":"Francesco","family":"Parisi","sequence":"first","affiliation":[{"name":"University of Calabria, Rende, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Noseong","family":"Park","sequence":"additional","affiliation":[{"name":"University of North Carolina, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrea","family":"Pugliese","sequence":"additional","affiliation":[{"name":"University of Calabria, Rende, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V. S.","family":"Subrahmanian","sequence":"additional","affiliation":[{"name":"Dartmouth College, Hanover, NH, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,9,27]]},"reference":[{"volume-title":"IEEE International Conference on Intelligence and Security Informatics (ISI). 19--24","author":"Andrews Ian A.","key":"e_1_2_1_1_1","unstructured":"Ian A. Andrews , Srijan Kumar , Francesca Spezzano , and V. S. Subrahmanian . 2015. SPINN: Suspicion prediction in nuclear networks . In IEEE International Conference on Intelligence and Security Informatics (ISI). 19--24 . Ian A. Andrews, Srijan Kumar, Francesca Spezzano, and V. S. Subrahmanian. 2015. SPINN: Suspicion prediction in nuclear networks. In IEEE International Conference on Intelligence and Security Informatics (ISI). 19--24."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187922"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772696"},{"volume-title":"International Semantic Web Conference Posters and Demos.","author":"Atre Medha","key":"e_1_2_1_4_1","unstructured":"Medha Atre , Jagannathan Srinivasan , and James A. Hendler . 2008. BitMat: A main-memory bit matrix of RDF triples for conjunctive triple pattern queries . In International Semantic Web Conference Posters and Demos. Medha Atre, Jagannathan Srinivasan, and James A. Hendler. 2008. BitMat: A main-memory bit matrix of RDF triples for conjunctive triple pattern queries. In International Semantic Web Conference Posters and Demos."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2019470.2019472"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4018\/jswis.2009081901"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04930-9_7"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1013367.1013381"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526806"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Jiefeng Cheng and Jeffrey Xu Yu. 2011. A survey of relational approaches for graph pattern matching over large graphs. In Graph Data Management. 112--141.  Jiefeng Cheng and Jeffrey Xu Yu. 2011. A survey of relational approaches for graph pattern matching over large graphs. In Graph Data Management. 112--141.","DOI":"10.4018\/978-1-61350-053-8.ch006"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544895"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/IWQOS.2008.32"},{"key":"e_1_2_1_13_1","volume-title":"Retrieved","author":"X.","year":"2016","unstructured":"CiteSeer X. 2016 . Public dataset . Retrieved March 15, 2018 from http:\/\/csxstatic.ist.psu.edu\/about\/data. CiteSeerX. 2016. Public dataset. Retrieved March 15, 2018 from http:\/\/csxstatic.ist.psu.edu\/about\/data."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2348283.2348438"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536258.2536263"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498247"},{"key":"e_1_2_1_17_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S . Johnson . 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 8 Co., New York. Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 8 Co., New York."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376676"},{"key":"e_1_2_1_19_1","volume-title":"Retrieved","author":"DB.","year":"2016","unstructured":"Graph DB. 2016 . Home page . Retrieved March 15, 2018 from http:\/\/www.ontotext.com. GraphDB. 2016. Home page. Retrieved March 15, 2018 from http:\/\/www.ontotext.com."},{"key":"e_1_2_1_20_1","volume-title":"International Semantic Web Conference Posters and Demos.","author":"Graves Alvaro","year":"2008","unstructured":"Alvaro Graves , Sibel Adali , and Jim Hendler . 2008 . A method to rank nodes in an RDF graph . In International Semantic Web Conference Posters and Demos. Alvaro Graves, Sibel Adali, and Jim Hendler. 2008. A method to rank nodes in an RDF graph. In International Semantic Web Conference Posters and Demos."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1998.2754"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920901"},{"key":"e_1_2_1_23_1","volume-title":"Retrieved","author":"Harris Steve","year":"2016","unstructured":"Steve Harris and Andy Seaborne . 2016 . SPARQL 1.1 Query Language . Retrieved March 15, 2018 from http:\/\/www.w3.org\/TR\/sparql11-query. Steve Harris and Andy Seaborne. 2016. SPARQL 1.1 Query Language. Retrieved March 15, 2018 from http:\/\/www.w3.org\/TR\/sparql11-query."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939815"},{"volume-title":"Retrieved","year":"2016","key":"e_1_2_1_25_1","unstructured":"IMDb. 2016 . Public dataset . Retrieved March 15, 2018 from http:\/\/www.imdb.com\/interfaces. IMDb. 2016. Public dataset. Retrieved March 15, 2018 from http:\/\/www.imdb.com\/interfaces."},{"volume-title":"Retrieved","year":"2016","key":"e_1_2_1_26_1","unstructured":"Jena. 2016 . Home page . Retrieved March 15, 2018 from https:\/\/jena.apache.org. Jena. 2016. Home page. Retrieved March 15, 2018 from https:\/\/jena.apache.org."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824054"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535569.2448952"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB).","author":"Lee Jinsoo","year":"2013","unstructured":"Jinsoo Lee , Wook-Shin Han , Romans Kasperovics , and Jeong-Hoon Lee . 2013 . An in-depth comparison of subgraph isomorphism algorithms in graph databases . In Proceedings of the International Conference on Very Large Data Bases (VLDB). Jinsoo Lee, Wook-Shin Han, Romans Kasperovics, and Jeong-Hoon Lee. 2013. An in-depth comparison of subgraph isomorphism algorithms in graph databases. In Proceedings of the International Conference on Very Large Data Bases (VLDB)."},{"key":"e_1_2_1_30_1","volume-title":"Retrieved","author":"Lehigh University Benchmark (LUBM).","year":"2016","unstructured":"Lehigh University Benchmark (LUBM). 2016 . Home page . Retrieved March 15, 2018 from http:\/\/swat.cse.lehigh.edu\/projects\/lubm. Lehigh University Benchmark (LUBM). 2016. Home page. Retrieved March 15, 2018 from http:\/\/swat.cse.lehigh.edu\/projects\/lubm."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2396805"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35176-1_22"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1298306.1298311"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/2063016.2063046"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.205"},{"volume-title":"Retrieved","year":"2016","key":"e_1_2_1_36_1","unstructured":"Neo4j. 2016 . Home page . Retrieved March 15, 2018 from http:\/\/neo4j.com. Neo4j. 2016. Home page. Retrieved March 15, 2018 from http:\/\/neo4j.com."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0165-y"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920877"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41335-3_30"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/WIIAT.2008.290"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2014.7004278"},{"key":"e_1_2_1_42_1","volume-title":"International Conference on Very Large Data Bases (VLDB). 507--518","author":"Qi Yan","year":"2007","unstructured":"Yan Qi , K. Sel\u00e7uk Candan , and Maria Luisa Sapino . 2007 . Sum-max monotonic ranked joins for evaluating top-k twig queries on weighted data graphs . In International Conference on Very Large Data Bases (VLDB). 507--518 . Yan Qi, K. Sel\u00e7uk Candan, and Maria Luisa Sapino. 2007. Sum-max monotonic ranked joins for evaluating top-k twig queries on weighted data graphs. In International Conference on Very Large Data Bases (VLDB). 507--518."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1815948.1815953"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2598561"},{"key":"e_1_2_1_45_1","volume-title":"Retrieved","author":"Intelligence Benchmark Social Network","year":"2016","unstructured":"Social Network Intelligence Benchmark . 2016 . Home page . Retrieved March 15, 2018 from http:\/\/www.w3.org\/wiki\/Social_Network_Intelligence_BenchMark. Social Network Intelligence Benchmark. 2016. Home page. Retrieved March 15, 2018 from http:\/\/www.w3.org\/wiki\/Social_Network_Intelligence_BenchMark."},{"volume-title":"Retrieved","year":"2016","key":"e_1_2_1_46_1","unstructured":"SP<sup>2<\/sup>Bench. 2016 . Home page . Retrieved March 15, 2018 from http:\/\/dbis.informatik.uni-freiburg.de\/forschung\/projekte\/SP2B. SP<sup>2<\/sup>Bench. 2016. Home page. Retrieved March 15, 2018 from http:\/\/dbis.informatik.uni-freiburg.de\/forschung\/projekte\/SP2B."},{"volume-title":"Retrieved","year":"2016","key":"e_1_2_1_47_1","unstructured":"SPARQLer. 2016 . Home page . Retrieved March 15, 2018 from http:\/\/www.sparql.org. SPARQLer. 2016. Home page. Retrieved March 15, 2018 from http:\/\/www.sparql.org."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402736"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311907"},{"volume-title":"Retrieved","year":"2016","key":"e_1_2_1_50_1","unstructured":"Titan. 2016 . Home page . Retrieved March 15, 2018 from http:\/\/thinkaurelius.github.io\/titan. Titan. 2016. Home page. Retrieved March 15, 2018 from http:\/\/thinkaurelius.github.io\/titan."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/2889905.2889914"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447863"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498307"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247650"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1316874.1316897"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0337-7"}],"container-title":["ACM Transactions on the Web"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3213891","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3213891","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3213891","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:42Z","timestamp":1750212462000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3213891"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,27]]},"references-count":56,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,11,30]]}},"alternative-id":["10.1145\/3213891"],"URL":"https:\/\/doi.org\/10.1145\/3213891","relation":{},"ISSN":["1559-1131","1559-114X"],"issn-type":[{"type":"print","value":"1559-1131"},{"type":"electronic","value":"1559-114X"}],"subject":[],"published":{"date-parts":[[2018,9,27]]},"assertion":[{"value":"2016-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-09-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}