Two-dimensional Substring Indexing

Summary: Reduce 2D substring indexing to the geometric “common colors in two ranges” problem, yielding the first I/O-efficient index with polylogarithmic query bounds for correlated substring queries. Provide an I/O-efficient common-colors algorithm and a family of exact secondary-memory indices (space/time tradeoffs) realizable by combining string B-trees and R-trees. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1243
Venue: PODS
Year: 2001
Pagerank: 5.8641664e-05
Overall Rank: 6,491 | 55.47%
DOI: 10.1145/375551.375610

Incoming Non-self Citations Over Time

Authors

1. Paolo Ferragina (University of Pisa)
2. Nick Koudas (AT&T)
3. S. Muthukrishnan (AT&T)
4. Divesh Srivastava (AT&T)

BibTeX Citation

@inproceedings{ferragina_pods01,
        address = {New York, NY, USA},
        series = {{PODS} '01},
        title = {{Two-dimensional Substring Indexing}},
        url = {https://dl.acm.org/doi/10.1145/375551.375610},
        doi = {10.1145/375551.375610},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Ferragina, Paolo and Koudas, Nick and Muthukrishnan, S. and Srivastava, Divesh},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,064	The CompleteSearch Engine: Interactive, Efficient, and Towards IR & DB Integration	2007	CIDR	7.8008109e-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
329	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00021068647
1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00010482997
2,648	On Effective Multi-Dimensional Indexing for Strings	2000	SIGMOD	8.2957097e-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	6,818	Space-efficient Substring Occurrence Estimation	2011	PODS
2	9,861	Text Indexing for Long Patterns: Anchors are All you Need	2023	VLDB
3	12,757	Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases	2005	VLDB
4	6,451	Efficient Search of Multidimensional B-Trees	1995	VLDB
5	12,489	Worst-Case Efficient Range Search Indexing	2009	PODS
6	2,776	Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data	1991	SIGMOD
7	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS
8	4,776	An Efficient Index Structure for String Databases	2001	VLDB
9	12,490	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS
10	2,648	On Effective Multi-Dimensional Indexing for Strings	2000	SIGMOD