Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing

Summary: iMinMax(θ): a tunable index mapping d‑dim points to one dimension via each point's min/max coordinate under knob θ, producing adaptable 1D embeddings. Range queries become ≤d 1D subqueries with pruning; simple approach empirically outperforms Pyramid. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1205
Venue: PODS
Year: 2000
Pagerank: 5.744549e-05
Overall Rank: 6,894 | 52.71%
DOI: 10.1145/335168.335219

Incoming Non-self Citations Over Time

Authors

1. Beng Chin Ooi (National University of Singapore)
2. Kian-Lee Tan (National University of Singapore)
3. Cui Yu (National University of Singapore)
4. Stephane Bressan (National University of Singapore)

BibTeX Citation

@inproceedings{ooi_pods00,
        address = {New York, NY, USA},
        series = {{PODS} '00},
        title = {{Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing}},
        url = {https://dl.acm.org/doi/10.1145/335168.335219},
        doi = {10.1145/335168.335219},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Ooi, Beng Chin and Tan, Kian-Lee and Yu, Cui and Bressan, Stephane},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
243	Efficient Progressive Skyline Computation	2001	VLDB	0.00023495903
705	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014829964
2,979	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.8984588e-05
3,310	Similarity Query Processing for High-Dimensional Data	2020	VLDB	7.5363562e-05
3,454	Towards Self-Tuning Data Placement in Parallel Database Systems	2000	SIGMOD	7.4001286e-05
5,726	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	6.1079184e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 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
46	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00044853085
864	The Pyramid-Technique: Towards Breaking the Curse of Dimensionality	1998	SIGMOD	0.00013522522

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,806	Computing Immutable Regions for Subspace Top-k Queries	2013	VLDB
2	9,034	Fast and Adaptive Indexing of Multi-Dimensional Observational Data	2016	VLDB
3	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS
4	705	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB
5	8,570	Modeling High-Dimensional Index Structures using Sampling	2001	SIGMOD
6	10,984	Benchmarking Adaptive Multidimensional Indices	2025	VLDB
7	4,730	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS
8	10,612	Index Intersection for High-Dimensional Range Queries	2026	VLDB
9	8,359	High-Dimensional Index Structures: Database Support for Next Decade's Applications	1998	SIGMOD
10	864	The Pyramid-Technique: Towards Breaking the Curse of Dimensionality	1998	SIGMOD