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: h25a4bf036fa5ee24
Venue: PODS
Year: 2000
Pagerank: 5.6380615e-05
Overall Rank: 6,943 | 53.32%
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
256	Efficient Progressive Skyline Computation	2001	VLDB	0.00022981799
650	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00015149775
3,016	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.7483267e-05
3,230	Similarity Query Processing for High-Dimensional Data	2020	VLDB	7.5056037e-05
3,511	Towards Self-Tuning Data Placement in Parallel Database Systems	2000	SIGMOD	7.244841e-05
5,444	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	6.1268526e-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.001992968
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
45	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.0004503446
886	The Pyramid-Technique: Towards Breaking the Curse of Dimensionality	1998	SIGMOD	0.0001325914

Semantically Similar Papers

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