Making Queries Tractable on Big Data with Preprocessing (through the eyes of complexity theory)
Summary: Formalizes offline preprocessing for big data with Pi-tractable queries (PiT0Q, PiTQ), enabling NC-time evaluation after PTIME preprocessing. PiT0Q ⊊ P unless P=NC; PiTQ = P via data/query refactorization and NC reductions, plus a PiTQ-complete class, advancing tractability in data management. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Wenfei Fan
- 2. Floris Geerts
- 3. Frank Neven
Incoming Citations (Sorted by Pagerank)
Showing 4 of 4 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,545 | Bounded Conjunctive Queries | 2014 | VLDB | 6.0917464e-05 |
| 7,061 | Querying Big Data by Accessing Small Data | 2015 | PODS | 4.8400281e-05 |
| 7,410 | On Scale Independence for Querying Big Data | 2014 | PODS | 4.7320027e-05 |
| 11,839 | Logical Aspects of Massively Parallel and Distributed Systems | 2016 | PODS | 4.1905499e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 6 of 6 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8 | Optimal Aggregation Algorithms for Middleware [Extended Abstract] | 2001 | PODS | 0.0015436578 |
| 47 | Data Integration: A Theoretical Perspective | 2002 | PODS | 0.00069691761 |
| 387 | Graph Summarization with Bounded Error | 2008 | SIGMOD | 0.00024682268 |
| 1,114 | Parallel Evaluation of Conjunctive Queries | 2011 | PODS | 0.00013871948 |
| 1,572 | Query Preserving Graph Compression | 2012 | SIGMOD | 0.00011296109 |
| 1,806 | Incremental Graph Pattern Matching | 2011 | SIGMOD | 0.00010478244 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 912 | The Complexity of Evaluating Relational Queries | 1983 | PODS | 0.00015374685 |
| 4,055 | On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates | 1998 | PODS | 6.4906839e-05 |
| 582 | The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version) | 1992 | PODS | 0.00019753367 |
| 11,326 | The Complexity of Conjunctive Queries with Degree 2 | 2022 | PODS | 4.1905499e-05 |
| 3,043 | Tractable Query Languages for Complex Object Databases | 1991 | PODS | 7.6632326e-05 |
| 3,374 | On the Enumeration Complexity of Unions of Conjunctive Queries | 2019 | PODS | 7.1631303e-05 |
| 1,269 | The Dichotomy of Conjunctive Queries on Probabilistic Structures | 2007 | PODS | 0.00012911894 |
| 7,061 | Querying Big Data by Accessing Small Data | 2015 | PODS | 4.8400281e-05 |
| 5,859 | Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries | 2021 | PODS | 5.2963939e-05 |
| 6,996 | Tractable Lineages on Treelike Instances: Limits and Extensions | 2016 | PODS | 4.8629707e-05 |