Study On New Spatial Queries And Pattern Mining Techniques Oriented Complicated Applications

With the developments of geographic information system,Internet,mobile intelligent terminal,spatial data has becoming massive,dynamic and heterogeneous,which provides new opportunities for the development of spatial database technology.Through querying and mining these diverse and abundant data,we can improve intelligent transportation,intelligent city,the location based services,geographic information service and other important applications.New characteristics of spatial data provide the basic condition for spatial complicated applications,and determine new challenges for querying and mining these data as follows:firstly,spatial queries prefer to finding the characteristic and relations of group objects and regions rather than a single object;secondly,spatial queries need to consider a variety of categories of information,e.g.,the location,text description,object relations and moving object activities;thirdly,spatial query and mining show the trend of intelligence,and intelligent mining techniques for multi type,massive spatial data can promote effectively the development of location-based services.These challenges motivate new requirements on querying and mining algorithms,indexing technologies,evaluation methods.We summarized and reviewed current spatial database applications and analyzed the existing research on spatial data query and mining.For some spatial complicated applications,we propose various types of spatial query processing and data mining techniques,including spatial region location based on clues,topic-relevant region query,object flow pattern mining in a region and flow pattern query processing.We proposed the corresponding solutions on query algorithms,indexes,mining methods and applications.At the same time,these techniques can improve effectively the data management ability and processing efficiency of spatial database system,and support the new complicated application of spatial applications.The main work includes the following aspects:(1)On the spatial query,we proposed the clue-based region locating query.Due to the diversity of environmental information and the user the fuzziness of spatial cognition,clues are diverse and fuzzy,so matching fuzzy and various clues with spatial feature data is an important research challenge.In order to effectively implement clue-based query,this paper designed three types of algorithms,including the branch-bound algorithm,the objects join one-by-one algorithm and the pre-computing algorithm.The pre-computing algorithm is implemented by keeping the results of pre-join,indexing them by cell structure.The clue-based query is carried out on pre-computing results,which improves greatly the query efficiency.(2)On the region query,we proposed and solved a novel type of spatial queries named topic-relevant region query,which can be applied to some spatial decision analyses including city region topic partitioning and facility location.In order to process topic-relevant region query,we propose three efficient algorithms to process the query,which are baseline algorithm,filtering-refinement and shrink algorithm.The shrink algorithm can obtain the best pruning performance by clustering regions with high relevance values and shrinking them compared with the other two algorithms.These algorithms solve a problem sorting the regions according to their relevance values with the topic at an arbitrary location.(3)On the region pattern mining,we studied the methods for mining spatial object flow patterns in regions which are represented by time series.Patterns can be used to improve urban planning and intelligent transportation systems.To construct patterns with high precision,we proposed a model for constructing the object flow patterns including data discretization and serialization,pattern training and evaluation and so on.Also we present a new hierarchical clustering tree with skewness.Based on the skewness,we designed a method for removing abnormal sequences and selecting of the patterns automatically which improves the prediction precision.(4)On the pattern query processing,we introduced a novel concept of converging envelop which bounds the tolerance of a group of patterns in various tolerances and equal length and thus dramatically reduce the number of patterns for similarity computation.To index patterns in various lengths and tolerances,the patterns are equally partitioned into the sub-patterns in equal length and various tolerances.We develop two index structures,multi-tree and single-tree,to index these sub-patterns with support of converging envelop.While the single-tree has more pruning power,the multi-tree requires less memory during the pattern matching.In view of the above problems,we evaluated the efficiency and effectiveness of the proposed algorithm with extensive experiments on real datasets.The proposed problems have extended the study of spatial database,satisfied some practical complicated application requirements.