Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams

Summary: Authentication for sliding-window queries on outsourced streams using Merkle hash trees over partitioned data structures. Proves results equal to original provider; analyzes update, query, signing, and authentication costs with empirical evaluation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h064b1e3d4a32df0b
Venue: VLDB
Year: 2007
Pagerank: 6.5590284e-05
Overall Rank: 4,498 | 69.86%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Feifei Li (Boston University)
2. Ke Yi (AT&T Labs Inc.)
3. Marios Hadjieleftheriou (AT&T Labs Inc.)
4. George Kollios (Boston University)

BibTeX Citation

@article{li_vldb07,
        title = {{Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams}},
        author = {Li, Feifei and Yi, Ke and Hadjieleftheriou, Marios and Kollios, George},
        journal = {PVLDB},
        series = {{VLDB} '07},
        pages = {147--158},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,848	Authenticated Join Processing in Outsourced Databases	2009	SIGMOD	9.5022605e-05
4,143	Authenticating the Query Results of Text Search Engines	2008	VLDB	6.7672192e-05
9,821	Lightweight Authentication of Linear Algebraic Queries on Data Streams	2013	SIGMOD	5.1100459e-05
12,647	Authenticating Location-based Services without Compromising Location Privacy	2012	SIGMOD	4.9605343e-05
12,886	An Audit Environment for Outsourcing of Frequent Itemset Mining	2009	VLDB	4.9605343e-05
14,024	Verifying Computations with Streaming Interactive Proofs	2012	VLDB	-

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0019892478
26	Models and Issues in Data Stream Systems	2002	PODS	0.00051942573
451	Dynamic Authenticated Index Structures for Outsourced Databases	2006	SIGMOD	0.00018054106
634	Verifying Completeness of Relational Query Results in Data Publishing	2005	SIGMOD	0.00015350423
667	Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure	2001	SIGMOD	0.00014941252
860	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.00013382689
861	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00013374869
2,411	Query Execution Assurance for Outsourced Databases	2005	VLDB	8.4895798e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,452	When Query Authentication Meets Fine-Grained Access Control: A Zero-Knowledge Approach	2018	SIGMOD
2	9,029	Authenticating Top-k Queries in Location-based Services with Confidentiality	2014	VLDB
3	4,564	CADS: Continuous Authentication on Data Streams	2007	VLDB
4	8,058	Authenticated Online Data Integration Services	2015	SIGMOD
5	451	Dynamic Authenticated Index Structures for Outsourced Databases	2006	SIGMOD
6	5,511	Practical Authenticated Pattern Matching with Optimal Proof Size	2015	VLDB
7	10,578	Sketch-based Secure Query Processing for Streaming Data	2026	SIGMOD
8	14,024	Verifying Computations with Streaming Interactive Proofs	2012	VLDB
9	5,012	Scalable Verification for Outsourced Dynamic Databases	2009	VLDB
10	9,821	Lightweight Authentication of Linear Algebraic Queries on Data Streams	2013	SIGMOD