On Effective Multi-Dimensional Indexing for Strings

Summary: Adapts multi-dimensional indexes to unbounded-length strings for wild-card, multi-attribute matching. Core ideas: string-to-rational mapping; fixed-length leaf offsets to external keys; and per-dimension elided tries for pruning; instantiated on a 2D string R-tree with analytic and experimental validation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3264
Venue: SIGMOD
Year: 2000
Pagerank: 8.2957097e-05
Overall Rank: 2,648 | 81.84%
DOI: 10.1145/342009.335434

Incoming Non-self Citations Over Time

Authors

1. H. V. Jagadish (University of Michigan)
2. Nick Koudas (AT&T)
3. Divesh Srivastava (AT&T)

BibTeX Citation

@inproceedings{jagadish_sigmod00,
        title = {{On Effective Multi-Dimensional Indexing for Strings}},
        author = {Jagadish, H. V. and Koudas, Nick and Srivastava, Divesh},
        series = {{SIGMOD} '00},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/342009.335434},
        url = {https://dl.acm.org/doi/10.1145/342009.335434},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
430	A Fast Index for Semistructured Data	2001	VLDB	0.00018600166
2,008	A Database Index to Large Biological Sequences	2001	VLDB	9.310515e-05
6,491	Two-dimensional Substring Indexing	2001	PODS	5.8641664e-05
8,078	Indexing Mixed Types for Approximate Retrieval	2005	VLDB	5.492543e-05
9,794	A Compact B-tree	2002	SIGMOD	5.2187932e-05
11,851	Autocompletion for Prefix-Abbreviated Input	2019	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 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
8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.00082404462
42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00046170812
116	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.0003221055
2,201	Querying Network Directories	1999	SIGMOD	8.9653966e-05
3,207	Multi-Dimensional Substring Selectivity Estimation	1999	VLDB	7.6364508e-05
5,202	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB	6.3194496e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,359	Incremental Maintenance of Length Normalized Indexes for Approximate String Matching	2009	SIGMOD
2	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS
3	12,489	Worst-Case Efficient Range Search Indexing	2009	PODS
4	12,940	Fast High-Dimensional Data Search in Incomplete Databases	1998	VLDB
5	2,776	Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data	1991	SIGMOD
6	9,861	Text Indexing for Long Patterns: Anchors are All you Need	2023	VLDB
7	9,472	Indexing for Keyword Search with Structured Constraints	2023	PODS
8	8,078	Indexing Mixed Types for Approximate Retrieval	2005	VLDB
9	4,776	An Efficient Index Structure for String Databases	2001	VLDB
10	6,491	Two-dimensional Substring Indexing	2001	PODS