Elisa Bertino, Barbara Catania, Boris Chidlovskii
LNCS 1377, Proc. of the EDBT Conference, March, 1998, Valencia, Spain
Research on efficient data structures for manipulating objects stored in secondary storage has recently
received increasing attention. Several techniques have been proposed for point databases, containing N points
on the plane. Much less work has been reported for } Segment databases store N non-crossing but possibly
touching segments in secondary storage. Efficient data structures have been defined to determine all segments
intersecting a vertical line (stabbing queries). In this paper, we consider a more general type of query for
segment databases, determining intersections with respect to a generalized segment (a line, a ray, a segment)
with a fixed angular coefficient. We propose two solutions to solve this problem. The first solution has optimal
O(N/B) space complexity, where N is the database size and B is the page size, but the query time is far from
optimal. The second solution requires O(N/B log_2(B)) space, the query time is
O(log_B N/B(log_B N/B +log_2 B+ IL^*(B)) + T/B) time, which is very close to the optimal, and insertion
amortized time is O(log_B N/B + log_2 B + T) T is the output size of the query, and IL^*(B) is a small constant,
representing the number of times we must repeatedly apply the log^* function to B before the result becomes
no greater than 2.
Report number: