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
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.