用于web数据库模型匹配的方法和系统

具体实施方式

提供一种识别web数据库模式的方法和系统。在一个实施例中，模式匹配系统生成一个web数据库的界面模式和结果模式之间的映射，用来表示基础的数据库模式。Web数据库的界面模式表示可用于搜索的数据库属性。Web数据库的结果模式表示作为搜索结果部分显示的数据库属性。所述映射指示哪些界面属性与哪些结果属性具有相同的(也涉及相当的或相匹配的)含义。模式匹配系统也生成web数据库中的界面属性和结果属性到全局模式中的全局属性的映射，所述全局属性的语义是已知的。利用这些映射，搜索引擎服务可以用全局属性把查询公式化，映射所述查询至相应的界面属性，提交所述查询，并从对应期望全局属性的结果属性中检索数值。这样，该模式匹配系统识别web数据库的模式，该模式可用于搜索web数据库。

图1表示一个书商的web数据库的各种模式的框图。该Web数据库包括一个数据库模式101，一个界面模式102和一个结果模式103。该数据库模式表示web数据库的底层模式，在本例中包括属性标题、作者、出版商、ISBN号、格式和出版日期。网站提供一个搜索网页，以便用户可以访问来查找书籍。该web数据库的界面模式包括属性标题、作者、格式和ISBN号。用户可以为任何界面属性的组合指定搜索字符串，来搜索书籍数据库。网页中“你的搜索”字段允许用户在web数据库的所有属性中进行搜索。搜索的结果显示在一个结果网页上。该web数据库的结果模式包括标题、作者、出版商、格式和出版日期。搜索结果典型地提供多个多个条目，这些条目对应于与搜索请求匹配的数据库的每个条目。结果的每一条目一般包含每个结果属性的一个值。在本例中，所述界面模式有一个未包括在结果模式中的属性(即ISBN号)，结果模式有一个未包括在界面模式中的属性(即出版日期)。

除了使用web数据库的界面模式和结果模式外，模式匹配系统还使用一个特殊区域(domain-specific)的全局模式。一个区域的全局模式表示在该区域内web数据库通常使用的属性设置。例如，在书籍区域内的web数据库典型地具有包括标题、作者和出版商的属性，并且在汽车区域内的web数据库典型地具有包括构造、型号和年代的属性。一个全局模式也可以具有与其对应的样本全局属性值。例如，书籍区域的出版商属性可以具有包括“Random House”和“MITPress”的全局属性值。

为了生成映射，该模式匹配系统一开始就识别web数据库的区域全局模式，和web数据库的界面模式和结果模式。(识别所述模式的技术在下面进行描述)。模式匹配系统从全局属性的全局属性值(例如，从一组样本值)生成查询，并通过界面网页向web数据库提交查询(例如，通过搜索网页发送一个对应提交查询的HTTP请求)。模式匹配系统分析结果网页给出的结果，来确定那些界面属性对应哪些结果属性(“界面-结果对应”)，哪些全局属性对应哪些界面属性(“全局-界面对应”)，哪些全局属性对应哪些结果属性(“全局-结果对应”)。因为界面和结果模式对应单个网站的模式，因此该对应关系称为“内部站(intra-site)”匹配。当搜索时使用的界面属性的值与结果属性的值相匹配时，模式匹配系统识别一个界面属性可以对应一个结果属性。例如，当给出标题界面属性的值为“Harry Potter”时，许多结果条目都可能在标题界面属性里具有“Harry Potter”值。相反，当给出作者界面属性的值为“Harry Potter”来搜索时，只有少数的结果条目可能在标题界面属性里具有“Harry Potter”值。同样的，所述标题界面属性可能对应标题结果属性，但是作者界面属性可能不对应标题结果属性。

在一个实施例中，该模式匹配系统也可以产生不同网站的界面模式和结果模式之间的映射。模式匹配系统分析如上述提交的查询结果，并识别某一网站模式的哪个界面属性对应另一网站模式的哪个界面属性(“界面-界面对应”)，和某一网站模式的哪个结果属性对应另一网站模式的哪个结果属性(“结果-结果对应”)。例如，该模式匹配系统可以识别，某一网站的类型(type)界面属性可以对应另一网站的格式(format)界面属性。因为是在不同网站之间进行模式的匹配，所以该对应关系称为“相互站(inter-site)”匹配。该inter-site匹配信息可以在一个区域中搜索多个web数据库时使用。所述inter-site匹配信息也可以用来帮助确认intra-site匹配是否正确。

