A Survey of Algorithms and Data Structures for Range Searching
Jon Louis Bentley, USDOE Office of Science (SC), Jerome H. Friedman · 1978
An important problem in database systems is answering queries quickly. This paper surveys a number of algorithms for efficiently answering range queries. First a set of "logical structures" is described and then their implementation in primary and secondary memories is discussed. The algorithms included are of both "practical" and "theoretical" interest. Although some new results are presented, the primary purpose of this paper is to collect together the known results on range searching and to present them in common terminology.