Spatial data mining: Database primitives, algorithms and efficient DBMS support

Spatial data mining algorithms heavily depend on the efficient processing o f neighborhood relations since the neighbors of many objects have to be inv estigated in a single run of a typical algorithm. Therefore, providing gene ral concepts for neighborhood relations as well as an efficient implementat ion of these concepts will allow a tight integration of spatial data mining algorithms with a spatial database management system. This will speed up b oth, the development and the execution of spatial data mining algorithms. I n this paper, we define neighborhood graphs and paths and a small set of da tabase primitives for their manipulation. We show that typical spatial data mining algorithms are well supported by the proposed basic operations. For finding significant spatial patterns, only certain classes of paths "leadi ng away" from a starting object are relevant. We discuss filters allowing o nly such neighborhood paths which will significantly reduce the search spac e for spatial data mining algorithms. Furthermore, we introduce neighborhoo d indices to speed up the processing of our database primitives. We impleme nted the database primitives on top of a commercial spatial database manage ment system. The effectiveness and efficiency of the proposed approach was evaluated by using an analytical cost model and an extensive experimental s tudy on a geographic database.