交换:top-k相似性在集合流中加入
Willi Mann1, Nikolaus Augsten2, Christian S Jensen3
1Celonis SE, Munich, Germany.
概括
我们介绍SWOOP,一个可扩展的流连接算法,用于在实时数据流中找到类似的集合. SWOOP通过保持最小的相似对集来有效地更新top-k结果,优于现有方法.
科学领域:
- 计算机科学 计算机科学
- 数据挖掘 数据挖掘
- 数据库系统 数据库系统
背景情况:
- 实时数据流产生了大量的数据,需要有效的方法来分析集合相似性.
- 像社交媒体分析这样的应用程序需要不断识别类似的集合 (例如,推特词组).
- 移动窗口模型对于处理动态流数据至关重要,但管理top-k类似对存在挑战.
研究的目的:
- 开发一种高效且可扩展的算法,用于在快速数据流中发现类似的集合对.
- 为了解决top-k结果的动态性质,当数据进入和离开滑动窗口时.
- 在支持的数据速率方面,改进现有的流连接算法.
主要方法:
- 提出了SWOOP (流窗口对比优化),一种新的流连接算法.
- 使用先进的索引技术和复杂的过器来修剪不相关的对.
- 实施了一种增量方法,以保持相似对的可证明最小库存.
- 采用滑动窗口模型来管理动态数据流.
主要成果:
- SWOOP显示了高可扩展性,支持比现有方法快得多的流速.
- 算法有效地修剪过时的对,减少计算开销.
- SWOOP逐步保持必要的相似对,以确保准确的top-k结果更新.
- 经验研究证实了SWOOP的卓越性能.
结论:
- SWOOP为数据流中的实时类似集合对发现提供了一种高效且可扩展的解决方案.
- 该算法的新技术有效地处理了滑动窗口模型所需的动态更新.
- SWOOP显著提升了相似性分析的流连接处理的最新技术.
更多相关视频
07:35Selecting Multiple Biomarker Subsets with Similarly Effective Binary Classification Performances
Published on: October 11, 2018
7.4K
07:59Author Spotlight: Alignment of Synchronized Time-Series Data Using the Characterizing Loss of Cell Cycle Synchrony Model for Cross-Experiment Comparisons
Published on: June 9, 2023
1.3K
相关概念视频
Multiple Comparison Tests
3.8K
Multiple comparison test, abbreviated as MCT, is a post hoc analysis generally performed after comparing multiple samples with one or more tests. An MCT will help identify a significantly different sample among multiple samples or a factor among multiple factors.
It would be easy to compare two samples using a significance alpha level of 0.05. In other words, there is only one sample pair to be compared. However, it would be difficult to identify a significantly different sample if the number...
It would be easy to compare two samples using a significance alpha level of 0.05. In other words, there is only one sample pair to be compared. However, it would be difficult to identify a significantly different sample if the number...
3.8K
Kendall's Tau Test
516
Kendall's tau test, also known as the Kendall rank coefficient test, is a nonparametric method for assessing association between two variables. This test is particularly useful for identifying significant correlations when the distributions of the sample and population are unknown. Developed in 1938 by the British statistician Sir Maurice George Kendall, the tau coefficient (denoted as τ) serves as a rank correlation coefficient, with values ranging from -1 to +1.
A τ value...
A τ value...
516
Wilcoxon Signed-Ranks Test for Matched Pairs
57
The Wilcoxon signed-rank test for matched pairs evaluates the null hypothesis by combining the ranks of differences with their signs. It essentially tests whether the median of the differences in a population of matched pairs is zero. Since the test incorporates more information than the sign test, it generally yields more trustable conclusions. This test also does not require the data to follow a normal distribution, but two conditions must be met for it to be applicable: (1) the data must...
57
Cluster Sampling Method
11.5K
Appropriate sampling methods ensure that samples are drawn without bias and accurately represent the population. Because measuring the entire population in a study is not practical, researchers use samples to represent the population of interest.
To choose a cluster sample, divide the population into clusters (groups) and then randomly select some of the clusters. All the members from these clusters are in the cluster sample. For example, if you randomly sample four departments from your...
To choose a cluster sample, divide the population into clusters (groups) and then randomly select some of the clusters. All the members from these clusters are in the cluster sample. For example, if you randomly sample four departments from your...
11.5K
Sign Test for Matched Pairs
60
The sign test for matched pairs offers a robust method for comparing two paired samples, often for the effects of an intervention in one of them. This method is very useful in situations where the underlying distribution of the data is unknown. The test compares two related samples—often pre- and post-treatment measurements on the same subjects—to determine if there are significant differences in their median values.
To conduct the sign test, we first calculate the differences in...
To conduct the sign test, we first calculate the differences in...
60
Sampling Theorem
244
In signal processing, the analysis of continuous-time signals, denoted as x(t), often involves sampling techniques to convert these signals into discrete-time signals. This process is essential for digital representation and manipulation. A critical component in sampling is the train of impulses, characterized by the sampling interval and the sampling frequency. The relationship between these parameters and the original signal's properties dictates the success of the sampling process.
244
