.png){kind=icon}
返回
Efficient algorithms for top-k range search on weighted interval data
.png){kind=icon}
OA
AI
DOI：10.1007/s10707-026-00576-0.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
加权区间无处不在，因为许多对象都与时间和数值维度相关联。由于区间数据集通常规模较大，因此需要高效管理和大容量加权区间数据的处理。本文解决了加权区间数据上的top-k范围搜索问题，该问题检索与给定查询区间重叠的一组区间中权重最大的k个区间。这对车辆、事件和加密货币等重要分析应用具有重要意义。现有针对区间数据的范围搜索算法效率低下，因为它们需要搜索所有与给定查询区间重叠的区间。为克服这一低效问题，我们首先提供一个基线算法，然后提出三种数据结构及其相关算法。我们提出的第一个算法在实际应用中速度快，但需要O(n log k)时间（n为区间数量），而其他算法所需时间小于O(n log k)。此外，我们还针对top-k范围搜索问题提出了一个时长约束变体。为高效解决该变体，我们扩展了算法，并展示了如何将时间复杂度维持在小于O(n log k)。我们在真实数据集上进行了大量实验，结果表明我们的算法在大多数情况下优于基线技术。
Keyword:
Weighted interval
Top-k query
Algorithm
期刊
G
IF:
2.6
论文数:
20
被引数:
813
机构
引用论文
.png){kind=icon}
分享收藏分享收藏
查看更多内容