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.00013507216
Overall Rank: 1,171 | 91.87%
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
428	The Onion Technique: Indexing for Linear Optimization Queries	2000	SIGMOD	0.0002349868
628	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00018957327
1,004	On Indexing Mobile Objects	1999	PODS	0.00014694512
1,499	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00011643887
1,924	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010075677
1,929	Efficient Numerical Error Bounding for Replicated Network Services	2000	VLDB	0.00010060709
2,316	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.0513688e-05
3,447	Towards Robust Indexing for Ranked Queries	2006	VLDB	7.082382e-05
4,718	Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach	2006	VLDB	5.9664602e-05
8,554	Lazy Updates: An Efficient Technique to Continuously Monitoring Reverse kNN	2009	VLDB	4.4893996e-05
9,309	Reverse k Nearest Neighbors Query Processing: Experiments and Analysis	2015	VLDB	4.3544778e-05
9,377	Towards Indexing Functions: Answering Scalar Product Queries	2014	SIGMOD	4.344689e-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.0032118946
5	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.0018380955
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016113151
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083300888
766	Client-Server Paradise	1994	VLDB	0.0001690298
833	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00016085787

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,469	Boolean + Ranking: Querying a Database by K-Constrained Optimization	2006	SIGMOD	4.7165172e-05
12,691	Fixed-Point Query Languages for Linear Constraint Databases	2000	PODS	4.1905499e-05
8,342	QPPT: Query Processing on Prefix Trees	2013	CIDR	4.5367151e-05
5,285	Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints	2003	VLDB	5.583298e-05
3,540	Approximation Techniques for Spatial Data	2004	SIGMOD	6.9922652e-05
1,499	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00011643887
75	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00057450043
8,013	Constraint-Based Query Optimization for Spatial Databases	1991	PODS	4.6021663e-05
8,890	A General Framework for Modeling and Processing Optimization Queries	2007	VLDB	4.4235206e-05
4,793	Toward Practical Constraint Databases	1993	VLDB	5.9107617e-05