Journal article
RASIM: a rank-aware separate index method for answering top-k spatial keyword queries
World wide web (Bussum), v 16(2), pp 111-139
01 Mar 2013
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
A top-k spatial keyword query returns k objects having the highest (or lowest) scores with regard to spatial proximity as well as text relevancy. Approaches for answering top-k spatial keyword queries can be classified into two categories: the separate index approach and the hybrid index approach. The separate index approach maintains the spatial index and the text index independently and can accommodate new data types. However, it is difficult to support top-k pruning and merging efficiently at the same time since it requires two different orders for clustering the objects: the first based on scores for top-k pruning and the second based on object IDs for efficient merging. In this paper, we propose a new separate index method called Rank-Aware Separate Index Method (RASIM) for top-k spatial keyword queries. RASIM supports both top-k pruning and efficient merging at the same time by clustering each separate index in two different orders through the partitioning technique. Specifically, RASIM partitions the set of objects in each index into rank-aware (RA) groups that contain the objects with similar scores and applies the first order to these groups according to their scores and the second order to the objects within each group according to their object IDs. Based on the RA groups, we propose two query processing algorithms: (i) External Threshold Algorithm (External TA) that supports top-k pruning in the unit of RA groups and (ii) Generalized External TA that enhances the performance of External TA by exploiting special properties of the RA groups. RASIM is the first research work that supports top-k pruning based on the separate index approach. Naturally, it keeps the advantages of the separate index approach. In addition, in terms of storage and query processing time, RASIM is more efficient than the IR-tree method, which is the prevailing method to support top-k pruning to date and is based on the hybrid index approach. Experimental results show that, compared with the IR-tree method, the index size of RASIM is reduced by up to 1.85 times, and the query performance is improved by up to 3.22 times.
Metrics
Details
- Title
- RASIM: a rank-aware separate index method for answering top-k spatial keyword queries
- Creators
- Hyuk-Yoon Kwon - Korea Advanced Institute of Science and TechnologyKyu-Young Whang - Korea Advanced Institute of Science and TechnologyIl-Yeol Song - Drexel UniversityHaixun Wang - Microsoft Research Asia
- Publication Details
- World wide web (Bussum), v 16(2), pp 111-139
- Publisher
- Springer Nature
- Number of pages
- 29
- Grant note
- 2012R1A2A2A01012605 / Korea government (MEST); Ministry of Education, Science and Technology, Republic of Korea; Korean Government NIPA-2010-C1810-1002-0010 / Microsoft Research, under IT/SW Creative research program National Research Foundation of Korea (NRF); National Research Foundation of Korea MKE(The Ministry of Knowledge Economy), Korea; Ministry of Knowledge Economy, Republic of Korea Microsoft Research Asia through KAIST-Microsoft Research Collaboration Center (KMCC)
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Information Science
- Web of Science ID
- WOS:000313662600001
- Scopus ID
- 2-s2.0-84872609783
- Other Identifier
- 991019169420004721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Industry collaboration
- Domestic collaboration
- International collaboration
- Web of Science research areas
- Computer Science, Information Systems
- Computer Science, Software Engineering