定性空间推理及其应用技术研究
|
摘要
定性空间推理技术对于研发新一代的智能空间信息处理系统起着关键性的作用,但无论是在理论方面和应用方面的研究都还不是很完善。本文从理论方面和应用角度对定性空间推理进行了研究,在理论上提出新的计算模型和推理算法,在几个应用方面给出比较完整的应用解决框架和相应的实验分析。
本文的研究主要包括以下几个方面:
(1)结合现有的空间拓扑模型RCC8和基于区域的主方向关系模型,研究了RCC8和主方向关系的交互规则知识,提出结合RCC8和主方向约束关系的定性空间约束满足问题的路径相容算法,并证明其复杂性和传统算法相比没有大的增加,还设计了一个针对定性空间约束满足问题的通用相容性判定算法。
(2)对Goyal和Egenhofer的主方向关系模型的不足进行了分析,基于数学形态学的膨胀操作提出区域间方向关系的定量的计算模型;结合模糊集合理论和数学形态学理论提出基于模糊区域的方向关系计算模型。实验证明计算模型符合人们认知。
(3)研究时空推理中的与运动连续性有关的概念邻域问题,提出扩展概念邻域图的概念和计算方法。为时空推理提供了理论和算法基础。
(4)对空间结构信息检索方法进行研究,基于区间演算提出结合拓扑和方向关系进行空间结构检索的计算模型,设计了四个系统检索算法,通过实验分析确定了两个实用的算法并总结出适用条件。
(5)研究空间数据挖掘问题,设计了一个基于多图层的空间数据挖掘算法框架,并应用到分类问题中,实验结果比较令人满意。
Various kinds of geospatial information technologies that have recently come to lifeextend the public's ability to quickly and easily access geo-referenced informationbeyond the confines of desktop GIS (Geographic Information System). The World WideWeb, wireless communication and information technologies, and telematicstechnologies represent the new face of geospatial applications. Through space-awaredevices, location-based services promise to offer users a profusion of information ontheir local environment in the field or on the street, which in turn enables them to answerall sorts of space-related questions in their daily life.
To keep pace with these new application demands, we must research new spatialinformation processing techniques. For example, the old paradigms of relevance todesktop GISs have to be retooled. A particular challenge for the design of spatialinformation systems of the next generation is to equip GISs to handle common-sensegeographic queries made by users without specific training in spatial technologies.Because the view of the geographic world held by the general public is in the form ofmental images or narrative descriptions, rather than in a digital form as stored incomputer databases, people often perceive spatial relations through qualitativedescriptions instead of metric measurements. Therefore, it is much more practical forthem to formulate spatial queries using qualitative terms in order to interact with spatialdatabases. This intuitive interaction entails providing facilities for the representation ofqualitative spatial information and making inferences, i.e. Qualitative Spatial Reasoning(QSR).
Although many research achievements have been obtained in QSR, some problemshave not been solved yet. The researches on QSR integrating multi-aspect spatialinformation are being paid more and more attention by scholars, because it is very rareto deal with only one aspect of spatial information in practice. Some researcher has everstudied on the QSR integrating topology and direction information based on intervalcalculus. The cardinal direction model proposed by Goyal and Egenhofer considers thereal shape of the primary spatial object, which leads to strong expressivity and favorableproperties of computing and reasoning. But the techniques of QSR combining Goyal andEgenhofer's cardinal direction model and topological model have not been given enough
studies. In the QSR research field, the research on direction relations between fuzzyregions is much less compared to topological relation between fuzzy regions, while thefuzziness in real world is pervasive. Spatio-temporal reasoning research relatedintimately to QSR is becoming a hot topic, which has triggered many problems aboutrepresentation and reasoning. This thesis focuses on a particular problem inspatio-temporal reasoning. The theoretical and practical researches on QSR are equallyimportant. This thesis carries out research on the algorithms in two typical applications,i.e. spatial configuration information retrieval and spatial data mining, which arepotential applications in GIS and other spatial information systems.The goals of this thesis are to develop QSR algorithms and investigate thecomputational properties combining the spatial topological calculus RCC8 and cardinaldirection calculus, to analyze the deficiency of Goyal and Egenhofer's cardinal directionmodel and provide a quantitative computational model handling cardinal directionsbetween both crisp and fuzzy regions, to investigate the conceptual neighborhoodproblem related to motion continuity in spatio-temporal reasoning and introduce thegeneralized conceptual neighborhood graph and the algorithm, to investigate the spatialconfiguration retrieval methods, to develop the scheme of retrieval considering thetopological and cardinal direction relations and the efficient retrieval algorithmsevaluated by some experiments, to investigate the spatial data mining techniques andprovide a new method.The major contributions, ideas and research results included in the thesis are asfollows:Firstly, Research on QSR techniques combining RCC8 and cardinal directioncalculus based on region.To combine the two calculi, we must consider the interaction between them.Because the number of cardinal direction relations based on region is 512, it's notrealistic to investigate the composition tables of the two calculi and the interaction rulesshould be considered which can be used by a computer program to generate compositiontables. Based on the semantics of RCC8 and cardinal direction calculus based on region,the interaction rules are derived. This thesis regard QSR as a special form of ConstraintSatisfaction Problems (CSPs): Qualitative Spatial Constraint Satisfaction Problems(QS-CSPs), whose domains are infinite. So the methods handling CSPs with infinitedomains can be applied. We define the consistency deciding problem and consistentscenarios problems, which are critical in QS-CSPs. We introduce the path consistencyconcept and the path consistency algorithm related to consistency deciding. Therelationship between path consistency and global consistency is also given. The solvingmethods of CSPs with infinite domains are described and the research results oncomputational properties achieved in RCC8 and cardinal direction calculus based onregion are outlined. In RCC8, three maximal tractable subsets whose consistency
deciding problem can be determined by path consistency algorithm are identified;In thecardinal direction calculus based on region, the algorithm solving the consistencydeciding problem based on constraint set consisting of basic cardinal direction relationsis worked out.This thesis designs a path consistency algorithm handling the CSPs combiningRCC8 and cardinal direction relations. Generally, path consistency algorithm operateswithin a CSP, but it should be extended to communicate interactions between RCC8component and cardinal direction component. To ensure the respective path consistencyof RCC8 component and cardinal direction component in a CSP that includes RCC8relations and cardinal direction relations and implement the interactions between them,our new algorithm uses two queues, which maintain two kinds of constraint relationsrespectively. Our algorithm pick out a constraint relation from one of the two queues inturn and this constraint relation affect not only the constraint relations within its queue,but also the constraint relations in the other queue according to the interaction rules. Thealgorithm doesn't terminate until the two queues are all empty or the empty constraintrelation is derived. The computational complexity of our algorithm does not improvemuch compared to traditional path consistency algorithm. A simple exampledemonstrates that the idea of combining RCC8 and cardinal direction calculus and theproposed new algorithm are very useful.Based on the achievements on the computational properties of RCC8 and cardinaldirection calculus based on region, this thesis analyzes the computational complexity ofthe CSPs combining RCC8 and cardinal directional relations based on differentconstraint subsets and concludes that the computational complexity of the consistencydeciding problem of the CSPs based on the constraint set composed of any maximaltractable subset in RCC8 and basic cardinal directional relations is still polynomialthough a little higher. The analysis on the computational complexity is very importantbecause the analysis results can guide us to design correct and efficient consistencydeciding algorithms. For CSPs whose constraint relations are not based on the tractableconstraint subsets, path consistency algorithm cannot decide its consistency problem,because path consistency is necessary but not enough condition for global consistency ofa CSP. So we must have a comprehensive algorithm deciding the consistency problemof CSPs based on any constraint set. The thesis designs a comprehensive consistencydeciding algorithm for CSPs combining RCC8 and cardinal direction relations. Thealgorithm uses aforementioned path consistency algorithm for pruning, and if the pathconsistency algorithm is run using tractable subsets, the efficiency of the comprehensivealgorithm can be improved.The research ideas and approaches used for combining RCC8 and cardinal directioncalculus can be generalized to the QSR combining other spatial aspects. The research onthe QSR techniques is very meaningful to GIS, computer vision and robot navigation,
etc.Secondly, Modeling cardinal directions between fuzzy regions based onfuzzy-morphology.Traditional cardinal direction model based on region approximate reference regionusing Minimum Bounding Rectangle (MBR), which leads that the model cannot identifythe correct cardinal directions in some cases. For example, a region A does not overlapwith another region B, but located in the convex hull of region B. The dilation operationin mathematics morphology can handle these cases naturally. This thesis defines acomputational model using the dilation operation in mathematics morphology andappropriate structure element, and illustrates that this new model can complement thedeficiency in current model through some examples. Our work does not discard thecurrent model, but a refinement of it, because the current cardinal direction model basedon region has a favorable property of qualitative reasoning.Traditionally, most of the spatial data models assume that the extent of the spatialobject, i.e. the boundary of it, is exactly defined and extensively acknowledged. Thiskind of model is crisp spatial model. Researchers are realizing that many spatial objectshave not crisp boundaries, or the boundaries cannot be exactly identified in the realworld. This thesis combines fuzzy set theory and mathematics morphology theory tomodel the cardinal direction relations between fuzzy regions. A fuzzy region is regardedas a set composed of a finite (or infinite) number of crisp regions, and each crisp regionis assigned a probability value that it is the “true” representative of the whole fuzzyregion. For any two fuzzy regions, each pair of crisp regions in the sets can be workedout the cardinal direction relation using the aforementioned computational model basedon mathematics morphology and all the resulting cardinal direction relations areaggregated using a special schema. After comparing the two models, i.e. the modelhandling the crsp regions and the model handling the fuzzy regions, we conclude that thefuzzy model can be reduced to the crisp model when handling crisp regions, i.e. weprovide a uniform computational model handling cardinal direction relations betweenregions quantitatively.The computational model of this thesis can deal with both the continuous anddiscrete space, and the approaches handling cardinal direction relations between fuzzyregions can be applied to other spatial models. The experiment results confirm thecognitive plausibility of our computational models.Thirdly, Research on generalized conceptual neighborhood graph inspatio-temporal reasoning.The simple integration of space and time is not enough in spatio-temporal datamanagement. This thesis introduces a spatio-temporal model taking space-time historiesof objects as primitive entities, the topology of space-time, temporal order, and spacerelations. The concepts of time slice and spatio-temporal continuity are presented. Based
on spatio-temporal continuity and time slice, spatial conceptual neighborhood isredefined. When we want to judge whether a spatio-temporal scenario can betransformed to another spatio-temporal scenario under the condition of spatio-temporalcontinuity, the traditional spatial conceptual neighborhood graph is not applicable. Sothis thesis presents the concept of generalized conceptual neighborhood graph, andproposes the computational method. The algorithm is computationally expensive. Thegeneralized conceptual neighborhood graph can be applied to spatio-temporal reasoning,especially consistency checking.Fourthly, Research on spatial configuration information retrieval algorithms.Spatial configuration information retrieval has potential applications in many fields,such as GIS, Multimedia database, Computer vision and VLSI (Very Large ScaleIntegration), etc. This thesis regards the spatial configuration retrieval problems as CSPswith finite domains, which are different from the aforementioned QS-CSPs based oninfinite domains. So the traditional algorithms for CSPs can be applied. This thesidefines the formulas computing the inconsistency degree and similarity degree, whichare used by the retrieval algorithms.In real applications, spatial regions often have complex geometric shapes. If wecompute the spatial relations between them directly, the expense will be very large andsometimes expensive computations will result in nothing. If we use MBR toapproximate the real shapes of the regions, the computational expense will be greatlyreduced because only the spatial relations between rectangles are calculated. Theretrieval of spatial configurations can be divided into two steps: first, the combinationsof rectangles which are not possible to satisfy the query conditions are eliminated;second, the combinations of real spatial objects corresponding to the remainingcombinations of rectangles are calculated using computational geometry techniques tocheck if they satisfy the query conditions. The thesis presents the method for computingthe inconsistency degree between two spatial relations through encoding spatial relationsbetween two rectangles as two binary strings along the horizontal and vertical axes. Thesimilarity degree is calculated according to the conceptual neighborhood graph ofinterval calculus.The thesis outlines search algorithms which can solve spatial configurationinformation retrieval problems, and designs four systematic search algorithms, i.e.SFC-DVOSolver which combines forward checking and dynamic variable ordering usedto solve traditional CSPs, RSFC-DVOSolver which is based on SFC-DVOSolver butemploys R-tree to accelerate pruning in forward checking, HRSFC-DVOSolver which isbased on RSFC-DVOSolver and uses hash index technique to accelerate rectanglematching process, RMLSFC-DVOSolver which combines R-tree and SFC-DVOSolverto realize constraint solving level by level. To implement the algorithms using R-tree,this thesis investigates the mapping relationship between spatial relations (including
topological and cardinal direction relations) of spatial objects and spatial relations oftheir MBRs, and the mapping relationship between spatial relations (includingtopological and cardinal direction relations) of intermediate nodes in R-tree and spatialrelations of the MBRs.Through experiments, this thesis concludes that algorithms SFC-DVOSolver andHRSFC-DVOSolver are the feasible ones for solving spatial configuration retrievalproblems, and fixes on the parameters of the two algorithms and the conditions underwhich the two algorithms can be applicable. If the constraint power of the querycondition is weak, the algorithm SFC-DVOSolver should be used;if the constraintpower is normal or strong, the algorithm HRSFC-DVOSolver is better. The judgment ofthe constraint power of the query condition should be based on the knowledge base, andthen we can decide to use SFC-DVOSolver or HRSFC-DVOSolver.When the number of query variable is large (usually larger than 20) or the spatialdata volume is very large (usually larger than one hundred and thousand), the systematicalgorithms will not be applicable and the local search algorithms or other optimizationalgorithms. The research on spatial configuration retrieval algorithms is valuable to theapplication systems related to spatial data.Fifthly, Research on spatial data mining techniques.Spatial Data Mining (SDM) is to abstract the implicit knowledge, spatial relationsor other meaningful patterns in spatial databases. The main difference SDM has from thetraditional data mining is that SDM considers not only the non-spatial attributes, but alsothe spatial attributes. For the problem of multi-layer (or multi-thematic) spatial datamining, we propose a multi-relational aggregation operator and an algorithm frame forspatial data mining based on this operator. The algorithm derives a relation table fromthe spatial data information (including spatial and non-spatial information) related toseveral layers. Then the traditional data mining techniques based on relational databasecan be directly applied. The algorithm can define spatial predicates according to actualneeds. We apply this frame to a real spatial data classification problem, which runsefficiently and achieves good classification results.To sum up, the study results of this thesis are of both theoretical and practicalbenefit to further researches in qualitative spatial reasoning, fuzzy spatial reasoning,spatio-temporal reasoning, spatial information retrieval, spatial data mining andgeographic information system.
本文的研究主要包括以下几个方面:
(1)结合现有的空间拓扑模型RCC8和基于区域的主方向关系模型,研究了RCC8和主方向关系的交互规则知识,提出结合RCC8和主方向约束关系的定性空间约束满足问题的路径相容算法,并证明其复杂性和传统算法相比没有大的增加,还设计了一个针对定性空间约束满足问题的通用相容性判定算法。
(2)对Goyal和Egenhofer的主方向关系模型的不足进行了分析,基于数学形态学的膨胀操作提出区域间方向关系的定量的计算模型;结合模糊集合理论和数学形态学理论提出基于模糊区域的方向关系计算模型。实验证明计算模型符合人们认知。
(3)研究时空推理中的与运动连续性有关的概念邻域问题,提出扩展概念邻域图的概念和计算方法。为时空推理提供了理论和算法基础。
(4)对空间结构信息检索方法进行研究,基于区间演算提出结合拓扑和方向关系进行空间结构检索的计算模型,设计了四个系统检索算法,通过实验分析确定了两个实用的算法并总结出适用条件。
(5)研究空间数据挖掘问题,设计了一个基于多图层的空间数据挖掘算法框架,并应用到分类问题中,实验结果比较令人满意。
Various kinds of geospatial information technologies that have recently come to lifeextend the public's ability to quickly and easily access geo-referenced informationbeyond the confines of desktop GIS (Geographic Information System). The World WideWeb, wireless communication and information technologies, and telematicstechnologies represent the new face of geospatial applications. Through space-awaredevices, location-based services promise to offer users a profusion of information ontheir local environment in the field or on the street, which in turn enables them to answerall sorts of space-related questions in their daily life.
To keep pace with these new application demands, we must research new spatialinformation processing techniques. For example, the old paradigms of relevance todesktop GISs have to be retooled. A particular challenge for the design of spatialinformation systems of the next generation is to equip GISs to handle common-sensegeographic queries made by users without specific training in spatial technologies.Because the view of the geographic world held by the general public is in the form ofmental images or narrative descriptions, rather than in a digital form as stored incomputer databases, people often perceive spatial relations through qualitativedescriptions instead of metric measurements. Therefore, it is much more practical forthem to formulate spatial queries using qualitative terms in order to interact with spatialdatabases. This intuitive interaction entails providing facilities for the representation ofqualitative spatial information and making inferences, i.e. Qualitative Spatial Reasoning(QSR).
Although many research achievements have been obtained in QSR, some problemshave not been solved yet. The researches on QSR integrating multi-aspect spatialinformation are being paid more and more attention by scholars, because it is very rareto deal with only one aspect of spatial information in practice. Some researcher has everstudied on the QSR integrating topology and direction information based on intervalcalculus. The cardinal direction model proposed by Goyal and Egenhofer considers thereal shape of the primary spatial object, which leads to strong expressivity and favorableproperties of computing and reasoning. But the techniques of QSR combining Goyal andEgenhofer's cardinal direction model and topological model have not been given enough
studies. In the QSR research field, the research on direction relations between fuzzyregions is much less compared to topological relation between fuzzy regions, while thefuzziness in real world is pervasive. Spatio-temporal reasoning research relatedintimately to QSR is becoming a hot topic, which has triggered many problems aboutrepresentation and reasoning. This thesis focuses on a particular problem inspatio-temporal reasoning. The theoretical and practical researches on QSR are equallyimportant. This thesis carries out research on the algorithms in two typical applications,i.e. spatial configuration information retrieval and spatial data mining, which arepotential applications in GIS and other spatial information systems.The goals of this thesis are to develop QSR algorithms and investigate thecomputational properties combining the spatial topological calculus RCC8 and cardinaldirection calculus, to analyze the deficiency of Goyal and Egenhofer's cardinal directionmodel and provide a quantitative computational model handling cardinal directionsbetween both crisp and fuzzy regions, to investigate the conceptual neighborhoodproblem related to motion continuity in spatio-temporal reasoning and introduce thegeneralized conceptual neighborhood graph and the algorithm, to investigate the spatialconfiguration retrieval methods, to develop the scheme of retrieval considering thetopological and cardinal direction relations and the efficient retrieval algorithmsevaluated by some experiments, to investigate the spatial data mining techniques andprovide a new method.The major contributions, ideas and research results included in the thesis are asfollows:Firstly, Research on QSR techniques combining RCC8 and cardinal directioncalculus based on region.To combine the two calculi, we must consider the interaction between them.Because the number of cardinal direction relations based on region is 512, it's notrealistic to investigate the composition tables of the two calculi and the interaction rulesshould be considered which can be used by a computer program to generate compositiontables. Based on the semantics of RCC8 and cardinal direction calculus based on region,the interaction rules are derived. This thesis regard QSR as a special form of ConstraintSatisfaction Problems (CSPs): Qualitative Spatial Constraint Satisfaction Problems(QS-CSPs), whose domains are infinite. So the methods handling CSPs with infinitedomains can be applied. We define the consistency deciding problem and consistentscenarios problems, which are critical in QS-CSPs. We introduce the path consistencyconcept and the path consistency algorithm related to consistency deciding. Therelationship between path consistency and global consistency is also given. The solvingmethods of CSPs with infinite domains are described and the research results oncomputational properties achieved in RCC8 and cardinal direction calculus based onregion are outlined. In RCC8, three maximal tractable subsets whose consistency
deciding problem can be determined by path consistency algorithm are identified;In thecardinal direction calculus based on region, the algorithm solving the consistencydeciding problem based on constraint set consisting of basic cardinal direction relationsis worked out.This thesis designs a path consistency algorithm handling the CSPs combiningRCC8 and cardinal direction relations. Generally, path consistency algorithm operateswithin a CSP, but it should be extended to communicate interactions between RCC8component and cardinal direction component. To ensure the respective path consistencyof RCC8 component and cardinal direction component in a CSP that includes RCC8relations and cardinal direction relations and implement the interactions between them,our new algorithm uses two queues, which maintain two kinds of constraint relationsrespectively. Our algorithm pick out a constraint relation from one of the two queues inturn and this constraint relation affect not only the constraint relations within its queue,but also the constraint relations in the other queue according to the interaction rules. Thealgorithm doesn't terminate until the two queues are all empty or the empty constraintrelation is derived. The computational complexity of our algorithm does not improvemuch compared to traditional path consistency algorithm. A simple exampledemonstrates that the idea of combining RCC8 and cardinal direction calculus and theproposed new algorithm are very useful.Based on the achievements on the computational properties of RCC8 and cardinaldirection calculus based on region, this thesis analyzes the computational complexity ofthe CSPs combining RCC8 and cardinal directional relations based on differentconstraint subsets and concludes that the computational complexity of the consistencydeciding problem of the CSPs based on the constraint set composed of any maximaltractable subset in RCC8 and basic cardinal directional relations is still polynomialthough a little higher. The analysis on the computational complexity is very importantbecause the analysis results can guide us to design correct and efficient consistencydeciding algorithms. For CSPs whose constraint relations are not based on the tractableconstraint subsets, path consistency algorithm cannot decide its consistency problem,because path consistency is necessary but not enough condition for global consistency ofa CSP. So we must have a comprehensive algorithm deciding the consistency problemof CSPs based on any constraint set. The thesis designs a comprehensive consistencydeciding algorithm for CSPs combining RCC8 and cardinal direction relations. Thealgorithm uses aforementioned path consistency algorithm for pruning, and if the pathconsistency algorithm is run using tractable subsets, the efficiency of the comprehensivealgorithm can be improved.The research ideas and approaches used for combining RCC8 and cardinal directioncalculus can be generalized to the QSR combining other spatial aspects. The research onthe QSR techniques is very meaningful to GIS, computer vision and robot navigation,
etc.Secondly, Modeling cardinal directions between fuzzy regions based onfuzzy-morphology.Traditional cardinal direction model based on region approximate reference regionusing Minimum Bounding Rectangle (MBR), which leads that the model cannot identifythe correct cardinal directions in some cases. For example, a region A does not overlapwith another region B, but located in the convex hull of region B. The dilation operationin mathematics morphology can handle these cases naturally. This thesis defines acomputational model using the dilation operation in mathematics morphology andappropriate structure element, and illustrates that this new model can complement thedeficiency in current model through some examples. Our work does not discard thecurrent model, but a refinement of it, because the current cardinal direction model basedon region has a favorable property of qualitative reasoning.Traditionally, most of the spatial data models assume that the extent of the spatialobject, i.e. the boundary of it, is exactly defined and extensively acknowledged. Thiskind of model is crisp spatial model. Researchers are realizing that many spatial objectshave not crisp boundaries, or the boundaries cannot be exactly identified in the realworld. This thesis combines fuzzy set theory and mathematics morphology theory tomodel the cardinal direction relations between fuzzy regions. A fuzzy region is regardedas a set composed of a finite (or infinite) number of crisp regions, and each crisp regionis assigned a probability value that it is the “true” representative of the whole fuzzyregion. For any two fuzzy regions, each pair of crisp regions in the sets can be workedout the cardinal direction relation using the aforementioned computational model basedon mathematics morphology and all the resulting cardinal direction relations areaggregated using a special schema. After comparing the two models, i.e. the modelhandling the crsp regions and the model handling the fuzzy regions, we conclude that thefuzzy model can be reduced to the crisp model when handling crisp regions, i.e. weprovide a uniform computational model handling cardinal direction relations betweenregions quantitatively.The computational model of this thesis can deal with both the continuous anddiscrete space, and the approaches handling cardinal direction relations between fuzzyregions can be applied to other spatial models. The experiment results confirm thecognitive plausibility of our computational models.Thirdly, Research on generalized conceptual neighborhood graph inspatio-temporal reasoning.The simple integration of space and time is not enough in spatio-temporal datamanagement. This thesis introduces a spatio-temporal model taking space-time historiesof objects as primitive entities, the topology of space-time, temporal order, and spacerelations. The concepts of time slice and spatio-temporal continuity are presented. Based
on spatio-temporal continuity and time slice, spatial conceptual neighborhood isredefined. When we want to judge whether a spatio-temporal scenario can betransformed to another spatio-temporal scenario under the condition of spatio-temporalcontinuity, the traditional spatial conceptual neighborhood graph is not applicable. Sothis thesis presents the concept of generalized conceptual neighborhood graph, andproposes the computational method. The algorithm is computationally expensive. Thegeneralized conceptual neighborhood graph can be applied to spatio-temporal reasoning,especially consistency checking.Fourthly, Research on spatial configuration information retrieval algorithms.Spatial configuration information retrieval has potential applications in many fields,such as GIS, Multimedia database, Computer vision and VLSI (Very Large ScaleIntegration), etc. This thesis regards the spatial configuration retrieval problems as CSPswith finite domains, which are different from the aforementioned QS-CSPs based oninfinite domains. So the traditional algorithms for CSPs can be applied. This thesidefines the formulas computing the inconsistency degree and similarity degree, whichare used by the retrieval algorithms.In real applications, spatial regions often have complex geometric shapes. If wecompute the spatial relations between them directly, the expense will be very large andsometimes expensive computations will result in nothing. If we use MBR toapproximate the real shapes of the regions, the computational expense will be greatlyreduced because only the spatial relations between rectangles are calculated. Theretrieval of spatial configurations can be divided into two steps: first, the combinationsof rectangles which are not possible to satisfy the query conditions are eliminated;second, the combinations of real spatial objects corresponding to the remainingcombinations of rectangles are calculated using computational geometry techniques tocheck if they satisfy the query conditions. The thesis presents the method for computingthe inconsistency degree between two spatial relations through encoding spatial relationsbetween two rectangles as two binary strings along the horizontal and vertical axes. Thesimilarity degree is calculated according to the conceptual neighborhood graph ofinterval calculus.The thesis outlines search algorithms which can solve spatial configurationinformation retrieval problems, and designs four systematic search algorithms, i.e.SFC-DVOSolver which combines forward checking and dynamic variable ordering usedto solve traditional CSPs, RSFC-DVOSolver which is based on SFC-DVOSolver butemploys R-tree to accelerate pruning in forward checking, HRSFC-DVOSolver which isbased on RSFC-DVOSolver and uses hash index technique to accelerate rectanglematching process, RMLSFC-DVOSolver which combines R-tree and SFC-DVOSolverto realize constraint solving level by level. To implement the algorithms using R-tree,this thesis investigates the mapping relationship between spatial relations (including
topological and cardinal direction relations) of spatial objects and spatial relations oftheir MBRs, and the mapping relationship between spatial relations (includingtopological and cardinal direction relations) of intermediate nodes in R-tree and spatialrelations of the MBRs.Through experiments, this thesis concludes that algorithms SFC-DVOSolver andHRSFC-DVOSolver are the feasible ones for solving spatial configuration retrievalproblems, and fixes on the parameters of the two algorithms and the conditions underwhich the two algorithms can be applicable. If the constraint power of the querycondition is weak, the algorithm SFC-DVOSolver should be used;if the constraintpower is normal or strong, the algorithm HRSFC-DVOSolver is better. The judgment ofthe constraint power of the query condition should be based on the knowledge base, andthen we can decide to use SFC-DVOSolver or HRSFC-DVOSolver.When the number of query variable is large (usually larger than 20) or the spatialdata volume is very large (usually larger than one hundred and thousand), the systematicalgorithms will not be applicable and the local search algorithms or other optimizationalgorithms. The research on spatial configuration retrieval algorithms is valuable to theapplication systems related to spatial data.Fifthly, Research on spatial data mining techniques.Spatial Data Mining (SDM) is to abstract the implicit knowledge, spatial relationsor other meaningful patterns in spatial databases. The main difference SDM has from thetraditional data mining is that SDM considers not only the non-spatial attributes, but alsothe spatial attributes. For the problem of multi-layer (or multi-thematic) spatial datamining, we propose a multi-relational aggregation operator and an algorithm frame forspatial data mining based on this operator. The algorithm derives a relation table fromthe spatial data information (including spatial and non-spatial information) related toseveral layers. Then the traditional data mining techniques based on relational databasecan be directly applied. The algorithm can define spatial predicates according to actualneeds. We apply this frame to a real spatial data classification problem, which runsefficiently and achieves good classification results.To sum up, the study results of this thesis are of both theoretical and practicalbenefit to further researches in qualitative spatial reasoning, fuzzy spatial reasoning,spatio-temporal reasoning, spatial information retrieval, spatial data mining andgeographic information system.
引文
[1]. Bernd Jahne, Horst Hau?ecker, and Peter Gei?ler, editors. Handbook Of Computer Vision and Applications. Academic Press, Boston, USA, 1999.
[2]. Franco P. Preparata and Michael I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, Berlin, Heidelberg, New York, 1991.
[3]. Jean-Claude Latombe. Robot Motion Planning. Kluwer, Dordrecht, Holland, 1991.
[4]. Weld, D.S., De Kleer, J. (eds.) Reading in Qualitative Reasoning About Physical Systems, Morgan Kaufman, San Mateo, Ca, 1990.
[5]. Anthony G. Cohn. Qualitative spatial representations. In: Working notes of IJCAI'99 workshop on Adaptive Spatial Representations of Dynamic Environments, 1999, pages 33–52.
[6]. Daniel Hernandez. Qualitative Representation of Spatial Knowledge, Lecture Notes in Artificial Intelligence 804, Springer-Verlag, Berlin, Heidelberg, New York, 1994.
[7]. J. Renz. Qualitative Spatial Reasoning with Topological Information, LNAI 2293, 2002.
[8]. B. Faltings. Qualitative Spatial Reasoning Using Algebraic Topology. In Proceedings of COSIT-95, volume 988 of LNCS, 1995, pages 17-30.
[9]. A.U. Frank. Qualitative Spatial Reasoning about Distances and Directions in Geographic Space. Journal of Visual Languages and Computing, 1992, 3:343–371.
[10]. C. Freksa. Using Orientation Information for Qualitative Spatial Reasoning. In: Proceedings of COSIT-92, LNCS 639, 1992, pages 162–178.
[11]. Yao, X., Thill, J.C. Spatial Queries With Qualitative Locations In Spatial Information Systems. Computers, Environment and Urban Systems. 2005 (In Press). http://www.ggy.uga.edu/people/faculty/xyao/QL05.pdf
[12]. Bergman, L. Castelli, V., Li C-S. Progressive Content-Based Retrieval from Satellite Image Archives. D-Lib Magazine, October 1997. http://www.dlib.org/dlib/october97/ibm/10li.html.
[13]. Chang S.F, Smith J.R., Meng H.J, Wang H., Zhong D. Finding Images/Video in Large Archives. CNRI Digital Library Magazine, Feb. 1997. http://www.dlib.org/dlib/december02/marchionini/12marchionini.html.
[14]. Gupta A., Jain R. Visual Information Retrieval. Communications of ACM, May 1997, 40(5): 70-79.
[15]. K. Koperski, J. Han and N. Stefanovic. An Efficient Two-Step Method for Classification of Spatial Data. Proc. Int. Symp. on Spatial Data Handling, Vancouver, BC, Canada, July 1998, pages 45-54.
[16]. Quinlan J. R. Induction of Decision Trees. Machine Learning, 1986, 1:81-106.
[17]. Alessandra Raffaetà, Franco Turini, Chiara Renso. Enhancing GISs for spatio-temporal reasoning. In: Proceedings of the 10th ACM international symposium on Advances in geographic information systems, ACM-GIS 2002, pages 42-48.
[18]. Tate, A., Hendler, J. and Drummond, M. A review of AI Planning Techniques. In Readings in Planning, J. Allen, J. Hendler, and A. Tate. (eds): Morgan Kaufmann Publishers, 1990, pages 26-49.
[19]. Fernyhough, J., Cohn, A G;Hogg, D C. Constructing qualitative event models automatically from video input. Image and Vision Computing, 2000, 18: 81-103.
[20]. M. Egenhofer and D. Mark. Naive Geography. COSIT '95, Semmering, Austria A. Frank and W. Kuhn (eds.), Lecture Notes in Computer Science, Vol. 988, Springer-Verlag, September 1995, pages 1-15.
[21]. M. Egenhofer. Query Processing in Spatial-Query-by-Sketch. Journal of Visual Languages and Computing, 1997, 8(4): 403-424.
[22]. B. Kuipers and Y.T. Byun. A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations. Journal of Robotics and Autonomous Systems, 1991, 8:47-63.
[23]. Faltings, B. Qualitative Spatial Reasoning Using Algebraic Topology. In: A. U. Frank and W. Kuhn (eds.), Spatial Information Theory: A Theoretical Basis for GIS, Proceedings of COSIT'95, LNCS 988, 1995, pages 17-30.
[24]. A. Mukerjee. Neat vs scruffy: A survey of computational models for spatial expressions. P. Oliver and K-P Gapp (eds.) Representation and Processing of Spatial Expressions, Kluwer, 1998.
[25]. Guarino, N., &Giaretta, P. Ontologies and knowledge bases: towards a terminological clarification. In N. Mars (Ed.), Towards very large knowledge bases. Amsterdam: IOS Press. 1995, pages 25-32.
[26]. P. Simons. Parts: A Study in Ontology. Clarendon Press, Oxford, 1987.
[27]. Vieu, L. Spatial Representation and Reasoning in Artificial Intelligence. In: O. Stock (ed.) Spatial and Temporal Reasoning. Dordrecht: Kluwer, 1997, pages 5-41.
[28]. A. G. Cohn, B. Bennett, J. M. Gooday and N. M. Gotts. Representing and Reasoning with Qualitative Spatial Relations about Regions. O. Stock (ed.) Temporal and spatial reasoning, Kluwer, 1997, pages 97-134.
[29]. A. G. Cohn, B. Bennett, J. M. Gooday and N. M. Gotts. RCC: a calculus for Region based Qualitative Spatial Reasoning. GeoInformatica, 1997, 1: 275-316.
[30]. N. M. Gotts, J. M. Gooday and A. G. Cohn. A connection based approach to commonsense topological description and reasoning. The Monist, 1996, 79 (1): 51-75.
[31]. Pratt, I. and O. Lemon. Ontologies for plane, polygonal mereotopology. Notre Dame Journal of Formal Logic, 1997, 38(2): 225-245.
[32]. M. Egenhofer and J. Sharma. Topological Relations Between Regions in R2 and Z2. In: D. Abel and B.C. Ooi (eds.), Advances in Spatial Databases-Third International Symposium on Large Spatial Databases, SSD'93, Singapore, LNCS 692, Springer-Verlag, 1993, pages 316-336.
[33]. N. M. Gotts. Using the RCC Formalism to Describe the Topology of Spherical Regions. Report 96.24, School of Computer Studies, University of Leeds, 1996.
[34]. Antony Galton. The Mereotopology of Discrete Space. In: C. Freksa and D. M. Mark (eds.), Spatial Information Theory: Cognitive and Computational Foundations of Geographic Science, Proceedings of the International Conference COSIT'99, LNCS 1661, Springer, 1999, pages 251-266.
[35]. Masolo, Claudio and Laure Vieu. Atomicity vs. Infinite Divisibility of Space. In: C. Freksa and D. Mark (eds.), Spatial Information theory. Proceedings of COSIT'99. Berlin: Springer Verlag, LNCS 1661, 1999, pages 235-250.
[36]. P. Hayes. Naive physics manifesto. In: D. Michie (ed.), Expert Systems in the Microelectronic Age. Edinburgh University Press, 1979.
[37]. Walischewski, H. Learning regions of interest in postal automation. In: Proc. 5th Intl. Conf. on Document Analysis and Recognition (ICDAR'99), Bangalore, India, 1999, pages 317-320.
[38]. Clarke, B. L. A calculus of individuals based on “connection”. Notre Dame Journal of Formal Logic, 1981, 22: 204-218.
[39]. D. A. Randell and A. G. Cohn. Modelling Topological and Metrical Properties in Physical Processes. In: Proc.of 1st International Conference on the Principles of Knowledge Representation and Reasoning. Morgan Kaufmann, Los Altos, 1989, pages 55-66.
[40]. D. A. Randell, Z. Cui and A. G. Cohn. A Spatial Logic Based on Regions and Connection. In: Proc. 3rd Int. Conf. on Knowledge Representation and Reasoning, Morgan Kaufmann, San Mateo, 1992, pages 165-176.
[41]. M. Egenhofer and R. Franzosa, Point-Set Topological Spatial Relations. International Journal of Geographical Information Systems, 1991, 5(2): 161-174.
[42]. Max J. Egenhofer. Reasoning about binary topological relations. In: O. Gunther and H. J. Schek (eds), Proceedings of the Second Symposium on Large Spatial Databases, SSD'91, LNCS 525, Springer-Verlag, Berlin, Heidelberg, New York, 1991, pages 143–160.
[43]. Brandon Bennett. Spatial reasoning with propositional logic. In: J. Doyle, E. Sandewall, and P. Torasso (eds), Principles of Knowledge Representation and Reasoning, Proceedings of the 4th International Conference, Bonn, Germany, May 1994. Morgan Kaufmann, pages 51–62.
[44]. Brandon Bennett. Modal logics for qualitative spatial reasoning. Bulletin of the IGPL, 1996,4(1): 23–45.
[45]. 陆钟万. 面向计算机科学的数理逻辑. 北京: 科学出版社, 2002.
[46]. J. Renz, B. Nebel. On the Complexity of Qualitative Spatial Reasoning: A Maximal Tractable Fragment of the Region Connection Calculus. Artificial Intelligence (AIJ), 1999, 108(1-2): 69-123.
[47]. J. Renz. Maximal Tractable Fragments of the Region Connection Calculus: A Complete Analysis. In: Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI'99), Stockholm, Sweden, August 1999, pages 448-455.
[48]. Max J. Egenhofer, Eliseo Clementini, and Paolino Di Felice. Topological relations between regions with holes. International Journal of Geographical Information Systems, 1994, 8(2):129–144.
[49]. C. Schlieder. Representing visible locations for qualitative navigation. In: Qualitative Reasoning and Decision Technologies: CIMNE, 1993, pages 523-532.
[50]. C. Schlieder. Qualitative shape representation. In: P. Burrough and AM Frank, editors, Proceedings of GISDATA Specialist Meeting on Geographical Objects with Undetermined Boundaries. Francis Taylor, 1996.
[51]. R. R?hrig, Representation and processing of qualitative orientation knowledge. In: Proc. KI: German Annual Conference on Artificial Intelligence, Lecture Notes in Artificial Intelligence, Vol. 1303, Springer, Berlin, 1997, pages 219–230.
[52]. A. Isli and A. G. Cohn. A new approach to cyclic ordering of 2D orientations using ternary relation algebras. Artificial Intelligence, 2000, 122 (1-2): 137-187.
[53]. Andrew U. Frank. Qualitative spatial reasoning about cardinal directions. In: Proceedings of the 7th Austrian Conference on Artificial Intelligence, 1991, pages 157–167.
[54]. Marc B. Vilain and Henry A. Kautz. Constraint propagation algorithms for temporal reasoning. In: Proceedings of the 5th National Conference of the American Association for Artificial Intelligence, Philadelphia, PA, August 1986, pages 377–382.
[55]. Gerard Ligozat. Reasoning about cardinal directions. Journal of Visual Languages and Computing, 1998, 9:23–44.
[56]. Zimmermann, K. and Freksa, C. Qualitative spatial reasoning using orientation, distance, path knowledge. Applied Intelligence, 1996, 6: 49-58.
[57]. Alexander Scivos and Bernhard Nebel. Double-crossing is harmful: First results on formal properties of a qualitative calculus for navigation. Unpublished manuscript, 1999.
[58]. Julio Pacheco, M. Teresa Escrig and Francisco Toledo. Qualitative Spatial Reasoning on Three-Dimensional Orientation Point Objects. Sixteenth International Workshop on Qualitative Reasoning QR2002, June 10-12, 2002.
[59]. Hans Guesgen. Spatial reasoning based on Allen's temporal logic. Technical Report TR-89-049, ICSI, Berkeley, CA, 1989.
[60]. Dimitris Papadias and Yannis Theodoridis. Spatial relations, minimum bounding rectangles, and spatial data structures. International Journal of Geographic Information Systems, 1997, 11(2):111–138.
[61]. James F. Allen. Maintaining knowledge about temporal intervals. Communications of the ACM, November 1983, 26(11): 832-843.
[62]. Philippe Balbiani, Jean-Francois Condotta, and Luis Farinas del Cerro. A model for reasoning about bidimensional temporal relations. In: A.G. Cohn, L. Schubert, and S.C. Shapiro (eds), Proc. of the 6th Int. Conf. On Principles of Knowledge Representation and Reasoning, 1998, pages 124–130.
[63]. Philippe Balbiani, Jean-Francois Condotta, and Luis Farinas del Cerro. A new tractable subclass of the rectangle algebra. In: Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, 1999, pages 442–447.
[64]. R. Goyal and M. Egenhofer. Cardinal Directions between Extended Spatial Objects. IEEE Transactions on Knowledge and Data Engineering, 2000(in press).
[65]. S. Skiadopoulos and M. Koubarakis. Consistency Checking for Qualitative Spatial Reasoning with Cardinal Directions. In: Proceedings of the 7th International Conference on Principles and Practice of Constraint Programing (CP'02), LNCS, Vol.2470, Springer, Berlin, 2002, pages 341-356.
[66]. S. Skiadopoulos and M. Koubarakis. Composing Cardinal Direction Relations. Artificial Intelligence, 2004, 152(2): 143-171.
[67]. S.Cicerone and P. Di Felice. Cardinal directions between spatial objects: the pairwise-consistency problem. Information Sciences. 2004, 164(1-4): 165-188.
[68]. Daniel Hernandez, Eliseo Clementini, and Paolino di Felice. Qualitative distances. In: Spatial Information Theory: A Theoretical basis for GIS, LNCS 988, Springer-Verlag,1995,pages 45–58.
[69]. Eliseo Clementini, Paolino di Felice, and Daniel Hernandez. Qualitative representation of positional information. Artificial Intelligence, 1997, 95(2):317–356.
[70]. A U Frank. Qualitative spatial reasoning about distances and directions in geographic space. Journal of Visual Languages and Computing, 1992, 3:343-371.
[71]. Amar Isli and Reinhard Moratz. Qualitative spatial representation and reasoning: Algebraic models for relative position. Technical Report 284, University at Hamburg, Fachbereich Informatik, 1999.
[72]. A. Pauly and M. Schneider. Vague Spatial Data Types, Set Operations, and Predicates. In: 8th East-European Conf. on Advances in Databases and Information Systems, 2004, pages 379–392.
[73]. 胡宝清. 模糊理论基础. 武汉:武汉大学出版社, 2004.
[74]. M. Worboys. Computation with Imprecise Geospatial Data. Computational, Environmental and Urban Systems, 1998, 22(2): 85–106.
[75]. E. Clementini and P. Di Felice. An Algebraic Model for Spatial Objects with Indeterminate Boundaries. In: Burrough PA, Frank AU (eds). Geographic Objects with Indeterminate Boundaries, 1996, pages 153–169.
[76]. A. G. Cohn and N. M. Gotts. The ‘Egg-Yolk' Representation of Regions with Indeterminate Boundaries. In: Burrough PA, Frank AU (eds.), Geographic Objects with Indeterminate Boundaries, 1996, pages 171–187.
[77]. M. Schneider. A Design of Topological Predicates for Complex Crisp and Fuzzy Regions. In: Int. Conf. on Conceptual Modeling, LNCS 2224,2001, pages 103-116.
[78]. 熊金城. 点集拓扑讲义. 北京:高等教育出版社, 2003.
[79]. Alejandro Pauly and Markus Schneider. Topological Predicates Between Vague Spatial Objects. In: Claudia Bauzer Medeiros, Max J. Egenhofer, Elisa Bertino (Eds.): Advances in Spatial and Temporal Databases, 9th International Symposium, SSTD 2005, LNCS 3633, 2005, pages 418–432.
[80]. F.B. Zhan. Approximate analysis of binary topological relations between geographic regions with indeterminate boundaries. Soft Computing, Springer-Verlag, 1998, 2: 28-34
[81]. Christophe Claramunt, Marius Thériault. Fuzzy semantics for direction relations between composite regions. Information Sciences. 2004, 160: 73-90.
[82]. Subasic, P. and Huettner, A. Affect Analysis of Text Using Fuzzy Semantic Typing, IEEE Transactions on Fuzzy Systems. 2001, 9(4): 483-496.
[83]. Girish Keshav Palshikar. Fuzzy region connection calculus in finite discrete space domains. Applied Soft Computing. 2004, 4: 13-23.
[84]. Jan Terje Bj?rke. Topological relations between fuzzy regions: derivation of verbal terms. Fuzzy Sets and Systems. 2004, 141:449-467.
[85]. Serafino Cicerone, Paolino Di Felice. Cardinal relations between regions with a broad boundary. In: Proceedings of the 8th ACM international symposium on Advances in geographic information systems, ACM Press, 2000, pages 15-20.
[86]. R Rohrig. A theory for qualitative spatial reasoning based on order relations. In: Proceedings of the 12th National Conference on AI, volume 2, Seattle, 1994, pages 1418-1423.
[87]. C. Schlieder. Reasoning about Ordering. In: A. U. Frank and W. Kuhn (eds.), Spatial Information Theory: A Theoretical Basis for GIS. LNCS 988, 1995, pages 341-350.
[88]. Vilain, M. and Kautz, H. Constraint Propogation Algorithm for Temporal Reasoning. In: Proc. 5th American Conf. on AI (AAAI-86), Philadelphia, 1986, pages 377-382.
[89]. B. Bennett, A. Isli and A. G. Cohn. When does a Composition Table Provide a Complete and Tractable Proof Procedure for a Relational Constraint Language? In: Proceedings of the IJCAI-97 workshop on Spatial and Temporal Reasoning, Nagoya, Japan, 1997.
[90]. Li SJ, Ying MS. Region connection calculus: Its models and composition table. Artificial Intelligence, 2003,145(1-2): 121-146.
[91]. Jochen Renz, Gérard Ligozat. Weak Composition for Qualitative Spatial and Temporal Reasoning. CP 2005, LNCS 3709, pages 534-548.
[92]. Alan K. Mackworth. Constraint satisfaction. In: S.C. Shapiro (ed.), Encyclopedia of Artificial Intelligence, Wiley, Chichester, England, 1987, pages 205-211.
[93]. Peter B. Ladkin and Roger Maddux. On binary constraint problems. Journal of the Association for Computing Machinery, May 1994, 41(3): 435–469.
[94]. Alfred Tarski. On the calculus of relations. Journal of Symbolic Logic, 1941, 6: 73–89.
[95]. Robin Hirsch. A finite relation algebra with undecidable network satisfaction problem. Bulletin of the IGPL, 1999, 7: 547-554.
[96]. Alan K. Mackworth. Consistency in networks of relations. Artificial Intelligence, 1977, 8: 99–118.
[97]. Ugo Montanari. Networks of constraints: fundamental properties and applications to picture processing. Information Science, 1974, 7: 95–132.
[98]. Alan K. Mackworth and Eugene C. Freuder. The complexity of some polynomial network consistency algorithms for constraint satisfaction problems. Artificial Intelligence, 1985, 25: 65–73.
[99]. Peter van Beek. Reasoning about qualitative temporal information. Artificial Intelligence, 1992, 58(1-3): 297–321.
[100]. B Nebel. Reasoning about temporal relations: a maximal tractable subset of Allen's interval algebra. Journal of the Association for Computing Machinery, January 1995, 42(1): 43-66.
[101]. Peter B. Ladkin and Alexander Reinefeld. Effective solution of qualitative interval constraint problems. Artificial Intelligence, September 1992, 57(1): 105–124.
[102]. Sebastian Brand. Relation Variables in Qualitative Spatial Reasoning. In: S. Biundo, T. Fr¨uhwirth, and G. Palm (Eds.): Proc. Of KI 2004, LNAI 3238, 2004, pages 337–350.
[103]. 王生生,刘大有,谢 琦,王新颖.集成多方面信息的定性空间推理及应用.软件学报,2003,14(11): 1857-1862.
[104]. A. Gerevini, J. Renz. Combining Topological and Size Constraints for Spatial Reasoning. Artificial Intelligence (AIJ), 2002, 137(1-2): 1-42.
[105]. A Isli, V Haarslev and R M?ller. Combining cardinal direction relations and relative orientation relations in Qualitative Spatial Reasoning. Technical report FBI-HH-M-304/01, Fachbereich Informatik, Universit?t Hamburg, 2001.
[106]. Peter van Beek and Robin Cohen. Exact and approximate reasoning about temporal relations. Computational Intelligence, 1990, 6:132–144.
[107]. P. Muller. Topological spatio-temporal reasoning and representation. Computational Intelligence. 2002, 18(3): 420–450.
[108]. F. Wolter and M. Zakharyaschev. Spatio-temporal representation and reasoning based on RCC-8. In: A. Cohn, F. Giunchiglia, and B. Selman (eds.), Principles of Knowledge Representation and Reasoning, Proceedings of the 7th International Conference (KR2000). Morgan Kaufmann, 2000, pages 3-14.
[109]. Z. Manna and A. Pnueli. The temporal logic of reactive and concurrent systems. Springer-Verlag, Berlin, Heidelberg, New York, 1992.
[110]. B. Bennett. Modal logics for qualitative spatial reasoning. Journal of the Interest Group on Pure and Applied Logic, 1996, 4(1): 23–45.
[111]. A. Gerevini and B. Nebel. Qualitative spatio-temporal reasoning with RCC-8 and Allen's interval calculus: Computational complexity. In: Proceedings of the 15th European Conference on Artificial Intelligence (ECAI-02), IOS Press, 2002, pages 312–316.
[112]. B. Bennett, A. G. Cohn, F. Wolter, and M. Zakharyaschev. Multi-dimensional modal logic as a framework for spatio-temporal reasoning. Applied Intelligence, 2002, 17(3): 239–251.
[113]. Guttman, A. R-trees: A Dynamic Index Structure for Spatial Searching. In: Proc. Of ACM SIGMOD, 1984, pages 47-57.
[114]. Roussopoulos, N., Kelley, F., Vincent, F. Nearest Neighbor Queries. In: Proc. Of ACM SIGMOD, 1995,pages 71-79.
[115]. Papadias, D., Theodoridis, Y., Sellis, T., Egenhofer, M. Topological Relations in the World of Minimum Bounding Rectangles: A study with R-trees. In: Proc. Of ACM SIGMOD, 1995,pages 92-103.
[116]. Rotem, D. Spatial Join Indices. In: Proceedings of the seventh International Conference on Data Engineering, 1991, pages 500-509.
[117]. Guenther, O. Efficient computation of spatial joins. In: Proceedings of the Ninth International Conference on Data Engineering, 1993, pages 50-59.
[118]. Brinkhoff, T., Kriegel, H. P., Seeger, B. Efficient processing of spatial joins using Rtrees. In: Proc. of the ACM-SIGMOD Conference on Management of Data, 1993,pages 237-246.
[119]. Blockeel, H., De Raedt, L. Top-down induction of first order logical decision trees. Artificial Intelligence, June 1998, 101(1-2): 285-297.
[120]. Blockeel, H., De Raedt, L., Ramon, J. Top-down induction of clustering trees. In Proceedings of the 15th International Conference on Machine Learning (ICML'98), 1998, pages 55-63.
[121]. J. Knobbe, H. Blockeel, A. Siebes, and Van der Wallen D. Multi-relational decision tree induction. In Proceedings of the 3rdEuropean Conference on Principles and Practice of Knowledge Discovery in Databases, PKDD99, Springer-Verlag, 1999, pages 378-383.
[122]. Krzysztof Koperski, Jiawei Han. Discovery of Spatial Association Rules in Geographic Information Databases. In Proc. 4th International Symposium Of Advances in Spatial Databases, 1995, pages 47-66.
[123]. Martin Ester, Hans-Peter Kriegel, J?rg Sander, Xiaowei Xu. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, AAAI Press, 1996, pages 226-231.
[124]. W. Lu, J. Han and B. C. Ooi. Discovery of General Knowledge in Large Spatial Databases, Proc. Far East Workshop on Geographic Information Systems, Singapore, June 1993, pages 275-289.
[125]. R. Ng and Y. Yu. Discovering Strong, Common and Discriminating Characteristics of Clusters from Thematic Maps. Proceedings of the Eleventh Annual Symposium on Geographic Information Systems, 1997, pages 392-394.
[126]. Ester M., Kriegel H.P., Sander J. Spatial Data Mining: A Database Approach. In: Proc. of the 5th Symposium on Spatial Databases, Lecture Notes in Computer Science, 1262. Berlin, Germany, 1997, pages 47-66.
[127]. J. Sharma. Integrated spatial reasoning in geographic information systems: combining topology and direction. Ph.D. Thesis, Department of Spatial Information Science and Engineering, University of Maine, Orono, ME, 1996.
[128]. 尤承业. 基础拓扑学讲义. 北京大学出版社, 1997.
[129]. M. Egenhofer. A Formal Definition of Binary Topological Relationships. In: Proc. of Third International Conference on Foundations of Data Organization and Algorithms (FODO), Paris, France, 1989, LNCS 367, pages 457-472.
[130]. Bennett, B. Determining consistency of topological relations. Constraints, 1998, 3: 213-225.
[131]. Clementini E. and P.D. Felice. A Comparison of Methods for Representing Topological Relationships. Information Sciences, 1995, 3 (3): 149-178.
[132]. 李成名,陈军. 空间关系描述的 9-交模型. 武汉测绘科技大学学报,1997, 22(2):207-211.
[133]. Clementini E, Di Felice P, Van Oosterom P. A small set of formal topological relationships suitable for end-user interaction. In: Abel D, Ooi BC (eds.), Advances in Spatial Databases, the 3rd International Symposium, SSD'93. LNCS 692, Berlin: Springer-Verlag, 1993, pages 277-295.
[134]. Randell, D. A., Cohn, A. G., and Cui, Z. Computing transitivity tables: A challenge for automated theorem provers. In: Kapur, D. (ed.), Proceedings of the 11th International Conference on Automated Deduction (CADE-11), LNAI 607, Saratoga Springs, NY. Springer, 1992, pages 786-790.
[135]. A. Prasad Sistla, Clement T. Yu and R. Haddad. Reasoning About Spatial Relationships in Picture Retrieval Systems. In: Proceedings of 20th International Conference on Very Large Data Bases, Morgan Kaufmann, 1994, pages 570-581.
[136]. D. Papadias, N. Arkoumanis, and N. Karacapilidis. On The Retrieval of Similar Configurations. In: Proceedings of 8th International Symposium on Spatial Data Handling (SDH),1998, pages 510-521.
[137]. Michelangelo Grigni, Dimitris Papadias, and Christos Papadimitriou. Topological inference. In: C.Mellish, editor, Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI), volume 1, Morgan kaufmann,1995, pages 901-906.
[138]. Peter Ladkin and Alexander Reinefeld. Fast Algebraic Methods for Interval Constraint Problems. Invited Paper in Annals of Mathematics and Artificial Intelligence, 1997, 19:383-411.
[139]. Yu Liu, Xiaoming Wang, Xin Jin, Lun Wu. On Internal Cardinal Direction Relations. In: Proc. Of Spatial Information Theory, International Conference, COSIT 2005, LNCS 3693, pages 283-299.
[140]. Markus Schneider. Uncertainty Management for Spatial Data in Databases: Fuzzy Spatial Data Types. In: R.H.Guting, et al. (Eds.): SSD'99, LNCS 1651, 1999, pages 330-351.
[141]. Isabelle Bloch. Fuzzy Spatial Relationships from Mathematical Morphology for Model-based Pattern Recognition and Spatial Reasoning, In: I. Nystrom et al. (Eds) : DGCI 2003, LNCS 2886, 2003, pages 16-33.
[142]. Isabelle Bloch. Unifying Quantitative, Semi-quantitative and Qualitative Spatial Relation knowledge Representation Using Mathematical Morphology, In: T.Asano et al. (Eds): Geometry, Morphology, and Computational Imaging, 11th International Workshop on Theoretical Foundations of Computer Vision Dagstuhl Castle, Germany, April 7-12, 2002, LNCS 2616, 2003, pages 153-164.
[143]. Martin Erig, Markus Schneider. Vague Regions, In: Proc. Of 5th Int. Symp. On Advances in Spatial Databases (SSD'97), LNCS 1262, 1997, pages 298-320.
[144]. L.A. Zadeh. Fuzzy Sets. Information and Control, 1965, 8: 338-353.
[145]. M.Koppen, K. Franke, O. Unold. A Tutorial on Fuzzy Morphology. http:// visionic.fhg.de/ipk/publikationen/pdf/fmorph.pdf.
[146]. I. Bloch, H. Maitre. Fuzzy Mathematical Morphologies: A Comparative Study, Pattern Recognition, 1995, 28(9): 1341-1387.
[147]. P. D. Gader. Fuzzy Spatial Relations Based on Fuzzy Morphology, In FUZZ-IEEE 1997 (IEEE Int. Conf. on Fuzzy Systems), Barcelona, Spain: 1997, 2:1179-1183.
[148]. A. Rosenfeld. Fuzzy geometry: An overview. In: Proceedings of First IEEE Conference in Fuzzy Systems (San Diego), March, 1992. pages 113-118.
[149]. Dubios D, Jaulent M-C. A general approach to parameter evaluation in fuzzy digital pictures. Pattern Recognition Lett, 1987, 6: 251-259.
[150]. 周培德. 计算几何—算法分析与设计. 北京: 清华大学出版社, 2000.
[151]. R.L. Graham. An Efficient Algorithm for determining the Convex Hull of a Finite Planar Set. Information Processing Letters, 1972, 1: 73-82.
[152]. 龚炜, 石青云等. 数字空间中的数学形态学—理论及应用. 北京: 科学出版社, 1997.
[153]. N. Asher and L. Vieu. Towards a geometry of common sense: a semantics and a complete axiomatisation of mereotopology. In: Proceedings of IJCAI95, 1995, pages 846-852.
[154]. H. Kamp. Events, instants and temporal reference. In Von Stechow B?uerle, Egli, editor, Meaning, use and interpretation of language, de Gruyter, Berlin, 1979, pages 376–417.
[155]. L. Vieu. Sémantique des relations spatiales et inférences spatiotemporelles: une contribution à l'étude des structures formelles de l'espace en langage naturel. PhD thesis, Université Paul Sabatier, Toulouse, 1991.
[156]. A. Galton. Towards an integrated logics of space, time and motion. In: Proc. Of the 13th International Joint Conference on Artificial Intelligence, 1993, pages 1550-1557.
[157]. J. Allen. Towards a general theory of action and time. Artificial Intelligence, 1984, 23: 123–154.
[158]. Marco Ragni and Stefan W?lfl. Branching Allen: Reasoning with intervals in branching time. In: Proc. Of Spatial Cognition 2004 (SC'04). Lecture Notes in Computer Science Publisher: Springer-Verlag Heidelberg, Volume 3343, 2005, pages 323-345.
[159]. Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos. The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. In: Proceedings of 13th International Conference on Very Large Data Bases, September 1-4, 1987, Brighton, England, pages 507-518.
[160]. Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger. The R*-tree: An Efficient and Robust Access Method for Points and Rectangles. In: Proceedings of the ACM SIGMOD, 1990, pages 322-331.
[161]. Orenstein, J. A. Spatial Query Processing in an Object-Oriented Database System. In: Proc. Of the 1986 ACM SIGMOD international conference on Management of data, 1986, pages 326-336.
[162]. Nadel, B. Constraint Satisfaction Algorithms. Computational Intelligence, 1989, 5: 188-224.
[163]. Haralick, R.M., Elliott, G.L. Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence, 1980, 14: 263-313.
[164]. Bacchus, F., Grove, A. On the Forward Checking Algorithm. In Proceedings the First International Conference on Principle and Practice of Constraint Programming, 1995,pages 292-309.
[165]. Bacchus, F., van Run, P. Dynamic Variable Ordering in CSPs. In Proceedings the First International Conference on Principle and Practice of Constraint Programming, 1995, pages 258-275.
[166]. 肖予钦,张巨,景宁,李军. 基于 R 树的方向关系查询处理.软件学报,2004,15(1): 103-111.
[167]. Dimitris Papadias, Nikos Mamoulis, Vasilis Delis. Algorithms for Querying by Spatial Structure. In: Proceedings of 24rd International Conference on Very Large Data Bases, August 24-27, 1998, New York, USA, pages 546-557.
[168]. 蒋夏军,吴慧中,李蔚清. 数据分发管理匹配算法的 R-树实现.计算机研究与发展,2006,43(2): 362-367.
[169]. Minton S., Johnston M., Philips A., Laird P. Minimizing Conflicts: A Heuristic Method for Constraint-Satisfaction and Scheduling Problems. 1992, Artificial Intelligence, 58: 161-205.
[170]. Rajat Bhattacharjee, et al.. JCL: Java Constraints Library, http://liawww.epfl.ch/JCL/index.htm.
[171]. Marios Hadjieleftheriou. SIL: Spatial Index Library. http://u-foria.org/marioh/spatialindex/index.html.
[172]. MBRs of streets (polylines) of Germany. http://isl.cs.unipi.gr/db/projects/rtreeportal/spatial.html
[173]. Jiawei Han and Micheline Kamber. Data Mining: Concepts and Techniques. Morgan Kaufmann Publishers, 2001.
[174]. 宋国杰,唐世渭,杨冬青等. 基于最大熵原理的空间特征选择方法.软件学报,2003.14(9): 1544-1550.
[175]. Mitchell T. Machine Learning [M] . New York: McGraw Hill College Press ,1997.
[176]. 毛国君,段立娟,王实,石云. 数据挖掘原理与算法.清华大学出版社, 2005.
[177]. Han J, Kambr M. Data Mining: Concepts and Techniques. Morgan Kaufmann Publishers, 2001: 279-333.
[178]. Ruggieri S. Efficient C4.5. IEEE Transactions on Knowledge and Data Engineering, 2002, 14(2): 438-444.
[179]. Breiman L, Friedman JH, Olshen RA, et al. Classification and Regression Trees. Chapman & Hall (Wadsworth, Inc.): New York, 1984.
[180]. Mehta M, Agrawal R, Rissanen J. SLIQ: A Fast Scalable Classifier for Data Mining. Research Report, IBM Almaden Research Center, San Jose, California, 1995.
[181]. Shafer J, Agrawal R, Mehta M. SPRINT: A Scalable Parallel Classifier for Data Mining. Research Report, IBM Almaden Research Center, San Jose, California, 1996.
[182]. Rastogi R, Shim K. PUBLIC: A Decision Tree Classifier that Integrates Building and Pruning. Technical Report, Bell Laboratories, Murray Hill, 1998.
[183]. Valduriez P. Join indices. ACM Transactions on Database Systems, 1987, 12 (2): 218-246.
[184]. Zeitouni K.,Yeh L., Aufaure M-A. Join indices as a tool for spatial data mining. In: Proc. of Int. Workshop on Temporal, Spatial and Spatio-Temporal Data Mining, Lecture Notes in Artificial Intelligence 2007, Springer, Lyon, France, September 12-16, 2000, pages 102-114.
[185]. Chelghoum N., Zeitouni K. A decision tree for multi-layered spatial data, In: Proc. Of Joint International Symposium on Geospatial Theory, Processing and Applications, Ottawa, Canada, July 8-12, 2002.
[186]. Mapinfo Corporation. Mapinfo Professional Hompage. http://www.mapinfo.com/events/mipro/mipro.html.
[187]. SANDAG. http://www.sandag.cog.ca.us/resources/maps_and_gis/gis_downloads/senlu.asp.
[188]. ESRI ARCINFO. http://www.esri.com/software/arcgis/arcinfo.
[189]. MAPX. http://www.mapinfo.com/mapx.
[2]. Franco P. Preparata and Michael I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, Berlin, Heidelberg, New York, 1991.
[3]. Jean-Claude Latombe. Robot Motion Planning. Kluwer, Dordrecht, Holland, 1991.
[4]. Weld, D.S., De Kleer, J. (eds.) Reading in Qualitative Reasoning About Physical Systems, Morgan Kaufman, San Mateo, Ca, 1990.
[5]. Anthony G. Cohn. Qualitative spatial representations. In: Working notes of IJCAI'99 workshop on Adaptive Spatial Representations of Dynamic Environments, 1999, pages 33–52.
[6]. Daniel Hernandez. Qualitative Representation of Spatial Knowledge, Lecture Notes in Artificial Intelligence 804, Springer-Verlag, Berlin, Heidelberg, New York, 1994.
[7]. J. Renz. Qualitative Spatial Reasoning with Topological Information, LNAI 2293, 2002.
[8]. B. Faltings. Qualitative Spatial Reasoning Using Algebraic Topology. In Proceedings of COSIT-95, volume 988 of LNCS, 1995, pages 17-30.
[9]. A.U. Frank. Qualitative Spatial Reasoning about Distances and Directions in Geographic Space. Journal of Visual Languages and Computing, 1992, 3:343–371.
[10]. C. Freksa. Using Orientation Information for Qualitative Spatial Reasoning. In: Proceedings of COSIT-92, LNCS 639, 1992, pages 162–178.
[11]. Yao, X., Thill, J.C. Spatial Queries With Qualitative Locations In Spatial Information Systems. Computers, Environment and Urban Systems. 2005 (In Press). http://www.ggy.uga.edu/people/faculty/xyao/QL05.pdf
[12]. Bergman, L. Castelli, V., Li C-S. Progressive Content-Based Retrieval from Satellite Image Archives. D-Lib Magazine, October 1997. http://www.dlib.org/dlib/october97/ibm/10li.html.
[13]. Chang S.F, Smith J.R., Meng H.J, Wang H., Zhong D. Finding Images/Video in Large Archives. CNRI Digital Library Magazine, Feb. 1997. http://www.dlib.org/dlib/december02/marchionini/12marchionini.html.
[14]. Gupta A., Jain R. Visual Information Retrieval. Communications of ACM, May 1997, 40(5): 70-79.
[15]. K. Koperski, J. Han and N. Stefanovic. An Efficient Two-Step Method for Classification of Spatial Data. Proc. Int. Symp. on Spatial Data Handling, Vancouver, BC, Canada, July 1998, pages 45-54.
[16]. Quinlan J. R. Induction of Decision Trees. Machine Learning, 1986, 1:81-106.
[17]. Alessandra Raffaetà, Franco Turini, Chiara Renso. Enhancing GISs for spatio-temporal reasoning. In: Proceedings of the 10th ACM international symposium on Advances in geographic information systems, ACM-GIS 2002, pages 42-48.
[18]. Tate, A., Hendler, J. and Drummond, M. A review of AI Planning Techniques. In Readings in Planning, J. Allen, J. Hendler, and A. Tate. (eds): Morgan Kaufmann Publishers, 1990, pages 26-49.
[19]. Fernyhough, J., Cohn, A G;Hogg, D C. Constructing qualitative event models automatically from video input. Image and Vision Computing, 2000, 18: 81-103.
[20]. M. Egenhofer and D. Mark. Naive Geography. COSIT '95, Semmering, Austria A. Frank and W. Kuhn (eds.), Lecture Notes in Computer Science, Vol. 988, Springer-Verlag, September 1995, pages 1-15.
[21]. M. Egenhofer. Query Processing in Spatial-Query-by-Sketch. Journal of Visual Languages and Computing, 1997, 8(4): 403-424.
[22]. B. Kuipers and Y.T. Byun. A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations. Journal of Robotics and Autonomous Systems, 1991, 8:47-63.
[23]. Faltings, B. Qualitative Spatial Reasoning Using Algebraic Topology. In: A. U. Frank and W. Kuhn (eds.), Spatial Information Theory: A Theoretical Basis for GIS, Proceedings of COSIT'95, LNCS 988, 1995, pages 17-30.
[24]. A. Mukerjee. Neat vs scruffy: A survey of computational models for spatial expressions. P. Oliver and K-P Gapp (eds.) Representation and Processing of Spatial Expressions, Kluwer, 1998.
[25]. Guarino, N., &Giaretta, P. Ontologies and knowledge bases: towards a terminological clarification. In N. Mars (Ed.), Towards very large knowledge bases. Amsterdam: IOS Press. 1995, pages 25-32.
[26]. P. Simons. Parts: A Study in Ontology. Clarendon Press, Oxford, 1987.
[27]. Vieu, L. Spatial Representation and Reasoning in Artificial Intelligence. In: O. Stock (ed.) Spatial and Temporal Reasoning. Dordrecht: Kluwer, 1997, pages 5-41.
[28]. A. G. Cohn, B. Bennett, J. M. Gooday and N. M. Gotts. Representing and Reasoning with Qualitative Spatial Relations about Regions. O. Stock (ed.) Temporal and spatial reasoning, Kluwer, 1997, pages 97-134.
[29]. A. G. Cohn, B. Bennett, J. M. Gooday and N. M. Gotts. RCC: a calculus for Region based Qualitative Spatial Reasoning. GeoInformatica, 1997, 1: 275-316.
[30]. N. M. Gotts, J. M. Gooday and A. G. Cohn. A connection based approach to commonsense topological description and reasoning. The Monist, 1996, 79 (1): 51-75.
[31]. Pratt, I. and O. Lemon. Ontologies for plane, polygonal mereotopology. Notre Dame Journal of Formal Logic, 1997, 38(2): 225-245.
[32]. M. Egenhofer and J. Sharma. Topological Relations Between Regions in R2 and Z2. In: D. Abel and B.C. Ooi (eds.), Advances in Spatial Databases-Third International Symposium on Large Spatial Databases, SSD'93, Singapore, LNCS 692, Springer-Verlag, 1993, pages 316-336.
[33]. N. M. Gotts. Using the RCC Formalism to Describe the Topology of Spherical Regions. Report 96.24, School of Computer Studies, University of Leeds, 1996.
[34]. Antony Galton. The Mereotopology of Discrete Space. In: C. Freksa and D. M. Mark (eds.), Spatial Information Theory: Cognitive and Computational Foundations of Geographic Science, Proceedings of the International Conference COSIT'99, LNCS 1661, Springer, 1999, pages 251-266.
[35]. Masolo, Claudio and Laure Vieu. Atomicity vs. Infinite Divisibility of Space. In: C. Freksa and D. Mark (eds.), Spatial Information theory. Proceedings of COSIT'99. Berlin: Springer Verlag, LNCS 1661, 1999, pages 235-250.
[36]. P. Hayes. Naive physics manifesto. In: D. Michie (ed.), Expert Systems in the Microelectronic Age. Edinburgh University Press, 1979.
[37]. Walischewski, H. Learning regions of interest in postal automation. In: Proc. 5th Intl. Conf. on Document Analysis and Recognition (ICDAR'99), Bangalore, India, 1999, pages 317-320.
[38]. Clarke, B. L. A calculus of individuals based on “connection”. Notre Dame Journal of Formal Logic, 1981, 22: 204-218.
[39]. D. A. Randell and A. G. Cohn. Modelling Topological and Metrical Properties in Physical Processes. In: Proc.of 1st International Conference on the Principles of Knowledge Representation and Reasoning. Morgan Kaufmann, Los Altos, 1989, pages 55-66.
[40]. D. A. Randell, Z. Cui and A. G. Cohn. A Spatial Logic Based on Regions and Connection. In: Proc. 3rd Int. Conf. on Knowledge Representation and Reasoning, Morgan Kaufmann, San Mateo, 1992, pages 165-176.
[41]. M. Egenhofer and R. Franzosa, Point-Set Topological Spatial Relations. International Journal of Geographical Information Systems, 1991, 5(2): 161-174.
[42]. Max J. Egenhofer. Reasoning about binary topological relations. In: O. Gunther and H. J. Schek (eds), Proceedings of the Second Symposium on Large Spatial Databases, SSD'91, LNCS 525, Springer-Verlag, Berlin, Heidelberg, New York, 1991, pages 143–160.
[43]. Brandon Bennett. Spatial reasoning with propositional logic. In: J. Doyle, E. Sandewall, and P. Torasso (eds), Principles of Knowledge Representation and Reasoning, Proceedings of the 4th International Conference, Bonn, Germany, May 1994. Morgan Kaufmann, pages 51–62.
[44]. Brandon Bennett. Modal logics for qualitative spatial reasoning. Bulletin of the IGPL, 1996,4(1): 23–45.
[45]. 陆钟万. 面向计算机科学的数理逻辑. 北京: 科学出版社, 2002.
[46]. J. Renz, B. Nebel. On the Complexity of Qualitative Spatial Reasoning: A Maximal Tractable Fragment of the Region Connection Calculus. Artificial Intelligence (AIJ), 1999, 108(1-2): 69-123.
[47]. J. Renz. Maximal Tractable Fragments of the Region Connection Calculus: A Complete Analysis. In: Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI'99), Stockholm, Sweden, August 1999, pages 448-455.
[48]. Max J. Egenhofer, Eliseo Clementini, and Paolino Di Felice. Topological relations between regions with holes. International Journal of Geographical Information Systems, 1994, 8(2):129–144.
[49]. C. Schlieder. Representing visible locations for qualitative navigation. In: Qualitative Reasoning and Decision Technologies: CIMNE, 1993, pages 523-532.
[50]. C. Schlieder. Qualitative shape representation. In: P. Burrough and AM Frank, editors, Proceedings of GISDATA Specialist Meeting on Geographical Objects with Undetermined Boundaries. Francis Taylor, 1996.
[51]. R. R?hrig, Representation and processing of qualitative orientation knowledge. In: Proc. KI: German Annual Conference on Artificial Intelligence, Lecture Notes in Artificial Intelligence, Vol. 1303, Springer, Berlin, 1997, pages 219–230.
[52]. A. Isli and A. G. Cohn. A new approach to cyclic ordering of 2D orientations using ternary relation algebras. Artificial Intelligence, 2000, 122 (1-2): 137-187.
[53]. Andrew U. Frank. Qualitative spatial reasoning about cardinal directions. In: Proceedings of the 7th Austrian Conference on Artificial Intelligence, 1991, pages 157–167.
[54]. Marc B. Vilain and Henry A. Kautz. Constraint propagation algorithms for temporal reasoning. In: Proceedings of the 5th National Conference of the American Association for Artificial Intelligence, Philadelphia, PA, August 1986, pages 377–382.
[55]. Gerard Ligozat. Reasoning about cardinal directions. Journal of Visual Languages and Computing, 1998, 9:23–44.
[56]. Zimmermann, K. and Freksa, C. Qualitative spatial reasoning using orientation, distance, path knowledge. Applied Intelligence, 1996, 6: 49-58.
[57]. Alexander Scivos and Bernhard Nebel. Double-crossing is harmful: First results on formal properties of a qualitative calculus for navigation. Unpublished manuscript, 1999.
[58]. Julio Pacheco, M. Teresa Escrig and Francisco Toledo. Qualitative Spatial Reasoning on Three-Dimensional Orientation Point Objects. Sixteenth International Workshop on Qualitative Reasoning QR2002, June 10-12, 2002.
[59]. Hans Guesgen. Spatial reasoning based on Allen's temporal logic. Technical Report TR-89-049, ICSI, Berkeley, CA, 1989.
[60]. Dimitris Papadias and Yannis Theodoridis. Spatial relations, minimum bounding rectangles, and spatial data structures. International Journal of Geographic Information Systems, 1997, 11(2):111–138.
[61]. James F. Allen. Maintaining knowledge about temporal intervals. Communications of the ACM, November 1983, 26(11): 832-843.
[62]. Philippe Balbiani, Jean-Francois Condotta, and Luis Farinas del Cerro. A model for reasoning about bidimensional temporal relations. In: A.G. Cohn, L. Schubert, and S.C. Shapiro (eds), Proc. of the 6th Int. Conf. On Principles of Knowledge Representation and Reasoning, 1998, pages 124–130.
[63]. Philippe Balbiani, Jean-Francois Condotta, and Luis Farinas del Cerro. A new tractable subclass of the rectangle algebra. In: Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, 1999, pages 442–447.
[64]. R. Goyal and M. Egenhofer. Cardinal Directions between Extended Spatial Objects. IEEE Transactions on Knowledge and Data Engineering, 2000(in press).
[65]. S. Skiadopoulos and M. Koubarakis. Consistency Checking for Qualitative Spatial Reasoning with Cardinal Directions. In: Proceedings of the 7th International Conference on Principles and Practice of Constraint Programing (CP'02), LNCS, Vol.2470, Springer, Berlin, 2002, pages 341-356.
[66]. S. Skiadopoulos and M. Koubarakis. Composing Cardinal Direction Relations. Artificial Intelligence, 2004, 152(2): 143-171.
[67]. S.Cicerone and P. Di Felice. Cardinal directions between spatial objects: the pairwise-consistency problem. Information Sciences. 2004, 164(1-4): 165-188.
[68]. Daniel Hernandez, Eliseo Clementini, and Paolino di Felice. Qualitative distances. In: Spatial Information Theory: A Theoretical basis for GIS, LNCS 988, Springer-Verlag,1995,pages 45–58.
[69]. Eliseo Clementini, Paolino di Felice, and Daniel Hernandez. Qualitative representation of positional information. Artificial Intelligence, 1997, 95(2):317–356.
[70]. A U Frank. Qualitative spatial reasoning about distances and directions in geographic space. Journal of Visual Languages and Computing, 1992, 3:343-371.
[71]. Amar Isli and Reinhard Moratz. Qualitative spatial representation and reasoning: Algebraic models for relative position. Technical Report 284, University at Hamburg, Fachbereich Informatik, 1999.
[72]. A. Pauly and M. Schneider. Vague Spatial Data Types, Set Operations, and Predicates. In: 8th East-European Conf. on Advances in Databases and Information Systems, 2004, pages 379–392.
[73]. 胡宝清. 模糊理论基础. 武汉:武汉大学出版社, 2004.
[74]. M. Worboys. Computation with Imprecise Geospatial Data. Computational, Environmental and Urban Systems, 1998, 22(2): 85–106.
[75]. E. Clementini and P. Di Felice. An Algebraic Model for Spatial Objects with Indeterminate Boundaries. In: Burrough PA, Frank AU (eds). Geographic Objects with Indeterminate Boundaries, 1996, pages 153–169.
[76]. A. G. Cohn and N. M. Gotts. The ‘Egg-Yolk' Representation of Regions with Indeterminate Boundaries. In: Burrough PA, Frank AU (eds.), Geographic Objects with Indeterminate Boundaries, 1996, pages 171–187.
[77]. M. Schneider. A Design of Topological Predicates for Complex Crisp and Fuzzy Regions. In: Int. Conf. on Conceptual Modeling, LNCS 2224,2001, pages 103-116.
[78]. 熊金城. 点集拓扑讲义. 北京:高等教育出版社, 2003.
[79]. Alejandro Pauly and Markus Schneider. Topological Predicates Between Vague Spatial Objects. In: Claudia Bauzer Medeiros, Max J. Egenhofer, Elisa Bertino (Eds.): Advances in Spatial and Temporal Databases, 9th International Symposium, SSTD 2005, LNCS 3633, 2005, pages 418–432.
[80]. F.B. Zhan. Approximate analysis of binary topological relations between geographic regions with indeterminate boundaries. Soft Computing, Springer-Verlag, 1998, 2: 28-34
[81]. Christophe Claramunt, Marius Thériault. Fuzzy semantics for direction relations between composite regions. Information Sciences. 2004, 160: 73-90.
[82]. Subasic, P. and Huettner, A. Affect Analysis of Text Using Fuzzy Semantic Typing, IEEE Transactions on Fuzzy Systems. 2001, 9(4): 483-496.
[83]. Girish Keshav Palshikar. Fuzzy region connection calculus in finite discrete space domains. Applied Soft Computing. 2004, 4: 13-23.
[84]. Jan Terje Bj?rke. Topological relations between fuzzy regions: derivation of verbal terms. Fuzzy Sets and Systems. 2004, 141:449-467.
[85]. Serafino Cicerone, Paolino Di Felice. Cardinal relations between regions with a broad boundary. In: Proceedings of the 8th ACM international symposium on Advances in geographic information systems, ACM Press, 2000, pages 15-20.
[86]. R Rohrig. A theory for qualitative spatial reasoning based on order relations. In: Proceedings of the 12th National Conference on AI, volume 2, Seattle, 1994, pages 1418-1423.
[87]. C. Schlieder. Reasoning about Ordering. In: A. U. Frank and W. Kuhn (eds.), Spatial Information Theory: A Theoretical Basis for GIS. LNCS 988, 1995, pages 341-350.
[88]. Vilain, M. and Kautz, H. Constraint Propogation Algorithm for Temporal Reasoning. In: Proc. 5th American Conf. on AI (AAAI-86), Philadelphia, 1986, pages 377-382.
[89]. B. Bennett, A. Isli and A. G. Cohn. When does a Composition Table Provide a Complete and Tractable Proof Procedure for a Relational Constraint Language? In: Proceedings of the IJCAI-97 workshop on Spatial and Temporal Reasoning, Nagoya, Japan, 1997.
[90]. Li SJ, Ying MS. Region connection calculus: Its models and composition table. Artificial Intelligence, 2003,145(1-2): 121-146.
[91]. Jochen Renz, Gérard Ligozat. Weak Composition for Qualitative Spatial and Temporal Reasoning. CP 2005, LNCS 3709, pages 534-548.
[92]. Alan K. Mackworth. Constraint satisfaction. In: S.C. Shapiro (ed.), Encyclopedia of Artificial Intelligence, Wiley, Chichester, England, 1987, pages 205-211.
[93]. Peter B. Ladkin and Roger Maddux. On binary constraint problems. Journal of the Association for Computing Machinery, May 1994, 41(3): 435–469.
[94]. Alfred Tarski. On the calculus of relations. Journal of Symbolic Logic, 1941, 6: 73–89.
[95]. Robin Hirsch. A finite relation algebra with undecidable network satisfaction problem. Bulletin of the IGPL, 1999, 7: 547-554.
[96]. Alan K. Mackworth. Consistency in networks of relations. Artificial Intelligence, 1977, 8: 99–118.
[97]. Ugo Montanari. Networks of constraints: fundamental properties and applications to picture processing. Information Science, 1974, 7: 95–132.
[98]. Alan K. Mackworth and Eugene C. Freuder. The complexity of some polynomial network consistency algorithms for constraint satisfaction problems. Artificial Intelligence, 1985, 25: 65–73.
[99]. Peter van Beek. Reasoning about qualitative temporal information. Artificial Intelligence, 1992, 58(1-3): 297–321.
[100]. B Nebel. Reasoning about temporal relations: a maximal tractable subset of Allen's interval algebra. Journal of the Association for Computing Machinery, January 1995, 42(1): 43-66.
[101]. Peter B. Ladkin and Alexander Reinefeld. Effective solution of qualitative interval constraint problems. Artificial Intelligence, September 1992, 57(1): 105–124.
[102]. Sebastian Brand. Relation Variables in Qualitative Spatial Reasoning. In: S. Biundo, T. Fr¨uhwirth, and G. Palm (Eds.): Proc. Of KI 2004, LNAI 3238, 2004, pages 337–350.
[103]. 王生生,刘大有,谢 琦,王新颖.集成多方面信息的定性空间推理及应用.软件学报,2003,14(11): 1857-1862.
[104]. A. Gerevini, J. Renz. Combining Topological and Size Constraints for Spatial Reasoning. Artificial Intelligence (AIJ), 2002, 137(1-2): 1-42.
[105]. A Isli, V Haarslev and R M?ller. Combining cardinal direction relations and relative orientation relations in Qualitative Spatial Reasoning. Technical report FBI-HH-M-304/01, Fachbereich Informatik, Universit?t Hamburg, 2001.
[106]. Peter van Beek and Robin Cohen. Exact and approximate reasoning about temporal relations. Computational Intelligence, 1990, 6:132–144.
[107]. P. Muller. Topological spatio-temporal reasoning and representation. Computational Intelligence. 2002, 18(3): 420–450.
[108]. F. Wolter and M. Zakharyaschev. Spatio-temporal representation and reasoning based on RCC-8. In: A. Cohn, F. Giunchiglia, and B. Selman (eds.), Principles of Knowledge Representation and Reasoning, Proceedings of the 7th International Conference (KR2000). Morgan Kaufmann, 2000, pages 3-14.
[109]. Z. Manna and A. Pnueli. The temporal logic of reactive and concurrent systems. Springer-Verlag, Berlin, Heidelberg, New York, 1992.
[110]. B. Bennett. Modal logics for qualitative spatial reasoning. Journal of the Interest Group on Pure and Applied Logic, 1996, 4(1): 23–45.
[111]. A. Gerevini and B. Nebel. Qualitative spatio-temporal reasoning with RCC-8 and Allen's interval calculus: Computational complexity. In: Proceedings of the 15th European Conference on Artificial Intelligence (ECAI-02), IOS Press, 2002, pages 312–316.
[112]. B. Bennett, A. G. Cohn, F. Wolter, and M. Zakharyaschev. Multi-dimensional modal logic as a framework for spatio-temporal reasoning. Applied Intelligence, 2002, 17(3): 239–251.
[113]. Guttman, A. R-trees: A Dynamic Index Structure for Spatial Searching. In: Proc. Of ACM SIGMOD, 1984, pages 47-57.
[114]. Roussopoulos, N., Kelley, F., Vincent, F. Nearest Neighbor Queries. In: Proc. Of ACM SIGMOD, 1995,pages 71-79.
[115]. Papadias, D., Theodoridis, Y., Sellis, T., Egenhofer, M. Topological Relations in the World of Minimum Bounding Rectangles: A study with R-trees. In: Proc. Of ACM SIGMOD, 1995,pages 92-103.
[116]. Rotem, D. Spatial Join Indices. In: Proceedings of the seventh International Conference on Data Engineering, 1991, pages 500-509.
[117]. Guenther, O. Efficient computation of spatial joins. In: Proceedings of the Ninth International Conference on Data Engineering, 1993, pages 50-59.
[118]. Brinkhoff, T., Kriegel, H. P., Seeger, B. Efficient processing of spatial joins using Rtrees. In: Proc. of the ACM-SIGMOD Conference on Management of Data, 1993,pages 237-246.
[119]. Blockeel, H., De Raedt, L. Top-down induction of first order logical decision trees. Artificial Intelligence, June 1998, 101(1-2): 285-297.
[120]. Blockeel, H., De Raedt, L., Ramon, J. Top-down induction of clustering trees. In Proceedings of the 15th International Conference on Machine Learning (ICML'98), 1998, pages 55-63.
[121]. J. Knobbe, H. Blockeel, A. Siebes, and Van der Wallen D. Multi-relational decision tree induction. In Proceedings of the 3rdEuropean Conference on Principles and Practice of Knowledge Discovery in Databases, PKDD99, Springer-Verlag, 1999, pages 378-383.
[122]. Krzysztof Koperski, Jiawei Han. Discovery of Spatial Association Rules in Geographic Information Databases. In Proc. 4th International Symposium Of Advances in Spatial Databases, 1995, pages 47-66.
[123]. Martin Ester, Hans-Peter Kriegel, J?rg Sander, Xiaowei Xu. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, AAAI Press, 1996, pages 226-231.
[124]. W. Lu, J. Han and B. C. Ooi. Discovery of General Knowledge in Large Spatial Databases, Proc. Far East Workshop on Geographic Information Systems, Singapore, June 1993, pages 275-289.
[125]. R. Ng and Y. Yu. Discovering Strong, Common and Discriminating Characteristics of Clusters from Thematic Maps. Proceedings of the Eleventh Annual Symposium on Geographic Information Systems, 1997, pages 392-394.
[126]. Ester M., Kriegel H.P., Sander J. Spatial Data Mining: A Database Approach. In: Proc. of the 5th Symposium on Spatial Databases, Lecture Notes in Computer Science, 1262. Berlin, Germany, 1997, pages 47-66.
[127]. J. Sharma. Integrated spatial reasoning in geographic information systems: combining topology and direction. Ph.D. Thesis, Department of Spatial Information Science and Engineering, University of Maine, Orono, ME, 1996.
[128]. 尤承业. 基础拓扑学讲义. 北京大学出版社, 1997.
[129]. M. Egenhofer. A Formal Definition of Binary Topological Relationships. In: Proc. of Third International Conference on Foundations of Data Organization and Algorithms (FODO), Paris, France, 1989, LNCS 367, pages 457-472.
[130]. Bennett, B. Determining consistency of topological relations. Constraints, 1998, 3: 213-225.
[131]. Clementini E. and P.D. Felice. A Comparison of Methods for Representing Topological Relationships. Information Sciences, 1995, 3 (3): 149-178.
[132]. 李成名,陈军. 空间关系描述的 9-交模型. 武汉测绘科技大学学报,1997, 22(2):207-211.
[133]. Clementini E, Di Felice P, Van Oosterom P. A small set of formal topological relationships suitable for end-user interaction. In: Abel D, Ooi BC (eds.), Advances in Spatial Databases, the 3rd International Symposium, SSD'93. LNCS 692, Berlin: Springer-Verlag, 1993, pages 277-295.
[134]. Randell, D. A., Cohn, A. G., and Cui, Z. Computing transitivity tables: A challenge for automated theorem provers. In: Kapur, D. (ed.), Proceedings of the 11th International Conference on Automated Deduction (CADE-11), LNAI 607, Saratoga Springs, NY. Springer, 1992, pages 786-790.
[135]. A. Prasad Sistla, Clement T. Yu and R. Haddad. Reasoning About Spatial Relationships in Picture Retrieval Systems. In: Proceedings of 20th International Conference on Very Large Data Bases, Morgan Kaufmann, 1994, pages 570-581.
[136]. D. Papadias, N. Arkoumanis, and N. Karacapilidis. On The Retrieval of Similar Configurations. In: Proceedings of 8th International Symposium on Spatial Data Handling (SDH),1998, pages 510-521.
[137]. Michelangelo Grigni, Dimitris Papadias, and Christos Papadimitriou. Topological inference. In: C.Mellish, editor, Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI), volume 1, Morgan kaufmann,1995, pages 901-906.
[138]. Peter Ladkin and Alexander Reinefeld. Fast Algebraic Methods for Interval Constraint Problems. Invited Paper in Annals of Mathematics and Artificial Intelligence, 1997, 19:383-411.
[139]. Yu Liu, Xiaoming Wang, Xin Jin, Lun Wu. On Internal Cardinal Direction Relations. In: Proc. Of Spatial Information Theory, International Conference, COSIT 2005, LNCS 3693, pages 283-299.
[140]. Markus Schneider. Uncertainty Management for Spatial Data in Databases: Fuzzy Spatial Data Types. In: R.H.Guting, et al. (Eds.): SSD'99, LNCS 1651, 1999, pages 330-351.
[141]. Isabelle Bloch. Fuzzy Spatial Relationships from Mathematical Morphology for Model-based Pattern Recognition and Spatial Reasoning, In: I. Nystrom et al. (Eds) : DGCI 2003, LNCS 2886, 2003, pages 16-33.
[142]. Isabelle Bloch. Unifying Quantitative, Semi-quantitative and Qualitative Spatial Relation knowledge Representation Using Mathematical Morphology, In: T.Asano et al. (Eds): Geometry, Morphology, and Computational Imaging, 11th International Workshop on Theoretical Foundations of Computer Vision Dagstuhl Castle, Germany, April 7-12, 2002, LNCS 2616, 2003, pages 153-164.
[143]. Martin Erig, Markus Schneider. Vague Regions, In: Proc. Of 5th Int. Symp. On Advances in Spatial Databases (SSD'97), LNCS 1262, 1997, pages 298-320.
[144]. L.A. Zadeh. Fuzzy Sets. Information and Control, 1965, 8: 338-353.
[145]. M.Koppen, K. Franke, O. Unold. A Tutorial on Fuzzy Morphology. http:// visionic.fhg.de/ipk/publikationen/pdf/fmorph.pdf.
[146]. I. Bloch, H. Maitre. Fuzzy Mathematical Morphologies: A Comparative Study, Pattern Recognition, 1995, 28(9): 1341-1387.
[147]. P. D. Gader. Fuzzy Spatial Relations Based on Fuzzy Morphology, In FUZZ-IEEE 1997 (IEEE Int. Conf. on Fuzzy Systems), Barcelona, Spain: 1997, 2:1179-1183.
[148]. A. Rosenfeld. Fuzzy geometry: An overview. In: Proceedings of First IEEE Conference in Fuzzy Systems (San Diego), March, 1992. pages 113-118.
[149]. Dubios D, Jaulent M-C. A general approach to parameter evaluation in fuzzy digital pictures. Pattern Recognition Lett, 1987, 6: 251-259.
[150]. 周培德. 计算几何—算法分析与设计. 北京: 清华大学出版社, 2000.
[151]. R.L. Graham. An Efficient Algorithm for determining the Convex Hull of a Finite Planar Set. Information Processing Letters, 1972, 1: 73-82.
[152]. 龚炜, 石青云等. 数字空间中的数学形态学—理论及应用. 北京: 科学出版社, 1997.
[153]. N. Asher and L. Vieu. Towards a geometry of common sense: a semantics and a complete axiomatisation of mereotopology. In: Proceedings of IJCAI95, 1995, pages 846-852.
[154]. H. Kamp. Events, instants and temporal reference. In Von Stechow B?uerle, Egli, editor, Meaning, use and interpretation of language, de Gruyter, Berlin, 1979, pages 376–417.
[155]. L. Vieu. Sémantique des relations spatiales et inférences spatiotemporelles: une contribution à l'étude des structures formelles de l'espace en langage naturel. PhD thesis, Université Paul Sabatier, Toulouse, 1991.
[156]. A. Galton. Towards an integrated logics of space, time and motion. In: Proc. Of the 13th International Joint Conference on Artificial Intelligence, 1993, pages 1550-1557.
[157]. J. Allen. Towards a general theory of action and time. Artificial Intelligence, 1984, 23: 123–154.
[158]. Marco Ragni and Stefan W?lfl. Branching Allen: Reasoning with intervals in branching time. In: Proc. Of Spatial Cognition 2004 (SC'04). Lecture Notes in Computer Science Publisher: Springer-Verlag Heidelberg, Volume 3343, 2005, pages 323-345.
[159]. Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos. The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. In: Proceedings of 13th International Conference on Very Large Data Bases, September 1-4, 1987, Brighton, England, pages 507-518.
[160]. Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger. The R*-tree: An Efficient and Robust Access Method for Points and Rectangles. In: Proceedings of the ACM SIGMOD, 1990, pages 322-331.
[161]. Orenstein, J. A. Spatial Query Processing in an Object-Oriented Database System. In: Proc. Of the 1986 ACM SIGMOD international conference on Management of data, 1986, pages 326-336.
[162]. Nadel, B. Constraint Satisfaction Algorithms. Computational Intelligence, 1989, 5: 188-224.
[163]. Haralick, R.M., Elliott, G.L. Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence, 1980, 14: 263-313.
[164]. Bacchus, F., Grove, A. On the Forward Checking Algorithm. In Proceedings the First International Conference on Principle and Practice of Constraint Programming, 1995,pages 292-309.
[165]. Bacchus, F., van Run, P. Dynamic Variable Ordering in CSPs. In Proceedings the First International Conference on Principle and Practice of Constraint Programming, 1995, pages 258-275.
[166]. 肖予钦,张巨,景宁,李军. 基于 R 树的方向关系查询处理.软件学报,2004,15(1): 103-111.
[167]. Dimitris Papadias, Nikos Mamoulis, Vasilis Delis. Algorithms for Querying by Spatial Structure. In: Proceedings of 24rd International Conference on Very Large Data Bases, August 24-27, 1998, New York, USA, pages 546-557.
[168]. 蒋夏军,吴慧中,李蔚清. 数据分发管理匹配算法的 R-树实现.计算机研究与发展,2006,43(2): 362-367.
[169]. Minton S., Johnston M., Philips A., Laird P. Minimizing Conflicts: A Heuristic Method for Constraint-Satisfaction and Scheduling Problems. 1992, Artificial Intelligence, 58: 161-205.
[170]. Rajat Bhattacharjee, et al.. JCL: Java Constraints Library, http://liawww.epfl.ch/JCL/index.htm.
[171]. Marios Hadjieleftheriou. SIL: Spatial Index Library. http://u-foria.org/marioh/spatialindex/index.html.
[172]. MBRs of streets (polylines) of Germany. http://isl.cs.unipi.gr/db/projects/rtreeportal/spatial.html
[173]. Jiawei Han and Micheline Kamber. Data Mining: Concepts and Techniques. Morgan Kaufmann Publishers, 2001.
[174]. 宋国杰,唐世渭,杨冬青等. 基于最大熵原理的空间特征选择方法.软件学报,2003.14(9): 1544-1550.
[175]. Mitchell T. Machine Learning [M] . New York: McGraw Hill College Press ,1997.
[176]. 毛国君,段立娟,王实,石云. 数据挖掘原理与算法.清华大学出版社, 2005.
[177]. Han J, Kambr M. Data Mining: Concepts and Techniques. Morgan Kaufmann Publishers, 2001: 279-333.
[178]. Ruggieri S. Efficient C4.5. IEEE Transactions on Knowledge and Data Engineering, 2002, 14(2): 438-444.
[179]. Breiman L, Friedman JH, Olshen RA, et al. Classification and Regression Trees. Chapman & Hall (Wadsworth, Inc.): New York, 1984.
[180]. Mehta M, Agrawal R, Rissanen J. SLIQ: A Fast Scalable Classifier for Data Mining. Research Report, IBM Almaden Research Center, San Jose, California, 1995.
[181]. Shafer J, Agrawal R, Mehta M. SPRINT: A Scalable Parallel Classifier for Data Mining. Research Report, IBM Almaden Research Center, San Jose, California, 1996.
[182]. Rastogi R, Shim K. PUBLIC: A Decision Tree Classifier that Integrates Building and Pruning. Technical Report, Bell Laboratories, Murray Hill, 1998.
[183]. Valduriez P. Join indices. ACM Transactions on Database Systems, 1987, 12 (2): 218-246.
[184]. Zeitouni K.,Yeh L., Aufaure M-A. Join indices as a tool for spatial data mining. In: Proc. of Int. Workshop on Temporal, Spatial and Spatio-Temporal Data Mining, Lecture Notes in Artificial Intelligence 2007, Springer, Lyon, France, September 12-16, 2000, pages 102-114.
[185]. Chelghoum N., Zeitouni K. A decision tree for multi-layered spatial data, In: Proc. Of Joint International Symposium on Geospatial Theory, Processing and Applications, Ottawa, Canada, July 8-12, 2002.
[186]. Mapinfo Corporation. Mapinfo Professional Hompage. http://www.mapinfo.com/events/mipro/mipro.html.
[187]. SANDAG. http://www.sandag.cog.ca.us/resources/maps_and_gis/gis_downloads/senlu.asp.
[188]. ESRI ARCINFO. http://www.esri.com/software/arcgis/arcinfo.
[189]. MAPX. http://www.mapinfo.com/mapx.