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: 1002
Venue: PODS
Year: 1993
Pagerank: 9.3214272e-05
Overall Rank: 2,003 | 86.26%
DOI: 10.1145/153850.153884

Incoming Non-self Citations Over Time

Authors

1. Paris C. Kanellakis (Brown University)
2. Sridhar Ramaswamy (Brown University)
3. Darren E. Vengroff (Brown University)
4. Jeffrey S. Vitter (Brown University)

BibTeX Citation

@inproceedings{kanellakis_pods93,
        address = {New York, NY, USA},
        series = {{PODS} '93},
        title = {{Indexing for Data Models with Constraints and Classes (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/153850.153884},
        doi = {10.1145/153850.153884},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kanellakis, Paris C. and Ramaswamy, Sridhar and Vengroff, Darren E. and Vitter, Jeffrey S.},
        year = {1993}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
889	Constraint Programming and Database Languages: A Tutorial	1995	PODS	0.00013398105
896	On Indexing Mobile Objects	1999	PODS	0.0001334014
1,139	Managing Intervals Efficiently in Object-Relational Databases	2000	VLDB	0.0001202217
1,512	On the Analysis of Indexing Schemes	1997	PODS	0.00010536001
2,135	Path Caching: A Technique for Optimal External Searching (Extended Abstract)	1994	PODS	9.1133971e-05
2,241	Finitely Representable Databases	1994	PODS	8.8845324e-05
3,790	OODB Indexing by Class-Division	1995	SIGMOD	7.1239529e-05
3,972	Tight bounds for 2-dimensional indexing schemes	1998	PODS	6.9814651e-05
4,212	Data Series Progressive Similarity Search with Probabilistic Quality Guarantees	2020	SIGMOD	6.8283344e-05
4,730	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS	6.5348792e-05
5,046	Toward Practical Constraint Databases	1993	VLDB	6.3879316e-05
5,912	Separability of Polyhedra for Optimal Filtering of Spatial and Constraint Data	1995	PODS	6.0442093e-05
8,559	Towards Practical Constraint Databases (Extended Abstract)	1996	PODS	5.4119882e-05
12,757	Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases	2005	VLDB	5.093636e-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
2,146	H-trees: A Dynamic Associative Search Index for OODB	1992	SIGMOD	9.0842711e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,302	Secondary Index Optimization	1975	SIGMOD
2	6,753	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS
3	12,757	Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases	2005	VLDB
4	7,678	The hcC-tree: An Efficient Index Structure For Object Oriented Databases	1994	VLDB
5	12,490	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS
6	1,512	On the Analysis of Indexing Schemes	1997	PODS
7	3,790	OODB Indexing by Class-Division	1995	SIGMOD
8	12,489	Worst-Case Efficient Range Search Indexing	2009	PODS
9	8,937	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS
10	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS