Earticle

The paper proposes spatial approximate keyword query algorithms for cloud systems. Existing work targets on single server solutions, and an exact algorithm is given in memory while another approximate algorithm is given for disk resident datasets. However, a single server fails to provide reasonable throughput due to the limited CPU time and disk bandwidth. Facing the above challenges, this paper gives a two-layered index consisting of global index and local index, which works in a shared nothing cluster for larger query throughput. This paper designs a novel external memory index as local index, which returns exact answer within disks efficiently. It is equipped with keyword set signature and multiple optimizing strategies to reduce I/O cost. The global index partitions the entire spatial space, and each computing node in system maintains a partition. A global index selection algorithm is given. This paper also provides spatial approximate keyword query algorithms based edit distance, including range and the nearest neighbor spatial conditions. An experiment in a shared nothing cluster illustrates the efficiency and effectiveness of our proposed index and query algorithms.