Priority Range Trees

DOI10.1007/978-3-642-17517-6_11MaRDI QIDQ3060725zbMATH OpenOpenAlexFDO

Authors Darren Strash, Michael T. Goodrich

Publication date 9 December 2010

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1009.3527

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: We describe a data structure, called a priority range tree, which accommodates fast orthogonal range reporting queries on prioritized points. Let $S$ be a set of $n$ points in the plane, where each point $p$ in $S$ is assigned a weight $w(p)$ that is polynomial in $n$, and define the rank of $p$ to be $r(p)=lfloorlogw(p)floor$. Then the priority range tree can be used to report all points in a three- or four-sided query range $R$ with rank at least $lfloorlogwfloor$ in time $O(logW/w+k)$, and report $k$ highest-rank points in $R$ in time $O(loglogn+logW/w^{\prime }+k)$, where $W=su{m}_{pinS}w(p)$, $w^{\prime }$ is the smallest weight of any point reported, and $k$ is the output size. All times assume the standard RAM model of computation. If the query range of interest is three sided, then the priority range tree occupies $O(n)$ space, otherwise $O(nlogn)$ space is used to answer four-sided queries. These queries are motivated by the Weber--Fechner Law, which states that humans perceive and interpret data on a logarithmic scale.

Recommendations

• Priority Search Trees
• Priority queue sorting and labeled trees
• The priority R-tree: a practically efficient and worst-case optimal R-tree
• Rank-Balanced Trees
• Rank-Balanced Trees
• Priority queues
• Rank-Sensitive Priority Queues
• Optimal node ranking of trees
• Range-restricted mergeable priority queues
• Biased range trees

Cited in

(2)

• An in-place min-max priority search tree
• scientific article; zbMATH DE number 7051217 (Why is no real title available?)

This page was built for publication: Priority Range Trees

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