Personalized best answer computation in graph databases

Michael Ovelgönne; Noseong Park; V. S. Subrahmanian; Elizabeth K. Bowman; Kirk A. Ogaard

doi:10.1007/978-3-642-41335-3_30

Personalized best answer computation in graph databases

Michael Ovelgönne, Noseong Park, V. S. Subrahmanian, Elizabeth K. Bowman, Kirk A. Ogaard

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Scopus citations

Abstract

Though subgraph matching has been extensively studied as a query paradigm in semantic web and social network data environments, a user can get a large number of answers in response to a query. Just like Google does, these answers can be shown to the user in accordance with an importance ranking. In this paper, we present scalable algorithms to find the top-K answers to a practically important subset of SPARQL-queries, denoted as importance queries, via a suite of pruning techniques. We test our algorithms on multiple real-world graph data sets, showing that our algorithms are efficient even on networks with up to 6M vertices and 15M edges and far more efficient than popular triple stores.

Original language	English (US)
Title of host publication	The Semantic Web, ISWC 2013 - 12th International Semantic Web Conference, Proceedings
Pages	478-493
Number of pages	16
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-642-41335-3_30
State	Published - 2013
Externally published	Yes
Event	12th International Semantic Web Conference, ISWC 2013 - Sydney, NSW, Australia Duration: Oct 21 2013 → Oct 25 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	8218 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	12th International Semantic Web Conference, ISWC 2013
Country/Territory	Australia
City	Sydney, NSW
Period	10/21/13 → 10/25/13

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-41335-3_30

Cite this

Ovelgönne, M., Park, N., Subrahmanian, V. S., Bowman, E. K., & Ogaard, K. A. (2013). Personalized best answer computation in graph databases. In The Semantic Web, ISWC 2013 - 12th International Semantic Web Conference, Proceedings (PART 1 ed., pp. 478-493). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8218 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-41335-3_30

Ovelgönne, Michael ; Park, Noseong ; Subrahmanian, V. S. et al. / Personalized best answer computation in graph databases. The Semantic Web, ISWC 2013 - 12th International Semantic Web Conference, Proceedings. PART 1. ed. 2013. pp. 478-493 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).

@inproceedings{179a6f2ed7594f3d8142346cb97b8ce5,

title = "Personalized best answer computation in graph databases",

abstract = "Though subgraph matching has been extensively studied as a query paradigm in semantic web and social network data environments, a user can get a large number of answers in response to a query. Just like Google does, these answers can be shown to the user in accordance with an importance ranking. In this paper, we present scalable algorithms to find the top-K answers to a practically important subset of SPARQL-queries, denoted as importance queries, via a suite of pruning techniques. We test our algorithms on multiple real-world graph data sets, showing that our algorithms are efficient even on networks with up to 6M vertices and 15M edges and far more efficient than popular triple stores.",

author = "Michael Ovelg{\"o}nne and Noseong Park and Subrahmanian, {V. S.} and Bowman, {Elizabeth K.} and Ogaard, {Kirk A.}",

year = "2013",

doi = "10.1007/978-3-642-41335-3_30",

language = "English (US)",

isbn = "9783642413346",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 1",

pages = "478--493",

booktitle = "The Semantic Web, ISWC 2013 - 12th International Semantic Web Conference, Proceedings",

edition = "PART 1",

note = "12th International Semantic Web Conference, ISWC 2013 ; Conference date: 21-10-2013 Through 25-10-2013",

}

Ovelgönne, M, Park, N, Subrahmanian, VS, Bowman, EK & Ogaard, KA 2013, Personalized best answer computation in graph databases. in The Semantic Web, ISWC 2013 - 12th International Semantic Web Conference, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 8218 LNCS, pp. 478-493, 12th International Semantic Web Conference, ISWC 2013, Sydney, NSW, Australia, 10/21/13. https://doi.org/10.1007/978-3-642-41335-3_30

Personalized best answer computation in graph databases. / Ovelgönne, Michael; Park, Noseong; Subrahmanian, V. S. et al.
The Semantic Web, ISWC 2013 - 12th International Semantic Web Conference, Proceedings. PART 1. ed. 2013. p. 478-493 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8218 LNCS, No. PART 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Personalized best answer computation in graph databases

AU - Ovelgönne, Michael

AU - Park, Noseong

AU - Subrahmanian, V. S.

AU - Bowman, Elizabeth K.

AU - Ogaard, Kirk A.

PY - 2013

Y1 - 2013

N2 - Though subgraph matching has been extensively studied as a query paradigm in semantic web and social network data environments, a user can get a large number of answers in response to a query. Just like Google does, these answers can be shown to the user in accordance with an importance ranking. In this paper, we present scalable algorithms to find the top-K answers to a practically important subset of SPARQL-queries, denoted as importance queries, via a suite of pruning techniques. We test our algorithms on multiple real-world graph data sets, showing that our algorithms are efficient even on networks with up to 6M vertices and 15M edges and far more efficient than popular triple stores.

AB - Though subgraph matching has been extensively studied as a query paradigm in semantic web and social network data environments, a user can get a large number of answers in response to a query. Just like Google does, these answers can be shown to the user in accordance with an importance ranking. In this paper, we present scalable algorithms to find the top-K answers to a practically important subset of SPARQL-queries, denoted as importance queries, via a suite of pruning techniques. We test our algorithms on multiple real-world graph data sets, showing that our algorithms are efficient even on networks with up to 6M vertices and 15M edges and far more efficient than popular triple stores.

UR - http://www.scopus.com/inward/record.url?scp=84891953988&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84891953988&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-41335-3_30

DO - 10.1007/978-3-642-41335-3_30

M3 - Conference contribution

AN - SCOPUS:84891953988

SN - 9783642413346

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 478

EP - 493

BT - The Semantic Web, ISWC 2013 - 12th International Semantic Web Conference, Proceedings

T2 - 12th International Semantic Web Conference, ISWC 2013

Y2 - 21 October 2013 through 25 October 2013

ER -

Ovelgönne M, Park N, Subrahmanian VS, Bowman EK, Ogaard KA. Personalized best answer computation in graph databases. In The Semantic Web, ISWC 2013 - 12th International Semantic Web Conference, Proceedings. PART 1 ed. 2013. p. 478-493. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). doi: 10.1007/978-3-642-41335-3_30

Personalized best answer computation in graph databases

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this