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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Consider an $m$-bit query $q$ to a bitwise trie $T$. A wildcard $*$ is anunspecified bit in $q$ for which the query asks the membership for both cases$*=0$ and $*=1$. It is common that such partial-match queries with wildcardsare issued in tries. With uniformly random occurrences of $w$ wildcards in $q$assumed, the obvious upper bound on the average number of traversal steps in$T$ is $2^w m$. We show that the average does not exceed \[ \frac{m+1}{w+1}\left( 2^{w+2} - 2 w - 4 \right) + m = O \left( \frac{2^w m}{w} \right), \] andequals the value exactly when $T$ includes all the $m$-bit keys as the worstcase. Here the query $q$ performs with the naive backtracking algorithm in $T$.It is similarly shown that the average is $O \left( \frac{k^w m}{w} \right)$ ina general trie of maximum out-degree $k$. Our analysis for tries is extended toa distributed hash table (DHT), which is among the most frequently useddecentralized data structures in networking. We show, under a naturalprobabilistic assumption for the largest class of DHTs, that the average numberof hops required by an $m$-bit query $q$ to a DHT $D$ with random $w$ wildcardsmeets the same asymptotic bound. As a result, $q$ is answered with average $O\left( \frac{2^w m}{w} \right)$ hops rather than $\Theta \left( 2^w m \right)$in the four major DHTs Chord, Pastry, Tapestry and Kademlia. In addition, witha uniform key distribution for sufficiently many entries, we prove that alookup request to the DHT Chord is answered correctly with $O(m)$ hops andprobability $1 - 2^{-\Omega (m)}$. To the author's knowledge, the probability$1 - 2^{-\Omega (m)}$ of correct lookup in Chord has not been identified sofar.

Partial-Match Queries with Random Wildcards: In Tries and Distributed Hash Tables