WCSE 2017
ISBN: 978-981-11-3671-9 DOI: 10.18178/wcse.2017.06.029

A KSNA-Tree Algorithm for the Top-k Exact Keyword Search in Spatial Databases

Ye-In Chang, Chia-En Li, Kai-Ning Yang

Abstract— In recent years, many websites and applications allow users to find objects which match with all of the query keywords and are close to a specified location. Tao et. al. propose a data access structure called the SI-index which integrates the inverted index with R-tree. However, it takes a long time for dealing with data of objects and some extra time for data decompression. Therefore, in this paper, we propose a KSNAtree algorithm. The KSNA-tree integrates a spatial index NA-tree with inverted index. The contributions of our approach are as follows. First, our approach only construct one KSNA-tree, instead of building n R-trees for n keywords in the database. Second, we organize the data of objects according to their spatial number. This will avoid random access in the query processing by directly accessing the spatial number of a node. Third, we enhance each node in the KSNA-tree with the inverted index. We can prune a node and all of its child nodes immediately once we know that one of the query keywords is definitely not in the node. From our simulation results, we show that our proposed approach is more efficient than the SI-index.

Index Terms— data mining, inverted index, keyword matching, spatial index structure, spatial database, top-k

Ye-In Chang, Chia-En Li, Kai-Ning Yang
Department of Computer Science and Engineering National Sun Yat-sen University Kaohsiung, TAIWAN


Cite: Ye-In Chang, Chia-En Li, Kai-Ning Yang, "A KSNA-Tree Algorithm for the Top-k Exact Keyword Search in Spatial Databases," Proceedings of 2017 the 7th International Workshop on Computer Science and Engineering, pp. 166-170, Beijing, 25-27 June, 2017.