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

Jiannan Yang, Hanpin Wang, Yongzhi Cao

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. devel…