General Methods for Adding Range Restrictions to Decomposable Searching Problems

摘要

The authors consider the problem of adding range restrictions to decomposable searching problems. Two classes of structures for the problem are described. The first class consists of structures that use little storage and preprocessing time but still have reasonable query time. The second class consists of structures that have a much better query time at the cost of an increase in the amount of storage required and preprocessing time. Both classes of structures can be tuned to obtain different trade-offs. First the authors describe only static structures. To dynamize the structures a new type of weight-balanced multiway tree (the MWB-tree) is introduced that is used as an underlying structure. The MWB-tree might be useful in other applications as well.