Skyline queries on keyword-matched data

Hyunsik Choi, Harim Jung, Ki Yong Lee, Yon Dohn Chung

Research output: Contribution to journalArticlepeer-review

18 Citations (Scopus)


Given a set of d-dimensional tuples with textual descriptions, a keyword-matched skyline query retrieves a skyline computed from tuples whose textual descriptions contain all query words. For example, suppose a customer prefers cars with low mileage and low price, and finds a car equipped with 'air bag' and 'sunroof' in an online shop. In such a case, a keyword-matched skyline query is highly recommended. Although there are many applications for this type of query, to date there have not been any studies on the keyword-matched skyline queries. In this paper, we define a keyword-matched skyline query and propose an efficient and progressive algorithm, named Keyword-Matched Skyline search (KMS). KMS utilizes the IR2-tree as an index structure. To retrieve a keyword-matched skyline, it performs nearest neighbor search in a branch and bound manner. While traversing the IR2-tree, KMS effectively prunes unqualified nodes by means of both spatial and textual information of nodes. To demonstrate the efficiency of KMS, we conducted extensive experiments in various settings. The experimental results show that KMS is very efficient in terms of computational cost and I/O cost.

Original languageEnglish
Pages (from-to)449-463
Number of pages15
JournalInformation Sciences
Publication statusPublished - 2013

Bibliographical note

Funding Information:
This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (No. 2010-0025218 ).


  • Database management
  • Information technology and system
  • Query processing
  • Spatial database
  • Textual database

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence


Dive into the research topics of 'Skyline queries on keyword-matched data'. Together they form a unique fingerprint.

Cite this