Towards Optimal Indexing for Segment Databases

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