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 approximate range emptiness problem requires a memory-efficient data structure <inline-formula> <tex-math notation="LaTeX">$\mathscr {D}$ </tex-math></inline-formula> to approximately represent a set <inline-formula> <tex-math notation="LaTeX">$S$ </tex-math></inline-formula> of <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> distinct elements chosen from a large universe <inline-formula> <tex-math notation="LaTeX">$U=\{0,1,\cdots ,N-1\}$ </tex-math></inline-formula> and answer an emptiness query of the form “<inline-formula> <tex-math notation="LaTeX">$S\cap [a;b]=\emptyset ?$ </tex-math></inline-formula>” for an interval <inline-formula> <tex-math notation="LaTeX">$[a;b]$ </tex-math></inline-formula> of length <inline-formula> <tex-math notation="LaTeX">$L$ </tex-math></inline-formula> (<inline-formula> <tex-math notation="LaTeX">$a,b\in U$ </tex-math></inline-formula>), with a false positive rate <inline-formula> <tex-math notation="LaTeX">$\varepsilon $ </tex-math></inline-formula>. The designed <inline-formula> <tex-math notation="LaTeX">$\mathscr {D}$ </tex-math></inline-formula> for this problem can be kept in high-speed memory and quickly determine approximately whether a query interval is empty or not. Thus, it is crucial for facilitating online query processing in the information-centric Internet of Things applications, where the IoT data are continuously generated from a large number of resource-constrained sensors or readers and then are processed in networks. However, the existing works on the approximate range emptiness problem only consider the simple case when the set <inline-formula> <tex-math notation="LaTeX">$S$ </tex-math></inline-formula> is static, rendering them unsuitable for the continuously generated IoT data. In this paper, we study the approximate range emptiness problem over sliding windows in the IoT Data streams, denoted by <inline-formula> <tex-math notation="LaTeX">$\varepsilon $ </tex-math></inline-formula><italic>-ARESD-problem</italic>, where both insertion and deletion are allowed. We first prove that, given a sliding window size <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> and an interval length <inline-formula> <tex-math notation="LaTeX">$L$ </tex-math></inline-formula>, the lower bound of memory bits needed in any data structure for <inline-formula> <tex-math notation="LaTeX">$\varepsilon $ </tex-math></inline-formula><italic>-ARESD-problem</italic> is <inline-formula> <tex-math notation="LaTeX">$n\log _{2} ({nL}/{\varepsilon })+\Theta (n)$ </tex-math></inline-formula>. Then, a data structure is proposed and proved to be within a factor of 1.33 of the lower bound. The extensive simulation results demonstrate the advantage of the efficiency of our data structure over the baseline approach.

Near-Optimal Data Structure for Approximate Range Emptiness Problem in Information-Centric Internet of Things