基于图数据库的空间频繁并置模式挖掘  

Mining Spatial Prevalent Co-location Patterns Based on Graph Databases

作　　者：胡自松 王丽珍[1] Vanha Tran 周丽华[1] 陈文和 HU Zisong;WANG Lizhen;Vanha Tran;ZHOU Lihua(School of Information Science and Engineering,Yunnan University,Kunming 650504,China)

机构地区：[1]云南大学信息学院,昆明650504 [2]不详

出　　处：《计算机科学与探索》2022年第4期806-821,共16页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金(61966036,61662086);云南省创新团队建设项目(2018HC019)。

摘　　要：空间频繁并置模式(SPCP)是一组空间特征的子集,它们的实例在地理空间中频繁地出现在一起。基于内存物化实例邻近关系并搜索模式实例效率较高,但实例信息会被重复存储。图数据库技术能高效地对具有复杂关联关系的数据建模,但基于实例邻近关系图移植已有的挖掘方法不能发挥图遍历的优势。针对上述问题,探索了基于图数据库的空间频繁并置模式挖掘方法。首先,利用图数据库对空间实例及其邻近关系建模,即将实例和关系存储在图数据库中。然后,基于图数据库设计了一个称为子图(团)搜索的基本算法,采用团查找的方式生成模式的表实例从而获得参与实例,避免了传统方法中效率较低的组合或连接操作。考虑到通过生成表实例收集参与实例的效率较低,设计了参与实例验证算法,包括过滤阶段和验证阶段。过滤阶段判断一个中心实例的邻居集中所涉及的特征是否完全包含了待计算模式中的特征,验证阶段则是判断是否存在一个模式实例包含该中心实例。参与实例验证算法每次验证一个中心实例都尽可能多地去确定参与对象,从而有效地减小了搜索空间和减少了团的搜索次数。此外,对提出算法的正确性和完备性进行了证明。最后,在真实和合成数据集上做了大量的实验,验证了所提算法的效率和有效性。A spatial prevalent co-location pattern(SPCP) is a subset of spatial features whose instances frequently appear together in geographic space. Memory-based neighbor relationship materialization method to search for pattern’s instances is efficient, but instance information is stored repeatedly. Graph database technology can efficiently model data with complex associations. Thus, it is possible to consider using the graph database technology to materialize neighbor relationships(i.e., to construct neighborhood graph), but directly transplanting existing mining methods cannot exert the advantages of graph traversal. To solve the above problem, this paper explores the graph databasebased approach to mine spatial prevalent co-location patterns. Firstly, the graph database is utilized to model the spatial instances and their neighbor relations, i.e., the instances and relations are stored in the graph database to construct the neighborhood graph. Then, a basic algorithm called subgraph(or clique) search is designed based on the graph database, using the way of clique search strategy to generate a pattern’s table instance to obtain the participating instances, and avoid the inefficient combination or join operations in the traditional method. Considering the low efficiency of collecting participating instances by generating table instances, a participating instance verification algorithm is designed, including the filtering and verification phases. The filtering phase determines whether the features involved in the center instance ’ s neighborhoods fully contain the features in the pattern, and the verification phase determines whether there is pattern instance containing the central instance. The participating instance verification algorithm determines as many participating instances as possible each time, thereby effectively reducing the search space and the number of clique searches. In addition, the correctness and completeness of the proposed algorithms are proven. Finally, extensive experiments are conducted

关 键 词：空间数据挖掘 图数据库 空间并置模式 子图搜索 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]