Top-k user-defined vertex scoring queries in edge-labeled graph databases

Francesco Parisi, Noseong Park, Andrea Pugliese, V. S. Subrahmanian

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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 scoring queries 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-k) 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-k, and (ii) two SemanticWeb query processing systems (Jena and GraphDB). Our algorithms show better performance than PScore-Base and the Semantic Web query processing systems-moreover, PScore-NWST outperforms PScore-LP on large queries and on queries with a tree structure.

Original languageEnglish (US)
Article number21
JournalACM Transactions on the Web
Issue number4
StatePublished - Sep 2018
Externally publishedYes


  • Graph databases
  • Scoring queries
  • Top-k querying

ASJC Scopus subject areas

  • Computer Networks and Communications


Dive into the research topics of 'Top-k user-defined vertex scoring queries in edge-labeled graph databases'. Together they form a unique fingerprint.

Cite this