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

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.