Study On Complex Query Processing Techniques For Advanced Spatial Applications

The research on spatial database originated from the field of map making and processing of remote sensing image data in 1970s.With the increasing of people demand for spatial information,the communication techniques and geo-positioning techniques have been widely developed,and spatial data management has acquired great attention.To solve spatial applications,a lot of exiting researches focus on various spatial queries such as the kNN query and the range query among others.Specifically,some optimized solutions based on filter and refinement strategies are proposed.However.both spatial environments and query semantics may be quite complicated in the real-world advanced spatial applications.For example,by utiliz-ing predictive queries on road networks.users can predict the vehicles along some road segments in ten minutes.Also,based on spatial preference queries,a user can find an appealing hotel with nearby preferred facilities such as shopping malls and cinemas.In the above examples,the inherent complexity of the queries and increas-ingly expanded data scale may incur considerable processing costs in term of CPU,I/O and even communication,and thus novel improved solutions are highly desired.This dissertation summarizes existing spatial data management and query op-timization techniques.Specifically,we conduct in-depth studies into two types of complex spatial queries:predictive queries and preference queries.Some improved methods are explored to enhance the efficiency for these queries.In detail,the contributions are summarized as follows:(1)Predictive range queries for moving objects on a Road Network.The disser-tation focuses on how efficiently and effectively to reduce the moving objects com-munication workload with the database server on the road networks.We propose an adaptive updating protocol for moving object databases with a smaller number of updates between objects and the database server.The adaptive updating protocol is considered from active updating and passive updating.In contrast to most of the previous methods to calculate the exact.location and speeds of moving objects,we build a motion model of Road-Network Safe Range for each object to effectively predict the locations of the objects in future.(2)Predictive density queries for indoor moving objects.In indoor environ-ments,such predictive density queries are valuable for high-level analysis.In this dissertation,by leveraging the Markov correlations,we predict the future locations of moving objects and conduct the density queries accordingly.In particular,we present an optimized framework which contains three phases to tackle this problem.First,an index structure based on the transition matrix is designed to facilitate the search process.Second,the space and probability pruning techniques are proposed to improve the query efficiency significantly.Finally,we apply an accurate method and an approximate sampling method to verify whether each unpruned region is a dense region.(3)Group preference queries processing.The queries aim to find a destination place for a group of users.The group of users want to go to a place labeled with a specified category feature together,and each of them has a location and a.set of additional preferences.It is expected that the result place of the query belongs to the specified feature,and it is close to places satisfying the preferences of each user.We develop a novel framework of space partition for answering the queries,which can be used to compute both exact query result and approximate result with proven approximation ratio.Finally,extensive experiments also verify the efficiency of the proposed methods.(4)Reverse top-k spatial preference queries.The queries retrieve the users that deem a given database object as one of their top-k results,and the attributes of the query object are given by the spatial distance of it and users preference.This dissertation presents a processing framework and some optimized techniques containing pruning methods and the grouping users' preferences method.In conclusion,this dissertation focuses on typical characteristics of complex spatial applications,we study several complex spatial query problems and propose main problems of spatial queries and proposes efficient query processing methods and frameworks.Extensive experiments also verify the effectiveness and efficiency of the proposed methods.