Publications
Authors:
  • Elisa Bertino , Barbara Catania , Boris Chidlovskii
Citation:
LNCS 1377, Proc. of the EDBT Conference, March, 1998, Valencia, Spain
Abstract:
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.
Year:
1998
Report number:
1998/204
Attachments: