General methods for adding range restrictions to decomposable searching problems (Q1118417): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Decomposable searching problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Efficient worst-case data structures for range searching / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Adding range restriction capability to dynamic data structures / rank | |||
Normal rank |
Latest revision as of 14:49, 19 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | General methods for adding range restrictions to decomposable searching problems |
scientific article |
Statements
General methods for adding range restrictions to decomposable searching problems (English)
0 references
1989
0 references
The problem of adding range restrictions to decomposable searching problems consists in associating a new parameter with every element of the given set of objects. Thus, queries will be restricted to those objects that have this new parameter in a certain given range. Two classes of structures for this problem are presented. The first class contains structures that have low storage cost at an expense of increased query time. The structure of the second class have much better query time but need more storage and preprocessing time. Both classes can be tuned to obtain different structures with different trade-offs for query time, memory cost and preprocessing time. In addition, the authors introduce a new weight-balanced multiway tree and use it to transform the previous static structures into dynamic structures with reasonable insertion and deletion times. Finally, they apply the results to the d-dimensional range searching problem and obtain a whole class of structures containing most of the known results and adding new ones.
0 references
range restrictions
0 references
decomposable searching
0 references
dynamic structures
0 references
range searching
0 references