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: 1122
Venue: PODS
Year: 1997
Pagerank: 0.00011620957
Overall Rank: 1,219 | 91.64%
DOI: 10.1145/263661.263689

Incoming Non-self Citations Over Time

Authors

1. Jonathan Goldstein (University of Wisconsin)
2. Raghu Ramakrishnan (University of Wisconsin)
3. Uri Shaft (University of Wisconsin)
4. Jie-Bing Yu (University of Wisconsin)

BibTeX Citation

@inproceedings{goldstein_pods97,
        address = {New York, NY, USA},
        series = {{PODS} '97},
        title = {{Processing Queries By Linear Constraints}},
        url = {https://dl.acm.org/doi/10.1145/263661.263689},
        doi = {10.1145/263661.263689},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Goldstein, Jonathan and Ramakrishnan, Raghu and Shaft, Uri and Yu, Jie-Bing},
        year = {1997}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
333	The Onion Technique: Indexing for Linear Optimization Queries	2000	SIGMOD	0.0002089582
560	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00016525569
896	On Indexing Mobile Objects	1999	PODS	0.0001334014
1,561	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00010361147
1,612	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010218134
2,062	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.24085e-05
2,676	Efficient Numerical Error Bounding for Replicated Network Services	2000	VLDB	8.2705376e-05
3,007	Towards Robust Indexing for Ranked Queries	2006	VLDB	7.8583548e-05
4,587	Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach	2006	VLDB	6.6170389e-05
8,760	Lazy Updates: An Efficient Technique to Continuously Monitoring Reverse kNN	2009	VLDB	5.3766157e-05
9,356	Reverse k Nearest Neighbors Query Processing: Experiments and Analysis	2015	VLDB	5.282937e-05
9,525	Towards Indexing Functions: Answering Scalar Product Queries	2014	SIGMOD	5.2555551e-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.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.00082404462
42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00046170812
726	Client-Server Paradise	1994	VLDB	0.0001460632
936	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00013092484

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,352	Boolean + Ranking: Querying a Database by K-Constrained Optimization	2006	SIGMOD
2	12,875	Fixed-Point Query Languages for Linear Constraint Databases	2000	PODS
3	8,625	QPPT: Query Processing on Prefix Trees	2013	CIDR
4	5,164	Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints	2003	VLDB
5	3,703	Approximation Techniques for Spatial Data	2004	SIGMOD
6	1,561	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS
7	96	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD
8	8,828	Constraint-Based Query Optimization for Spatial Databases	1991	PODS
9	9,115	A General Framework for Modeling and Processing Optimization Queries	2007	VLDB
10	5,046	Toward Practical Constraint Databases	1993	VLDB