查询算法（共8篇）
查询算法 篇1
通过由网站提供的查询接口提交查询来获取数据是Deep Web中信息获取的主要方式,而且自动抽取查询接口中的属性并生成合法有效的查询条件是提升访问Deep Web能力的有效方法。因此数据源的发现与查询接口的识别在Deep Web应用系统中处于特别重要的地位,也是查询接口集成阶段和信息获取阶段的基础。
从形式上来讲,Deep Web查询接口均以表单(form)的形式出现在页面中,因此利用表单的结构特征作为Deep Web查询接口的判断依据是一种合理的解决方式。但并不是所有的表单都是查询接口,如用户注册、bbs留言板、搜索引擎等都以表单的形式出现,却均不属于查询接口的范畴。由此,需要对Web中的表单进行提取和识别,识别出哪些是真正的查询接口。由于Deep Web蕴含了数量众多的查询接口,且这些查询接口又时刻处于变化之中,这又无形中增加了识别查询接口的难度。
1 数据源与查询接口
1.1 数据源的发现与查询接口识别
就此经典的解决方案大致有如下三种[1]:一是从completeplanet.com和invisible-web.net这样的站点中获取;二是首先收集WWW站点的IP地址,然后按照一定的策略遍历所有IP;三是利用搜索引擎进行搜索Web数据库所在的网站。
第三种方案由于必须向搜索引擎提交查询,因此这种方案是基于某个领域的Web数据库的发现,因而更加具有实际应用价值。其关键在于如何向搜索引擎提交有效的查询,使得含有Web数据库的网站尽可能多地出现在查询结果中,并使其排名尽量靠前。
同时,部分研究人员在传统搜索引擎爬虫的基础上开发出了Deep Web爬虫,并通过对网页的爬取、分析来定位Deep Web数据源[2,3],在此基础上文献[4,5,6]增加了对数据源所属主题的分类,使得通过Deep Web爬虫发现的数据源更加具有针对性,同时也减轻了数据源分类的工作量。
1.2 查询接口的识别方式
在数据源发现的基础上需要将其中的查询接口识别出来,通常通过两种方式来实现查询接口的识别:
一类是提交查询法:需通过提交试探性查询,根据返回的结果进行判断是否为Deep Web查询页面,该方法一般通过表单的结构特征,按照一定的策略自动填写表单,并根据返回结果的情况来对其是否为Deep Web查询接口进行判断[7],此方法适用于结构简单的搜索页面。此方法虽然加大了网络的开销,但是可以根据返回结果的情况对数据库内容进行分析,从而可以对Deep Web接口进行较高精度的识别。
另一类是非提交查询法:直接利用网页表单的结构信息,如对控件的类型、其内部属性以及描述控件的标签进行特征提取,从而实现对查询接口的判断。当数据库中表结构可以完全由页面表单的特征来表示的时候常采用此方法。
由于网页表单很容易获取,并且非提交查询法比较适合对内容和结构多变的表单进行判断,因而大部分研究者倾向采用该方法来识别Deep Web查询接口。如Juliano Palmieri Lage等人提出了两个根据实际经验总结出的启发式规则来判断网页表单是否为查询接口[8];Jared[9]等人则首先提取查询接口的特征,在这些特征之上利用C4.5算法得到一棵决策树,通过这棵决策树来找出真正的查询接口,从而实现了查询接口的识别。
1.3 查询接口与表单
Deep Web的查询接口主要由基于表单的形式体现。表单是指存在与页面中的、供使用者输入信息的区域。使用者可以在文本框中输入文字,或者通过点击下拉框来进行选择,或者通过点击一些小框进行选择。在填写选择完毕后,通过点击“提交”按钮来把所填写或者选择的信息提交出去。这些交互性的文本框、下拉框和按钮等称为控件,它们的内容就是相应控件的值。例如:一个包含了部分基本控件的表单代码如下,
其运行结果如图1。
之间的控件主要包括、
摘要：查询接口是Deep Web的唯一入口,在对后台数据库展开研究时,查询接口的识别凸显重要。该文首先分析了查询接口的结构特点,并总结出一系列可用于进行查询接口识别的启发式规则,并通过概率计算对规则的使用顺序进行了优化,实验证明,具有较好的使用价值。
关键词：Deep Web,查询接口,表单,正则表达式
参考文献
[1]刘伟,孟小峰,孟卫一.Deep Web数据集成研究综述[J].计算机学报,2007.30(9):1475-1489.
[2]Raghavan S,Garcia-Molina H.Crawling the Hidden Web[C].Proceedings of the 27th International Conference on Very Large DataBases.Roma.2001:129-138.
[3]Cope J,craswell N.Automated Discovery of Search Interfaces on the Web[C].Proc.of the 4th Australasian Database Conference(ADC2003).2003.
[4]王辉,刘艳威,左万利.使用分类器发现特定领域深度网入口[J].软件学报,2008(2):246-256.
[5]Barbosa L,Freire J.Searching for Hidden Web Databases[C].Proc.of the 8th International Workshop on the Web and Databases(WebDB 2005).
[6]Barbosa L,Freire J.An Adaptive Crawler for Locating Hidden Web Entry Points[C].Proceedings of the 16th international Conference onWorld Wide Web.New York:ACM,2007:441-450.
[7]Pang Bo,Lee Lillian,Vaithyananthan S.Thumbs up Sentiment classification using machine Learning techniques[C].Proceeings of the2002 Conference on Emprical Methods in Natural Language Processing.NJ,UAS:Association for Computational Liguistics Morristown2002:79-86.
[8]Julian Palmieri Lage,Altigran S da Silva,Paulo B Golgher,et,al.Automatic Generation of Agents for Collecting Hidden Web Pages forData Extraction[J].Data and Knowledge Engineering,2004(2):177-196.
[9]Jared Cope,Nick Craswell,David Hawking.Automated Discovery of Search Interfaces on the Web[C].Proceedings of the 14th Aus-tralasian Database Conference(ADC2003):Adelaide Australia,2003.
查询算法 篇2
关键词：多维数据库；模糊查询；Edit Distance算法
中图分类号：TP311.131文献标识码：A文章编号：1007-9599 (2010) 14-0000-02
The Fuzzy Query Algorithm Study on Multi-dimensional Analysis Application
Jing Rui
(Local Taxation Bureau of Jilin,Changchun130000,China)
Abstract:An improved Edit Distance algorithm has completed in C# in this paper,and embed into multidimensional reports application on SQLServer ReportingServices.Achieved the fuzzy query function for multidimensional database applications.Number of actual operation application shows that the combination of fuzzy query algorithm with multidimensional dabases is one of the effective ways to improves the practical and the user experience.
Keywords：Cube;fuzzy query;Edit Distance algorithm
在多维数据库中，维度是多维数据集的基本组件。多维数据集逻辑上就是维度成员在空间上构成的超立方体，数据的度量值就存储在这些维度成员的交叉点上。由于数据的度量值事先按着维度的交叉关系聚集，与传统的关系数据库系统相比，多维数据库在查询数度、并发响应能力方面有明显的优势，人们可以通过多维视图来观察、分析和展现数据。
在现有的多维数据库系统中，维度成员及其层次结构是建立在离散化的、完全划分的基础之上的，维度成员彼此分立，并且按着成员属性构建了结构稳定的层次结构。目前成熟的多维数据查询技术只能支持精确维度成员选择。而实际应用，经常会遇到模糊的、不完全的查询条件问题。例如，在基于多维数据库的税收分析系统中，由于业务的特殊性，“一户式分析”是系统被广泛使用功能。而纳税人的基本信息具有非常大的不规则性，并且数量巨大，通过“模糊查询”的方式筛选关注对象，成为基本的用户体验需求。针对这一实际问题，本文利用成熟的Edit Distance算法与ReportingService服务，提出一个多维数据模糊查询机制，并给出实现方法。
一、Edit Distance算法思想
字符串模糊搜索（fuzzy string searching）（通常也成为字符串近似匹配approximate string matching）是一种在一个字符串中查找近似的匹配模板的技术。
1965年俄国科学家Vladimir Levenshtein首先提出了一种算法用于计算计算从原串（s）转换到目标串（t）所需要的最少的插入，删除和替换的数目，这种数据被称为编辑距离（Edit Distance）也叫Levenshtein distance（LD）。基于Edit Distance开发的模糊搜索算法，在计算机技术领域得到广泛应用，除了直接用于数据库查询应用以外，还可应用于自然语言理解、拼写检查、欺诈检测，乃至核苷酸的序列匹配等。
算法的核心思想是利用从源字符串转换成目标字符串所必须的基本操作次数了测量使用字符串的接近程度。通常的基本操作为：
插入：tst→test
删除：test→tst
替换：tent→test
增加一个NULL（这里使用λ）字符后，这三种操作被转换成一种通用的替换模式：
插入：tsλt→test
删除：tλst→tst
替换：tent→test
从上面的介绍中我们可以看到，字符串模糊查找的问题可以转化成两个字符串编辑距离的计算。
两个字符串x和y之间的距离d（x，y）就是从x转换成y所进行的一系列操作的代价。这一系列操作的代价等于每个操作代价之和。所谓的操作是一个δ（z，w）=t变换的有限集，这里z，w是不同的字符串，t是一个正整数。一旦操作已经将一个字字符串z转换成w，就不需要在w上做其他操作。
对于上述的三种常用操作，操作集合可以限定为：
插入：δ（ε，a），即插入字符a
删除：δ（a，ε），即删除字符a
替换：δ（a，b），即对于a≠b，用b替换a。
为了简单起见，可以将每种操作所花费的操作代价定位1。那么，两个字符串之间的编辑距离就可以理解为：“使两个字符串相等所需要的插入、删除和替换操作的最小次数”。
二、算法描述
设：
n，m分别为字符串s和t的长度；
si（i ）为字符串s中的第i个字符记；
ti（i ）为字符串t中的第i个字符记；
d[n，m]为一个正整数二维矩阵。
则，计算s，t之间编辑距离的函数d（s，t）的算法如下：
Step 1：
如果n=0，返回m，并结束
如果m=0，返回n，并结束
构建n+1*m+1的二维矩阵d[n，m]
Step 2：
将d[n，m]的第一行分别赋值为0……n
将d[n，m]的第一列分别赋值为0……m
Step 3：
检测s中的每个字符（1≥i≤n）
Step 4：
检测t中的每个字符（1≥j≤m）
Step 5：
如果si=tj，则cost=0
如果si≠tj，则cost=1
Step 6：
将距离矩阵的d[I，j]单元格赋值为下面三个数值中的最小值：
（1）该单元格上方的单元格的数值加1：d[i-1，j]+1
（2）该单元格左边的单元格的数值加1：d[i，j-1]+1
（3）该单元格左上方的单元格的数值加cost：d[i-1，j-1]+cost
Step 7：
完成3，4，5，6步骤后，返回d[n，m]，得到d（s，t）距离值。
三、算法实现及其改进
在实际应用场合，除了插入、删除和替换三种基本操作以外，相邻字符的交换也是经常遇到的一种基本操作。如下例所示：
交换：tsett→test。
下面是采用C#重写的，改进的Levenshtein distance算法：
public static int LevenshteinDistance（string src，string dest）
{
int[，]d=newint[src.Length+1，dest.Length+1]；
inti，j，cost；
char[]str1=src.ToCharArray（）；
char[]str2=dest.ToCharArray（）；
for（i=0；i<=str1.Length；i++）{d[i，0]=i；}
for（j=0；j<=str2.Length；j++）{d[0，j]=j；}
for（i=1；i<=str1.Length；i++）{
for（j=1；j<=str2.Length；j++）{
if（str1[i-1]==str2[j-1]）
cost=0；
else
cost=1；
d[i，j]=
Math.Min（
d[i-1，j]+1，//Deletion
Math.Min（
d[i，j-1]+1，//Insertion
d[i-1，j-1]+cost））；//Substitution
if（（i>1）&&（j>1）&&（str1[i-1]==str2[j-2]）&&（str1[i-2]==str2[j-1]））
{d[i，j]=Math.Min（d[i，j]，d[i-2，j-2]+cost）；}
}
}
return d[str1.Length，str2.Length]；
}
四、ReportingService报表参数的模糊查询
SQL Server 2005/2008的Reporting Services是一个基于服务器的报表平台，可以从关系数据源、多维数据源和基于XML的数据源检索数据、发布可通过多种格式查看的报表。由于报表服务没有内置的模糊条件查询控件，所以在开发报表门户应用时，实现多维数据集的模糊条件查询，成为实现的难点。
笔者在开发税收分析系统多维报表展现平台过程中，利用Reporting Services自行开发了支持模糊查询功能的报表展示门户，成功地利用Levenshtein Distance算法实现了维度成员的模糊查询功能，满足用户对模糊查询的需求，改善了系统的整体客户体检。
关键的实现环节报告如下：
（1）根据报表参数中已有的参数值，获取报表参数区中特定维度的维度成员
private ReportParameter GetParameters（）
{
ReportParameter[]rpOUT；
RSPS=new List
parameterLength=ParameterCollection.Length；
ParameterValue[]pavsIN=new ParameterValue[parameterLength]；
int i=0；
foreach（RSParameter rspa in ParameterCollection）
{
pavsIN[i].Label=rspa.ParameterTitle；
pavsIN[i].Name=rspa.ParameterName；
pavsIN[i].Value=rspa.parameterValue；
}
rpOUT=rs2006.GetReportParameters（rsReporURL，null，pavsIN，null）；
return（rpOUT）；
}
（2）Levenshtein Distance算法对参数区中的维度成员进行模糊过滤
public List
{
List
foreach（string s in wordList）
{
int levenshteinDistance=LevenshteinDistance（word，s）；
int length=Math.Max（word.Length，s.Length）；
double score=1.0-（double）levenshteinDistance/length；
if（score>fuzzyness）
foundWords.Add（s）；
}
return foundWords；
}
将FuzzySearch返回的成员集合转换成报表参数对应的维度成员集后，回传作为报表参数，即完成了多维数据的模糊查询。
五、结论
本文介绍的思路和具体实现方法已在多个系统中的实际运用，使用结果证明Levenshtein distance算法简洁有效，与多维数据库应用结合，极大提高了系统的是实用性，改进了用户体验。
模糊查询算法在多维数据分析中的应用场合还会有许多，如：通过多维数据前端工具，将模糊查询算法与MDX结合，动态生成支持模糊查询的MDX脚本；开发支持模糊查询的报表参数控件，以便最终用户无需变成直接实现多维报表参数的模糊查询等等。
参考文献：
[1]B.J.Oommen and R.K.S.Loke,Pattern recognition of strings with substitutions,insertions,deletions and generalized transpositions
[2]Roy Lowrance,Robert A.Wagner.An Extension of the String-to-String Correction Problem,JACM,1975
[3]Gonzalo Navarro.A guided tour to approximate string matching.ACM Computing Surveys(CSUR)archive,2001,33,1:31-88
[4]刘青宝,金燕.模糊维结构及模糊多维数据模型.FUZZY SYSTEMS AND MATHEMATICS,2008,22,1
查询算法 篇3
关键词：公交,换乘,自适应蚁群算法
这些年来,北京市的公交线路已达800条以上,使得公众的出行更加通畅、便利,但同时也面临多条线路的选择问题。为此需要设计公交线路选择问题的自主查询计算机系统以方便人们的出行选择。
1 蚁群算法
蚁群算法是近年来兴起的高效的启发式算法[1,2]。蚁群算法(Ant Colony Algorithm,ACA)是M.Dorigo等人于1991年提出的。经观察发现,蚂蚁个体之间是通过一种称之为信息素(pheromone)的物质进行信息传递的。在运动过程中,蚂蚁能够在它所经过的路径上留下该种信息素,而且能够感知信息素的浓度,并以此指导自己的运动方向,倾向于朝着信息素浓度高的方向移动[3]。
基本蚁群算法的程序大致如下:
Step 1:参数初始化。循环次数N=0,设置最大循环次数Nmax,将G个蚂蚁分别放在起始站点上,初始化有向图的每条边(Si,Sj)的信息量,将每个蚂蚁的禁忌表置为空。
Step 2:循环次数N=N+1;
Step 3:按照一定的规则为每个蚂蚁选择下一个节点。
Step 4:修改该蚂蚁的禁忌表;
Step 5:若还有蚂蚁没有选完,转Step 3;
Step 6:根据每个蚂蚁走过的路径,由此更新每条路上的信息量;
Step 7:若循环次数N>Nmax结束程序,否则转Step 2。
基本蚁群算法有诸多的缺点,如收敛速度慢,容易出现早熟,停滞现象。许多学者[4,5,6]提出自适应蚁群算法来克服基本蚁群算法的缺点。在利用自适应蚁群算法之前,假设我们已经知道每条公交线路经过的站点信息,对站点进行编号,编号为i的站点记为Si(i=1,…,m),用Tij表示站点Si到站点Sj的直达关系,Tij=1表示从站点Si到站点Sj有公交车直达,否则Tij=0(在这里,规定Tii=0),并用D表示站点Si可以直达到的站点编号的集合,即满足Tij=1的j的集合。将公交网络抽象成有向图,节点表示站点,当Tij=1时,节点i有指向j的有向弧。并用Start和End分别表示要查询的起始站点和目的站点的编号。
为每个蚂蚁建立一个标志位,标志它是否到达目的站点,初始化为0,并且为每个蚂蚁建立一个禁忌表,记录它走过的站点,初始化为空。用τij(t)表示t时刻弧(Si,Sj)上的信息量,初始化为同一常数。
1.1 选择站点
假设进行到第k+1步,已经知道前k个站点,要为每只蚂蚁选择第k+1个站点,设其中一只蚂蚁经过的站点依次是Sstart,Si1,…Sik,按下列规则产生第k+1个站点:
若Tik,End=1,即Sik可以直达到SEnd,则令Sik+1=SEnd,并且将该蚂蚁的标志位置为1。
若Tik,End=0,按下列公式计算转移概率
其中t表示时间,这里以一次完整的迭代为一个时间步长。α与β分别表示蚂蚁在运动过程中所积累的信息量及启发式因子在蚂蚁选择路径中所起的不同作用。ηij(t)是t时刻从站点i到j的启发因子,显然,出度数大的节点可以直达的站点多,为了能尽快搜索到目的站点,应尽可能让蚂蚁往节点度数大的节点运动,所以令ηij(t)=(di+dj)/2,(i,j=1,…,m)。运用轮盘转赌规则求第k+1个站点。设置一个上限来限制蚂蚁的选择站点数目。设这一上限为K,当k
1.2 信息素的自适应更新
在基本蚁群算法中,当所有的蚂蚁选择完后,需要更新信息量:
其中ρ表示信息素挥发系数,因为信息量τij(t)会随着时间的流逝衰减。
在基本蚁群算法中,加速收敛与防止早熟,停滞现象是一对矛盾。这里面信息素的挥发系数ρ的大小是平衡两者的关键。ρ表示信息的消逝程度,而1-ρ就表示信息的残留比例。当ρ比较大时,信息挥发得快,使得那些未被搜索到的路径上的信息素迅速的降为0,下一次的迭代蚂蚁就不会走这些路径,算法会很快的收敛,但全局搜索能力比较弱,会出现早熟,停滞现象。当ρ比较小时,路径上的残留信息占主导地位,信息的正反馈比较弱,算法的随机性和全局搜索能力比较强,但收敛的速度就会慢。因此可以引入动态的ρ来平衡收敛速度与算法的全局搜索能力。令ρ(0)=ρmax。
ρ(t)∈[ρmax,ρmin],因此(1)式变为:
其中:
Δτgij(t)表示第g只蚂蚁在本次迭代中在站点i和j之间留下的信息量。关于Δτgij(t)的计算方法,则可以按下式计算
其中Q为常数,函数f(v)表示对路径v的评价,它可以根据不同的目标而设定。
假设求出的路线v是Sstart-Si1-…-Sik-SEnd,其中‘-’表示直达关系,可以按下列方法找出最小换乘数目和途径的站点总数:
Step 1:count1=0,它用来记录换乘次数,count2=0,用来记录途径的站点总数。Ori=Start,用来记录换乘之后的出发点,Fnal=i1。
Step 2:判断Fnal是否为End,
如果是,则输出count,退出。
如果不是,执行下一步。
Step 3:用Fnal+1表示路线v中Fnal的下一站,比如Fnal=i1,则Fnal+1=i2。判断Tori,Fnal是否为1,如果为1,则Fnal=Fnal+1,如果为0,则count1=count1+1,count2=count2+Ori到Fnal-1之间所有直达车的所经过的最短站点数。Ori=Fnal,Fnal=Fnal+1。
判断之后转Step 2
Step 4:输出count1,以及count2=count2+Ori到End之间所有直达车的所经过的最短站点数。
统计表明人们出行首先考虑的是换乘的次数,其次是途径的站点数,我们把换乘次数最少,途经站点数最少的乘车路线称为最优的。所以可以令f(v)=c*2count1*count2,c是常数。F(v)的值越小则该条路径越好,由(4)算出来Δτgij(t)越大,信息的正反馈越强。
在实际操作时,笔者发现当公交站点数m比较大时,信息素矩阵的规模为m2,每次按(3)式更新信息素矩阵都要耗费很多的时间。通过对公交网络的特点考察发现,在寻找起始站点与目的站点之间的路径时,蚂蚁途径的站点相比于m来说是很小的一部分,每次更新信息素矩阵有绝大部分路径直接按(3)式挥发了,而只有少数路径需要加上信息素的增量。笔者设计了迟滞更新信息素的方法来减少运算,具体来说为每个τij增加一个标示πij,πij=k表示τij更新到了第k次迭代。每次更新路径τij时,若当前迭代产生的Δτij,则不需要更新,否则检查当前迭代次数N是否与πij+1吻合,如果吻合,则按(3)式更新,若不吻合,首先将τij乘以ρ(πij+1),再乘以ρ(πij+2)等等直到ρ(N-1),然后按(3)式更新。每次更新完之后,将πij置为当前的迭代次数。另外,当按(1)式计算转移概率时,对用到的τij需要先检查πij是否为当前的迭代次数N-1,如果是,则可以直接用来计算转移概率,如果不是,需要先按上述方法更新τij至N-1代。
该算法的主要思想是将选择公交车的过程视为动态规划,因为走完路线v的方法有很多种,所以最后花费的费用也不一样。根据动态规划的最优策略原则:无论过去的状态和决策如何,对前面的决策所形成的当前状态而言,余下的诸决策必须构成最优策略。
2 结束语
与公交查询的其它方法相比,本文所设计的方法具有更快的速度,更好的寻找最优解的能力以及更广泛的适应范围。究其原因主要有两点,第一,启发式的蚁群算法能避免隐式枚举带来的复杂度。第二,自适应蚁群算法使得能够兼顾收敛速度与避免早熟。
参考文献
[1]闫小勇,牛学勤.公交网络多路径选择启发式算法研究[J].城市交通,2005(3):23-26.
[2]李文勇,王炜,陈学武.公交出行路径蚂蚁算法[J].交通运输工程学报,2004,4(4):102-105.
[3]段海滨,蚁群算法原理及其应用[M].北京:科技出版社,2005:34-37.
[4]赵宝江,李士勇,金俊.给予自适应路径选择和信息素更新的蚁群算法[J].计算机工程与应用,2007,43(3):12-14.
[5]徐晓华,陈峻.一种自适应的蚂蚁聚类算法[J].软件学报,2006,17(9):385-389.
城市公交查询算法的分析与实现 篇4
1 数据准备
1.1 所需数据
根据城市交通路网和公交站点的实际情况, 本系统采用的数据网络包括公交站点和公交车线路数据。
公交站点数据用于记录城市所有公交车站的基本信息, 包括车站的ID号、车站的中文名称、站点序号等。该数据的构建采用在ArcGIS的ArcMap中编辑站点图层 (point类型) 的方式得以实现。
公交车线路数据用于记录组成公交路线的若干条折线段的基本信息, 包括线段的ID号、线段两个端点 (即两个公交站) 的站点序号、站点名称等。该数据的构建采用在ArcGIS的ArcMap中编辑路线图层 (polyline类型) 的方式得以实现。
并且根据公交数据的数据量大、数据类型丰富、管理困难等特点, 对公交数据进行了以下处理:
1) 围绕站点信息对市辖所有公交站点统一编码 (站点序号) , 以保证站点的唯一性;
2) 对公交线路进行统一编码, 以保证线路信息的唯一性。
1.2 数据库设计
为了能在地图中查询、显示公交信息, 需要在数据库中建立公交线路表和公交站点表。见表1、2。
2 算法分析
对于公交换乘的算法, 很多学者都进行了研究, 其中很多算法是基于最短路径的, 例如:Dijkstra算法、遗传算法和燃烧算法等。但对公交乘客的心理调查表明:在公交换乘方案的选取上, 首先要考虑的因素是到达目的地的换乘次数要最少, 其次才是要求路径最短。因此, 基于最短路径的公交换乘算法并不能满足实际的需要。本文在此基础上提出基于换乘次数最少的最优路径改进算法。
2.1 公交换乘算法
2.1.1 直达算法
1) 由起始站S1, 列出经过起始站的公交车列表B1;
2) 由终点站S2, 列出经过终点站的公交车列表B2;
3) 求集合B1和B2的交集B, 如果B中有元素, 则可以在起始站S1乘坐集合B中的公交车直达终点站S2。
2.1.2 一次换乘算法
1) 由起始站S1, 列出经过起始站的公交车列表B1;
2) 在公交车列表B1所经站点中找出序号大于起始站序号的站点列表M1, 即由起始站可以直达的公交车站点;
3) 由终点站S2, 列出经过终点站的公交车列表B2;
4) 在公交车列表B2所经站点中找出序号小于终点站序号的站点列表M2, 即可以直达终点站的公交车站点;
5) 求集合M1和M2的交集M, 如果M中有元素, 则可以在起始站S1坐车到达中间站M, 再由中间站M转乘至终点站S2。
2.1.3 二次换乘算法
1) 由起始站S1, 列出经过起始站的公交车列表B1;
2) 在公交车列表B1所经站点中找出序号大于起始站序号的站点列表M1, 即由起始站可以直达的公交车站点;
3) 由站点列表M1, 列出经过站点的公交车列表C1;
4) 由终点站S2, 列出经过终点站的公交车列表B2;
5) 在公交车列表B2所经站点中找出序号小于终点站序号的站点列表M2, 即可以直达终点站的公交车站点;
6) 由站点列表M2, 列出经过站点的公交车列表C2;
7) 求集合C1和C2的交集C, 如果C中有元素, 则说明从起始站S1换乘2次可到达终点站S2。
算法的流程图如图1所示。
2.2 乘换方案的选择
1) 换乘便利原则:即在所有方案中找出换乘次数最少的方案作为最佳方案;
优先选择直达方案, 其次是一次换乘方案, 最后选择二次换乘方案;
2) 最短路径原则:即在所有方案中找出换乘站数最少的方案作为最佳方案;
通过在系统中对每一路车经过的站点按其行车线 (方向) 都定义一个序号, 乘坐时根据上车、下车的序号计算出经过的站点数。按照此算法, 即可对各种行车方案进行排序, 得到最佳出行方案。
3 功能实现
就此论述的基于换乘次数最少的最优路径改进算法, 成功应用于数字城市中公交查询功能的开发与实现。
通过给出起点与终点的公交站名, 系统查询出所有的换乘方案, 并根据换乘便利原则和最短路径原则对换乘方案进行排序。功能实现如图2所示。
4 结论
针对目前我国大多数城市都存在换乘比率高的现象, 实现了以公交换乘为主的公交出行查询功能。从一定意义上真正实现了GIS与公交查询的有机结合, 更科学、更全面地反映所在地交通基础地理信息, 为市政公交管理部门提供方便快捷的交通信息, 为城市公交信息快速发布和调整提供平台, 从而充分发挥数字城市的作用, 为城市交通信息建设和社会发展做出贡献。
参考文献
[1]周万枝.基于地理信息系统的城市交通管理系统研究[J].测绘通报, 1997, 10 (8) :90-91.
[2]于小平, 杨国东, 王凤艳, 等.城市公交查询系统的设计与实现[J].吉林大学学报 (信息科学版) , 2005, 23 (6) :150-151.
[3]陈立潮, 刘玉树, 张永梅.城市交通智能咨询系统的设计与实现[J].计算机工程, 2003, 29 (1) :32-340.
[4]陆忠, 钱翔东, 张登荣.基于最短路径查询的城市公交网络拓扑建模研究[J].遥感信息, 2002, 15 (1) :11-14.
[5]刘仁义.图形数据与关系数据库的结合及其应用[J].测绘学报, 2000, 29 (4) :329-333.
查询算法 篇5
关键词：多连接查询优化,免疫遗传算法,抗体浓度,免疫接种
1 引言
随着Internet技术与信息管理系统的发展与普及, 基于数据库、数据仓库的联机事务处理和联机分析处理已成为银行、企业、政府等部门最为重要的计算机应用之一。在这些应用中, 多连接查询操作在各种数据库操作中所占比重非常大, 而且, 执行多连接查询操作时, 运算先后次序不同, 查询请求响应的时间就不同。多连接查询优化就是对于由N个 (N>10) 关系的连接操作构成的一个查询请求, 在合理的时间内找到一个最佳的查询执行计划。一个好的查询计划往往可以使程序性能提高数十倍。然而, 在大规模数据库、数据仓库、联机分析处理的环境下, 参与多连接查询运算的表的数目较大, 导致多连接查询优化的计算复杂性非常大。因此, 多连接查询优化对获得好的查询性能至关重要[1]。
多连接查询优化问题是一个NP问题, 高效的优化算法是提高查询性能的关键问题。目前, 已有一些算法解决这个问题, 这些方法在某些方面提高或改进了查询性能。文献[2]利用增量启发式信息来初始化种群, 提高了遗传算法的收敛速度。文献[3]在遗传算法的过程中加入了模拟退火操作, 有利于保持物种的多样性。文献[4]在查询优化中, 结合哈希过滤方法, 减少查询执行计划的计算代价, 从而提高多连接查询效率。文献[5]结合遗传算法和模拟退火算法提出了一种混合算法, 并将其应用到多连接优化问题, 改进了获得最佳查询计划的性能。本文的主要内容是将免疫思想和遗传算法相结合, 设计一个多连接查询优化算法, 在保持遗传算法优良特性的前提下, 加入抽取疫苗、接种疫苗、疫苗选择等免疫算子, 抑制优化过程中出现的退化现象, 提高算法的寻优能力。
2 多连接查询优化问题
多连接查询优化问题可以描述为合理时间内在搜索空间中找到一个最好或者近似最好的关系连接次序问题。搜索空间常采用左线性树空间, 并根据关系代数的等价变换规则, 利用“选择操作下移、投影操作尽量先做、避免笛卡尔积”等启发式信息。多连接查询优化问题可简化为一个带约束的组合优化问题, 求解该问题的数学模型如下。
上述模型中, C表示多连接查询的代价, ti表示左线性树中的内部结点, r和s是ti的左右子结点 (即ti是r与s连接后的中间结果) , n (ti) 表示关系ti的元组个数, n (r) 和n (s) 分别表示关系r和s的元组个数, R是关系r和s的公共属性, V (A, r) 为关系r中属性A的不同取值的个数。
对于某个具体的多连接查询, 假设X为全部可能查询执行计划的集合, X中每个成员x都有其代价C (x) , 则需要找出X中的某个查询执行计划q (q∈X) , 使得q满足:
多连接查询优化的目标是优化时间与找到的查询执行计划x的执行时间之和最小。
3 免疫遗传算法的基本思想
免疫遗传算法是借鉴生物免疫机制提出的一种改进的遗传算法。它模拟生物抗体浓度自适应调节过程, 在算法中加入免疫记忆功能, 提高了算法的收敛速度。由生物免疫原理可知, 生物免疫系统对入侵生命体的抗原通过细胞的分裂和分化作用自动产生相应的抗体来抵御, 其中部分抗体作为记忆细胞保存下来。当相似抗原再次侵入时, 记忆细胞将被激活并迅速产生大量抗体, 体现了免疫系统的记忆功能。抗体与抗原结合后会通过一系列的反应而破坏抗原。同时, 算法根据抗体与抗原的亲和力和抗体的浓度进行选择操作, 亲和力高且浓度小的抗体选择概率大, 这样就抑制了群体中浓度高的抗体, 保持了群体的多样性, 体现了免疫系统的自我调节功能[6]。免疫遗传算法的流程如图1。
4 多连接查询优化的免疫遗传算法设计
本文吸取免疫遗传算法的思想, 结合多连接查询优化的特点, 将它用于求解多连接查询优化问题。首先, 将免疫遗传算法中涉及的基本概念与多连接查询优化的基本概念进行对照, 它们之间的对应关系如表1所示。
4.1 初始抗体的产生、编码、适应度、亲和度和抗体浓度
初始抗体的产生可以先从记忆细胞库中搜索该问题的记忆抗体, 从而生成初始抗体, 不足的抗体则在解空间中随机产生。这个初始抗体产生的方法提高了初始种群中抗体的适应度, 更快的找到全局最优解。
抗体的评价主要用抗体与抗原的适应度以及抗体和抗体的亲和度来表示。适应度函数由 (1) 、 (2) 、 (3) 式计算出cost值, 再求其倒数。抗体v的适应度函数:
适应值越大, 被选择的概率就越大。
抗体v和抗体w的亲和度函数:
其中E (2) 为v和w的平均信息熵。通过这些平均信息熵可以实现抗体的多样化。
抗体v的浓度计算函数如下:
其中, qv表示和抗体v有较大亲和度的抗体个数, N表示全局抗体个数。通过 (8) 式能有效地抑制抗体的过分相似。
4.3 选择算子、交叉算子、变异算子的设计
选择算子采用最优保存策略和基于抗体浓度选择策略相结合。最优保存策略使得适应值最好的抗体尽可能保留到下一代群体中, 以免交叉和变异运算破坏种群中的优秀解, 保证了算法的收敛。群体的浓度定义为群体中相似抗体所占的比率。基于抗体浓度选择策略原理是, 群体更新时, 亲和度高的抗体不断提高, 到达一定的值时则抑制这种抗体的产生。也就是说, 抗体集合中与抗体x基因相似的抗体越多, 则抗体x被选中的概率就越小;反之, 与抗体x基因相似的抗体越少, 抗体x被选中的概率就越大。基于抗体浓度选择策略不仅能有效地抑制浓度过高的抗体繁殖, 保证抗体的多样性, 避免算法陷入局部最优值, 而且使含有有效进化基因的低适应值个体也可获得繁殖的机会。
交叉操作时通过交换两个父个体的一部分来产生新的子个体, 该操作要根据一定的概率进行。
变异操作时以一定的概率随机地改变个体中某个基因, 以提供初始群体中不存在的基因或找回选择过程中丢失的基因, 为群体提供新的内容。变异算子将个体的基因链的各个基因按某个概率进行变异。变异本身是一种局部随进搜索, 与选择算子结合在一起, 保证了免疫遗传算法的有效性, 使得免疫遗传算法具有局部的随机搜索能力, 同时, 也使得免疫遗传算法保持种群的多样性, 以防止出现不成熟收敛。变异算子采用单点基因换位法。
4.4 疫苗接种、免疫选择
首先, 根据多连接查询问题的特征信息和先验知识得到该问题的疫苗。个体接种疫苗的概率取0.6, 接种疫苗包括对于个体x接种疫苗, 对群体接种疫苗两个步骤。第一步, 按照先验知识来修改个体x的某些基因位上的基因或其分量, 使所得个体以较大的概率具有更高的适应度。第二步, 对群体进行接种疫苗, 从种群中随机抽取Nα个个体进行接种。为了使个体接种疫苗后满足约束条件, 作如下处理:设接种疫苗前, 个体的某基因位上取值为vi, 接种疫苗后取值为vi′, 则将原个体基因位上取值为vi的基因与取值为vi′的基因对换。免疫选择对加强接种算子有积极作用, 消除其负面影响, 防止群体的退化, 具有较强的鲁棒性。
免疫选择操作分两步完成。第一步是免疫检测, 即对接种了疫苗的个体进行检测, 若其适应度不如父代, 说明在交叉、变异的过程中出现了严重的退化现象。这时保留父代个体。如果子代适应度优于父代, 则选择子代。
5 总结
免疫遗传算法已经在一些领域的优化计算中取得了很好的效果。本文结合多连接查询优化问题的实际特点, 提出应用免疫遗传算法解决多连接查询优化问题。免疫遗传算法在遗传算法的基础上引入了基于浓度的抗体抑制和促进的免疫算子, 能有效地抑制浓度过程的抗体繁殖, 保证抗体的多样性, 避免算法陷入局部最优值;根据先验知识保存最优抗体, 有效提高初始种群的质量;疫苗接种使得问题的特征信息能注入抗体, 保证算法的快速有效收敛。
参考文献
[1]玄萍, 李金宝.基于机群系统的并行多连接查询优化算法[J].黑龙江大学自然科学学报, 2006, 23 (6) :821-826.
[2]董红斌, 梁意文, 康立山, 等.利用启发式信息优化多连接查询的遗传算法[J].武汉大学学报 (自然科学版) , 1999, 45 (5) :743-746.
[3]杨艺, 李延东.退火遗传算法的多连接查询应用[J].计算机工程与应用, 2004, 34:190-192.
[4]王果, 徐仁佐.结合哈希过滤的一种改进多连接查询优化算法[J].计算机工程, 2004, 30 (7) :57-59.
[5]闫晓慧, 董丽丽, 张慧娜.基于混合遗传算法的关系数据库多连接查询优化策略[J].微电子学与计算机, 2008, 25 (11) :181-183.
基于增量信息索引的子图查询算法 篇6
随着互联网步入2.0时代,图数据库越来越多地出现在我们的生活中,例如社交网络、蛋白质网络、化学结构等,对于它的检索需求也与日俱增。你可以在Facebook查看你好友或者好友的好友发出的消息;你可以在生物信息数据库中研究某种DNA、某种氨基酸、某种蛋白质;你可以在化学数据库中查询某种化学结构。支撑这些应用的底层存储数据库不是普通的数据库,而是图数据库。当你使用这些应用时会有图数据库查询,即使你没有意识到,这一切都在不知不觉中进行着。
有的图数据库本身就是一张大图[1],有的图数据库中存储了千千万万的小图。传统的数据库只能将一个图存为一个整体,不能利用其中的结构信息。随着技术的进步和发展,图数据库的实用价值不断增大,所以使用的比例也不断加大。
图数据库需要检索技术,本文研究的检索是子图同构检索。进行这样的检索有几个要求:检索结果需要完全正确,不能漏掉数据库中应该检索到的图,或者检索出不正确的图;检索处理的速度需要足够快,同时使用的内存要合理。
顺序枚举数据库里的每个图,并且查看查询是不是它的子图是效率比较低的做法。因为子图同构查询是NP完全问题[2],在整个图数据库上进行,花费很大。因此,现在通行的做法是建立索引,之后在查询时进行两阶段的处理:过滤和验证。过滤是在图数据库中选出部分图组成候选集集合,过滤掉一些不符合的图,缩小需要运行子图同构检测的数据范围大小。这时,候选集已经大大减小了,需要运行子图同构检测的次数变少了,可以加快查询的速度。验证部分运行子图同构检测,确定正确的结果。如果过滤步骤能够显著地降低候选集的大小,那么这个基于索引的两阶段算法就是有效并且实用的。候选集的大小可以作为不同算法性能直接比较的一个重要指标。
Graph Grep[3]提出了子图查询问题,Tree+Δ[4]使用了树作为索引,g Index[5]使用了图作为索引,FG-Index[6]提出了避免过滤阶段的方法。传统的索引是建立频繁子图的倒排索引,没有利用其中的结构信息。本文在构建索引时在子图之间增加信息,构建的索引是由子图构成的图。
本文研究的主要目的是设计一个符合以上要求的支持子图查询的算法。
1 基本概念
1.1 相关定义
定义1一个图G(V,E,ф)是由结点集V和边集构成的。另有映射φ:V→Vl指定结点上的标签,其中Vl是结点标签的集合。图的大小|G|=|E|,为边的个数。
定义2图G1子图同构于图G2(表示为),若存在一个单射函数f:V1→V2,使得u∈V1都有ф1(u)=ф2(f(u));(u,v)∈E1都有(f(u),f(v))∈E2。
定义3一个图G的正规表示Canon(G)是一个带标签的图,同构于G,且任意同构于G的图都和G有相同的正规表示,正规表示是唯一的。找寻图的正规表示的问题叫作图的正规化。因此,如果有一个图的正规化的算法,这个算法同样能够解决图的同构问题。对于两个图G和H,计算它们的正规表示Canon(G)和Canon(H),然后检测两个正规表示是否相同。如果相同必定同构,如果不同必定不同构[7]。
定义4一个图数据库D是由一系列图组成的,其中的每一个图都有唯一的标识符(id)。所以记图数据库D={G1,G2,…,Gn}。其中Gi的id是i(1≤i≤|D|)。
定义5术语片段用于称呼图数据库或者查询图中的一个小的子图。
定义6如果有一个片段并且G∈D,那么称G是f的片段支持图。记f在图数据库D中的片段支持图集合为Df。Df被称为f的支持度,记为sup(f)。并且|Df|中所有图的标识符的集合记为fsg Id(f)。
定义7给出一个最小支持度阈值α(0<α<1),若一个片段f在图数据库D中的支持度不小于α|D|,那么称f是频繁片段。同时,记所有图数据库D中的频繁片段组成的集合为F。任意频繁片段的子图必定也是频繁片段[4]。
定义8若一个片段g在图数据库D中是非频繁片段,并且|g|=1或者,那么称g是显著非频繁片段DIF(Discriminative Infrequent Fragment)[8]。
1.2 问题描述
本文研究的图数据库,是由许多的小图组成的。每个小图的规模都不大(点数、边数<200),但是小图的数目非常多(10×103~200×103)。给定图数据库D={G1,G2,…,Gn},查询图Q。子图查询问题是找出所有的Gi,使得。
2 算法
传统的索引是建立频繁子图的倒排索引,没有利用其中的结构信息。并且传统的索引没有考虑到索引本身和查询之间的联系。本文在构建索引时在子图之间增加信息,构建的索引是由子图构成的图。这是为了查询时使用的特性而特别优化的。
图1是整体系统的结构,包含有索引构建器、查询处理机和验证器。索引构建器能够输入图数据库并且为其构建索引。查询处理器用于处理查询,输入查询后对查询进行分析,在读取索引的同时维护一个数据结构保存图的特征信息。这些信息是同时和查询图和索引相关联的,从这个数据结构中可以提取候选集,传递给验证器。验证器用于验证候选集,输出查询结果。
2.1 增量信息索引
本文提出的增量信息索引结构本身是一个分层的有向无环图,图2是从本文使用的索引所进行的可视化展示中截取的。
定义9若有图数据库D和其上的频繁片段集合F,可以构建增量信息索引I={I1,I2,…,In}。索引中的每一项Ii都对应一个片段,由标识符、正规编码、类型、大小、转移信息、父亲和支持图集合组成。
这里我们只将频繁片段和显著非频繁片段放入增量信息索引中,这样做的原因是所有片段的种类是非常多的,不可能全部放入索引中。已知使用频繁片段是一种能大幅度降低片段数量的方法,可以通过调节最小支持度阈值α来控制数量,并且过滤效果很好。本文使用一种已有的图数据库挖掘算法g Span生成频繁片段[9]。
片段的转移信息是一个数组,表示片段上所有可以进行的操作和操作的结果。操作就是给片段增加一条边,因为增加完边后片段仍旧是连通的,所以操作有两种:
(1)增加边的同时增加一个新的结点,新的边将新的结点连接到片段中一个已有的结点上,我们记这种操作为Nx(y)。其中x为已有结点的编号,y为新结点的标签。如N0(C)表示将一个标签为C的新结点连接到已有的0号结点上。
(2)在已有的两个没有边连接的结点之间连接一条边,我们记这种操作为Cx-y。其中x、y分别为已有两个结点的编号,且x<y,因为这是一个对称操作。
定义10操作的结果叫作转移(trans),形如(id,new Ids)。若这个操作是对片段a做的,得到片段a',a'的正规表示为b,那么id为b的标识符,new Ids表示的是a'到b的同构映射函数f。
2.2 增量信息索引的构建
首先,将所有频繁片段连同它们的信息(包括它们的支持图集合)放入增量信息索引中。然后依次枚举所有的频繁片段,并对其尝试前文所提到的两种操作:增加边的同时增加一个新的结点,在已有的两个没有边连接的结点之间连接一条边。若操作的结果从片段f得到新图new Graph和转移new Ids,片段f在索引中对应的项为If。根据new Graph的性质进行以下操作:
1)若new Graph是频繁片段,对应索引中的项Inew Graph,我们记录三元组(op,Inew Graph.id,new Ids)到索引中If项的信息中。
2)若需要检测new Graph是否是显著非频繁片段,我们枚举它包含的所有大小为|new Graph|-1的连通子图。若全都是频繁片段,那么new Graph是显著非频繁片段。然后将new Graph作为显著非频繁片段插入到增量信息索引中。
3)若new Graph是显著非频繁片段,对应索引中的项Inew Graph,我们记录三元组(op,Inew Graph.id,new Ids)到索引中If项的信息中。
4)若new Graph是非显著非频繁片段,我们不做任何事。
最后检查所有的DIF,若其支持图集合为空,则其支持图集合的候选集C可由它所有父节点支持图集合的交集得到。在C上运行验证器可以得到其支持图集合。
2.3 简单纺锤形图
在文献[10]中,作者提出了纺锤形图的概念。本文在此基础上提出了简单纺锤形图,作为查询图的特性信息。简单纺锤形图改变了图中每个结点所代表的意义和包含的信息,不过还是继承了其纺锤形的特征和思想。文献[10]中使用多个纺锤形图,本文只使用一个简单纺锤形图;原有纺锤形图每个结点都是原有查询中的一个片段,本文只是索引项的标识符;原有纺锤形图中结点的总个数一定是查询图所有连通子图的个数,本文简单纺锤形图中结点数量的增长较为平缓。因此本文缩减了操作简单纺锤形图的时间,使得添加边、删除边的操作更加高效。
定义11简单纺锤形图(Simple SPIG)是一个图,结点i带有数据{id,edge Sets}。i.id是增量信息索引中索引项的标识符。若两个简单纺锤形图中的结点各自对应的索引项在增量信息索引中有边连接,那么在简单纺锤形图中这两个结点也有边连接。i.edge Sets是边集的集合且不为空。
图3展示了简单纺锤形图的结构。当用户插入了一条边后,简单纺锤形图只会增加结点和结点中的边集。当用户删除边后,简单纺锤形图中的结点和结点中的边集只会减少。我们需要实现增加边和删除边的算法。
2.4 增加查询边算法
每次加入新的边时,会更新简单纺锤形图。用广度优先搜索从小到大找出所有包含种子边的查询图的连通子图。广度优先搜索所使用的队列里存储的是用于表示片段的三元组(查询结点标识符数组,边集,索引项的标识符)。其中查询结点标识符数组和边集可以定位片段在查询图中的位置,索引项的标识符可以定位片段在索引中的位置。
每次从队列中取出一个三元组后,我们尝试所有给它加边的方法,加上新的边得到新的边集。若还没有被处理过,使用加边操作在索引信息中查找。若能找到对应的转移,利用查询结点标识符数组和转移中的new Ids构建新的查询结点标识符数组,并且将新的三元组加入到队列中去。并且,同时将标识符添加到简单纺锤形图中,这里添加时需要使用父亲信息。这是因为若有父亲已经存在在简单纺锤形图中,我们需要连一条到父亲的边。然后将边集加入到简单纺锤形图结点的边集中。
等到队列全部处理完成的时候,算法也就终止了,此时更新也完成了。
2.5 删除查询边算法
删除一条边的算法只需要对简单纺锤形图进行更新就可以了,不需要使用到索引的信息。其主要的思想是移除所有简单纺锤形图中包含有需要删除边的边集,若移除后简单纺锤形图中结点的边集集合为空,说明此结点的限制不必再应用于这个查询,可以移除这个结点了。更新完成后就可以得到所需的新的简单纺锤形图。
2.6 得到查询结果
这里需要根据简单纺锤形图的层数分两种情况:
1)若层数存在和查询大小相同的这一层,简单纺锤形图形成一个完整的纺锤形,那么说明查询本身就在索引中出现过。可以直接使用索引的支持图集合作为查询的结果,不需要再做验证。
2)否则,还需要再次通过验证器验证才能作为查询的结果。先从简单纺锤形图中所有叶子结点中取出它们的支持图集合,并把这些集合的交集作为查询结果的候选集,验证完后作为查询结果。只取所有的叶子结点是因为,若一个结点不是叶子结点,那么它一定有一个后代并且这个后代的支持图集合是它的支持图集合的子集,所以没有必要再和非叶子结点的支持图集合做交集操作。
3 实验结果与分析
本文所实现的程序称为Inc-Info,将与之前的算法Prague进行比较,并进行性能测试。实验是在一台Intel Core i7-4700MQ处理器、12 GB内存、运行Windows 8.1 x64操作系统的计算机上进行的。实验环境上安装有Java 1.8和Graphviz 2.38。
实验的数据集是AIDS抗病毒数据集,是一个真实的数据集,总共包含有43 000个化学结构。取频率阈值α为0.1,并运行g Span生成频繁片段。
图4显示了在AIDS数据集上建立索引,得到片段数与索引大小、片段大小的关系。频繁片段的总数为2847,构建时间为70分钟,总索引大小为139.3 MB,其中支持图集合占138.5MB,数据库文件占用磁盘总空间237 MB。实验表明,片段个数会随着片段大小的增长而增多,但是达到一个最大值后反而会下降,最后归零,说明此算法片段数是可控的。在最后得到的增量信息索引中,支持图集合占据了绝大部分空间,说明本算法表示索引结构部分的信息是十分高效的。
本文手工构建了18个查询图,作为测试样例。在Inc-Info和Prague上输入测试Q1-Q18,得到查询用时,见图5、图6所示。其中Q7-Q12、Q15-Q18的图比较大,Prague无法处理,因此没有结果。可以发现Inc-Info的查询用时较小。
表1是在Inc-Info和Prague上输入Q1后,删除一条边所获得的操作用时。Prague不支持删除边5-边7的操作,因为Prague不能留下不连通的查询图,这点上Inc-Info较为灵活。而且可以看到Inc-Info较Prague在时间效率上有优势。
4 结语
本文提出了能够快速转移的新索引结构、一种新的查询时数据结构简单纺锤形图,组成一种新的相似度查询过滤算法。这种新算法可以支持更大的查询图,并有更高的查询性能。通过实验,将本文系统和现有系统进行比较,证明了本文提供的算法在实践上也具有良好的表现。未来可能的研究方向将关注如何缩小增量信息索引的大小,加快索引构建速度。
摘要：当前图数据库中的子图同构查询算法主要是依赖倒排索引,然而处理那些具有庞大数据的数据库和复杂的查询愈发成为挑战。研究目的是设计一个算法,使用新的索引作为查询处理的核心,记录查询图的每一个细小改变,并使用一种特殊的数据结构来维护。先是引出一个索引算法,然后逐渐分析整个索引、查询过程,并利用该算法实现一个系统,最后在不同数据集和查询上进行实验。实验证明了该算法具有良好的时间、空间效率和扩展性。新的索引算法能够支持更大的查询图和更加灵活的查询。通过实现的系统和其他系统的对比实验,验证了算法的有效性。
关键词：图数据库,子图同构,片段,子图查询,索引,查询算法
参考文献
[1]Sun Z,Wang H Z,Wang H X,et al.Efficient subgraph matching on billion node graphs[J].Proceedings of the VLDB Endowment,2012,5(9):788-799.
[2]Garey M R,Johnson D S.Computers and intractability:a guide to the theory of NP-completeness[M].USA:W.H.Freeman and Company,1979.
[3]Giugno R,Shasha D.Graph Grep:a fast and universal method for querying graphs[C]//Proceedings of the 16th International Conference on Pattern Recognition,Quebec,Canada,2002,2:112-115.
[4]Zhao P X,Yu J X,Yu P S.Graph indexing:tree+delta>=graph[C]//Proceedings of the 33rd International Conference on Very Large Data Bases,2007:938-949.
[5]Yan X F,Yu P S,Han J W.Graph indexing:a frequent structure-based approach[C]//Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data,2004:335-346.
[6]Cheng J,Ke Y P,Ng W,et al.FG-Index:towards verification-free query processing on graph databases[C]//Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data,2007:857-872.
[7]Canonical form[EB/OL].Wikipedia[2015-03-20].http://en.wikipedia.org/wiki/Canonical_form.
[8]Jin C,Bhowmick S S,Xiao X K,et al.GBLENDER:towards blending visual query formulation and query processing in graph databases[C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data,2010:111-122.
[9]Yan X F,Han J W.g Span:graph-based substructure pattern mining[C]//Proceedings of the 2002 IEEE International Conference on Data Mining,2002:721-724.
查询算法 篇7
为了避免XML多分支树查询过程中多条单路径的连接操作而带来的查询效率低的问题,本文提出一种基于递归思想的多分支树查询算法算法TBQ,很好的解决了这类的查询。该算法是将多分支树的每个结点进行查询,然后根据查询结果进行匹配。实验表明,与现有的XML多分支树查询算法pathsjoin相比,算法TBQ的查询效率更高。
1 XML文档的编码
为了快速的识别一篇XML文档结点之间的祖先后代关系,本文对XML文档采用流编码。思路如下:将XML文档看作是流文件,XML文档树中的每一个结点在解析文档时根据每个标签在文档中出现的先后次序赋予两个序号begin和end。其中begin代表文档标签的开始位置,end代表文档标签的结束位置。祖先结点u的编码区间[begin(u),end(u)]包含后裔结点v的编码区间[begin(v),end(v)]。XML文档树及其编码如图1所示。
2 XML文档树的索引创建方法
一般多分支树的查询算法都是对XML文档树进行遍历,由于遍历XML文档树要在内存中完成,这样的算法效率比较低。本文提出一种为XML文档树建立索引,主要的思想是将XML文档的各个结点按结点的名称聚类存放,同时记录下每个结点的流编码。图1所对应的XML文档树及其编码,其部分结点索引如表1所示。
3 多分支树查询算法TBQ
下面以查询语句PLAY[/ACT[//SCENE[/SPEECH][/STAGEDIR]][//SPEECH[/SPEAKER][/LINE]]][//PGROUP[/PERSONA][/GRPDE-SCR]]为例,介绍多分支查询树算法TBQ的基本思想:
Step1:把文档树每个结点按流编码编码;
Step2:创建XML文档树的索引,遍历编码后的文档树,对每个文档树的结点按其名称存放;
Step3:对多分支树结构的查询条件采用递归算法。
例如,在图1所示的XML文档树中要查询如图3所示的多分支树结构。首先,定位到查询树的第一个叶子结点SPEECH。在索引结构中,找出SPEECH的结点信息:(24,37),(45,52),(85,92),(73,80),(53,66);同理可得出STAGEDIR的结点信息:(21,23),(38,40),(41,43),(81,83);在得出的这些结点中,要判断哪两个结点信息是符合多分支树中结点的关系首先是要判断这两个结点是否有共同的祖先或父结点SCENE;通过索引结构可以得知SCENE的结点信息为SCENE(17,44),(72,84)。
判断过程如下:首先在多分支树查询条件中,SPEECH为左结点,STAGEDIR为右结点,那么必须满足SPEECH.begin
算法TBQ描述如下:
4 实验及结果分析
为了验证算法TBQ的效率,我们利用VC++实现了算法TBQ。实验环境为:CORE2,2.93G CPU,2G内存,Windows XP。实验数据为莎士比亚XML数据集[8]。
在实验中,我们测试了莎士比亚XML数据集的5个分支查询语句,查询语句如表2所示。对于多分支树查询,分别使用算法TBQ和算法pathjoins进行查询。它们的查询效率如图4所示,结果表明算法TBQ的性能明显优于算法pathjoins。
由图4可以看出,算法TBQ的执行效率要优于算法pathjoins。
5 结束语
对XML文档实现多分支树查询,一般方法是将多分支树拆分成若干个单路径,对单路径分别进行查询,然后再对单路径查询结果进行连接操作,这样的算法效率低。而本文提出的算法TBQ为实现XML多分支树快速查询,提出了先查询每个查询树的树结点然后将查询结果进行匹配的有效方法,从而大大提高了查询效率。
摘要：目前XML单路径查询和简单的分支路径查询已经得到了较好地解决,但如何高效地实现XML多分支树查询还没有很好的方法。该文提出了算法TBQ,该算法将多分支树的每个结点进行查询,然后根据查询结果进行匹配。实验表明,与现有的XML多分支树查询算法pathsjoin相比,算法TBQ的查询效率更高。
关键词：XML查询,XML多分支路径查询,XML编码,XML索引
参考文献
[1]Kaushik R,Shenoy P,Bohannon P.Exploiting Local Similarity for Efficient Indexing of Paths in Graph Structured Data[C].10th Interna-tional Conference on Database Theory,San Jose,California,USA,2002:129-140.
[2]Chen Q,Lim A,Ong K W.D(k)-index:An adaptive structural summary for graph-structured data[C].Proc.of the 2003 ACM SIGMOD Intl.Conf.on Management of Data,San Diego,California,USA,2003:134-144.
[3]Chung C,Min J,Shim K.APEX:An adaptive path index for XML data[C].Proc.of the 2002 ACM SIGMOD Intl.Conf.on Management ofData,Madison,Wisconsin,2002:121-132.
[4]Milo T,Suciu D.Index structures for path expressions[C].7th International Conference on Database Theory,Jerusalem,Israel,1999:277-255.
[5]Quanzhong Li,Bongki Moon.Indexing and Querying XML Data for Regular Path Expressions[C].Proceedings of the 27th VLDB Confer-ence,Roma,Italy,2001:361-370.
[6]Roy Goldman,Jennifer Widom.DataGuide:enabling query formulation and optimization in semistructured databases[C].23th InternationalConference on Very Large Data Bases,pages,Athens,Greece,1997:436-445.
[7]Bruno N,Koudas N,Srivastava D.Holistic Twig Joins:Optimal XML Pattern Matching[C].Franklin M J.Proceedings of the 21th ACMSIGMOD International Conference on Management of Data.Madison,Wisconsin,USA,2002:310-321.
查询算法 篇8
关键词：分层遗传算法,多深度概念树,索引,查询
1.前言
随着经济的发展和社会的进步,编码信息资源种类及其数量呈爆炸式增长,结果造成数据库非常庞大与复杂。如果按照某种顺序排列的编码作为聚焦索引,进行全面扫描查询,则查询速度非常缓慢,且造成资源的浪费。如果将编码进行分层,使用多表联结查询,查询数量会大幅度上升,查询效果同样不理想[3]。
为帮助用户快速查询所需信息,有许多学者提出了多种查询优化策略,如常用的二分查询、并行查询处理等。但这些方法在处理大规模编码数据库时,都没有避免完整的扫描索引,故查询效果并不理想。近年来,遗传算法被引入到信息检索领域,从而为编码信息查询技术提供了新的解决途径。
2. 概述
2.1 编码
编码就是在信息分类的基础上,将信息对象(编码对象)赋予有一定的规律性,易于计算机和人识别与处理的符号。编码类型有许多种,但工程技术上使用最多的是分类编码,如公民身份证号码、电厂KKS码等。分类编码就是将一个数据块分成若干个表示特定意义的小数据块,每个数据块代表一层,各层都有具体的含义。分类编码都是由数字、字母或符号构成,其具体格式如表一所示。
2.2 遗传算法原理
生物进化过程本质上就是生物群体在其生存环境约束下通过个体竞争、自然选择、杂交、变异等方式所进行的“适者生存、优胜劣汰”的一种自然优化过程。因此,生物进化的过程,实际上可以认为是某种优化问题的求解过程。遗传算法是美国密歇根大学J.Holland教授于1962年提出的,该方法按照类似有机体的自然选择和杂交的自然进化方式,借助计算机程序可以有效地解决较复杂的非线性组合问题及多目标函数优化问题。遗传算法正是模拟生物的这种自然选择和群体遗传机制的数值优化方法。它把一组随机生成的可行解作为父代个体适应环境能力的度量,经选择、杂交生产子代个体,后者再经变异,优胜劣汰,如此反复进化迭代,使个体的适应能力不断提高,优秀个体不断向最优点逼近。
分层遗传算法是对基本遗传算法的改进。在分层遗传算法中,子种群中进行各自独立的遗传操作,经过一段时间可以获得位于个体串上的一些特定位置的优良模式。再通过高层遗传算法的操作,可以获得不同种类的优良模式的新个体[1]。
3.模型建立
按照编码分层原理,我们可以构成一个层次树,树上的每个接点都是一个概念,如地区、出生日期、电厂部件编码等。但对于部分编码,并不能利用较高层次概念替换低层次概念,故不能构成传统的概念层次树。因此,根据领域专家经验,我们构建一棵多深度概念树[5]。对于部分编码,其某层只有一位,为了便于利用遗传算法,我们可以将其同其上层或下层合并。
在结构简单层次树中,通过指针实现记录之间的联系,查询效率较高。但对于多深度概念树,复杂的层次及分支使得数据的查询及更新操作比较复杂。因此,要使用其它的方法来实现查询优化。按照多深度概念树结构,以接点概念建立分级索引,不但能有效地减少索引和关系表的数量,同时还可以有效地实现查询优化。然后利用分层遗传算法,对每级索引单独地进行遗传算法搜索,可以有效提高查询速度。
多深度概念树的深度用N表示,即子种群的个数;每层包含的个体数用n表示,即子种群包含的个体数;对每个子种群独立地运行各自的遗传算法,记它们为GAi(i=1,2…N)。在每个子种群的遗传算法运行到一定代数后,将N个遗传算法的结果种群记录到二维数组R[1…N,1…n]中,则R[i,j]表示GAi的结果种群的第j个个体。
4. 遗传算法设计
4.1 个体编码
问题的解编码使其成为染色体是遗传算法使用中的关键问题。编码方式对遗传算法的设计有较大的影响,并且一定程度上影响到进化的速度。
由于编码的遗传算法查询属于组合优化问题,且编码都是由数字、字母或符号组成,故根本不可能采用二进制编码。而整数和字母排列对于组合优化问题最为有效,故采用基于整数和字母排列编码[2]。
4.2 遗传操作
4.2.1 选择
按各个个体数目在群中占的比例计算适应度f,个体在群中出现的次数愈多,则其适应度愈大。
对群体中的所有个体按其适应度大小降序排序,其对应的适宜度值记录到数组A[1…N,1…n]中,A[i,j]表示GAi的种群个体适宜度值。个体适应度越高,表示此个体出现的次数就越多,那么它被选择的概率就越高。各个个体所分配到的概率值作为其能够被遗传到下一代的概率,基于这个概率值使用比例选择的方法产生下一代群体。
4.2.2 交叉算子
交叉是把两个父子体的部分结构加以替换重组而生成新个体的操作,其目的是为了能够在下一代产生新的个体。通过交叉操作,可以使遗传算法搜索能力得以飞跃提高。
本文采用单点交叉和多点交叉相结合的方式,交叉主要发生在每层信息内部。采用哪种交叉方式根据多深度概念树每层信息的块数来决定,块数大于二的采用多点交叉,否则使用单点交叉。交叉点选择在块与块之间,具体例子如图二所示。
根据Srinvivas提出的自适应遗传算法,交叉概率可以设计成随适应值而自动调整,交叉概率的计算公式如下:
根据算法本身优化参数要求,p的取值范围为0.75～0.95,为了限制遗传算法过快的收敛,我们取Pc1=0.95、Pc2=0.7。
4.2.3 变异算子
以很小的概率将少量随机生成的新个体替换R[1…N,1…n]中抽取的个体。至此,第一轮遗传操作结束。N个遗传操作GAi(i=1,2…N)可以从相应新的R[1…N,1…n]种群继续各自的操作。变异概率设计成与交叉概率一样,随适应值自动调整,计算公式如下:
根据算法本身优化参数要求,公式部分参数取值为pm1=0.01,pm2=0.001。
4.3 算法流程及算法描述
N个种群各自运行到一定的代数后,将N个遗产算法的结果更新为新的数组R[1…N,1…n],再整体地进行选择、交叉和变异。如此继续循环操作,直到得到满意结果为止。分层遗传算法流程图如图三所示:
整个分层遗传算法程序可以描述如下:
5. 结果生成
经过分层遗传算法对种群搜索后,可以获得最优结果,即各级数据库的分级索引。通过查找各分级索引对应的关系表,就能从数据库中调出各个层次概念所对应的信息,再按照多深度概念生成树的顺序对各层信息组织还原,就生成了用户需要的信息。
6. 结论
本文提出了一种基于分层遗传算法的编码信息查询方式,适用于多概念属性、多层次概念的编码数据库,适用于处理较大规模的问题。与其它信息查询优化算法相比,该方法充分利用了遗传算法快速全局搜索能力,有效避免了在数据库中对编码进行全面扫描,因此查询速度得到大大提高。
但本文群规模设置得过大,不能满足算法本身参数优化要求。因此,下一步的工作是尽量将群个体数目设置为由算法自动确定,进一步提高算法的效率。
参考文献
[1]王小平,曹立明.遗传算法—理论、应用与软件实现[M].西安:西安交通大学出版社.2002:68-69
[2]玄光男,程润伟.遗传算法与工程优化[M].北京:清华大学出版社.2004:2-6
[3]张俊玲.数据库原理与运用[M].北京:清华大学出版社:22-85
[4]张廷香,时念云.基于多深度概念层次树与遗传算法的数据挖掘技术研究[J].微计算机应用.2005,26(5):530-533
[5]Pathak p,GordonM,Fan W G.Effective information retrieval using genetic algorighms based matching functions adaptation[A].Proc of the33rd Annual Haw aii International Conference on System Science[C].Piscataw:IEEE Sermice Center.2000:1-8
[6]M.Korytkowski et al,Genetic Algorithm for Database Indexing[A].Lecture Notes in computer Science.2004:1142-1147