共查询到18条相似文献,搜索用时 78 毫秒
1.
2.
研究基于时间序列相似搜索技术的煤矿瓦斯涌出分析新途径,提出基于PPR的煤矿瓦斯监测数据相似搜索方法。实验采用玉华煤矿的真实煤矿瓦斯监测数据,评价指标为信息损失量及相似查询效率。与基于离散傅立叶变换(DFT)和离散小波变换(DWT)的时间序列相似搜索算法的对比实验显示:在相同压缩比下,3种方法的信息损失相近;但是基于PPR的相似搜索算法的平均查询效率分别比基于DFT和基于DWT方法高32%和34%。因此PPR算法适合用于瓦斯监测数据相似搜索。 相似文献
3.
大规模时间序列数据库降维及相似搜索 总被引:4,自引:0,他引:4
提出一种基于分段多项式表示(PPR)的时间序列数据库相似查询的系统化方法.PPR是一类基于线性多项式回归的正交变换.用PPR变换索引时间序列数据在理论上具备非漏报性质.文中分析了PPR的计算复杂性以及查询阈值的下界,并提出了一种衡量时间序列相似查询算法之查询效率的定量指标.与基于离散傅立叶变换(DFT)和离散小波变换(DWT)的时间序列相似查询算法所作的对比实验表明,所提算法可以用低的索引结构维数获得高的查询效率. 相似文献
4.
5.
不确定时间序列的每个时间点上对应一个可能取值的集合,无法给出其确定值,这种不确定性给时间序列降维处理和相似性匹配带来巨大挑战,现有的时间序列降维方法和相似性匹配算法已经无法适用。针对此问题,提出了描述统计模型,将不确定时间序列归约为3条确定时间序列,通过离散傅里叶变换(discrete Fou-rier transform,DFT)、离散余弦变换(discrete cosine transform,DCT)、离散小波变换(discrete wavelet trans-form,DWT)对模型下不确定时间序列降维;根据模型特点,提出了以观察值区间和区间集中趋势为核心的相似性匹配算法。经过实验验证,描述统计模型下DCT和DWT有良好的降维效果,提出的相似匹配算法与现有算法相比提高了匹配准确率。 相似文献
6.
7.
8.
9.
10.
基于回归系数的时间序列维约简与相似性查找 总被引:1,自引:0,他引:1
在时间序列中进行相似性查找往往需要进行维约简.以往的维约简方法或者时间复杂度太大并且不直观(如DWT、DFT等),或者无法用于准确的相似性查找(如PAA方法).本文提出一种新的基于回归系数的时间序列维约简方法--逐段回归近似(PRA).该方法具有线性时间复杂度,并且对均值平稳的独立噪声干扰不敏感,同时证明了基于PRA方法的相似性查找满足下界定理,因而是实用有效的.对实际数据的实验结果验证了本文的结论. 相似文献
11.
Similarity search usually encounters a serious problem in the high-dimensional space, known as the “curse of dimensionality.” In order to speed up the retrieval efficiency, most previous approaches reduce the dimensionality of the entire data set to a fixed lower value before building indexes (referred to as global dimensionality reduction (GDR)). More recent works focus on locally reducing the dimensionality of data to different values (called the local dimensionality reduction (LDR)). In addition, random projection is proposed as an approximate dimensionality reduction (ADR) technique to answer the approximate similarity search instead of the exact one. However, so far little work has formally evaluated the effectiveness and efficiency of GDR, LDR, and ADR for the range query. Motivated by this, in this paper, we propose general cost models for evaluating the query performance over the reduced data sets by GDR, LDR, and ADR, in light of which we introduce a novel (A)LDR method, Partitioning based on RANdomized Search (PRANS). It can achieve high retrieval efficiency with the guarantee of optimality given by the formal models. Finally, a {rm B}^{+}-tree index is constructed over the reduced partitions for fast similarity search. Extensive experiments validate the correctness of our cost models on both real and synthetic data sets and demonstrate the efficiency and effectiveness of the proposed PRANS method. 相似文献
12.
在大数据时代背景下,越来越多的用户或者企业将大量的数据上传至云端存储以便减轻本地存储的压力和获得高效的数据共享服务管理,由此可搜索加密技术应运而生,检索效率与保证数据安全一直是研究的热点。因此,本文提出一种基于特征匹配的快速降维排序搜索方法(DRFM)。通过提出的特征得分算法,创建每一篇文档的索引特征向量;通过提出的匹配得分算法,创建查询关键词的查询匹配向量。使用K-L变换算法对所有文档索引特征向量以及查询匹配向量进行降维,提高算法效率。理论分析与实验结果表明所提的方案高效且可行。 相似文献
13.
Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases 总被引:36,自引:3,他引:33
Eamonn Keogh Kaushik Chakrabarti Michael Pazzani Sharad Mehrotra 《Knowledge and Information Systems》2001,3(3):263-286
The problem of similarity search in large time series databases has attracted much attention recently. It is a non-trivial
problem because of the inherent high dimensionality of the data. The most promising solutions involve first performing dimensionality
reduction on the data, and then indexing the reduced data with a spatial access method. Three major dimensionality reduction
techniques have been proposed: Singular Value Decomposition (SVD), the Discrete Fourier transform (DFT), and more recently
the Discrete Wavelet Transform (DWT). In this work we introduce a new dimensionality reduction technique which we call Piecewise
Aggregate Approximation (PAA). We theoretically and empirically compare it to the other techniques and demonstrate its superiority.
In addition to being competitive with or faster than the other methods, our approach has numerous other advantages. It is
simple to understand and to implement, it allows more flexible distance measures, including weighted Euclidean queries, and
the index can be built in linear time.
Received 16 May 2000 / Revised 18 December 2000 / Accepted in revised form 2 January 2001 相似文献
14.
随着基因测序技术和人类基因组计划的发展,从大量的生物数据中寻找相似的序列就越来越成为当前研究的热点问题.本文提出了一种聚类的多解析度字符串索引结构,用于解决生物序列的相似性查询问题.首先,以较小容量的MBR(最小绑定矩形)构造基因序列的多解析度字符串索引结构,然后通过对MBR的聚类以夏保序技术的应用,减小索引中MBR的平均体积,从而增加了查询向量到索引的空间距离,提高了索引的过滤能力.还给出了一种新的后处理方法,通过大量的减少编辑距离的计算,提高索引的性能.文中给出了该索引结构并详细介绍了索引的相关算法.实验表明,该索引结构是一种有效的处理生物数据的相似性查询的索引结构. 相似文献
15.
为了解决高维数据相似性连接查询中存在的维度灾难和计算代价高等问题,基于p-稳态分布,将高维数据映射到低维空间。根据卡方分布的性质,证明了如果低维空间的距离大于kε,则原始空间距离大于ε的概率具有一定的下界,从而可以在低维空间以较低的计算代价进行有效过滤。在此基础上,提出了基于卡方分布的高维数据相似性连接查询算法。为了进一步提高查询效率,提出了基于双重过滤的高维数据相似性连接查询算法。利用真实数据集进行了实验,实验结果表明所提方法具有较好的性能。基于卡方分布的相似性连接查询算法召回率可以达到90%以上。基于双重过滤的相似性连接查询算法可以进一步提高性能,但是会损失一定的召回率。对时间性能要求比较高、对召回率要求不太严格的查询任务可以采用基于双重过滤的相似性连接查询算法;反之,可以采用基于卡方分布的相似性连接查询算法。 相似文献
16.
现今的图像搜索引擎主要利用图像周围文本信息为图像排序,根据图像内容重排序可以进一步提高搜索性能。图像相似性的度量对重排序算法的性能至关重要。然而已有的相似性度量没有考虑针对不同的查询,图像的相似性应该不同。提出一种与查询相关的相似性度量方法,将基于全局特征的相似性,基于局部特征的相似性,以及视觉单词同时出现率融合到一个迭代算法中,挖掘出与查询相关的图像信息,计算图像相似性。在Bing图像搜索引擎上的实验结果证明本文提出的相似性度量方法优于基于全局特征,局部特征,或它们线性组合的相似性。 相似文献
17.
Skyline index for time series data 总被引:4,自引:0,他引:4
We have developed a new indexing strategy that helps overcome the curse of dimensionality for time series data. Our proposed approach, called skyline index, adopts new skyline bounding regions (SBR) to approximate and represent a group of time series data according to their collective shape. Skyline bounding regions allow us to define a distance function that tightly lower bounds the distance between a query and a group of time series data. In an extensive performance study, we investigate the impact of different distance functions by various dimensionality reduction and indexing techniques on the performance of similarity search, including index pages accessed, data objects fetched, and overall query processing time. In addition, we show that, for k-nearest neighbor queries, the proposed skyline index approach can be coupled with the state of the art dimensionality reduction techniques such as adaptive piecewise constant approximation (APCA) and improve its performance by up to a factor of 3. 相似文献
18.
针对HBase无法直接建立时空索引所带来的交通数据查询性能问题,基于HBase行键设计了面向海量交通数据的HBase时空索引。首先利用Geohash降维方法将二维空间位置数据转化为一维编码,再与时间维度进行组合;然后根据组合顺序的不同,提出了四种结构模型,分别讨论了模型的具体构成以及交通数据查询中的适应面;最后提出了相应的时空索引管理算法及基于Hbase时空索引的交通数据查询方法。通过实验验证了提出的HBase时空索引结构能有效提升海量交通数据的区域查询性能,并比较了四种时空索引结构在不同数据规模、不同查询半径以及不同时间范围的查询性能,量化验证了不同索引结构在交通数据查询中的适应场景。 相似文献