没有合适的资源?快使用搜索试试~ 我知道了~
≤≥×ð Þ沙特国王大学学报静态和动态度量空间Youssef Hanyf Al-Hassan SilkanChouaib Doukkali大学理学院计算机科学系,El Jadida,摩洛哥阿提奇莱因福奥文章历史记录:收到2018年2018年3月28日修订2018年5月11日接受2018年5月12日在线提供保留字:基于内容的检索数据结构索引最近邻范围查询A B S T R A C T本文的目的是开发一种度量索引方法,使用用户我们提出了一种索引方法,这是能够改善其结构的基础上用户的查询。所提出的方法,称为I-Clusters,是一种基于度量聚类的方法,从集群列表方法扩展而来。该方法降低了构造成本,提高了查询执行后的搜索成本。I-Clusters方法允许解决构建成本和搜索成本之间的权衡,并且它还允许索引动态数据集而无需额外的对象插入成本。实验结果表明,I-Clusters方法显著降低了基于查询执行的搜索开销,搜索性能达到了聚类列表的水平©2018作者制作和主办:Elsevier B.V.代表沙特国王大学这是一CC BY-NC-ND许可下的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。1. 介绍近年来,图像、视频、指纹和文档等复杂数据集在各种应用中的由于数据使用和生产的发展,相似性搜索系统得到了越来越多的关注,并且在信息检索、计算生物学和模式识别等许多领域都有越来越多的需求。有两种类型的相似性搜索查询,最常用的文学;范围查询和最近的邻居查询。范围查询是指检索距查询对象一定距离r内的所有对象的任务,而k最近邻查询返回与查询对象最相似的k个对象由于数据集的规模和相似性度量的复杂性,搜索成本被视为相似性搜索系统的主要问题在这种情况下,度量方法已被证明是一个显着的性能,以减少搜索成本。也就是说,当定义测量相似度的函数d(x,y)*通讯作者。电子邮件地址:youssef. gmail.com(Y。Hanyf)。沙特国王大学负责同行审查在一组对象X上,当它满足度量空间的三个性质(正性(d(x,y)0),对称性(d(x,y)= d(y,x))和三角不等式(d(x,z)d(x,y)+ d(y,z),所以对(X,d)称为度量空间。相似性搜索方法利用三角不等式来索引数据集,以避免搜索过程中的顺序扫描因此,由于距离计算是昂贵的,度量访问方法(MAM)的目的是索引度量空间对象,以尽量减少搜索过程中的距离计算在静态和动态度量数据空间中,相似性搜索存在三个主要缺点在这项工作中,我们感兴趣的建设成本和搜索成本的度量访问方法。在静态数据空间中,度量访问方法受到搜索成本和构建成本之间在搜索中不昂贵的方法需要昂贵的构造成本,反之亦然;在构造中不昂贵的方法被迫牺牲搜索性能。为了说明这个问题,让但是,与此同时,它在构建成本(n2距离计算)方面是最昂贵的,因此,这种方法在大数据集的情况下是无用为了降低AESA的但与原算法https://doi.org/10.1016/j.jksuci.2018.05.0041319-1578/©2018作者。制作和主办:Elsevier B.V.代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。制作和主办:Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页:www.sciencedirect.comY. Hanyf,H.Silkan/ Journal of King Saud University189≤×(AESA)。关于第二个例子,众所周知,枢轴集的选择对搜索效率有显著影响。因此,在文献中提出了许多方法来选择良好的枢轴集,以便提高度量访问方法的搜索效率(Buffett等人,2003年,Pedreira和Kazaboa,2007年)。这些方法需要昂贵的成本来选择枢轴集,因此,在这种情况下,搜索成本的降低也通过构造成本的增加来实现在动态数据集中,除了初始结构的构建成本外,还存在额外的昂贵的对象插入成本对象插入成本通常大于搜索成本;它包括检索适当节点(或集群)的成本,拆分完整节点(或群集)的成本。本文提出了一种索引方法,该方法可以最小化搜索和初始结构构建成本之间的权衡,并且可以避免对象插入成本在可扩展的数据集中。该方法是聚类列表的一种变体,称为I-Clusters,它基于用户的查询,以减少构建成本,避免在动态数据集中的插入成本,并逐步提高搜索成本。实验结果表明,该方法的搜索代价随着用户查询的增加而逐步提高2. 相关作品2.1. 度量访问方法在文献中(Chávez等人,2001)中,度量访问方法有两种著名的方法,即基于枢轴的方法和划分方法。基于分区的MAM,如LC(Chávez和Navarro,2005)、D索引(Dohnal等人,2003年,Hanyf等人,2015a,b)和GNAT(Brin,1995)旨在将数据集划分为尽可能紧凑的许多子集。基本上,存在两种著名类型的划分方法;球划分和超平面划分,但是存在在(Lokoc. 2014年)称为分区切割区域,其目的是通过组合球和枢轴来压缩区域。其他方法将这两种类型的分区结合起来以提高效率。例如,在(Pola等人,2014)作者提出了一系列方法,旨在通过使用超平面和球分区技术来减少分区之间的重叠。在所有的分区方法中,没有被查询球覆盖的区域将在搜索过程中被丢弃。分割方法已经表明(Chávez等人,2001年,查韦斯和纳瓦罗,2005年)的一个显着的阻力的诅咒的维度的问题。相比之下,旋转MAMs,如AESA(Ruiz,1986年,Chávez等人,2001)、LAESA(Micó等人,1994年,Chávez等人,2001)、I-LEASA(Hanyf等人,2016)和EP(Ruiz等人,2013),使用距离矩阵来丢弃对象,并避免搜索过程中的一些距离计算。度量访问方法也可以根据数据集的动态性进行分类。像AESA和LAESA这样的静态方法基于固定数据集构建索引结构,并且无法从结构中插入或删除对象。然而,大多数最近的方法是动态的,如DiSAT(Chávez等人,2017),支持在结构中删除和插入新对象。2.2. 集群列表List of Clusters(Chávez and Navarro,2005)方法将对象划分为子组。要构建集群列表的结构,该算法从数据集中选择一个pivot p,然后创建一组最接近p的m个对象。该过程递归地应用于剩余的对象,直到获得一个称为簇的列表n/(m + 1)组,例如n是数据库中对象的数量,m是簇的大小。在查询R(q,r)的执行期间,该算法将值d(q,pi)与每个聚类i的覆盖半径cr(pi)进行比较。如果满足条件d(q,pi)- r cr(pi),则搜索过程处理该聚类,否则将其排除。满足条件d(q,p)+r cr(p)意味着聚类的所有对象都属于结果集。 构造成本为O(n2/m)距离。在(Barrientos等人,2013年),其原则是用多层次结构取代每一层次。事实上,每个星团都被超星团所取代,每个超星团都包含一个子星团的列表。与其他方法相比,聚类列表方法的主要优点是构造算法简单,减少了聚类之间的重叠问题。DLC是在(Navarro和Reyes,2016)中提出的集群列表的另一个扩展。它基于二级存储器,与原来的LC相比,减少了存储器的消耗。该方法在主存中只保留簇的中心、簇的大小和簇的覆盖半径。3. 该方法I-Clusters保留了List of Clusters方法的主要聚类特性它将数据集对象重新分组到紧凑的集群中,这允许搜索算法在查询执行期间仅访问某些下面的小节描述了I-Clusters的结构,搜索成本的改进技术和I-Clusters的搜索算法。3.1. I-Clusters结构I-Clusters结构的构造类似于集群列表。构造算法创建一个clus-ter列表;每个clus-ter重新组合彼此接近的对象。它从数据集的n个对象中选择一个pivot p开始;m个最接近此轴心的对象将加入到群集。递归地应用该过程,直到创建n/(m + 1)个聚类。每一个的特征在于一个枢轴和一个覆盖半径,该覆盖半径等于枢轴和集群中最远对象之间的距离。一个完整的I-Clusters的构造成本,像List of Clusters方法一样,是O(n2/m)。在大型数据集中,构建成本是昂贵的,特别是如果聚类大小m很小。为了降低构建成本,I-Clusters构建了一个不完整的集群列表,其中包含k个集群和一组自由对象。该方法确实降低了不完全I-Clusters的搜索代价图1表示二维空间中I-簇的不完整结构不完全簇表的概念在动态数据集中除了降低构造成本外,还有另一个优点:动态数据集的新对象可以无代价地插入到结构中在包含k个簇的经典簇列表结构中插入对象至少需要计算k个距离。因此,插入一组m个对象需要至少k m个距离计算,这比在该组中的顺序搜索更昂贵。在动态数据集中,I-Clusters方法将新对象插入到自由对象的簇中,而不需要任何距离计算。在改进过程中,出现了自由对象的聚类,包括新插入的对象190Y. Hanyf,H.Silkan/ Journal of King Saud UniversityR1p1C1(p1,r1)C2(p2,r2p2R3p3集群列表Fig. 1. 二维空间中I-团簇的不完全结构。3.2. 改进过程为了改善搜索成本,改进过程旨在通过基于查询结果创建新的聚类来最小化空闲对象的数量当用户发起查询时,计算对象查询和数据集对象之间的许多距离以执行查询,并且获得关于对象分布的更多信息。I-Clusters的改进过程仅使用在执行用户查询期间计算的距离,改善不完善的结构。因此,当用户执行更多查询时,搜索变得更快。在执行查询R(q,r)之后,使用结果对象来创建新的集群。对象查询将不被存储,并且其最近的邻居将被用作所创建的集群的引用,以避免额外的内存空间消耗。因此,集群的参考(ref)和对象之间的距离小于r + d(ref,q)。所创建的集群Ci由三元组Ci(ref,dNN,ri)定义,ref是集群的参考对象,i是表示集群创建的顺序的集群标识符,ri是集群参考与集群的最远对象之间的距离。 图图2表示基于查询执行创建新集群的示例。3.2.1. 创建新的集群定义1. 设S是一个包含n个簇Ci(ref,dNN,ri)的结构. 如果dNN =0,则聚类Ci(ref,dNN,ri)称为正常聚类。当dNN> 0时,聚类Ci(ref,dNN,ri)称为模糊聚类.在改进过程中,我们区分了两种类型的集群。正常的集群是一个没有差异的实际中心和参考中心之间的距离。而模糊聚类是中心与参考点之间存在距离的聚类(参见定义1)。因此,当用户启动属于数据集对象的查询对象时,即将到来的聚类将是正常聚类,因为距离最接近的邻居是零(dNN = 0)。这意味着集群具有精确的边界,并且所有对象都在距离参考点小于ri = dmax的范围内(参见定义1),其中dmax查询对象查询到结果集中最远对象的距离。如果查询不属于数据集对象,则将不知道即将到来的聚类的确切中心(确切引用)和确切边界,但将对其进行估计。参考由最近邻居的对象估计这种类型的星系团在本文中被称为模糊环星系团(见定义1).图图3示出了二维空间中的正常聚类(a)和模糊聚类(b)的示例。虚线表示基于由实线表示的查询结果集创建的聚类。实心圆表示附着到簇的对象,而空心圆表示尚未附着的对象。创建新集群的简单情况是,查询的所有结果对象尚未附加到任何集群。在这种情况下,改进算法直接创建一个新的聚类。但是当某些结果对象属于已有的聚类时,算法应该在创建新的聚类之前消除重叠。3.2.2. 重叠消除为了避免集群之间的重叠,我们需要一些优先级标准来控制新集群的创建。很明显,正常聚类比模糊聚类更好,更有效。但是,如果重叠是在相同类型的两个聚类之间;在两个正常聚类或两个模糊聚类之间,我们提出以下标准:● 如果即将到来的聚类是一个模糊聚类,并且它与另一个模糊聚类相交,则小dNN的聚类优于大dNN的聚类。如果即将到来的簇是正常簇,并且它与其他正常簇相交,则丢失更多对象的簇,如果它被更新,则优先保持原样。该标准可以通过速率损失值(参见定义2)来衡量,并且通过比较集群的速率损失值来决定r1p1C1(p 1,r 1)r2C(p,r)p222 2C3( p3, r3)r3p3C4(q,d)免费DQ集群列表改进过程后的结构图二. 基于查询结果创建新聚类的示例。R1p1C1(p1,r 1)C2( p2,r2)C3R2 p2R3p3集群列表RQQQI-簇结构上的查询执行●Y. Hanyf,H.Silkan/ Journal of King Saud University191\不⁄⁄\←←\其中,size(Co)是Co中的对象数,size(Co)是Co和CE之间的交集的对象数。←←C)是RNCQNNDMaxBCDMaxRQrdmax+d NNNN(a)正常聚类(b)模糊聚类图3.第三章。正常和模糊聚类的示例定义2. 假设Co(ref,dNN,ro)是旧的正常聚类,并且CE(ref,dNN,rE)是正常的即将到来的聚类。 的损失率删除C0被定义为:速率损失(C0)=大小(C0)-大小(C0TT CE),如果(速率损失(Ci)>速率损失(CE)),则减少(CE),更新R直到R Cielse释放Ci对象并更新Intsct end if更 新 即 将到 来 的 集 群 的 丢失 率 被 定 义 为: Rateloss ( CE ) =Nbr_obj_freed为了避免重叠,只有两种解决方案:删除与查询球重叠的旧聚类或减小即将到来的聚类的范围基于前面的讨论,我们提出了一个算法(见算法1),通过创建新的集群,没有重叠,基于查询结果,以改善结构。算法1.创建新的集群N_c,Intsct = N//与R输入:R,NN,dNN,dmax/<$结果对象的集合,查询的最近邻居,距离d(q,NN)和从查询到最远对象的距离/输出量:Ci(rc,ref,dNN)/<$NewCluster是标识符,rc是参考,dNN是聚类中心和参考之间的距离/ Begin如果(所有R对象都还没有被附加),那么//查询N_c++,参考NN,rcdmax + dNN,创建CN_c(ref,dNN,rc)然后退出else对于所有(Ci/R\ Ci对于所有(CieIntsct),如果(Ci(dNN)= = 0),则如果(速率损失(Ci)>速率损失(CE)),则减少(CE),更新R直到R Cielse释放Ci对象并更新Intsct end if如果结束,则结束For all(Cie Intsct)do其他For all(Cie Intsct)do如果(Ci(dNN)> dNN),则释放Ci对象并更新Intsct否则减小CE,更新R直到R CiIntsct如果结束,则结束N_c++,ref NN,rc dmax和Create CN_c(ref,dNN,rc)end算法1的工作原理如下:如果查询不与任何簇相交,则算法直接创建一个新簇并更新结构。否则,如果即将到来的簇是正常的,则算法分为两个阶段:在第一阶段,如果即将到来的簇的速率损失优于即将到来的簇,则减小即将到来的簇的范围,直到不再与正常簇重叠。在第二阶段:如果即将到来的簇与正常簇相交,则算法比较速率损失值;如果即将到来的簇的速率损失劣于旧簇的速率损失,则算法减小即将到来的簇的范围,否则删除旧簇并释放对象。否则,如果旧聚类是模糊聚类,算法将删除它并释放其对象。然后,如果即将到来的聚类是模糊的,则算法减小其范围,直到消除与所有正态聚类的重叠。然后,对于所有的模糊聚类,如果其dNN劣于旧聚类,则该算法减小即将到来的聚类的范围,或者在其他情况下删除旧聚类。最后,该算法创建一个新的簇并更新结构。3.3. 查询的顺序增量构建的顺序通常会对结构产生影响,但没有办法控制用户查询的顺序然而,所提出的用新的更好的簇替换旧簇的技术192Y. Hanyf,H.Silkan/ Journal of King Saud University-1←←-←t×无论查询顺序如何,都将保持渐进的效率。因此,当用户启动适当的查询时,每个集群将在稍后被更有效的集群替换。3.4. 搜索算法3.4.1. 范围查询范围查询(q,r)的执行旨在返回距离查询q的对象在距离r内的对象。与所有聚类方法一样,该算法的主要搜索思想是只访问某些聚类,避免在与查询球不相关的聚类中搜索。因此,所提出的范围搜索算法(参见算法2)如下工作:该算法仅在与查询相交的聚类中搜索,加上自由对象的集合。如果查询被独占地包含在一个集群中,则它区分两种情况。在第一种情况下,如果聚类是模糊的,则算法继续搜索,因为可能有一些对象被放置在模糊聚类区域中,尽管它们没有附着到模糊聚类区域。是一个正常的聚类,算法算法2.范围查询输入:q,r //查询对象和查询输出的范围:R // set of object results开始对于所有(Ci),如果(d(q,Ci(ref))r +Ci(r)),则访问Ci,将结果对象添加到R如果(d(q,Ci(ref)Ci(r)r和Ci(dNN)= =0),则返回Rend ifelse breakend if端搜索未附加的对象将结果对象添加到R返回R端3.4.2. 最近邻查询最近邻算法(参见算法3)从最近到最远访问聚类因此,访问聚类的优先级是根据与对象查询的接近度,因为如果聚类最接近查询对象,则更有可能包含结果对象。聚类搜索类似于范围查询搜索,不同之处在于查询范围在搜索期间减小。在开始时,搜索算法使用最大范围,并且当它检索到相关的新对象时,它通过到当前k个最近邻的距离来更新范围。算法3. 最近邻居Priority//用于存储访问集群的优先级的数组i输入:q,k //查询对象和最近邻的数量产出:R,rk//最近邻的集合和到k个最近邻的距离开始对于所有(Ci)do优先级优先级Ci结束尝试优先级,i 0做C优先事项(一)如果(d(q,C(ref)r + C(r)),则访问Ci,更新R和更新rk如果(d(q,C(ref))C(r)r和C(dNN)== 0)确实返回R,则退出end ifelse breakend ifI++Until(i==n)在未附加对象的集合中搜索,更新R,rk返回R端4. 结果我们已经测试了所提出的方法的性能,通过一系列的实验在两个不同的数据集。一方面,我们测试了搜索性能的改善及其与执行查询数量的关系。另一方面,我们比较了所提出的方法与集群列表方法。在这些实验中,我们专注于基于查询执行的自由对象的聚类,因为离线创建的集群列表的性能已经被评估,读者可以参考原始集群列表的论文(Chávez和Navarro,2005,Navarro和Reyes,2014,2016)以了解更多细节。因此,实验中使用的初始I-Clusters结构不包含在离线阶段创建的任何群集,即群集的初始数量为零(k = 0)。为了评估所提出的方法对查询顺序的敏感性,改进中使用的查询顺序在每个结构中随机生成。所有呈现的成本值都是通过执行100个不同查询获得的平均值。搜索成本和构建成本是根据计算的距离的数量来测量的,因为距离计算与算法的其他部分相比是非常昂贵的,并且因为它独立于所使用的设备。实验中使用的数据集NASA:一组40,150个20维特征向量,由从NASA下载的图像生成,并消除了重复向量。欧氏距离用于度量相似性。李斯特菌:一组20,660个单核细胞增生李斯特菌基因的DNA序列。使用编辑距离这些数据集在Metric Space Library中提供。我们使用相同的库来实现所建议的方法,并且使用了库中已经实现的List of Clusters方法。在本文的其余部分,我们使用符号I-Clusters_xq来表示已经解决了查询的I-Clusters结构。此外,我们使用符号LC(m)来表示其簇大小等于m个对象的LC结构Y. Hanyf,H.Silkan/ Journal of King Saud University1934.1. 搜索性能这部分实验旨在评估所提出的方法的搜索性能改进,以及它与查询执行的关系;我们比较了所提出的方法在执行查询后的搜索成本。因此,搜索性能进化的测试分为两个部分。在第一部分中,我们测试了属于数据集的查询的基础上的成本改善。第二部分是基于不属于数据集的查询来测试成本改进。测试查询是随机生成的,它们不用于生成I-Cluster_xq结构。用于生成Nasa数据集的I-Cluster_xq结构的查询范围在0.1和1之间变化,而用于生成李斯特菌I-Cluster_xq结构的查询范围在10和200之间。为了测试所提出的方法对查询顺序的敏感性,在Cluster_xq结构的生成期间执行的x个查询的顺序被随机生成。4.1.1. 属于数据集的在这一部分中,我们的目标是评估属于数据库的查询对搜索性能的我们比较了在执行属于NASA数据集的0、50、100和150个查询后的搜索成本。同时,我们比较了在执行0、100、200和300次查询后李斯特菌结构中的搜索表1表示在执行属于数据集的查询之后的Nasa结构参数的细节,而表2表示李斯特菌结构的细节。每当执行更多的查询时,自由对象的数量就会但是,集群的数量会根据查询的执行情况而增加。范围查询的结果如图所示。 4,最近邻查询的查询结果如图4所示。五、从这些结果中,我们可以看到,I-Clusters结构的性能显着提高的查询执行的结果;每当我们执行更多的查询,范围和最近邻居4.1.2. 不属于数据集为了评估不属于索引对象的查询的执行与搜索性能提高之间的关系,在本节中,我们比较了300不属于索引对象的查询。 范围查询结果如图6所示,最近邻查询结果如图6所示。7.第一次会议。表3表示在执行不属于数据集的查询之后的Nasa结构的参数值,并且李斯特菌结构的参数值在表4中表示。在Nasa结构中,每当我们执行更多查询时,自由对象的数量就会减少,而集群的数量在执行200个查询后减少,在执行300个问题。 在李斯特菌结构集群的数量是表1在执行属于数据集的查询后,Nasa结构的参数详细信息I-Clusters_0qI-Clusters_50qI-Clusters_100qI-Clusters_150聚类数0182239自由对象40,15033,93128,50626,836群集对象0621911,64413,314集群的平均大小345.5529.27341.38表2执行属于数据集的查询后李斯特菌结构的参数详细信息I-Clusters_0qI-Clusters_100qI-Clusters_200qI-Clusters_300聚类数046151226自由对象20660187191767417157群集对象0194129863503集群的平均大小42.1919.7715.5450004000035000300002500020000150000.1 0.30.5范围21000200001900018000170001600015000李斯特菌数据集顺序搜索I-Cluster_0 qI-Cluster_100qI-Cluster_200qI-Cluster_300q10 40 70 100 150范围见图4。 基于查询属于数据集的范围搜索性能的改进。NASA数据集顺序搜索I-Cluster_0 qI-Cluster_50qI-Cluster_100qI-Cluster_150q距离计算距离计算194Y. Hanyf,H.Silkan/ Journal of King Saud University距离计算420004000038000360003400032000300001 10 20 3050最近邻居顺序搜索I-Cluster_0 qI-Cluster_50qI-Cluster_100qI-Cluster_150q210002050020000195001900018500李斯特菌数据集1 2 3 4 5最近邻居顺序搜索I-Cluster_0 qI-Cluster_100qI-Cluster_200qI-Cluster_300q图五. 基于数据集查询的K-NN性能改进。4100039000370003500033000310002900027000Nasa数据集0.1 0.30.5范围210002050020000195001900018500180001750017000李斯特菌数据集10 40 70 100 150范围顺序搜索I-Cluster_0 qI-Cluster_100qI-Cluster_200qI-Cluster_300q见图6。 基于不属于数据集的查询的范围搜索成本的改进。420004000038000360003400032000210002050020000195001900018500300001 10 20 3050最近邻居顺序搜索I-Cluster_0 qI-Cluster_100qI-Cluster_200q I-Cluster_300q180001 10 20 30 50最近邻居顺序搜索I-Cluster_0 qI-Cluster_100q I-Cluster_200q I-Cluster_300q见图7。 基于不属于数据集的查询的K-NN性能改进。基于查询的执行,自由对象的数量逐渐增加,并且当该方法执行100、200和查询时,自由对象的数量减少从这些结果来看,在查询执行之后,Nasa和Listeria数据集的I-Cluster结构得到了显著改善。确实,基于不属于索引对象集的查询的改进明显小于基于属于索引数据集的查询的改进。但这当用户通常通过索引数据集之外的查询工作时,这种改进非常重要。4.2. 搜索性能比较实验结果表明,该算法能够根据用户的历史查询信息来提高查询效率本实验旨在顺 序 搜 索 I-Cluster_0 qI-Cluster_100qI-Cluster_200qI-Cluster_300q距离计算距离计算距离计算距离计算Nasa数据集距离计算Nasa数据集李斯特菌数据集Y. Hanyf,H.Silkan/ Journal of King Saud University195表3执行不属于数据集的查询后,Nasa结构的参数详细信息I-Clusters_0qI-Clusters_100qI-Clusters_200qI-Clusters_300聚类数0431468自由对象40,15035,64228,11426,657群集对象0450812,03613,493集群的平均大小104.84859.71198.43表4执行不属于数据集的查询后李斯特菌结构的参数详细信息I-Clusters_0qI-Clusters_100qI-Clusters_200qI-Clusters_300聚类数061165272自由对象20,66018,80917,76117,241群集对象0185128993419集群的平均大小30.3417.5712.5735200302002520020200152001020052002000.1 0.30.5范围I-cluster_30000q LC(1000)LC(500)LC(100)252002020015200102005200200K-NN搜索1 10 20 30 50最近邻居I-cluster_30000q LC(1000)LC(500)LC(100)见图8。NASA数据集上搜索成本的比较。表5执行30,000次查询后的NASA结构参数详细信息聚类数自由对象群集对象集群的平均大小I-Clusters_30000q275013,32426,8269.759000000800000070000006000000500000040000003000000200000010000000lcluster(100)lcluster(500)lcluster(1000)I-cluster_30000q结构见图9。 建筑成本的比较。从所呈现的图中,我们可以看到,I-Chronter_30000 q在范围查询和最近邻查询这两种情况下都达到了LC(1000)的性能。还可以很好地观察到,在大范围查询的情况下,I-Cluster_30000 q可以达到LC(500)的性能。除了I-Cluster能够显著提高其性能之外,I-Cluster在构建阶段无需计算数千个距离,这与集群列表方法的结构不同(见图1)。 9)。5. 结论和未来工作本文提出了一种基于用户查询的聚类度量访问方法。所提出的方法重组成几个集群的对象。所提出的方法的结构构造是基于测试该方法的搜索性能是否达到NASA数据集的聚类列表的搜索性能。为了与LC [2]比较,我们使用三种不同的簇大小(m = 100,m =500,m = 1000)构建了三种簇列表方法的结构。因此,这些结构与I-Cluster_30000 q结构进行了比较。搜索成本比较的结果可在图8中获得。I-Cluster_30000 q结构的详细信息见表5。用户的查询。因此,搜索成本随着时间的推移而改善,并且取决于查询执行。当用户执行查询时,结果是包含彼此接近的对象的子集。该方法根据结果集生成新的簇并插入到索引结构中。我们已经区分了两种类型的聚类;基于属于索引数据集的查询创建的精确聚类,以及基于不属于索引数据集的查询创建的模糊聚类。范围搜索距离计算距离计算距离计算196Y. Hanyf,H.Silkan/ Journal of King Saud University到索引数据集。在旧聚类和新聚类之间存在重叠的情况下,我们提出了删除旧聚类或修改新聚类的标准,以避免重叠。标准基于集群的类型和释放的对象的数量。所提出的方法有两个主要优点。第一个是构造和对象插入动态数据集的廉价性第二个优点是在查询执行后搜索成本的改善。所提出的方法的效率在两个不同的数据集上得到了证明:一组40,150个20维图像特征向量,称为NASA和一组20,660个单核细胞增多性李斯特菌基因的DNA序列实验结果表明,I-Cluster算法可以显著提高搜索代价。此外,实验结果表明,在处理大的查询集,I-集群的性能可以达到LC的效率。在未来,这项工作的核心思想可以用来改善任何其他指标的索引和搜索方法。我们计划使用相同的想法来改进其他最近的文献方法;每个结构都需要特定的技术来利用用户我们还计划基于提高其搜索效率的能力来比较不同类型的索引方法,而不是基于修复效率的经典比较引用Barrientos,R.J.,Gómez,J.I.,Tenllado角,马蒂亚斯议员Zezula,P.,2013.使用多gpu平台在度量空间上进行多级聚类。欧洲并行处理会议,施普林格。Brin,S.,1995.大度量空间中的近邻搜索。超大型数据库国际会议。 摩根·考夫曼出版公司Buffett,B.,Navarro,G.,Chávez,E.,2003.度量空间中邻近搜索的主元选择技术。模式识别通讯 24(14),2357-2366。Chávez,E.,Di Genaro,医学博士,Reyes,N.S.,Roggero,P.,2017. DiSAT的可分解性用于索引动态化。J. Comp. Sci. Technol. 十七岁Chávez,E.,Navarro,G.,2005.一个紧凑的空间分解,用于有效的度量索引。模式识别通讯26(9),1363-1376。Chávez,E.,Navarro,G.,巴埃萨-耶茨河,Marroquín,J.L.,2001.在度量空间中搜索。ACM Comp. Surveys(CSUR)33(3),273-321.Dohnal,V.,詹纳罗角,Savino,P.,Zezula,P.,2003. D-index:度量数据集的距离搜索索引。Multimedia Tools Appl. 21(1),9-33.Hanyf,Y.,Silkan,H., Labani,H., 2015年a。 选择优良品质的标准和技巧D-index的值。智能系统和计算机视觉国际会议,非斯,摩洛哥。Hanyf,Y.,Silkan,H.,Labani,H.,2015年b。在2D/3D图像数据库中进行快速高效的索引和相似性搜索。Int. Rev. Comp. Software 10(5),481-488。Hanyf,Y.,Silkan,H.,Labani,H.,2016.度量空间中相似性搜索的可扩展结构:在图像数据库中的应用。 国际计算机图形、成像和可视化会议(CGiV)。美国电气与电子工程师协会。LokocJ. ,Moško,J., C.P.,Skopal,T.,2014年。关于度量空间的割-地区Inf. Syst. 43,1-19.Micó,M.L.,Oncina,J.,Vidal,E.,1994.一种新的具有线性预处理时间和存储要求的最近邻近似和消除搜索算法(AESA)。 模式识别通讯 15(1),9-17。Navarro,G., Reyes,N., 2014. 二级内存中群集的动态列表。相似性搜索和应用国际会议。斯普林格。Navarro,G.,Reyes,N.,2016年。新的动态指标索引辅助内存。Inf. Syst. 59,48佩德雷拉岛N.R.,2007.度量空间中相似性搜索的稀疏枢轴空间选择。SOFSEM 2007:计算机科学理论与实践施普林格,pp. 434- 445宝拉,爱尔兰共和军,Traina Jr,C.,Traina,AJM,2014年。NOBH树:通过使用具有非重叠节点的度量超平面来改进内存中的度量访问方法。Data Knowledge Eng. 94,65-88.鲁伊斯,E.V. 1986.一种在(近似)恒定平均时间内寻找最近邻的算法。模式识别通讯4(3),145-157。Ruiz,G.,Santoyo,F.,Chávez,E.,Figueroa,K.,Tellez,E.S.,2013.用于更快度量索引的极端枢轴。相似性搜索和应用国际会议。斯普林格。
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功