Space-efficient Substring Occurrence Estimation

Summary: Space-optimal substring-occurrence estimators: for additive error l store Θ(|T| log σ / l) bits to answer Count≈_l(P), enabling compact selectivity estimation via compressed text indexing. Also a frequency-aware Count≥_l structure exact for counts ≥l with space scaling by number of frequent patterns. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1542
Venue: PODS
Year: 2011
Pagerank: 5.7643154e-05
Overall Rank: 6,818 | 53.23%
DOI: 10.1145/1989284.1989300

Incoming Non-self Citations Over Time

Authors

1. Alessio Orlandi (University of Pisa)
2. Rossano Venturini (Institute of Information Science and Technologies, National Research Council)

BibTeX Citation

@inproceedings{orlandi_pods11,
        address = {New York, NY, USA},
        series = {{PODS} '11},
        title = {{Space-efficient Substring Occurrence Estimation}},
        url = {https://dl.acm.org/doi/10.1145/1989284.1989300},
        doi = {10.1145/1989284.1989300},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Orlandi, Alessio and Venturini, Rossano},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,810	Dynamic Data Structures for Document Collections and Graphs	2015	PODS	5.3654354e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,140	Estimating Alphanumeric Selectivity in the Presence of Wildcards	1996	SIGMOD	0.0001200574
1,427	Substring Selectivity Estimation	1999	PODS	0.00010812749

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,427	Substring Selectivity Estimation	1999	PODS
2	6,491	Two-dimensional Substring Indexing	2001	PODS
3	1,140	Estimating Alphanumeric Selectivity in the Presence of Wildcards	1996	SIGMOD
4	2,061	Selectivity Estimation For Boolean Queries	2000	PODS
5	7,692	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD
6	10,642	Differentially Private Substring and Document Counting	2025	PODS
7	12,490	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS
8	9,861	Text Indexing for Long Patterns: Anchors are All you Need	2023	VLDB
9	4,776	An Efficient Index Structure for String Databases	2001	VLDB
10	10,097	SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index	2026	SIGMOD