图2表示一个实施例中的intra-site匹配和inter-site匹配。椭圆202表示关于在一个书籍区域内的web数据库的模式。每个站点1…N具有一个界面模式(“IS”)和一个结果模式(“RS”)，并且所述区域具有一个全局模式(“GS”)。模式间的连线表示“intra-site”匹配和“inter-site”匹配。例如，站点1的IS和GS之间的线表示intra-site的全局-界面对应，站点1的IS和站点1的RS之间的线表示intra-site的界面-结果对应，站点1的IS和站点2的IS之间的线表示站点1和站点2间inter-site的界面-界面对应。

在一个实施例中，模式匹配系统生成一个事件立方体(occurrence cube)，对应web数据库的全局属性、界面属性和结果属性的每一组合，当搜索时全局属性值被用作该界面属性值时，该立方体识别该全局属性的全局属性值在该结果属性中出现的次数。模式匹配系统为每一界面属性提交多个查询。每个查询具有设为不同全局属性值的该界面属性值。例如，如果全局属性包括一个附带平装本、硬装本和光盘值的格式属性，和一个附带Rowling值的作者属性，那么模式匹配系统提交一个附带设为平装本的标题属性的查询，一个附带设为硬装本的标题属性的查询，一个附带设为光盘的标题属性的查询，和一个附带设为Rowling的标题属性的查询。该模式匹配系统为每个界面属性提交平装本、硬装本、光盘和Rowling的全局属性值的查询。该模式匹配系统为每一查询结果计数查询的全局属性值作为每一结果属性值出现的次数。例如，当提交一个带有设为平装本标题界面属性的查询时，可能只有很少或没有匹配，这表示该标题界面属性很可能与格式全局属性不匹配。相反，当提交一个带有设为平装本格式界面属性的查询时，可能找到许多匹配，且可以在格式结果属性内许多结果条目中找到搜索项“平装本”，这表示格式全局属性、格式界面属性和格式结果属性是相互对应的。特定的全局属性、界面属性和结果属性组合尤其是相对于其它的组合的高次数，表示所述属性很可能是对应的，即它们表示相同的语义内容。

生成事件立方体后，模式匹配系统创建用于全局-界面对应、全局-结果对应和界面-结果对应的事件矩阵。在一个实施例中，模式匹配系统通过把事件立方体的维数投影到一个平面上，来创建一个事件矩阵。为了生成全局-界面对应的事件矩阵，模式匹配系统把每一全局属性和界面属性的组合的所有结果属性出现的次数相加。该模式匹配系统以类似的方式生成全局-结果对应和界面-结果对应的生成事件矩阵。表1是一个全局-界面对应的事件矩阵的例子。

表1

          标题_GS     作者_GS     出版商_GS     ISBN_GS

作者_IS   93               534           0

标题_IS        345         501           0

出版商_IS 62          184                2

关键词_IS 120         248         143          

ISBN_IS   0           0           0             258

虽然计算的值是成对属性之间对应关系的一个指示，但是相对值比绝对值更能指示匹配关系。尤其是，一个高出现次数不一定表示对应的属性。例如，作者_IS和出版商_GS的矩阵元素(534)在矩阵中是最大值，但是作者_IS和出版商_GS在语义上不是相互对应的。通常，给出一个特定矩阵元素m_ij，在界面属性i和全局属性j的所有元素中，它的相对值比它的绝对值更加重要。例如，可能包括“你的搜索”字段，并且不是书籍区域的真正属性的关键词_IS，具有一个与全局属性相似的特性，表示其不可以与任何一个全局属性很好得匹配。出版商_IS和出版商_GS(468)的元素不是出版商_GS元素中最高的。然而，与其它出版商IS的元素相比，它较大。

为了识别哪一对属性是对应的，所述模式匹配系统估计属性对的一个交互信息内容。交互信息内容也可以被称为交叉熵(cross-entropy)和信息增益(information gain)。所述模式匹配系统根据模式的属性，假设每一模式代表一个web数据库的分区。来自分区重叠最大的不同模式的成对属性可能对应。在一个实施例中，所述模式匹配系统根据下列方程式估计一对属性间的交互信息：

