Structured search result differentiation

Ziyang Liu, Peng Sun, Yi Chen

Research output: Contribution to journalArticlepeer-review

58 Scopus citations


Studies show that about 50% of web search is for information exploration purpose, where a user would like to investigate, compare, evaluate, and synthesize multiple relevant results. Due to the absence of general tools that can effectively analyze and di®erentiate multiple results, a user has to manually read and comprehend potentially large results in an exploratory search. Such a process is time consuming, labor intensive and error prone. With meta information embedded, keyword search on structured data provides the potential for automating or semi-automating the comparison of multiple results. In this paper we present an approach for differentiating search results on structured data. We define the differentiability of query results and quantify the degree of difference. then we define the problem of identifying a limited number of valid features in a result that can maximally differentiate this result from the others, which is proved to be NP-hard. We propose two local optimality conditions, namely singleswap and multi-swap. Efficient algorithms are designed to achieve local optimality. To show the applicability of our approach, we implemented a system XRed for XML result differentiation. Our empirical evaluation verifies the effectiveness and efficiency of the proposed approach.

Original languageEnglish (US)
Pages (from-to)313-324
Number of pages12
JournalProceedings of the VLDB Endowment
Issue number1
StatePublished - 2009
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • General Computer Science


Dive into the research topics of 'Structured search result differentiation'. Together they form a unique fingerprint.

Cite this