Paper Info
Title
Top-k User-Defined Vertex Scoring Queries in Edge-Labeled Graph Databases.
Abstract
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 Semantic Web 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.
Year
DOI
Venue
2018
10.1145/3213891
TWEB
Keywords
Field
DocType
Graph databases, scoring queries, top- k querying
Graph database,Vertex (geometry),Ranking,Information retrieval,Computer science,Steiner tree problem,Semantic Web,Tree structure
Journal
Volume
Issue
ISSN
12
4
1559-1131
Citations 
PageRank 
References 
0
0.34
35
Authors
4
Name
Order
Citations
PageRank
Francesco Parisi120719.15
Noseong Park25021.54
A. Pugliese311512.90
V. S. Subrahmanian468641053.38