Efficient keyword search on large tree structured datasets

Aggeliki Dimitriou, Dimitri Theodoratos

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

7 Scopus citations

Abstract

Keyword search is the most popular paradigm for querying XML data on the web. In this context, three challenging problems are (a) to avoid missing useful results in the answer set, (b) to rank the results with respect to some relevance criterion and (c) to design algorithms that can efficiently compute the results on large datasets. In this paper, we present a novel multi-stack based algorithm that returns as an answer to a keyword query all the results ranked on their size. Our algorithm exploits a lattice of stacks each corresponding to a partition of the keyword set of the query. This feature empowers a linear time performance on the size of the input data for a given number of query keywords. As a result, our algorithm can run efficiently on large input data for several keywords. We also present a variation of our algorithm which accounts for infrequent keywords in the query and show that it can significantly improve the execution time. An extensive experimental evaluation of our approach confirms the theoretical analysis, and shows that it scales smoothly when the size of the input data and the number of input keywords increases.

Original languageEnglish (US)
Title of host publicationKEYS 2012 - Proceedings of the 3rd International Workshop on Keyword Search on Structured Data
Pages63-74
Number of pages12
DOIs
StatePublished - Jul 9 2012
Event3rd International Workshop on Keyword Search on Structured Data, KEYS 2012 - Scottsdale, AZ, United States
Duration: May 20 2012May 20 2012

Publication series

NameKEYS 2012 - Proceedings of the 3rd International Workshop on Keyword Search on Structured Data

Other

Other3rd International Workshop on Keyword Search on Structured Data, KEYS 2012
CountryUnited States
CityScottsdale, AZ
Period5/20/125/20/12

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Information Systems

Keywords

  • Keyword search
  • LCA
  • Ranking
  • Search algorithm
  • Tree-structured data
  • XML

Fingerprint Dive into the research topics of 'Efficient keyword search on large tree structured datasets'. Together they form a unique fingerprint.

Cite this