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: 1046
Venue: PODS
Year: 1995
Pagerank: 6.0442093e-05
Overall Rank: 5,912 | 59.44%
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
889	Constraint Programming and Database Languages: A Tutorial	1995	PODS	0.00013398105
4,165	Variable Independence and Aggregation Closure	1996	PODS	6.858392e-05
5,948	Measuring Infinite Relations (Extended Abstract)	1995	PODS	6.0317886e-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.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
116	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.0003221055
1,019	Redundancy in Spatial Databases	1989	SIGMOD	0.00012622386
2,003	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS	9.3214272e-05
2,111	Querying Constraints	1990	PODS	9.1515689e-05
4,978	Efficient Spatial Access To A Data Base	1982	SIGMOD	6.4152309e-05
5,046	Toward Practical Constraint Databases	1993	VLDB	6.3879316e-05
7,262	A Population Analysis for Hierarchical Data Structures	1987	SIGMOD	5.6612247e-05

Semantically Similar Papers

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