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: h8c91fbd519734227
Venue: PODS
Year: 2011
Pagerank: 5.635646e-05
Overall Rank: 6,952 | 53.26%
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,959	Dynamic Data Structures for Document Collections and Graphs	2015	PODS	5.2503805e-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,163	Estimating Alphanumeric Selectivity in the Presence of Wildcards	1996	SIGMOD	0.00011750813
1,461	Substring Selectivity Estimation	1999	PODS	0.00010583833

Semantically Similar Papers

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