Processing Queries By Linear Constraints

Summary: Introduces QBLC: a processing framework for selection queries defined by linear inequalities over multidimensional data, realized atop R-tree/k-d-B and related indexes to enable aggressive pruning. Key novelty: numerically safe pruning that guarantees no false negatives, with theoretical analysis and experiments showing dramatic cost reductions for OLAP/GIS/scientific workloads. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1123
Venue: PODS
Year: 1997
Pagerank: 0.00013505441
Overall Rank: 1,172 | 91.85%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
430	The Onion Technique: Indexing for Linear Optimization Queries	2000	SIGMOD	0.00023463938
631	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00018935493
1,002	On Indexing Mobile Objects	1999	PODS	0.00014702555
1,502	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00011643406
1,926	Efficient Numerical Error Bounding for Replicated Network Services	2000	VLDB	0.00010067514
1,933	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010038508
2,308	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.0591406e-05
3,463	Towards Robust Indexing for Ranked Queries	2006	VLDB	7.069675e-05
4,711	Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach	2006	VLDB	5.9790683e-05
8,557	Lazy Updates: An Efficient Technique to Continuously Monitoring Reverse kNN	2009	VLDB	4.4937074e-05
9,309	Reverse k Nearest Neighbors Query Processing: Experiments and Analysis	2015	VLDB	4.3571035e-05
9,453	Towards Indexing Functions: Answering Scalar Product Queries	2014	SIGMOD	4.339214e-05

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
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0032169493
5	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.0018397217
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016162015
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083378538
769	Client-Server Paradise	1994	VLDB	0.00016918508
838	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00016088938

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,468	Boolean + Ranking: Querying a Database by K-Constrained Optimization	2006	SIGMOD	4.7210446e-05
12,682	Fixed-Point Query Languages for Linear Constraint Databases	2000	PODS	4.1945683e-05
8,347	QPPT: Query Processing on Prefix Trees	2013	CIDR	4.5410746e-05
5,299	Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints	2003	VLDB	5.5796719e-05
3,543	Approximation Techniques for Spatial Data	2004	SIGMOD	6.9917053e-05
1,502	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00011643406
76	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00057303551
8,011	Constraint-Based Query Optimization for Spatial Databases	1991	PODS	4.6065603e-05
8,889	A General Framework for Modeling and Processing Optimization Queries	2007	VLDB	4.4278238e-05
4,793	Toward Practical Constraint Databases	1993	VLDB	5.9164359e-05