Separability of Polyhedra for Optimal Filtering of Spatial and Constraint Data

Summary: Approximate d‑D objects by minimal convex polyhedra whose facets are normal to a chosen set of axes (axes not tied to coordinates), and optimize axis selection to trade filtering quality against storage/access cost. Introduce separability classification and algorithms to minimize axes for a target filter quality or to optimize quality under a fixed axis budget; suited to low‑dim, directionally skewed static spatial data. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hcba6b6ba1665cd21
Venue: PODS
Year: 1995
Pagerank: 5.8865586e-05
Overall Rank: 6,050 | 59.45%
DOI: 10.1145/212433.212449

Incoming Non-self Citations Over Time

Authors

1. Alexander Brodsky (George Mason University)
2. Catherine Lassez (IBM)
3. Jean-Louis Lassez (IBM)
4. Michael J. Maher (IBM)

BibTeX Citation

@inproceedings{brodsky_pods95,
        address = {New York, NY, USA},
        series = {{PODS} '95},
        title = {{Separability of Polyhedra for Optimal Filtering of Spatial and Constraint Data}},
        url = {https://dl.acm.org/doi/10.1145/212433.212449},
        doi = {10.1145/212433.212449},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Brodsky, Alexander and Lassez, Catherine and Lassez, Jean-Louis and Maher, Michael J.},
        year = {1995}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
917	Constraint Programming and Database Languages: A Tutorial	1995	PODS	0.00013054852
4,262	Variable Independence and Aggregation Closure	1996	PODS	6.6817915e-05
6,086	Measuring Infinite Relations (Extended Abstract)	1995	PODS	5.8743333e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 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.0019892478
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011386412
8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.00081207565
116	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00031562001
1,038	Redundancy in Spatial Databases	1989	SIGMOD	0.00012349149
2,051	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS	9.1080736e-05
2,165	Querying Constraints	1990	PODS	8.9182663e-05
5,129	Efficient Spatial Access To A Data Base	1982	SIGMOD	6.2478038e-05
5,190	Toward Practical Constraint Databases	1993	VLDB	6.2213007e-05
7,434	A Population Analysis for Hierarchical Data Structures	1987	SIGMOD	5.5133644e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,495	Filtering with Approximate Predicates	1998	VLDB
2	4,888	Rectangle-Efficient Aggregation in Spatial Data Streams	2012	PODS
3	9,023	Constraint-Based Query Optimization for Spatial Databases	1991	PODS
4	2,176	Selectivity Estimation in Spatial Databases	1999	SIGMOD
5	8,637	Efficient Geometry-based Similarity Search of 3D Spatial Databases	1999	SIGMOD
6	9,308	Spatial Priority Search: An Access Technique for Scaleless Maps	1991	SIGMOD
7	3,765	Approximation Techniques for Spatial Data	2004	SIGMOD
8	1,594	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS
9	5,350	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB
10	14,805	A Dual Space Representation for Geometric Data	1987	VLDB