共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
随着移动传感器设备的普及,人们能够采集到的位置数据越来越多,轨迹数据的规模也越来越庞大.从大规模时空数据中查找与指定轨迹最相似的前k条轨迹一直是时空大数据挖掘的重要挑战之一.现有的相似轨迹查询方法大都包括三个阶段:(1)对海量的离线轨迹数据建立索引;(2)基于索引结构从已知轨迹集中查询与指定轨迹相似的候选轨迹;(3)计算指定轨迹与候选轨迹之间的精确相似度并返回相似度最大的前k条轨迹.但大多数现有方法对轨迹进行聚类索引时不能有效利用时间和空间信息,导致时间相似度不高的轨迹也会被划分到相同的索引项上,最终影响查询的准确性和效率.此外,现有的时空轨迹相似度计算方法存在大量的无效运算,使得相似轨迹的查询效率整体较低.针对当前伴随轨迹查询方法对时间与空间信息利用不充分的问题,本文提出一种新的二级时空分桶索引结构,首先将每条轨迹数据按照时间滑动窗口划分为若干带有时间槽信息的子轨迹,在时间上对轨迹进行一级索引聚类;在此基础上对在相同时间槽内的子轨迹进行二级空间索引聚类,利用哈希算法将具有连续相同位置点的子轨迹映射到同一时空分桶中.与已有索引方法相比,该方法对不同轨迹在索引时具有更好的区分度,查询时的... 相似文献
3.
4.
5.
6.
7.
大规模时间序列数据库降维及相似搜索 总被引:4,自引:0,他引:4
提出一种基于分段多项式表示(PPR)的时间序列数据库相似查询的系统化方法.PPR是一类基于线性多项式回归的正交变换.用PPR变换索引时间序列数据在理论上具备非漏报性质.文中分析了PPR的计算复杂性以及查询阈值的下界,并提出了一种衡量时间序列相似查询算法之查询效率的定量指标.与基于离散傅立叶变换(DFT)和离散小波变换(DWT)的时间序列相似查询算法所作的对比实验表明,所提算法可以用低的索引结构维数获得高的查询效率. 相似文献
8.
随着基因测序技术和人类基因组计划的发展,从大量的生物数据中寻找相似的序列就越来越成为当前研究的热点问题.本文提出了一种聚类的多解析度字符串索引结构,用于解决生物序列的相似性查询问题.首先,以较小容量的MBR(最小绑定矩形)构造基因序列的多解析度字符串索引结构,然后通过对MBR的聚类以夏保序技术的应用,减小索引中MBR的平均体积,从而增加了查询向量到索引的空间距离,提高了索引的过滤能力.还给出了一种新的后处理方法,通过大量的减少编辑距离的计算,提高索引的性能.文中给出了该索引结构并详细介绍了索引的相关算法.实验表明,该索引结构是一种有效的处理生物数据的相似性查询的索引结构. 相似文献
9.
对当前聚类算法进行研究的基础上,提出了有效地实现多元时间序列聚类的方法.用离散哈达玛变换对多元数据进行降维,求出多元变量相关系数矩阵的特征值作为权值.采用带权值的矩阵相似性度量方法,利用改进的K-means算法对多元时间序列进行聚类分析.实验结果表明,该方法能够有效地实现多元时间序列聚类,把具有相似趋势变化的多元时间序列对象划分到同一类中. 相似文献
10.
针对基于u-shapelets的时间序列聚类中u-shapelets集合质量较低的问题,提出一种基于最佳u-shapelets的时间序列聚类算法DivUshapCluster。首先,探讨不同子序列质量评估方法对基于u-shapelets的时间序列聚类结果的影响;然后,选用最佳的子序列质量评估方法对u-shapelet候选集进行质量评估;其次,引入多元top-k查询技术对u-shapelet候选集进行去除冗余操作,搜索出最佳的u-shapelets集合;最后,利用最佳u-shapelets集合对原始数据集进行转化,达到提高时间序列聚类准确率的目的。实验结果表明,DivUshapCluster算法在聚类准确度上不仅优于经典的时间序列聚类算法,而且与BruteForce算法和SUSh算法相比,DivUshapCluster算法在22个数据集上的平均聚类准确度分别提高了18.80%和19.38%。所提算法能够在保证整体效率的情况下有效提高时间序列的聚类准确度。 相似文献
11.
12.
13.
14.
逐维聚类的相似度索引算法 总被引:5,自引:0,他引:5
随着多媒体信息技术的迅速发展,多维度索引技术在图像、视频等可视信息的存储、检索方面成为一个重要的研究领域,针对“维数危机”难题,提出逐维聚类相似度索引算法,该算法根据数据集的分布特性,对特征矢量的每一维进行聚类,算法在实现检索时可以逐步滤除与查询矢量不相似的数据集,缩小检索范围,进而提高了检索速度,实验结果表明,逐维聚类算法适用于基于相似度的高维数据矢量检索和查询,是一种简单、灵活的索引结构。 相似文献
15.
一种基于网格索引的数据聚类算法 总被引:1,自引:0,他引:1
为了提高基于密度聚类算法的效率,避免算法在执行过程中的多余搜索,提出了一种基于DBSCAN算法的改进的空间数据聚类算法。该算法采用对象邻域空间进行划分的方法,将网格索引结构应用于该算法。在核心对象的邻域内选择八个方向上未标记且距离核心对象最边缘的对象来扩展种子对象,减少查询次数,降低聚类的时间复杂度。在实验中,利用海量数据集对算法进行测试,测试结果证明新算法在保证聚类精度的情况下时间效率显著高于DBSCAN算法。 相似文献
16.
索引大规模时序数据库是高效时序搜索中的关键问题.提出了一种新颖的索引方案RQI, 它包括3种过滤策略: 即first-k过滤、索引低边界和上边界以及三角不等式修剪.基本的思想为首先运用Haar小波变换计算每个时序的小波系数,利用前面的k个小波系数形成一个最小边界矩阵,以利用点过滤方法;然后将预先计算每个时序的低边界特征和上边界特征存放到索引当中;最后采用三角不等式来修剪不相似的序列并确保没有漏报.同时提出了一种新的低边界距离函数SLBS和聚类算法CSA.通过CSA可保持索引良好的聚类特征以提高点过滤方法的效率,从而引入了一种更好的算法RQIC.在合成数据集和实时数据集的大量对比实验表明,RQIC是有效的且具备较高的查询效率. 相似文献
17.
时间序列相似度是时间序列数据挖掘的重要研究方向之一。如何利用时间序列相似度对提高时间序列数据聚类有着重要的意义。提出一种基于时间序列相似度的半监督谱聚类算法,通过选取适当的时间序列特征构造相似度与距离,在谱聚类算法的基础上利用标签数据选取初始类簇。实验表明,该算法使具有相似特征的时间序列可以很有效地被聚集到同一类中。 相似文献
18.
19.
有效管理生物数据并提供高效的查询方法是生物信息处理的重要研究内容.BioSeg是一个新的生物序列数据模型.查询优化研究是生物数据库管理系统开发的重要内容之一.研究当前生物数据索引技术,针对BioSeg数据模型的特点和生物序列相似性查询需求设计了一种新的生物序列数据索引BioIndex,并设计相应的查询算法.首先,使用MEME(Multiple EM for Moeif Elicitation)算法挖掘生物序列集中的序列模式作为索引建立索引序列库;之后,在索引序列库中查找与查询序列最相似的索引序列,将其对应的序列集作为候选集;再在候选集中查找与查询序列最相似的序列.在真实生物序列数据集上的实验表明使用新的生物序列数据索引BioIndex的序列查询算法提高了序列查询的效率. 相似文献
20.
一种支持DTW距离的多元时间序列索引结构 总被引:2,自引:0,他引:2
现有的索引结构难以有效地支持DTW距离度量下的多元时间序列相似性搜索.首先给出一种将不等长多元时间序列转换为等长一元时间序列的方法,并证明这种转换满足下界距离引理;以此为基础,提出一种多元时间序列的DTW下界距离,并对其性质进行分析;然后,针对给出的下界距离,提出一种支持DTW距离度量的多元时间序列索引结构,对多元时间序列数据库进行有效组织;再给出多元时间序列相似模式搜索算法及流程,并证明该搜索方法具有非漏报性;最后,通过实验对所提方法的有效性进行验证. 相似文献