Partial Match Queries in Random k-d Trees
Authors:
- Hua-Huai ChernHCHua-Huai Chern
- Hsien-Kuei HwangHHHsien-Kuei Hwang
- 1 January 2006
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 35 (6) , 1440-1466
Abstract
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.Keywords
This publication has 20 references indexed in Scilit:
- Partial Match Queries in Random QuadtreesSIAM Journal on Computing, 2003
- An asymptotic theory for Cauchy–Euler differential equations with applications to the analysis of algorithmsJournal of Algorithms, 2002
- On the average performance of orthogonal range search in multidimensional data structuresJournal of Algorithms, 2002
- Phase changes in random m‐ary search trees and generalized quicksortRandom Structures & Algorithms, 2001
- Analysis of range search for random k-d treesActa Informatica, 2001
- Squarish k-d TreesSIAM Journal on Computing, 2000
- Mellin transforms and asymptotics: Harmonic sumsTheoretical Computer Science, 1995
- Analytic variations on quadtreesAlgorithmica, 1993
- Data Structures for Range SearchingACM Computing Surveys, 1979
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975