Two Papers on Range Searching: A Survey of Algorithms and Data Structures for Range Searching. Efficient Worst-Case Data Structures for Range Searching.

摘要

This report contains two independent papers on range searching. A range search retrieves from a file all records which conjunctively satisfy a set of range requirements for the keys; that is, each key must lie in some specified range. Range searching arises in many applications, such as data base management and statistical computing. The first paper in this report, 'A survey of algorithms and data structures for range searching' by J. L. Bentley and J. H. Friedman, describes the known 'logical structures' which can be used for range searching and then discusses the implementation of those structures in different storage media. This paper is slanted towards the practitioner. The second paper, 'Efficient worst-case data structures for range searching' by J. L. Bentley and H. A. Maurer, is more theoretical. Two new classes of data structures are proposed for range searching, establishing bounds on the asymptotic complexity of the problem. (Author)