English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Karpinski and Nekrich (2008) introduced the problem of parameterized rangemajority, which asks to preprocess a string of length $n$ such that, given theendpoints of a range, one can quickly find all the distinct elements whoserelative frequencies in that range are more than a threshold $\tau$. Subsequentauthors have reduced their time and space bounds such that, when $\tau$ isgiven at preprocessing time, we need either $\Oh{n \log (1 / \tau)}$ space andoptimal $\Oh{1 / \tau}$ query time or linear space and $\Oh{(1 / \tau) \log\log \sigma}$ query time, where $\sigma$ is the alphabet size. In this paper wegive the first linear-space solution with optimal $\Oh{1 / \tau}$ query time.For the case when $\tau$ is given at query time, we significantly improveprevious bounds, achieving either $\Oh{n \log \log \sigma}$ space and optimal$\Oh{1 / \tau}$ query time or compressed space and $\Oh{(1 / \tau) \log\frac{\log (1 / \tau)}{\log w}}$ query time. Along the way, we consider thecomplementary problem of parameterized range minority that was recentlyintroduced by Chan et al.\ (2012), who achieved linear space and $\Oh{1 /\tau}$ query time even for variable $\tau$. We improve their solution to useeither nearly optimally compressed space with no slowdown, or optimallycompressed space with nearly no slowdown. Some of our intermediate results,such as density-sensitive query time for one-dimensional range counting, may beof independent interest.

Better Space Bounds for Parameterized Range Majority and Minority