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.
Bibliographical noteFunding 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
- Control and Systems Engineering
- Theoretical Computer Science
- Computer Science Applications
- Information Systems and Management
- Artificial Intelligence