Data Structures for Range Searching

10.1145/361002.361007

BENTLEY , J. L. , AND STANAT , D F . " Analysis of range searches m quad trees ," Inf Process Lett 3 , 6 ( July 1975 ), 170-173 BENTLEY, J. L., AND STANAT, D F. "Analysis of range searches m quad trees," Inf Process Lett 3, 6 (July 1975), 170-173

BENTLEY , J L , AND BURKHARD , W A . " HeurLstms for partial match retrieval data base design ," Inf Process. Lett 4 , 5 ( Feb 1976 ), 132-135.1 BENTLEY, J L, AND BURKHARD, W A. "HeurLstms for partial match retrieval data base design," Inf Process. Lett 4, 5 (Feb 1976), 132-135.1

BENTLEY , J L ., STANAT , D. F. , AND WIL - L IAMS , E. H JR " The complexity of fixed-radius near neighbor searching ," Inf Process. Lett. 6 , 6 ( Dec. 1977 ), 209-212. BENTLEY, J L., STANAT, D. F., AND WIL- LIAMS, E. H JR "The complexity of fixed-radius near neighbor searching," Inf Process. Lett. 6, 6 (Dec. 1977), 209-212.

BENTLEY , J L ., AND FRIEDMAN , J H . A survey of algortthms and data structures for range searching, Carnegie-Mellon Computer Science Rep CMU-CS-78-136 and Stanford hnear Accelerator Center Rep SLAC-PUB-2189, prehmlnary version in Proc. Computer Science and Statistics: 1 lth Ann . Symp. on the Interface , March 1978 , pp. 297 - 307 . BENTLEY, J L., AND FRIEDMAN, J H. A survey of algortthms and data structures for range searching, Carnegie-Mellon Computer Science Rep CMU-CS-78-136 and Stanford hnear Accelerator Center Rep SLAC-PUB-2189, prehmlnary version in Proc. Computer Science and Statistics: 1 lth Ann. Symp. on the Interface, March 1978, pp. 297-307.

BENTLEY , J.L. " Decomposable searching problems ," Inf. Process. Lett. 8 , 5 ( June 1979 ), 133--136. BENTLEY, J.L. "Decomposable searching problems," Inf. Process. Lett. 8, 5 (June 1979), 133--136.

BENTLEY , J. L. " Multidimensional binary search trees in database applications ," IEEE Trans Soflw. Eng SE-5 , 4 ( July 1979 ), 333 - 340 . BENTLEY, J. L. "Multidimensional binary search trees in database applications," IEEE Trans Soflw. Eng SE-5, 4 (July 1979), 333-340.

BENTLEY J. L "Multidimensional divide-and-conquer " to appear m Comm. ACM. 10.1145/358841.358850 BENTLEY J. L "Multidimensional divide-and-conquer " to appear m Comm. ACM. 10.1145/358841.358850

BENTLEY J. L AND MAURER H. A. "Efficient worst-case data structures for range searching " to appear m Acta Inf. BENTLEY J. L AND MAURER H. A. "Efficient worst-case data structures for range searching " to appear m Acta Inf.

DOBKIN , D , AND LIPTON , R. J " Multdimensional searching problems ," SIAM J. Comput. 5 , 2 ( 1976 ), 181-186. DOBKIN, D, AND LIPTON, R. J "Multdimensional searching problems," SIAM J. Comput. 5, 2 (1976), 181-186.

FINKEL , R. A , AND BENTLEY , J. L. " Quad trees--a data structure for retrieval on composite keys ," Acta Inf 4 , 1 ( 1974 ), 1-9. FINKEL, R. A, AND BENTLEY, J. L. "Quad trees--a data structure for retrieval on composite keys," Acta Inf 4, 1 (1974), 1-9.

