Two-dimensional substring indexing
Paolo Ferragina, Nick Koudas, Divesh Srivastava, Subramanian Muthukrishnan · 2001
As databases have expanded in scope to storing string data (XML documents, product catalogs), it has become increasingly important to search databases based on matching substrings, often on multiple, correlated dimensions. While string B-trees are I/O optimal in one dimension, no index structure with non-trivial query bounds is known for two-dimensional substring indexing.