On Computing Functions with Uncertainty

Summary: Adaptive probing to compute f(x1..xn) when each xi is only known to lie in an interval and probes are costly; objective: minimize probe cost while guaranteeing f within specified precision for all realizations. Presents online, competitive (asymptotically optimal) algorithms for selection, aggregation (sum/avg) and their compositions under three precision models. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1233
Venue: PODS
Year: 2001
Pagerank: 7.0158184e-05
Overall Rank: 3,923 | 73.09%
DOI: 10.1145/375551.375577

Incoming Non-self Citations Over Time

Authors

1. Sanjeev Khanna (University of Pennsylvania)
2. Wang-Chiew Tan (University of Pennsylvania)

BibTeX Citation

@inproceedings{khanna_pods01,
        address = {New York, NY, USA},
        series = {{PODS} '01},
        title = {{On Computing Functions with Uncertainty}},
        url = {https://dl.acm.org/doi/10.1145/375551.375577},
        doi = {10.1145/375551.375577},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Khanna, Sanjeev and Tan, Wang-Chiew},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
359	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.0002023153
3,034	Compressing Historical Information in Sensor Networks	2004	SIGMOD	7.8302786e-05
7,027	Adaptive Stream Filters for Entity-based Queries with Non-Value Tolerance	2005	VLDB	5.7231968e-05
12,681	Asking the Right Questions: Model-driven Optimization using Probes	2006	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
170	Combining Fuzzy Information from Multiple Systems	1996	PODS	0.00027376361
402	Fuzzy Queries in Multimedia Database Systems	1998	PODS	0.00019072958
635	Evaluating Top-k Selection Queries	1999	VLDB	0.00015527042
646	Adaptive Precision Setting for Cached Approximate Values	2001	SIGMOD	0.00015335457
1,716	Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data	2000	VLDB	9.9330086e-05
2,376	Data Caching Tradeoffs in Client-Server DBMS Architectures	1991	SIGMOD	8.6715978e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,467	Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations	2010	VLDB
2	1,605	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB
3	6,974	Uncertain Centroid based Partitional Clustering of Uncertain Data	2012	VLDB
4	6,812	Exceeding Expectations and Clustering Uncertain Data	2009	PODS
5	8,741	Improvements on the k-center Problem for Uncertain Data	2018	PODS
6	8,260	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD
7	8,646	Supporting User-Defined Functions on Uncertain Data	2013	VLDB
8	12,027	Range-Max Queries on Uncertain Data	2016	PODS
9	6,345	Clustering Uncertain Graphs	2018	VLDB
10	2,253	Approximation Algorithms for Clustering Uncertain Data	2008	PODS