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.9088735e-05
Overall Rank: 6,035 | 59.43%
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
914	Constraint Programming and Database Languages: A Tutorial	1995	PODS	0.00013104061
4,242	Variable Independence and Aggregation Closure	1996	PODS	6.7070443e-05
6,069	Measuring Infinite Relations (Extended Abstract)	1995	PODS	5.8966049e-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.001992968
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.0008122792
116	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00031645463
1,035	Redundancy in Spatial Databases	1989	SIGMOD	0.00012393393
2,047	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS	9.123147e-05
2,152	Querying Constraints	1990	PODS	8.951621e-05
5,104	Efficient Spatial Access To A Data Base	1982	SIGMOD	6.271356e-05
5,170	Toward Practical Constraint Databases	1993	VLDB	6.2448851e-05
7,412	A Population Analysis for Hierarchical Data Structures	1987	SIGMOD	5.5342698e-05

Semantically Similar Papers

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