$>>EMI>>(>>S>>1>i>>>,>>S>>2>j>>>)>>=>>>m>ij>>M>>log>>>>m>ij>>M>>>>>m>>i>+>>>M>>*>>>m>>+>j>>>M>>>>->->->>(>1>)>>>s>$

其中EMI是估计的模式S_1i的第i属性和模式S_2j的第j属性之间的交互信息，M是m_i+是m_+j是

表1事件矩阵的EMI矩阵如表2所示。

表2

          标题GS    作者GS    出版商GS    ISBNGS

作者IS    -0.04        0.06        0.00

标题IS      -0.03     -0.01       0.00

出版商IS  -0.03     -0.02         -0.01

关键词IS  -0.01     0.01      -0.07       0.17

ISBNIS    0.00      0.00      0.00       

当一个EMI矩阵元素大于其它相同界面属性的元素(即在同一行中)，并且也大于其它相同全局属性的元素(即在同一列中)时，所述模式匹配系统检测属性间的匹配关系。如长方形所示的，相应的属性彼此之间在信息内容上，比与相反模式的其它属性具有更大重叠。例如，对应作者界面属性和作者全局属性，作者_IS和作者_GS的EMI矩阵元素(即0.11)是最大的，并是正确的匹配。属性的匹配由下列方程表示：

MAP(S_1i，S_2j)＝match爓hen e_ij≥e_ik|k≠j燼d爘_ij≥e_ik k≠i    (2)

其中，MAP表示模式S₁的第i属性和模式S₂的第j属性是否相匹配，e_ij是对应模式S₁的第i属性和模式S₂的第j属性的EMI矩阵元素。

在一个实施例中，所述模式匹配系统识别不同web数据库的属性间的匹配关系。该模式匹配系统基于web数据库的对应事件矩阵的向量之间的相似性，来识别匹配关系。例如，表3表示模式S₁的全局-界面事件矩阵，表4表示模式S₂的全局-界面事件矩阵。全局模式_GS是{标题，作者，出版商，ISBN}，站点1的界面模式IS₁是{作者₁，题目₁，出版商₁，关键词₁，ISBN₁}，站点2的界面模式IS₂是{题目₂，作者₂，ISBN₂}。

表3

            T_G        A_G        P_G       I_G

A₁         93         498        534        0

T₁         451        345        501        0

P₁         62         184        468        2

K₁         120        248        143        275

I₁         0          0          0          258

表4

            T_G        A_G        P_G       I_G

T₂         166        177        118        0

A₂(P)      39         331        406        0

I₂         0          0          0          18

属性A1由表3中第一行的向量表示，属性A2由表4中第二行的向量表示。该模式匹配系统用下列方程来计算两属性间的相似性：

$>>EVS>>(>>S>>1>i>>>,>>S>>2>j>>>)>>=>>>>\Sigma >k>>>a>ik>>>b>jk>>>>>>\Sigma >k>sup>>a>ik>2sup>\; >*>>>\Sigma >k>sup>>b>jk>2sup>\; >>>->->>(>3>)>>>s>$

其中EVS是模式S₁的第i属性和模式S₂的第j属性间的估计向量相似性，a_ik表示模式S₁的事件矩阵的值，b_jk表示模式S₂的事件矩阵的值。

表5表示从表3和表4中导出的估计向量相似性。

表5

          T2        A2(P)        I2

A₁       0.84           0

T₁         0.84         0

P₁       0.71      0.95         0.01

K₁       0.72      0.67         0.66

I₁       0         0           

当一个EVS矩阵元素大于同一网站的相同界面属性的其它元素，并也大于其它网站的相同界面属性的其它元素时，所述模式匹配系统检测属性间的匹配关系。表5中的长方形表示行和列中的最大相似性值，也表示正确的匹配。虽然IS₂，作者₂的第二属性不能与GS的出版商₂正确匹配，但是模式匹配系统运用inter-site匹配来校正所述匹配。

在一个实施例中，所述模式匹配系统交叉确认(cross-validates)全局-界面对应、全局-结果对应、界面-结果对应、界面-界面对应和结果-结果对应，以便识别和校正可能错误的匹配。该模式匹配系统基于匹配的全局属性将界面属性(和类似的结果属性)集群为多个群集(cluster)。例如，与某一个全局属性匹配的各种web数据库的属性表示一个群集。该群集是基于intra-site匹配的。inter-site匹配也可以用于交叉确认群集。如果intra-site和inter-site匹配完全正确，那么web数据库的每一属性将只映射到在相同群集中其它web数据库的属性。换句话说，web数据库的属性一向是彼此映射，且被映射到全局属性。在一个实施例中，模式匹配系统表示web数据库模式的属性为顶点，inter-site匹配为顶点之间的边缘。模式匹配系统划分顶点，这样使边缘切割(edge-cut)最小化。所述边缘切割(edge-cut)是分区间所有边缘加权和(例如，每一边缘具有相同的权)。通过最小化边缘切割(edge-cut)，模式匹配系统使不同群集的顶点之间的边缘数目最小化。

