Indexing for Data Models with Constraints and Classes (Extended Abstract)

Summary: Map single-attribute indexing in constraint-based models and attribute+class indexing in OO hierarchies to external dynamic 2D range searching. Present a semi-dynamic index with optimal space O(n/B), optimal query I/O O(log_B n + t/B), amortized insert O(log_B n + (log_B n)^2/B) (expected O(log_B n) for random inserts) and improve class-index queries to O(log_B n + t/B + log_B c). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1003
Venue: PODS
Year: 1993
Pagerank: 9.8126082e-05
Overall Rank: 2,003 | 86.07%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
620	Constraint Programming and Database Languages: A Tutorial	1995	PODS	0.00019005954
986	Managing Intervals Efficiently in Object-Relational Databases	2000	VLDB	0.00014838568
1,002	On Indexing Mobile Objects	1999	PODS	0.00014702555
1,488	On the Analysis of Indexing Schemes	1997	PODS	0.00011699446
1,649	Finitely Representable Databases	1994	PODS	0.00011017687
2,013	Path Caching: A Technique for Optimal External Searching (Extended Abstract)	1994	PODS	9.7928688e-05
3,795	OODB Indexing by Class-Division	1995	SIGMOD	6.7604747e-05
3,900	Tight bounds for 2-dimensional indexing schemes	1998	PODS	6.6518011e-05
4,536	Data Series Progressive Similarity Search with Probabilistic Quality Guarantees	2020	SIGMOD	6.104642e-05
4,793	Toward Practical Constraint Databases	1993	VLDB	5.9164359e-05
5,013	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS	5.7598528e-05
5,461	Separability of Polyhedra for Optimal Filtering of Spatial and Constraint Data	1995	PODS	5.4947899e-05
8,323	Towards Practical Constraint Databases (Extended Abstract)	1996	PODS	4.5435639e-05
12,564	Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases	2005	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1,352	H-trees: A Dynamic Associative Search Index for OODB	1992	SIGMOD	0.00012412548

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,985	Secondary Index Optimization	1975	SIGMOD	4.613363e-05
5,682	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS	5.372736e-05
12,564	Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases	2005	VLDB	4.1945683e-05
7,550	The hcC-tree: An Efficient Index Structure For Object Oriented Databases	1994	VLDB	4.713674e-05
12,295	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS	4.1945683e-05
1,488	On the Analysis of Indexing Schemes	1997	PODS	0.00011699446
3,795	OODB Indexing by Class-Division	1995	SIGMOD	6.7604747e-05
12,294	Worst-Case Efficient Range Search Indexing	2009	PODS	4.1945683e-05
8,767	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS	4.456315e-05
1,182	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00013455963