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/

Global: Zendy Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The problem of Text Indexing is a fundamental algorithmic problem in whichone wishes to preprocess a text in order to quickly locate pattern querieswithin the text. In the ever evolving world of dynamic and on-line data, thereis also a need for developing solutions to index texts which arrive on-line,i.e. a character at a time, and still be able to quickly locate said patterns.In this paper, a new solution for on-line indexing is presented by providing anon-line suffix tree construction in $O(\log \log n + \log\log |\Sigma|)$worst-case expected time per character, where $n$ is the size of the string,and $\Sigma$ is the alphabet. This improves upon all previously known on-linesuffix tree constructions for general alphabets, at the cost of having the runtime in expectation.  The main idea is to reduce the problem of constructing a suffix tree on-lineto an interesting variant of the order maintenance problem, which may be ofindependent interest. In the famous order maintenance problem, one wishes tomaintain a dynamic list $L$ of size $n$ under insertions, deletions, and orderqueries. In an order query, one is given two nodes from $L$ and must determinewhich node precedes the other in $L$. In the Predecessor search on DynamicSubsets of an Ordered Dynamic List problem (POLP) it is also necessary tomaintain dynamic subsets of $L$ such that given some $u\in L$ it will bepossible to quickly locate the predecessor of $u$ in any subset. This paperprovides an efficient data structure capable of solving the POLP withworst-case expected bounds that match the currently best known bounds forpredecessor search in the RAM model, improving over a solution which may beimplicitly obtained from Dietz [Die89].  Furthermore, this paper improves or simplifies bounds for several additionalapplications, including fully-persistent arrays and the Order-MaintenanceProblem.

On-line Indexing for General Alphabets via Predecessor Queries on Subsets of an Ordered List