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: h07aec312d2436d48
Venue: PODS
Year: 2001
Pagerank: 6.8627697e-05
Overall Rank: 3,998 | 73.13%
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
370	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.00019846702
3,092	Compressing Historical Information in Sensor Networks	2004	SIGMOD	7.6563998e-05
7,168	Adaptive Stream Filters for Entity-based Queries with Non-Value Tolerance	2005	VLDB	5.5947893e-05
12,971	Asking the Right Questions: Model-driven Optimization using Probes	2006	PODS	4.9793485e-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
172	Combining Fuzzy Information from Multiple Systems	1996	PODS	0.00026835705
412	Fuzzy Queries in Multimedia Database Systems	1998	PODS	0.00018694414
643	Evaluating Top-k Selection Queries	1999	VLDB	0.00015217076
659	Adaptive Precision Setting for Cached Approximate Values	2001	SIGMOD	0.00015015728
1,755	Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data	2000	VLDB	9.7206727e-05
2,430	Data Caching Tradeoffs in Client-Server DBMS Architectures	1991	SIGMOD	8.4799909e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,639	Efficient Summarization Framework for Multi-Attribute Uncertain Data	2014	SIGMOD
2	1,635	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB
3	7,114	Uncertain Centroid based Partitional Clustering of Uncertain Data	2012	VLDB
4	6,950	Exceeding Expectations and Clustering Uncertain Data	2009	PODS
5	8,904	Improvements on the k-center Problem for Uncertain Data	2018	PODS
6	8,426	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD
7	8,808	Supporting User-Defined Functions on Uncertain Data	2013	VLDB
8	12,322	Range-Max Queries on Uncertain Data	2016	PODS
9	6,475	Clustering Uncertain Graphs	2018	VLDB
10	2,304	Approximation Algorithms for Clustering Uncertain Data	2008	PODS