A Survey of Algorithms and Data Structures for Range Searching

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 a common terminology. (Submitted to ACM Transactions on Database Systems) -Work partially supported by Department of Energy