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)
Incoming Non-self Citations Over Time
Authors
- 1. Paolo Ferragina
- 2. Nick Koudas
- 3. S. Muthukrishnan
- 4. Divesh Srivastava
Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,531 | The CompleteSearch Engine: Interactive, Efficient, and Towards IR & DB Integration | 2007 | CIDR | 8.5911728e-05 |
| 11,656 | Autocompletion for Prefix-Abbreviated Input | 2019 | SIGMOD | 4.1945683e-05 |
Previous
Page 1 / 1
Next
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.0032169493 |
| 5 | The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes | 1981 | SIGMOD | 0.0018397217 |
| 6 | The R*-tree: An Efficient and Robust Access Method for Points and Rectangles | 1990 | SIGMOD | 0.0016162015 |
| 24 | The R+-Tree: A Dynamic Index For Multi-Dimensional Objects | 1987 | VLDB | 0.00083378538 |
| 354 | Hilbert R-tree: An Improved R-tree Using Fractals | 1994 | VLDB | 0.00026137988 |
| 1,182 | On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) | 1999 | PODS | 0.00013455963 |
| 1,184 | On Effective Multi-Dimensional Indexing for Strings | 2000 | SIGMOD | 0.00013455208 |
| 4,612 | Filter Trees for Managing Spatial Data Over a Range of Size Granularities | 1996 | VLDB | 6.0484423e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,813 | Space-efficient Substring Occurrence Estimation | 2011 | PODS | 5.3170565e-05 |
| 9,724 | Text Indexing for Long Patterns: Anchors are All you Need | 2023 | VLDB | 4.295436e-05 |
| 12,564 | Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases | 2005 | VLDB | 4.1945683e-05 |
| 6,480 | Efficient Search of Multidimensional B-Trees | 1995 | VLDB | 5.0475112e-05 |
| 12,294 | Worst-Case Efficient Range Search Indexing | 2009 | PODS | 4.1945683e-05 |
| 2,586 | Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data | 1991 | SIGMOD | 8.4928908e-05 |
| 1,182 | On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) | 1999 | PODS | 0.00013455963 |
| 4,333 | An Efficient Index Structure for String Databases | 2001 | VLDB | 6.2805237e-05 |
| 12,295 | Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes | 2009 | PODS | 4.1945683e-05 |
| 1,184 | On Effective Multi-Dimensional Indexing for Strings | 2000 | SIGMOD | 0.00013455208 |