FREDMAN , M. "A near optimal data structure for a type of range query problem," in Proc. 11 th A CM Syrup . Theory of Computing , May 1979 , pp. 62 - 66 . 10.1145/800135.804398 FREDMAN, M. "A near optimal data structure for a type of range query problem," in Proc. 11 th A CM Syrup. Theory of Computing, May 1979, pp. 62-66. 10.1145/800135.804398

FRIEDMAN , J H ., BASKETT , F. , AND SHUS - TEK , L. J " An algorithm for finding nearest neighbors ," IEEE Trans Cornput. C-24 , 10 ( Oct. 1975 ), 1000 - 1006 . FRIEDMAN, J H., BASKETT, F., AND SHUS- TEK, L. J "An algorithm for finding nearest neighbors," IEEE Trans Cornput. C-24, 10 (Oct. 1975), 1000-1006.

10.1145/355744.355745

GOTLIEB , C. C. , AND GOTLIEB , L. R Data types and structures , Prentice-Hall , Englewood Cliffs , N.J, pp. 357 - 363 GOTLIEB, C. C., AND GOTLIEB, L. R Data types and structures, Prentice-Hall, Englewood Cliffs, N.J, pp. 357-363

KNUTH , D.E. The art of computer programming, vol. 3" sorting and searching, Addison-Wesley, Reading , Mass. , 1973 . KNUTH, D.E. The art of computer programming, vol. 3" sorting and searching, Addison-Wesley, Reading, Mass., 1973.

LAUTHER , U. " 4-dimensional binary search trees as a means to speed up associative searches in design rule verification of integrated circuits ," J Des. Autom Fault-Tolerant Comput. 2 , 3 ( July 1978 ), 241-247. LAUTHER, U. "4-dimensional binary search trees as a means to speed up associative searches in design rule verification of integrated circuits," J Des. Autom Fault-Tolerant Comput. 2, 3 (July 1978), 241-247.

LEE , R. C. T., CHIN , Y. H , AND CHANG , S.C. " Application of principal component analysm to multi-key searching ," IEEE Trans. Soflw. Eng. SE-2 , 3 ( Sept 1976 ), 185 - 193 . LEE, R. C. T., CHIN, Y. H, AND CHANG, S.C. "Application of principal component analysm to multi-key searching," IEEE Trans. Soflw. Eng. SE-2, 3 (Sept 1976), 185-193.

LEE , D. T , AND WONG , C K . " Worstcase analysis for region and partml region searches In multidlmensmnal binary search trees and quad trees ," A cta Inf 9 , 1 ( 1978 ), 23-29. LEE, D. T, AND WONG, C K. "Worstcase analysis for region and partml region searches In multidlmensmnal binary search trees and quad trees," A cta Inf 9, 1 (1978), 23-29.

LEE D. T. AND WONG C.K. "Qulntary trees' a i'de structure for multidimensmnal database systems " to appear m A CM Trans. Database Syst 10.1145/320613.320618 LEE D. T. AND WONG C.K. "Qulntary trees' a i'de structure for multidimensmnal database systems " to appear m A CM Trans. Database Syst 10.1145/320613.320618

LEVINTHAL , C. " Molecular model-budding by computer ," Sct Am 214 ( June 1966 ), ~ 2 - 52 . LEVINTHAL, C. "Molecular model-budding by computer," Sct Am 214 (June 1966), ~2-52.

