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,546 | Bounded Conjunctive Queries | 2014 | VLDB | 6.0987778e-05 |
| 7,085 | Querying Big Data by Accessing Small Data | 2015 | PODS | 4.8388174e-05 |
| 7,413 | On Scale Independence for Querying Big Data | 2014 | PODS | 4.7358047e-05 |
| 11,831 | Logical Aspects of Massively Parallel and Distributed Systems | 2016 | PODS | 4.1945683e-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 |
|---|---|---|---|---|
| 7 | Optimal Aggregation Algorithms for Middleware [Extended Abstract] | 2001 | PODS | 0.0015496097 |
| 48 | Data Integration: A Theoretical Perspective | 2002 | PODS | 0.00069720859 |
| 388 | Graph Summarization with Bounded Error | 2008 | SIGMOD | 0.00024662272 |
| 1,110 | Parallel Evaluation of Conjunctive Queries | 2011 | PODS | 0.00013968198 |
| 1,579 | Query Preserving Graph Compression | 2012 | SIGMOD | 0.00011283792 |
| 1,720 | Incremental Graph Pattern Matching | 2011 | SIGMOD | 0.00010779343 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 915 | The Complexity of Evaluating Relational Queries | 1983 | PODS | 0.0001538509 |
| 4,048 | On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates | 1998 | PODS | 6.4968603e-05 |
| 581 | The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version) | 1992 | PODS | 0.00019767772 |
| 11,324 | The Complexity of Conjunctive Queries with Degree 2 | 2022 | PODS | 4.1945683e-05 |
| 3,040 | Tractable Query Languages for Complex Object Databases | 1991 | PODS | 7.6707607e-05 |
| 3,371 | On the Enumeration Complexity of Unions of Conjunctive Queries | 2019 | PODS | 7.1696145e-05 |
| 1,268 | The Dichotomy of Conjunctive Queries on Probabilistic Structures | 2007 | PODS | 0.00012931993 |
| 7,085 | Querying Big Data by Accessing Small Data | 2015 | PODS | 4.8388174e-05 |
| 5,858 | Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries | 2021 | PODS | 5.2997454e-05 |
| 6,997 | Tractable Lineages on Treelike Instances: Limits and Extensions | 2016 | PODS | 4.8676446e-05 |