Top-k Range Search on Weighted Interval Data
Daichi Amagata, Jimin Lee Β· 2025
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 paper addresses the problem of top-π range search on weighted interval data, which retrieves π 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 two data structures and their associated algorithms.Our first proposed algorithm is practically fast but requires π (π log π) time, where π is the number of intervals, whereas the other requires less than π (π log π) time.We conduct extensive experiments on real-world datasets, and the results show that our algorithms outperform baseline techniques in most cases.