Lmu, J H., AND YAO , S B " Multi-dimensional clustering for data base organization ," Inf Syst. 2 ( 1977 ), 187 -{98. Lmu, J H., AND YAO, S B "Multi-dimensional clustering for data base organization," Inf Syst. 2 (1977), 187-{98.

LOFTSGAARDEN , D. O , AND QUESEN - B ERRY , C. P. " A nonparametric density function ," Ann. Math. Star. 36 ( 1965 ), 1049 - 1051 LOFTSGAARDEN, D. O, AND QUESEN- BERRY, C.P. "A nonparametric density function," Ann. Math. Star. 36 (1965), 1049-1051

LUEKER , G. "A data structure for orthogonal range queries," m Proc 19th Syrup Foundattons of Computer Scwnce , IEEE , Oct. 1978 , pp. 28 - 34 LUEKER, G. "A data structure for orthogonal range queries," m Proc 19th Syrup Foundattons of Computer Scwnce, IEEE, Oct. 1978, pp. 28-34

LUEKER , G. "A transformation for addmg range restractlon capability to dynamtc data structures for decomposable searchmg problems," Tech. Rep. 129 , U of Califorma at irvine , 1979 . LUEKER, G. "A transformation for addmg range restractlon capability to dynamtc data structures for decomposable searchmg problems," Tech. Rep. 129, U of Califorma at irvine, 1979.

RABIN , M O "Probabdmtm algorithms," m Agortthms and complexity. new dwectlons and recent results , J. F Traub (Ed.), Academm Press , New York , 1976 , pp. 21 - 39 . RABIN, M O "Probabdmtm algorithms," m Agortthms and complexity. new dwectlons and recent results, J. F Traub (Ed.), Academm Press, New York, 1976, pp. 21-39.

RIVEST , R L . " Parhal match retrieval algorithms ," SIAM J Comput. 5 , 1 ( March 1976 ), 19-50 RIVEST, R L. "Parhal match retrieval algorithms," SIAM J Comput. 5, 1 (March 1976), 19-50

SAXE J. B "On the number of range queries m k-space " to appear m Dtscrete Appl Math SAXE J. B "On the number of range queries m k-space " to appear m Dtscrete Appl Math

SHNEIDERMAN , B. " Reduced combined indexes for efficient multiple attribute retrieval ," Inf. Syst. 2 ( 1977 ), 149 - 154 . SHNEIDERMAN, B. "Reduced combined indexes for efficient multiple attribute retrieval," Inf. Syst. 2 (1977), 149-154.

SILVA-FILHO , Y.V. Average case analysts of regton search m balanced k-d trees, Rep ., U. of Kent , Canterbury, England , Nov. 1978 . SILVA-FILHO, Y.V. Average case analysts of regton search m balanced k-d trees, Rep., U. of Kent, Canterbury, England, Nov. 1978.

S/ LVA-FILHO , Y V . Multtdimenstonal search trees as radices of fdes, Rep ., U of Kent , Canterbury, England , Dec 1978 . S/LVA-FILHO, Y V. Multtdimenstonal search trees as radices of fdes, Rep., U of Kent, Canterbury, England, Dec 1978.

WILLARO , D. E. Predicate-oriented database search algorithms, Rep. TR-20- 78 , Harvard U. Aiken Lab. , 1978 . WILLARO, D. E. Predicate-oriented database search algorithms, Rep. TR-20- 78, Harvard U. Aiken Lab., 1978.

WILLAR t), D. E. "Balanced forests of k-d* trees as a dynamic data structure," mformative abstract , Harvard U. , Boston, Mass , 1978 . WILLARt), D. E. "Balanced forests of k-d* trees as a dynamic data structure," mformative abstract, Harvard U., Boston, Mass, 1978.

YANG , C. "Avoiding redundant record accesses in unsorted multilist t'de orgamzations," inf Syst. 2 ( 1977 ), 155-158 . YANG, C. "Avoiding redundant record accesses in unsorted multilist t'de orgamzations," inf Syst. 2 (1977), 155-158.

YANG , C. " A class of hybrid list file orgamzations ," Inf. Syst. 3 ( 1978 ), 49 - 58 . YANG, C. "A class of hybrid list file orgamzations," Inf. Syst. 3 (1978), 49-58.

YUVAL , G. " Finding near neighbors m k-dimensional space ," Inf. Process. Lett. 3 , 4 ( March 1975 ), 113-114 YUVAL, G. "Finding near neighbors m k-dimensional space," Inf. Process. Lett. 3, 4 (March 1975), 113-114