在一个实施例中，使用初始群集作为初始分区，且只要切割的数目降低就把顶点从一个群集移动到另一群集，模式匹配系统将边缘切割(edge-cut)近似于最小化。通常，一个顶点被移动至其中有它大多数相邻顶点的群集。相邻的顶点之间具有一个边缘。因为如果多个临近顶点发生移动，这个顶点就需要移动，那么模式匹配系统可以使用多通道以便边缘切割(edge-cut)集中到局部最佳。当边缘切割(edge-cut)集中时，模式匹配系统分解交叉的群集，该群集通过放弃交叉群集匹配在站点S₁的A_i属性和站点S₂的B_j属性之间匹配，所述站点S₂包含在两个群集C₁和C₂中，并再匹配A_i到站点S₂的B_k属性，所述站点S₂群集到C₁，反之亦然。

图3表示一个实施例中模式匹配系统的分区的一个通道。在该例中，全局模式包含两个属性{作者，出版商}，5个web数据库包含IS属性IS₁＝{Aa}，IS₂＝{Ba，Bp}，IS₃＝{Ca，Cp}，IS₄＝{Da，Dp}和IS₅＝{Ea，Ep}。群集301和302基于其匹配(intra-site匹配)的全局属性来指示属性(用顶点表示)的初始群集，成对属性之间的边缘指示属性匹配(inter-site匹配)。在初始状态，Aa不能与出版商全局属性正确匹配，也不能与Bp正确匹配，但是它在作者范畴里已经与其它三个属性正确匹配。因此，该模式匹配系统将交叉群集边缘数目从3减少到1来移动Aa。该移动把Aa的属性从出版商校正到作者全局属性。该移动之后，模式匹配系统消除Aa和Bp之间的边缘，并增加Aa和Ba之间新的边缘(站点2的属性匹配到作者全局属性)。群集311和312表示校正后的对应。

全局模式、界面模式和结果模式可以用各种技术来识别。一些识别全局模式的技术依靠属性的名字和元素的结构。(参见S.Castano，V.Antonellis，andS.Vimercati.Global Viewing of Heterogeneous Data Sources.IEEE Trans.Data andKnowledge Eng.，vol.13，no.2，2001；和B.He，and C.C.Chang.Statistical SchemaMatching across Web Query Interfaces.Proc.ACM SIGMOD conf.，2003，这里引入作为参考)其它技术依靠形式本体论(参见B.He，and C.C Chang.Statistical SchemaMatching across Web Query Interfaces.Proc.ACM SIGMOD Conf.，2003；和F.Hakimpour，and A.Geppert.Global Schema Generation Using FormalOntologies.Proc.21st Conf.on Conceptual Modeling，2002，这里引入作为参考)全局属性值样本可以从各种web数据库样本中收集或手动产生。Web数据库的界面模式可以从作为HTML说明的查询网页的输入关联(input-related)标签中识别。(参见A.Arasu，and H.Garcia-Molina.Extracing Structured Data from WebPages.Proc.ACM SIGMOD Conf.，2003；C.H.Chang，and S.C.Lui.IEPAD：InformationExtraction based on Pattern Discovery.Proc.10th World Wide WebConf.，681-688，2001；V.Crescenzi，G.Mecca and P.Merialdo.ROADRUNNER：TowardsAutomatic Data Extraction from Large Web Sites.Proc.27thVLDB.Conf.，109-118，2001；和J.Wang and F.Lochovsky.Data Extraction and LabelAssignment for Web Databases.Proc.12th World Wide Web Conf.，187-196，2003，这里引入作为参考)一项技术基于嵌套在HTML页面中的重复图案(repeated-pattern)来生成一个规则表达式(regular-expression)(参见J.Wang and F.Lochovsky.DataExtraction and Label Assignment for Web Databases.Proc.12th World Wide WebConf.，187-196，2003，这里引入作为参考)本领域普通技术人员可以理解，每一模式也可以手动或结合手动来识别，也可以用自动化设备识别。

