Selection by rank in K-dimensional binary search trees

DOI10.1002/RSA.20476MaRDI QIDQ2877767zbMATH OpenOpenAlexWikidataFDO

Authors Amalia Duch, Rosa M. Jiménez, Conrado Martí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

\(K\)-dimensional search treesmultidimensional data structurespartial matchprobabilistic analysis of algorithmsselection

Mathematics Subject Classification ID

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

Recommendations

• Rank selection in multidimensional data
• Analysis of range search for random \(k-d\) trees
• Random partial match in quad-K-d trees
• On the average performance of fixed partial match queries in random relaxed K-d trees
• Partial Match Queries in Random k-d Trees

Cites work

• A general limit theorem for recursive algorithms and combinatorial structures
• Adaptive sampling strategies for quickselects
• Analysis of range search for random \(k-d\) trees
• Efficient worst-case data structures for range searching
• Foundations of multidimensional and metric data structures.
• scientific article; zbMATH DE number 5688292 (Why is no real title available?)
• Multidimensional binary search trees used for associative searching
• On the analysis of stochastic divide and conquer algorithms
• On the average performance of orthogonal range search in multidimensional data structures
• Partial Match Queries in Random k-d Trees
• Partial match queries in relaxed multidimensional search trees
• Partial match queries in two-dimensional quadtrees: a probabilistic approach
• Probability metrics and recursive algorithms
• Quad trees: A data structure for retrieval by composite keys
• Randomized binary search trees
• Squarish \(k\)-\(d\) trees
• The contraction method for recursive algorithms
• Time bounds for selection
• Updating relaxed K-d trees

Cited in

(6)

• Efficient selection on a binary tree
• On the cost of fixed partial match queries in K-d trees
• Rank selection in multidimensional data
• Random hyperplane search trees
• Analysis of range search for random \(k-d\) trees
• On the expected cost of partial match queries in random quad-K-d trees

Describes a project that uses

Uses Software

• Find

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2877767)