Author name cluster

Patrick K. Nicholson

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

TCS Journal 2018 Journal Article

Encoding nearest larger values

Michael Hoffmann
John Iacono
Patrick K. Nicholson
Rajeev Raman

In nearest larger value (NLV) problems, we are given an array A [ 1. . n ] of distinct numbers, and need to preprocess A to answer queries of the following form: given any index i ∈ [ 1, n ], return a “nearest” index j such that A [ j ] > A [ i ]. We consider the variant where the values in A are distinct, and we wish to return an index j such that A [ j ] > A [ i ] and | j − i | is minimized, the nondirectional NLV (NNLV) problem. We consider NNLV in the encoding model, where the array A is deleted after preprocessing. The NNLV encoding problem turns out to have an unexpectedly rich structure: the effective entropy (optimal space usage) of the problem depends crucially on details in the definition of the problem. Of particular interest is the tiebreaking rule: if there exist two nearest indices j 1, j 2 such that A [ j 1 ] > A [ i ] and A [ j 2 ] > A [ i ] and | j 1 − i | = | j 2 − i |, then which index should be returned? For the tiebreaking rule where the rightmost (i. e. , largest) index is returned, we encode a path-compressed representation of the Cartesian tree that can answer all NNLV queries in 1. 89997 n + o ( n ) bits, and can answer queries in O ( 1 ) time. An alternative approach, based on forbidden patterns, achieves a very similar space bound for two tiebreaking rules (including the one where ties are broken to the right), and (for a more flexible tiebreaking rule) achieves 1. 81211 n + o ( n ) bits. Finally, we develop a fast method of counting distinguishable configurations for NNLV queries. Using this method, we prove a lower bound of 1. 62309 n − Θ ( 1 ) bits of space for NNLV encodings for the tiebreaking rule where the rightmost index is returned.

Details DOI

TCS Journal 2016 Journal Article

Dynamic range majority data structures

Amr Elmasry
Meng He
J. Ian Munro
Patrick K. Nicholson

Given a set P of n coloured points on the real line, we study the problem of answering range α-majority (or “heavy hitter”) queries on P. More specifically, for a query range Q, we want to return each colour that is assigned to more than an α-fraction of the points contained in Q. We present a new data structure for answering range α-majority queries on a dynamic set of points, where α ∈ ( 0, 1 ). Our data structure uses O ( n ) space, supports queries in O ( ( lg ⁡ n ) / α ) time, and updates in O ( ( lg ⁡ n ) / α ) amortized time. If the coordinates of the points are integers, then the query time can be improved to O ( lg ⁡ n / ( α lg ⁡ lg ⁡ n ) ). For constant values of α, this improved query time matches an existing lower bound, for any data structure with polylogarithmic update time. We also generalize our data structure to handle sets of points in d dimensions, for d ≥ 2, as well as dynamic arrays, in which each entry is a colour.

Details DOI

I&C Journal 2013 Journal Article

Range majority in constant time and linear space

Stephane Durocher
Meng He
J. Ian Munro
Patrick K. Nicholson
Matthew Skala

Given an array A of size n, we consider the problem of answering range majority queries: given a query range [ i. . j ] where 1 ⩽ i ⩽ j ⩽ n, return the majority element of the subarray A [ i. . j ] if it exists. We describe a linear space data structure that answers range majority queries in constant time. We further generalize this problem by defining range α-majority queries: given a query range [ i. . j ], return all the elements in the subarray A [ i. . j ] with frequency greater than α ( j − i + 1 ). We prove an upper bound on the number of α-majorities that can exist in a subarray, assuming that query ranges are restricted to be larger than a given threshold. Using this upper bound, we generalize our range majority data structure to answer range α-majority queries in O ( 1 α ) time using O ( n lg ( 1 α + 1 ) ) space, for any fixed α ∈ ( 0, 1 ). This result is interesting since other similar range query problems based on frequency have nearly logarithmic lower bounds on query time when restricted to linear space.

Details DOI

TCS Journal 2011 Journal Article

Untangled monotonic chains and adaptive range search

Diego Arroyuelo
Francisco Claude
Reza Dorrigiv
Stephane Durocher
Meng He
Alejandro López-Ortiz
J. Ian Munro
Patrick K. Nicholson

We present the first adaptive data structure for two-dimensional orthogonal range search. Our data structure is adaptive in the sense that it gives improved search performance for data that is better than the worst case (Demaine et al. , 2000) [8]; in this case, data with more inherent sortedness. Given n points on the plane, the linear space data structure can answer range queries in O ( log n + k + m ) time, where m is the number of points in the output and k is the minimum number of monotonic chains into which the point set can be decomposed, which is O ( n ) in the worst case. Our result matches the worst-case performance of other optimal-time linear space data structures, or surpasses them when k = o ( n ). Our data structure can be made implicit, requiring no extra space beyond that of the data points themselves (Munro and Suwanda, 1980) [16], in which case the query time becomes O ( k log n + m ). We also present a novel algorithm of independent interest to decompose a point set into a minimum number of untangled, similarly directed monotonic chains in O ( k 2 n + n log n ) time.

Details DOI