图4表示一个实施例中模式匹配系统的部件的方框图。模式匹配系统410通过通信链路402连接到多个web数据库站点401。该模式匹配系统包括一个内部站(intra-site)部件411，一个相互站(inter-site)匹配部件412，一个交叉确认(cross-validate)部件413，一个立方体生成部件414，一个立方体投影部件415，一个EMI计算部件416，和一个匹配矩阵生成部件417。该模式匹配系统还包括一个立方体存储器421，一个投影存储器422，一个EMI存储器423，和一个匹配存储器424。intra-site匹配部件调用立方体生成部件来生成一个事件立方体，并调用立方体投影部件来生成全局-界面、全局-结果和界面-结果事件矩阵。intra-site匹配部件也调用EMI计算部件基于事件矩阵计算估计交互信息，并调用匹配矩阵生成部件来识别哪个属性对是匹配的。cross-validate部件改变没有正确匹配的属性间的匹配。立方体存储器包含事件立方体，投影存储器包含事件矩阵，EMI存储器包含EMI矩阵，匹配存储器包含匹配矩阵。

模式匹配系统上的计算装置包括一个中央处理单元、内存、输入装置(例如，键盘和点击设备)、输出设备(例如，显示设备)和存储设备(例如磁盘驱动器)。所述内存和存储设备是计算机可读介质，可以包含实现所述模式匹配系统的指令。另外，数据结构和消息结构可被存储或通过数据传输媒体被发送，例如作为通信链路上的信号。可以采用各种通信链路，如因特网、局域网、广域网或点对点的拨号连接。

该模式匹配系统可以在各种操作环境下实现，包括个人计算机、服务器计算机、手提或膝上计算机、多处理器系统、微处理器系统、可编程电子消费装置、网络PC、小型计算机、大型计算机、包括任何上述系统或设备分布式计算环境，等等。

该模式匹配系统在上下文中可以概括地描述为计算机可执行指令，例如由一个或更多计算机或其它装置执行程序模块。通常，程序模块包括例程、程序、对象、分量、数据结构等等，可执行特定的任务或实现特定的抽象数据类型。典型地，在各种实施例中程序模块的功能可以按期望的进行结合或分配。

图5表示一个实施例中intra-site匹配部件处理过程的流程图。该部件识别web数据库的全局-界面、全局-结果和界面-结果的对应关系。在方框501中，该部件调用立方体生成部件来生成事件立方体。在方框502-506中，该部件循环选择成对的模式(即全局和界面，全局和结果，界面和结果)，并生成表示每对对应关系的匹配矩阵。在方框502中，该部件选择下一对模式。在判别方框503中，如果所有的成对模式都已经选定，那么该部件工作完成，否则该部件继续到方框504。在方框504中，该部件调用立方体投影部件来生成选定成对模式的事件矩阵。在方框505中，该部件调用EMI计算部件，来估计选定成对模式的成对属性之间的交互信息。在方框506中，该部件调用匹配矩阵生成部件，来生成指示选定成对模式的属性对应关系的匹配矩阵。然后该部件循环至方框502，选择下一对模式。

图6表示一个实施例中立方体生成部件处理过程的流程图。该部件基于全局模式、界面模式和结果模式，生成一个web数据库的事件立方体。一个事件立方体是一个三维矩阵，它把每一全局属性、界面属性和结果属性的组合映射为计数。该计数是查询的结果条目在该结果属性中具有该全局属性值的次数，其中查询具有被设置为该全局属性的全局属性值的该结果属性。在方框601中，该部件选择下一全局属性。在判定方框602中，如果所有的全局属性都已经选定，该部件返回，否则该部件继续到方框603。在方框603中，该部件选择已选定全局属性的下一全局属性值。在判定方框604中，如果所有的已选定全局属性的全局属性值都已经选定，该部件循环至方框601来选择下一全局属性。否则该部件继续到方框605。在方框605-609中，该部件循环选择每一界面属性并提交一个带有设为选定全局属性值的那个界面属性的查询。本领域普通技术人员可以理解，一些界面属性的值域是可以有限制的。例如，如果一个界面属性是用HTML SELECT元素来表示的，那么它的值域可以限制为与OPTION元素相关的值。在这种情况下，该部件可以只提交用于与选择(option)值“相似”的全局属性值的查询。如果一个全局属性值包含一个option值，可以认为它是相似的。本领域普通技术人员可以理解，也可以采用其它衡量相似性的方法。CHECKBOX和RADIOBOX元素的查询可以按类似的方式处理。因为TEXTBOX的值域可能未知，该部件可以完全提交所有使用TEXTBOX表示界面属性的全局属性值的查询。在一个实施例中，该部件只为每一查询的一个界面属性设置数值。其它界面属性的值可以具有一个网站定义的默认值。在方框605中，该部件选择下一界面属性。在判定方框606中，如果所有界面属性已经选定，该部件循环至方框603来为选定的全局属性选择下一全局属性值。在方框607中，该部件利用选定的界面属性和选定的全局属性值，来公式化查询。在方框608中，该部件将公式化的查询提交至网站。在方框609中，该部件基于查询结果更新事件立方体，并循环至方框605来选择下一界面属性。

