On the algebra of data sketches

Summary: Introduces a mergeable sketch algebra for distributed streams, supporting unions, intersections, and weighted-set cardinalities across many sketches. Handles weighted elements and large simultaneous operations with lightweight computation and explicit accuracy–space/cost guarantees. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: ha4cbfc6b9ab30b61
Venue: VLDB
Year: 2021
Pagerank: 5.2650116e-05
Overall Rank: 8,845 | 40.56%
DOI: 10.14778/3461535.3461553
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Jakub Lemiesz (Wrocław University of Science and Technology)

BibTeX Citation

@article{lemiesz_vldb21,
        title = {{On the algebra of data sketches}},
        author = {Lemiesz, Jakub},
        journal = {PVLDB},
        series = {{VLDB} '21},
        volume = {14},
        number = {9},
        pages = {1655--1667},
        doi = {10.14778/3461535.3461553},
        url = {https://doi.org/10.14778/3461535.3461553},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,844	Efficient framework for operating on data sketches	2023	VLDB	5.2650116e-05
9,376	OmniSketch: Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary Predicates	2024	VLDB	5.1843659e-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
456	Mergeable Summaries	2012	PODS	0.00017904764

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,516	An LDP Compatible Sketch for Securely Approximating Set Intersection Cardinalities	2024	SIGMOD
2	10,512	Sketch-based Secure Query Processing for Streaming Data	2026	SIGMOD
3	12,834	Composable, Scalable, and Accurate Weight Summarization of Unaggregated Data Sets	2009	VLDB
4	843	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
5	7,875	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB
6	1,170	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS
7	2,931	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD
8	7,921	Sketch-based Geometric Monitoring of Distributed Stream Queries	2013	VLDB
9	1,067	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB
10	8,844	Efficient framework for operating on data sketches	2023	VLDB