On Scale Independence for Querying Big Data

Summary: Formalizes scale independence—queries whose needed retrieval size depends on query+access methods, not dataset size—and gives matching upper/lower bounds for deciding it across languages and complexity regimes. Since exact checks are hard and non-syntactic, derives sufficient conditions via access schemas (indexes, constraints, cardinality bounds) and studies scale-independent incremental maintenance and view-based rewrites. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1627
Venue: PODS
Year: 2014
Pagerank: 4.7320027e-05
Overall Rank: 7,410 | 48.51%
DOI: 10.1145/2594538.2594551

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,574	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00011289028
3,590	Automatic Enforcement of Data Use Policies with DataLawyer	2015	SIGMOD	6.9376243e-05
4,545	Bounded Conjunctive Queries	2014	VLDB	6.0917464e-05
7,061	Querying Big Data by Accessing Small Data	2015	PODS	4.8400281e-05
8,712	Data Driven Approximation with Bounded Resources	2017	VLDB	4.4578168e-05
8,963	An Effective Syntax for Bounded Relational Queries	2016	SIGMOD	4.4165156e-05
11,677	Block as a Value for SQL over NoSQL	2019	VLDB	4.1905499e-05
11,793	BEAS: Bounded Evaluation of SQL Queries	2017	SIGMOD	4.1905499e-05
11,834	Bounded Query Rewriting Using Views	2016	PODS	4.1905499e-05
11,839	Logical Aspects of Massively Parallel and Distributed Systems	2016	PODS	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
47	Data Integration: A Theoretical Perspective	2002	PODS	0.00069691761
82	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00054430106
585	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00019682634
937	Queries Independent of Updates	1993	VLDB	0.00015194231
1,114	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00013871948
1,706	SCADS: Scale-Independent Storage for Social Computing Applications	2009	CIDR	0.00010806188
2,062	PIQL: Success-Tolerant Query Processing in the Cloud	2012	VLDB	9.654149e-05
2,714	Minimal MapReduce Algorithms	2013	SIGMOD	8.2426646e-05
3,069	Processing First-Order Queries under Limited Access Patterns	2004	PODS	7.6161135e-05
4,457	Generalized Scale Independence Through Incremental Precomputation	2013	SIGMOD	6.1636855e-05
5,467	Relative Information Completeness	2009	PODS	5.4904942e-05
12,105	Making Queries Tractable on Big Data with Preprocessing (through the eyes of complexity theory)	2013	VLDB	4.1905499e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,713	Query Centric Partitioning and Allocation for Partially Replicated Database Systems	2017	SIGMOD	4.6662571e-05
12,528	Scalable Continuous Query Processing by Tracking Hotspots	2006	VLDB	4.1905499e-05
4,545	Bounded Conjunctive Queries	2014	VLDB	6.0917464e-05
1,114	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00013871948
6,661	Scalable Querying of Nested Data	2021	VLDB	4.9663934e-05
5,309	Continuous Cloud-Scale Query Optimization and Processing	2013	VLDB	5.5714729e-05
5,144	Scalable Query Rewriting: A Graph-Based Approach	2011	SIGMOD	5.6597671e-05
1,155	A Scalable Algorithm for Answering Queries Using Views	2000	VLDB	0.00013606507
7,061	Querying Big Data by Accessing Small Data	2015	PODS	4.8400281e-05
4,457	Generalized Scale Independence Through Incremental Precomputation	2013	SIGMOD	6.1636855e-05