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.1111109e-05
Overall Rank: 2,706 | 81.81%
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
441	A Fast Index for Semistructured Data	2001	VLDB	0.00018215078
2,059	A Database Index to Large Biological Sequences	2001	VLDB	9.1020248e-05
6,616	Two-dimensional Substring Indexing	2001	PODS	5.7330951e-05
8,245	Indexing Mixed Types for Approximate Retrieval	2005	VLDB	5.3694945e-05
9,977	A Compact B-tree	2002	SIGMOD	5.1016975e-05
12,151	Autocompletion for Prefix-Abbreviated Input	2019	SIGMOD	4.9793485e-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.001992968
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.0008122792
44	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00045337853
116	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00031645463
2,241	Querying Network Directories	1999	SIGMOD	8.7708234e-05
3,269	Multi-Dimensional Substring Selectivity Estimation	1999	VLDB	7.4756338e-05
5,328	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB	6.1778312e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,780	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS
2	1,559	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS
3	12,779	Worst-Case Efficient Range Search Indexing	2009	PODS
4	13,230	Fast High-Dimensional Data Search in Incomplete Databases	1998	VLDB
5	2,828	Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data	1991	SIGMOD
6	10,052	Text Indexing for Long Patterns: Anchors are All you Need	2023	VLDB
7	9,653	Indexing for Keyword Search with Structured Constraints	2023	PODS
8	8,245	Indexing Mixed Types for Approximate Retrieval	2005	VLDB
9	4,889	An Efficient Index Structure for String Databases	2001	VLDB
10	6,616	Two-dimensional Substring Indexing	2001	PODS