Two-level indexes have been widely used to handle trajectories of moving objects that are constrained to a network. The top-level of these indexes handles the spatial dimension, whereas the bottom level handles the temporal dimension. The latter turns out to be an instance of the interval-intersection problem, but it has been tackled by non-specialized spatial indexes. In this work, we propose the use of a compact data structure on the bottom level of these indexes. Our experimental evaluation shows that our approach is both faster and smaller than existing solutions.
Like FNR-tree and MON-tree, we focus on these two-level indexes. To solve the spatial problem, that is, the representation of the network in space (two-dimensional plane), aforementioned structures use a 2D R-tree, storing the segments of the network as lines. With the spatial problem solved, time has to be associated with segments in the network. More precisely, it is necessary to look for all the time intervals (times in which some objects pass through a segment) that intersect with a given query interval. This problem is known in the literature as , an extension of the interval stabbing problem @cite_2 . Classical structures to solve this problem are Interval trees and Priority trees @cite_25 .
@cite_25 @cite_2
2149906774 1579902393
This introduction to computational geometry focuses on algorithms. Motivation is provided from the application areas as all techniques are related to particular applications in robotics, graphics, CAD CAM, and geographic information systems. Modern insights in computational geometry are used to provide solutions that are both efficient and easy to understand and implement. Given a set I of n intervals, a stabbing query consists of a point q and asks for all intervals in I that contain q. The Interval Stabbing Problem is to find a data structure that can handle stabbing queries efficiently. We propose a new, simple and optimal approach for different kinds of interval stabbing problems in a static setting where the query points and interval ends are in 1,...,O(n) .