Scholarlink

<p>Weighted intervals are ubiquitous, because many objects are associated with temporal and numeric dimensions. As interval datasets are usually large, efficient management and processing of large weighted interval data are required. This article addresses the problem of top-<i>k</i> range search on weighted interval data, which retrieves <i>k</i> intervals with the largest weight among a set of intervals overlapping a given query interval. It finds important analytical applications for vehicles, events, and cryptocurrencies. Existing algorithms for range search on interval data are inefficient for this problem, because they need to search for all intervals that overlap a given query interval. To overcome this inefficiency issue, we first provide a baseline algorithm and then propose three data structures, along with their associated algorithms. Our first proposed algorithm is practically fast but requires <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\varvec{O(n\log k)}\)</EquationSource> </InlineEquation> time, where <i>n</i> is the number of intervals, whereas the others require less than <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\varvec{O(n\log k)}\)</EquationSource> </InlineEquation> time. Furthermore, we address a duration-constrained variant of the top-<i>k</i> range search problem. To solve this variant efficiently, we extend our algorithms and present how to maintain a time complexity of less than <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\varvec{O(n\log k)}\)</EquationSource> </InlineEquation>. We conduct extensive experiments on real-world datasets, and the results show that our algorithms outperform baseline techniques in most cases.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Efficient algorithms for top-k range search on weighted interval data

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年5月9日

查看全文
  • Jimin Lee,
  • Daichi Amagata

摘要

Weighted intervals are ubiquitous, because many objects are associated with temporal and numeric dimensions. As interval datasets are usually large, efficient management and processing of large weighted interval data are required. This article addresses the problem of top-k range search on weighted interval data, which retrieves k intervals with the largest weight among a set of intervals overlapping a given query interval. It finds important analytical applications for vehicles, events, and cryptocurrencies. Existing algorithms for range search on interval data are inefficient for this problem, because they need to search for all intervals that overlap a given query interval. To overcome this inefficiency issue, we first provide a baseline algorithm and then propose three data structures, along with their associated algorithms. Our first proposed algorithm is practically fast but requires \(\varvec{O(n\log k)}\) time, where n is the number of intervals, whereas the others require less than \(\varvec{O(n\log k)}\) time. Furthermore, we address a duration-constrained variant of the top-k range search problem. To solve this variant efficiently, we extend our algorithms and present how to maintain a time complexity of less than \(\varvec{O(n\log k)}\) . We conduct extensive experiments on real-world datasets, and the results show that our algorithms outperform baseline techniques in most cases.