Research On Related Problems In Spatial Keyword Query

With the popularization of mobile Internet,social network,sensor network and global po-sitioning navigation system,the spatial data with geographical location is growing rapidly.The mobile Internet,social network and sensor network generate lots of spatial data,which has many characteristics,such as massive,heterogeneous and multidimensional.To process the spatial data efficiently has received considerable attention in spatial database,which can be used to support di-versified query needs.Spatial keyword queries,which is an important branch of spatial database,considering the spatial proximity and textual similarity during the query processing.It is important for location-based services,meteorological monitoring and prediction,as well as social network monitoring.Spatial keyword query has important theoretical research value as well.It contains three el-ements,namely query model,index mechanism and query algorithm.However,three elements are needed to be studied to solve the problems in real applications.Firstly,various applications promote the increase of query needs.But existing query models cannot capture query needs ef-fectively,which leads to the mismatch between query results and query needs.Secondly,existing road network index mechanisms are built over original networks,which cannot deal with the index maintenance problem when data is updated frequently.Previous keyword index mechanisms either fall short in false hits or space overhead,and there is no technique to control false hits and space overhead.Finally,existing algorithms cannot efficiently handle applications which are complicat-ed or need to addressed quickly.Besides,there is no effective technology to build safe interval dynamically.The thesis aims to study and solve aforementioned problems,to obtain valuable information from spatial data effectively.Three elements are studied in single point query,multi-point query and continuous query scene.The main contents and contributions are:·Level-aware collective spatial keyword queries in Euclidean space(Single Point Query).The thesis introduces keyword level into the query model,and studies the level-aware col-lective spatial keyword query(NP-hard)to get better query results.The thesis improves existing index mechanisms to maintain objects with keyword level,and develops exact and approximate algorithms for different applications.In addition,it proposes two optimizing strategies,namely branch and bound and triggered update,to further improve the efficiency of approximate algorithm.·Aggregate keyword nearest neighbor queries on road network(Multiple Point Query).The thesis introduce keywords into the query model,and study the aggregate keyword nearest neighbor query.Previous index mechanisms and algorithms are inefficient for this problem.The thesis utilize a two-granularity index mechanism to maintain the road network,and studies the delay update mechanism to deal with frequent data updates.It also utilizes the ''collaborative filtering' technology to control false hits and space overhead.Based on the two-granularity index mechanism,the thesis develops the minimum first search algorithm as well as two optimizing strategies,namely share path and progressive computation to address the aggregate keyword nearest neighbor query and aggregate keyword k nearest neighbor query.·Path-based spatial keyword queries on road network(Continuous Query).Above stud-ies assume that the query location is fixed,however,the user usually moves continuously along the route given by the navigation system or public transport in real life.The query path is introduced into the continuous query model,and the thesis studies the range keyword query model and k nearest neighbor keyword query model.For efficient query processing in large road network,the thesis build the index over the backbone network.Besides,the thesis proposes to build safe intervals dynamically,and develops the two-phase query processing framework to deal with path-based query model.Spatial keyword query has great value in application research and theoretical research.The thesis study the query model,index mechanism and query algorithm over the single point query(Level-aware collective spatial keyword query in Euclidean space),multiple point query(Aggre-gate keyword nearest neighbor queries on road network)and continuous query(Path-based spatial keyword queries on road network),to support various query needs.