Text Indexing for Long Patterns: Anchors are All you Need

Summary: bd-anchors (a locally-consistent-anchor scheme) for indexing long patterns (length ≥ l), yielding simultaneously small index size, fast query time, and low construction time/space. Key contributions: avg-case linear bd-anchor extraction and a semi-external, low‑space build; empirically outperforms (compressed) suffix arrays/trees and FM-index on long-pattern queries. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13252
Venue: VLDB
Year: 2023
Pagerank: 5.2055975e-05
Overall Rank: 9,861 | 32.35%
DOI: 10.14778/3598581.3598586

Incoming Non-self Citations Over Time

Authors

1. Lorraine A. K. Ayad (Brunel University)
2. Grigorios Loukides (King's College London)
3. Solon P. Pissis (Centrum Wiskunde & Informatica; Vrije Universiteit Amsterdam)

BibTeX Citation

@article{ayad_vldb23,
        title = {{Text Indexing for Long Patterns: Anchors are All you Need}},
        author = {Ayad, Lorraine A. K. and Loukides, Grigorios and Pissis, Solon P.},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {9},
        pages = {2117--2131},
        doi = {10.14778/3598581.3598586},
        url = {https://doi.org/10.14778/3598581.3598586},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,097	SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index	2026	SIGMOD	5.1502319e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
978	Winnowing: Local Algorithms for Document Fingerprinting	2003	SIGMOD	0.00012859554

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,810	Dynamic Data Structures for Document Collections and Graphs	2015	PODS
2	1,587	An Efficient Indexing Technique for Full-Text Database Systems	1992	VLDB
3	3,897	Searching Large Lexicons for Partially Specified Terms using Compressed Inverted Files	1993	VLDB
4	12,490	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS
5	3,470	Practical Suffix Tree Construction	2004	VLDB
6	4,776	An Efficient Index Structure for String Databases	2001	VLDB
7	6,491	Two-dimensional Substring Indexing	2001	PODS
8	4,359	Incremental Maintenance of Length Normalized Indexes for Approximate String Matching	2009	SIGMOD
9	2,648	On Effective Multi-Dimensional Indexing for Strings	2000	SIGMOD
10	6,818	Space-efficient Substring Occurrence Estimation	2011	PODS