View Related Documents

Abstract

Segment databases store N non-crossing but possibly touching segments in secondary storage. Efficient data structures have been proposed 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 log2 B) space, the query time is O(logB N/B(logB N/B+log2 B+IL * (B))+T/B), which is very close to the optimal, and insertion amortized time is O(logB N/B+log2 B+1/Blog2 B N/B), where T is the size of the query result, 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 ≤ 2.

Fulltext Preview

Image of the first page of the fulltext document