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 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 language | English |
|---|---|
| Article number | 21 |
| Journal | ACM Transactions on the Web |
| Volume | 12 |
| Issue number | 4 |
| DOIs | |
| Publication status | Published - 2018 Sept |
Bibliographical note
Funding Information:F. Parisi and N. Park equally contributed to the paper. Some of the authors may have been partly funded by ONR Grants No. N000141612739, No. N000141512007, No. N000141612896, and No. N000141512742, by ARO Grant No. W911NF1410358, by the Start-(H)Open POR Grant No. J28C17000380006 funded by the Calabria Region Administration, and by the NextShop PON Grant No. F/050374/01-03/X32 funded by the Italian Ministry for Economic Development. Authors’ addresses: F. Parisi and A. Pugliese, DIMES Department, University of Calabria, Cubo 42C, Rende, Italy; emails: fparisi@dimes.unical.it, andrea.pugliese@unical.it; N. Park, Research Hall, Suite 417, George Mason University, 4400 University Drive, Fairfax, VA 22030-4422; email: npark2@uncc.ed; V. S. Subrahmanian, Dept. of Computer Science, Dartmouth College, 9 Maynard Street, Hanover, NH 03755; email: vs@dartmouth.edu. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2018 ACM 1559-1131/2018/09-ART21 $15.00 https://doi.org/10.1145/3213891
Publisher Copyright:
© 2018 Association for Computing Machinery.
All Science Journal Classification (ASJC) codes
- Computer Networks and Communications