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: haf97b093d98d7e16
Venue: SIGMOD
Year: 2000
Pagerank: 8.0808382e-05
Overall Rank: 2,717 | 81.79%
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
445	A Fast Index for Semistructured Data	2001	VLDB	0.0001815112
2,070	A Database Index to Large Biological Sequences	2001	VLDB	9.0676405e-05
6,631	Two-dimensional Substring Indexing	2001	PODS	5.7114931e-05
8,267	Indexing Mixed Types for Approximate Retrieval	2005	VLDB	5.3492332e-05
10,013	A Compact B-tree	2002	SIGMOD	5.0839435e-05
12,200	Autocompletion for Prefix-Abbreviated Input	2019	SIGMOD	4.9605343e-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.0019892478
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011386412
8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.00081207565
44	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00045231517
116	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00031562001
2,259	Querying Network Directories	1999	SIGMOD	8.7384901e-05
3,281	Multi-Dimensional Substring Selectivity Estimation	1999	VLDB	7.4493372e-05
5,350	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB	6.1545256e-05

Semantically Similar Papers

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