Leveraging Pattern Mining Techniques for Efficient Keyword Search on Data Graphs

Xinge Lu, Dimitri Theodoratos, Aggeliki Dimitriou

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

Abstract

Graphs model complex relationships among objects in a variety of web applications. Keyword search is a promising method for extraction of data from data graphs and exploration. However, keyword search faces the so called performance scalability problem which hinders its widespread use on data graphs. In this paper, we address the performance scalability problem by leveraging techniques developed for graph pattern mining. We focus on avoiding the generation of redundant intermediate results when the keyword queries are evaluated. We define a canonical form for the isomorphic representations of the intermediate results and we show how it can be checked incrementally and efficiently. We devise rules that prune the search space without sacrificing completeness and we integrate them in a query evaluation algorithm. Our experimental results show that our approach outperforms previous ones by orders of magnitude and displays smooth scalability.

Original languageEnglish (US)
Title of host publicationWeb Information Systems Engineering - WISE 2019 Workshop, Demo, and Tutorial, Revised Selected Papers
EditorsLeong Hou U, Jian Yang, Yi Cai, Kamalakar Karlapalem, An Liu, Xin Huang
PublisherSpringer
Pages98-114
Number of pages17
ISBN (Print)9789811532801
DOIs
StatePublished - 2020
Event20th International Conference on Web Information Systems Engineering, WISE 2019 and on the International Workshop on Web Information Systems in the Era of AI, 2019 - Hong Kong, China
Duration: Jan 19 2020Jan 22 2020

Publication series

NameCommunications in Computer and Information Science
Volume1155 CCIS
ISSN (Print)1865-0929
ISSN (Electronic)1865-0937

Conference

Conference20th International Conference on Web Information Systems Engineering, WISE 2019 and on the International Workshop on Web Information Systems in the Era of AI, 2019
Country/TerritoryChina
CityHong Kong
Period1/19/201/22/20

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics

Keywords

  • Canonical form
  • Graph data
  • Keyword search
  • Tree encoding

Fingerprint

Dive into the research topics of 'Leveraging Pattern Mining Techniques for Efficient Keyword Search on Data Graphs'. Together they form a unique fingerprint.

Cite this