Biased Range Trees

Biased Range Trees

0.00 Avg rating0 Votes
Article ID: iaor2012381
Volume: 62
Issue: 1
Start Page Number: 21
End Page Number: 37
Publication Date: Feb 2012
Journal: Algorithmica
Authors: , ,
Keywords: sets
Abstract:

A data structure, called a biased range tree, is presented that preprocesses a set S of n points in ℝ2 and a query distribution D for 2‐sided orthogonal range counting queries (a.k.a. dominance counting queries). The expected query time for this data structure, when queries are drawn according to D, matches, to within a constant factor, that of the optimal comparison tree for S and D. The memory and preprocessing requirements of the data structure are O(nlog n).

Reviews

Required fields are marked *. Your email address will not be published.