Study on Optimization for Constraint Query Processing and Framework for Constraint Databases

约束查询处理优化及约束数据库框架研究

• 批准号: 17500097
• 负责人: KITAKAMI HAJIME
• 金额: $ 1.73万
• 依托单位: Hiroshima City University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2005
• 资助国家: 日本
• 起止时间: 2005 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17500097/
• 关键词: Data Mining; Variable Wildcard Region; Mismatch Cluster; Distributed Parallel Processing; Gibbs Sampler; Suffix Tree; Sequence Database; Blog User Space; 最的化; 曖昧表現; 制約データベース; 曖昧パターン; 可変長パターン; 配列データマイニング; Webマイニング; 最小汎化; 文字列制約; 数式制約; 分子配列

A central research theme for constraint query processing includes a study on methods for solving constraint satisfaction problems in constraint databases. At the start of this study, we investigated many frameworks related to the processing of constraint databases. In order to proceed effectively, we focused on the following constraints : character sequence, network structure, spatial data, computational geometry, and finite domain. The fruitful productions of the study are below :(1) Character Sequence ConstraintsIn order to solve the character sequence constraints that are represented as extracting frequent subsequences from databases storing character or word sequences, we focused on molecular sequence databases and revealed methods for extracting frequent sequential patterns with a regular expression that has a capability to represent variable wildcard regions and ambiguous characters. Moreover, we revealed a dynamic load-balancing technique on distributed parallel processing to sp … More eed up the processing of frequent variable pattern extraction.(2) Network Structure ConstraintsTo solve the network structure constraints that are represented as understanding databases with a network relationship, we revealed a method for decomposing the network relation of a Blog user space using a clustering technique. Sub-networks extracted by the decomposition denote Blog user communities.(3) Spatial Data ConstraintsTo solve special data constraints included in constraint databases that store special information, we focused on logs of Web services that are accessed from cellular phones tracked by GPS, and revealed a method to speed up the extraction of frequent neighboring attribute patterns from constraint databases that store spatial objects located in two-dimensional space.(4) Computational Geometry ConstraintsTo solve computational geometry constraints, we focused on a reconciliation graph that is constructed by connecting the leaf layers of two ordered heterogeneous trees, i.e., genetic and taxonomic trees. As a result, we revealed a method that drastically reduces the number of crossovers on a reconciliation graph.(5) Finite Domain ConstraintsTo solve finite domain constraints defined over finite sets, we focused on a job-shop scheduling problem that is defined by n jobs J_1, J_2, ., J_n of varying sizes, which need to be scheduled on m identical machines, while trying to minimize the total length of the schedule. As a result, we revealed a method to speed up the computation of a constraint solver in PC cluster environments. Less

约束查询处理的中心研究主题包括研究解决约束数据库中的约束满足问题的方法。在本研究开始时，我们研究了与约束数据库处理相关的许多框架。字符序列、网络结构、空间数据、计算几何、有限域等方面的研究成果如下：(1)字符序列约束，以解决表示为提取频繁的字符序列约束。为了从存储字符或单词序列的数据库中获取子序列，我们专注于分子序列数据库，并揭示了使用正则表达式提取频繁序列模式的方法，该正则表达式能够表示可变通配符区域和模糊字符。此外，我们还揭示了一种动态负载平衡技术。 (2)网络结构约束为了解决表现为理解具有网络关系的数据库的网络结构约束，我们提出了一种分解网络关系的方法使用聚类技术提取的博客用户空间的子网络表示博客用户社区。(3)空间数据约束为了解决存储特殊信息的约束数据库中包含的特殊数据约束，我们重点关注以下Web服务的日志：通过GPS跟踪的手机访问，并揭示了一种加速从存储位于二维空间中的空间对象的约束数据库中提取频繁相邻属性模式的方法。（4）计算几何约束解决计算几何问题由于约束条件，我们专注于通过连接两个有序异质树（即遗传树和分类树）的叶层构建的协调图。因此，我们揭示了一种可以显着减少协调图上交叉数量的方法。（5） ) 有限域约束为了解决在有限集上定义的有限域约束，我们重点关注由 n 个不同大小的作业 J_1, J_2, ., J_n 定义的作业车间调度问题，这些作业需要调度在相同的机器，同时尝试最小化调度的总长度，因此，我们揭示了一种在 PC 集群环境中加速约束求解器计算的方法。

项目成果

Extremal Optimizationによる調停グラフの交差数減少

使用极限优化减少仲裁图中的交集数量

• 发表时间: 2008
• 作者: 田村 慶一; 森 康真; 北上 始
• 通讯作者: 北上 始

グリッド環境下での分散型ワーカモデルを用いたModified PrefixSpan法の動的負荷分散方式

网格环境下分布式Worker模型的Modified PrefixSpan法动态负载均衡方法

• 发表时间: 2006
• 作者: 高木允; 田村慶一; 北上始
• 通讯作者: 北上始

Extraction for Frequent Sequential Patterns with Minimum Variable-Wildcard Regions

具有最小可变通配符区域的频繁序列模式的提取

• 发表时间: 2006
• 作者: Tomoyuki; Kato; Hajime; Kitakami; Makoto; Takaki; Keiichi; Tamura; Yasuma; Mori; Susumu; Kuroki
• 通讯作者: Kuroki

Extraction of Ambiguous Sequential Patterns with Least Minimum Generalization from Mismatch Clusters

从不匹配簇中提取具有最小泛化的模糊序列模式

• 发表时间: 2005
• 作者: Makoto; Takaki; Keiichi; Tamura; Toshihide; Sutou; Hajime; Kitakami
• 通讯作者: Kitakami

The Minimum Generalization of Flexible Sequence Patterns Extracted by Prefix-Projected Pattern-Growth Approach

前缀投影模式增长方法提取的灵活序列模式的最小泛化

• 发表时间: 2005
• 作者: Hajime; Kitakami; Makoto; Takaki; Keiichi; Tamura; Tomoaki; Kato; Susumu; Kuroki
• 通讯作者: Kuroki