Partial match queries in random k-d trees

被引：8
作者：
Chern, HH
Hwang, HK
机构：
[1] Natl Taiwan Ocean Univ, Dept Comp Sci, Chilung 20224, Taiwan
[2] Acad Sinica, Inst Stat Sci, Taipei 115, Taiwan
来源：
SIAM JOURNAL ON COMPUTING | 2006年 / 35卷 / 06期
关键词：
k-d trees; partial match queries; differential equations; average-case analysis of algorithms; method of linear operators; asymptotic analysis;
D O I：
10.1137/S0097539703437491
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We solve the open problem of characterizing the leading constant in the asymptotic approximation to the expected cost used for random partial match queries in random k-d trees. Our approach is new and of some generality; in particular, it is applicable to many problems involving differential equations ( or difference equations) with polynomial coefficients.
引用
收藏
页码：1440 / 1466
页数：27
相关论文
共 38 条
  • [1] Abramowitz M., 1972, HDB MATH FUNCTIONS F
  • [2] [Anonymous], QUICKSORT
  • [3] MULTIDIMENSIONAL BINARY SEARCH TREES USED FOR ASSOCIATIVE SEARCHING
    BENTLEY, JL
    [J]. COMMUNICATIONS OF THE ACM, 1975, 18 (09) : 509 - 517
  • [4] BENTLEY JL, 1990, PROCEEDINGS OF THE SIXTH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY, P187, DOI 10.1145/98524.98564
  • [5] BENTLEY JL, 1979, ACM COMPUT SURV, V11, P397
  • [6] BERTINO E, 1997, INDEXING TECHNIQUES
  • [7] Analysis of range search for random k-d trees
    Chanzy, P
    Devroye, L
    Zamora-Cura, C
    [J]. ACTA INFORMATICA, 2001, 37 (4-5) : 355 - 383
  • [8] Partial match queries in random quadtrees
    Chern, HH
    Hwang, HK
    [J]. SIAM JOURNAL ON COMPUTING, 2003, 32 (04) : 904 - 915
  • [9] An asymptotic theory for Cauchy-Euler differential equations with applications to the analysis of algorithms
    Chern, HH
    Hwang, HK
    Tsai, TH
    [J]. JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2002, 44 (01): : 177 - 225
  • [10] Phase changes in random m-ary search trees and generalized quicksort
    Chern, HH
    Hwang, HK
    [J]. RANDOM STRUCTURES & ALGORITHMS, 2001, 19 (3-4) : 316 - 358
1234