Description

With advances in geo- positioning technologies and geo-location services, there are a rapidly g rowing amount of spatio-textual object s collected in many applications such as location based services and social network s, in which an object i s Described by its s partial location and a s et of keywords ( terms ) . Consequently, the stud y of spatial keyword se arch which explores both location and textual description of the objects has attracted great attention from the commercial organizations and research Communities. In the paper, we study two fundamental problems in the spatial keyword queries: t op k spatial keyword search (TOP K-S K), and batch t op k spatial keyword search (B TO PK-S K). Given a set of spatio- textual objects, a query location and a set of query key words, the TOPK- SK retrieves the closest k objects e ach of which contain s all key word s in the query. BTOPK -SK is the batch processing of sets of TOPK -SK queries. Based on the inverted index and the linear quad tree, we propose a novel index structure, called inverted li near quad tree ( IL- Quad tree) , which is care full y designed to exploit both spatial and key word based pruning techniques to effectively reduce the search space. An efficient algorithm is then developed to tackle top k spatial key word search. To further enhance the filtering capability of the signature of linear quad tree, we propose a partition based method. In addition, to deal with BTOPK -SK, we design a new computing paradigm which partition the queries in to groups based on both spatial proximity and the textual relevance between queries. We show t ha t the I L –Quad tree technique can also efficiently support BTOPK -SK. Comp rehensive experiments on real and synthetic data clearly demonstrate the efficiency of our methods.