Author name cluster

Matthew Skala

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.

3 papers

2 author rows

MFCS Conference 2013 Conference Paper

Linear-Space Data Structures for Range Frequency Queries on Arrays and Trees

Stephane Durocher
Rahul Shah 0001
Matthew Skala
Sharma V. Thankachan

Abstract We present O ( n )-space data structures to support various range frequency queries on a given array A [0: n − 1] or tree T with n nodes. Given a query consisting of an arbitrary pair of pre-order rank indices ( i, j ), our data structures return a least frequent element, mode, or α -minority of the multiset of elements in the unique path with endpoints at indices i and j in A or T. We describe a data structure that supports range least frequent element queries on arrays in \(O(\sqrt{n / w})\) time, improving the \(\Theta(\sqrt{n})\) worst-case time required by the data structure of Chan et al. (SWAT 2012), where w ∈ Ω(log n ) is the word size in bits. We describe a data structure that supports range mode queries on trees in \(O(\log\log n \sqrt{n / w})\) time, improving the \(\Theta(\sqrt{n} \log n)\) worst-case time required by the data structure of Krizanc et al. (ISAAC 2003). Finally, we describe a data structure that supports range α -minority queries on trees in O ( α − 1 loglog n ) time, where α ∈ [0, 1] is specified at query time.

Details

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