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

In this paper, we investigate space-time tradeoffs for answering Booleanconjunctive queries. The goal is to create a data structure in an initialpreprocessing phase and use it for answering (multiple) queries. Previous workhas developed data structures that trade off space usage for answering time andhas proved conditional space lower bounds for queries of practical interestsuch as the path and triangle query. However, most of these results cater toonly those queries, lack a comprehensive framework, and are not generalizable.The isolated treatment of these queries also fails to utilize the connectionswith extensive research on related problems within the database community. Thekey insight in this work is to exploit the formalism of relational algebra bycasting the problems as answering join queries over a relational database.Using the notion of boolean {\em adorned queries} and {\em access patterns}, wepropose a unified framework that captures several widely studied algorithmicproblems. Our main contribution is three-fold. First, we present an algorithmthat recovers existing space-time tradeoffs for several problems. The algorithmis based on an application of the {\em join size bound} to capture the spaceusage of our data structure. We combine our data structure with {\em querydecomposition} techniques to further improve the tradeoffs and show that it isreadily extensible to queries with negation. Second, we falsify two proposedconjectures in the existing literature related to the space-time lower boundfor path queries and triangle detection for which we show unexpectedly betteralgorithms. This result opens a new avenue for improving several algorithmicresults that have so far been assumed to be (conditionally) optimal. Finally,we prove new conditional space-time lower bounds for star and path queries.

General Space-Time Tradeoffs via Relational Queries