图7表示一个实施例中立方体更新部件处理过程的流程图。该部件传送一个全局属性、一个全局属性值、一个界面属性和一个查询结果的指示。在方框701中，该部件选择结果的下一条目或行。在判定方框702中，如果所有结果条目都已经选定，该部件返回，否则该部件继续到方框703。在方框703中，该部件选择下一结果属性或列。在判定方框704中，如果所有的结果属性已经选定，该部件循环至方框701来选择下一结果条目，否则该部件继续到方框705。在方框705中，如果全局属性值等于选定条目的选定结果属性值，那么该部件继续到方框706，否则该部件循环至方框703来选择下一选定条目的结果属性。在方框706中，该部件在通过全局属性、通过界面属性和选定结果属性的事件立方体内增加计数。然后该部件循环至方框703来选择下一选定条目的结果属性。

图8表示一个实施例中立方体投影部件处理过程的流程图。在该实施例中，该部件生成全局-界面对应的事件矩阵。所述模式匹配系统可以以相似的方式生成全局-结果对应和界面-结构对应的事件矩阵。在该实施例中，该部件对全局属性的结果属性和界面属性对的结果求和，来将事件立方体的三维投影为相应矩阵的二维。本领域普通技术人员可以理解，除直接求和外还可以采用其它投影技术。例如，该部件可以采用加权求和，其中加权是基于在结果模式的自动识别期间得到的可信度。在方框801中，该部件选择下一全局属性。在判定方框802中，如果所有的全局属性都已经选定，该部件返回，否则该部件继续到方框803。在方框803中，该部件选择下一界面属性。在判定方框804中，如果所有的界面属性已经选定，该部件循环至方框801来选择下一全局属性，否则该部件继续到方框805。在方框805中，该部件选择下一结果属性。在判定方框806中，如果所有的结果属性已经选定，该部件循环至方框803来选择下一界面属性，否则该部件继续到方框807。在方框807中，该部件将选定界面属性和结果属性的事件立方体中的计数加上选定全局属性，界面属性和全局属性的事件矩阵中的计数。然后该部件循环至方框805来选择下一结果属性。

图9表示一个实施例中EMI计算部件处理过程的流程图。该部件采用方程式1估计在一个事件矩阵中成对属性的交互信息。本领域普通技术人员可以理解，可以采用各种技术来估计成对属性匹配的似然性。该部件传送一个事件矩阵并返回EMI矩阵。在方框901中，该部件计算事件矩阵内所有计数的和。在方框902中，该部件计算事件矩阵的每一行内计数的和。在方框903中，该部件计算事件矩阵的每一列内计数的和。在方框904-908中，该部件循环选择事件矩阵每一对事件矩阵属性，并确定属性匹配的似然性。在方框904中，该部件选择事件矩阵的下一行。在判定模块905中，如果事件矩阵的所有行都已经选定，那么该部件返回，否则该部件继续到方框906。在方框906中，该部件选择事件矩阵的下一列。在判定方框907中，如果事件矩阵的所有列都已经选定，那么该部件循环至方框904来选择事件矩阵的下一行，否则该部件继续到方框908。在方框908中，该部件计算由选定的行和列来表示的属性的估计交互信息。然后该部件循环至方框906来选择下一列。

