Selection by rank inK-dimensional binary search trees

DOI10.1002/rsa.20476zbMath1304.68034OpenAlexW2023902609WikidataQ61734781 ScholiaQ61734781MaRDI QIDQ2877767

Conrado Martínez, Amalia Duch, Rosa M. Jiménez

Publication date: 25 August 2014

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20476

zbMATH Keywords

selectionprobabilistic analysis of algorithms\(K\)-dimensional search treesmultidimensional data structurespartial match

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Related Items (2)

On the cost of fixed partial match queries in \(K\)-d trees ⋮ On the expected cost of partial match queries in random quad-\(K\)-d trees

Uses Software

• Find

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient worst-case data structures for range searching
• Quad trees: A data structure for retrieval by composite keys
• Time bounds for selection
• A general limit theorem for recursive algorithms and combinatorial structures
• The contraction method for recursive algorithms
• Partial match queries in relaxed multidimensional search trees
• On the analysis of stochastic divide and conquer algorithms
• Foundations of multidimensional and metric data structures.
• Squarish k-d Trees
• Partial match queries in two-dimensional quadtrees: a probabilistic approach
• Randomized binary search trees
• Multidimensional binary search trees used for associative searching
• On the average performance of orthogonal range search in multidimensional data structures
• Probability metrics and recursive algorithms
• Partial Match Queries in Random k-d Trees
• Analysis of range search for random \(k-d\) trees

This page was built for publication: Selection by rank inK-dimensional binary search trees