BigDataFr recommends: Making problems tractable on big data via preprocessing with polylog-size output

To provide a dichotomy between those queries that can be made feasible on big data after appropriate preprocessing and those for which preprocessing does not help, Fan et al. developed the ⊓-tractability theory. This theory provides a formal foundation for understanding the tractability of query classes in the context of big data.

Along this line, we introduce a novel notion of ⊓′-tractability in this paper. Inspired by some technologies used to deal big data, we place a restriction on preprocessing function, which limits the function to produce a relatively small database as output, at most polylog-size of the input database. At the same time, we bound the redundancy information when re-factorizing data and queries for preprocessing. These changes aim to make our theory more closely linked to practice. […] […]

Read paper
By Sugam Shrar
Source: arxiv.fr