Fast best-effort search on graphs with multiple attributes

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

We address the problem of top-k search on graphs with multiple nodal attributes, which we call WAGs (short for Weighted Attribute Graphs). For example, a co-authorship network is a WAG, where each author is a node; each attribute corresponds to a particular topic (e.g., databases, data mining, and machine learning); and the amount of expertise in a particular topic is represented by a non-negative weight on that attribute. A typical search in this setting may be: find three coauthors (i.e., a triangle) where each author's expertise is greater than 50% in at least one topic area (i.e., attribute). We show that the problem of retrieving the optimal answer for graph search on WAGs is NP-complete. Moreover, we propose a fast and effective top-k graph search algorithm for WAGs. In an extensive experimental study, our proposed algorithm exhibits significant speed-up over competing approaches. On average, our proposed method achieves 7× faster query processing than the best competitor.

Original languageEnglish (US)
Title of host publication2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1574-1575
Number of pages2
ISBN (Electronic)9781509020195
DOIs
StatePublished - Jun 22 2016
Event32nd IEEE International Conference on Data Engineering, ICDE 2016 - Helsinki, Finland
Duration: May 16 2016May 20 2016

Publication series

Name2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016

Other

Other32nd IEEE International Conference on Data Engineering, ICDE 2016
CountryFinland
CityHelsinki
Period5/16/165/20/16

All Science Journal Classification (ASJC) codes

  • Information Systems and Management
  • Artificial Intelligence
  • Information Systems
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Computer Graphics and Computer-Aided Design

Fingerprint Dive into the research topics of 'Fast best-effort search on graphs with multiple attributes'. Together they form a unique fingerprint.

  • Cite this

    Roy, S. B., Eliassi-Rad, T., & Papadimitriou, S. (2016). Fast best-effort search on graphs with multiple attributes. In 2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016 (pp. 1574-1575). [7498432] (2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICDE.2016.7498432