3 citations · 5 across the 4 of their papers we have counts for
4 papers
Biased Predecessor Search
Prosenjit Bose, Rolf Fagerberg, John Howat +1
We consider the problem of performing predecessor searches in a bounded universe while achieving query times that depend on the distribution of queries. We obtain several data stru…
The Fresh-Finger Property
John Howat, John Iacono, Pat Morin
The unified property roughly states that searching for an element is fast when the current access is close to a recent access. Here, "close" refers to rank distance measured among…
Layered Working-Set Trees
Prosenjit Bose, Karim Douïeb, Vida Dujmović +1
The working-set bound [Sleator and Tarjan, J. ACM, 1985] roughly states that searching for an element is fast if the element was accessed recently. Binary search trees, such as spl…
Biased Range Trees
Vida Dujmovic, John Howat, Pat Morin
A data structure, called a biased range tree, is presented that preprocesses a set S of n points in R^2 and a query distribution D for 2-sided orthogonal range counting queries. Th…