图10表示一个实施例中匹配矩阵生成部件处理过程的流程图。该部件传送一个矩阵，例如EMI矩阵，该矩阵指示成对属性匹配的似然性。如果一对属性的似然性是双属性中最高的(例如，在表示一个属性的行中最高的和表示其它属性的列中最高的)，该部件找出所述的属性匹配。在方框1001中，该部件选择传送矩阵(passed matrix)的下一行。在判定方框1002中，如果传送矩阵(passedmatrix)的所有行都已经选定，那么该部件返回，否则该部件继续到方框1003。在方框1003，该部件选择传送矩阵(passed matrix)的下一列。在判定方框1004中，如果传送矩阵(passed matrix)的所有列都已经选定，那么该部件循环至方框1101来选择传送矩阵(passed matrix)的下一行，否则该部件继续到方框1005。在判定方框1005中，如果选定行和列的值是该行内最高的，那么该部件继续到方框1006，否则该部件循环至方框1003来选择下一列。在判定方框1006中，如果选定行和列的值是该列内最高的，那么该部件继续到方框1007，否则该部件循环至方框1003来选择下一列。在方框1007中，该部件设定选定行和列的匹配矩阵的值，来指示匹配关系，然后循环至方框1003来选择选定行的下一列。

图11表示一个实施例中inter-site匹配部件处理过程的流程图。该部件识别一个网站的哪一属性(界面和结果)与另一网站的哪一属性相匹配。该部件使用网站的全局-界面对应的事件矩阵，来识别界面模式的匹配，使用网站的全局-结果对应的事件矩阵，来识别结果模式的匹配。在方框1101中，该部件调用立方体生成部件来生成站点A的事件立方体。在方框1102中，该部件调用立方体投影部件来生成站点A的事件矩阵。在方框1103中，该部件调用立方体生产部件来生成站点B的事件立方体。在方框1104中，该部件调用立方体投影部件来生成站点B的事件矩阵。在方框1105中，该部件调用一个计算界面属性的估计向量相似性的部件，来生成来自站点A和站点B的界面属性的匹配似然性。本领域普通技术人员可以理解，可以采用许多不同技术来估计这个似然性，向量相似性只是一个例子。在方框1106中，该部件调用匹配矩阵生成部件，来生成一个指示哪些成对界面属性是相匹配的矩阵，该匹配矩阵生成部件传送估计界面属性的矢量相似性矩阵。在方框1107中，该部件调用一个计算估计向量相似性的部件，来生成结果属性的估计向量相似性矩阵。在方框1108中，该部件调用一个匹配矩阵生成部件，来生成一个指示哪些成对结果属性相匹配的矩阵。然后该部件完成处理。

图12表示一个实施例中计算估计向量相似性的部件处理过程的流程图。该部件传送一个界面-界面对应的或一个结果-结果对应的事件矩阵，并确定每一对属性匹配的似然性。在方框1201中，该部件选择站点A的下一属性。在判定方框1202中，如果站点A的所有属性已经选定，那么该部件返回，否则该部件继续到方框1203。在方框1203中，该部件选择站点B的下一属性。在判定方框1204中。如果站点B的所有属性已经选定，那么该部件循环至方框1201来选择站点A的下一属性，否则继续到方框1205。在方框1205中，该部件按照方程式3计算选定属性的估计向量的相似性，然后循环至方框1203来选择站点B的下一属性。

图13表示一个实施例中cross-validate部件处理过程的流程图。当inter-site匹配指示一个intra-site匹配不正确时，该部件改变属性的匹配。在方框1301中，该部件选择下一全局属性。在判定方框1302中，如果所有的全局属性已经选定，那么该部件完成处理，否则该部件继续到方框1303。在方框1303中，该部件选择下一网站。在判定方框1304中，如果所有网站已经选定，那么该部件循环至方框1301中来选择下一全局属性，否则该部件继续到方框1305。在方框1305中，如果选定网站具有一个属性与选定的全局属性相匹配，那么该部件继续到方框1306，否则该部件循环至方框1303来选择下一网站。在判定方框1306中，如果该选定属性移动至另一全局属性，那么该部件继续到方框1307，否则该部件循环至方框1303来选择下一网站。在方框1307中，该部件改变选定属性来匹配不同的全局属性。在方框1308中，该部件改变选定属性的intra-site匹配。然后该部件循环至方框1303来选择下一网站。

本领域普通技术人员可以理解，虽然在这里结合附图描述了模式匹配系统的特定实施例，但是可以在不背离本发明精神和范围的情况下做出各种改变。因此，本发明不仅限于所附的权利要求。