Reasoning and identifying relevant matches: For XML keyword search

Ziyang Liu, Yi Chen

Research output: Contribution to journalArticlepeer-review

126 Scopus citations


Keyword search is a user-friendly mechanism for retrieving XML data in web and scientific applications. An intuitively compelling but vaguely defined goal is to identify matches to query keywords that are relevant to the user. However, it is hard to directly evaluate the relevance of query results due to the inherent ambiguity of search semantics. In this work, we investigate an axiomatic framework that includes two intuitive and non-trivial properties that an XML keyword search technique should ideally satisfy: monotonicity and consistency, with respect to data and query. This is the first work that reasons about keyword search strategies from a formal perspective. Then we propose a novel semantics for identifying relevant matches, which, to the best of our knowledge, is the only existing algorithm that satisfies both properties. An efficient algorithm is designed for realizing this semantics. Extensive experimental studies have verified the intuition of the properties and shown the effectiveness of the proposed algorithm.

Original languageEnglish (US)
Pages (from-to)921-932
Number of pages12
JournalProceedings of the VLDB Endowment
Issue number1
StatePublished - 2008
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • General Computer Science


Dive into the research topics of 'Reasoning and identifying relevant matches: For XML keyword search'. Together they form a unique fingerprint.

Cite this