Abstract
We initiate a new line of investigation into online property-preserving data reconstruction. Consider a dataset which is assumed to satisfy various (known) structural properties; e.g., it may consist of sorted numbers, or points on a manifold, or vectors in a polyhedral cone, or codewords from an error-correcting code. Because of noise and errors, however, an (unknown) fraction of the data is deemed unsound, i.e., in violation with the expected structural properties. Can one still query into the dataset in an online fashion and be provided data that is always sound? In other words, can one design a filter which, when given a query to any item I in the dataset, returns a sound item J that, although not necessarily in the dataset, differs from I as infrequently as possible. No preprocessing should be allowed and queries should be answered online.
We consider the case of a monotone function. Specifically, the dataset encodes a function f:{1,…,n} ↦ R that is at (unknown) distance ε from monotone, meaning that f can—and must—be modified at ε n places to become monotone.
Our main result is a randomized filter that can answer any query in O(log 2 nlog log n) time while modifying the function f at only O(ε n) places. The amortized time over n function evaluations is O(log n). The filter works as stated with probability arbitrarily close to 1. We provide an alternative filter with O(log n) worst case query time and O(ε nlog n) function modifications. For reconstructing d-dimensional monotone functions of the form f:{1,…,n}d ↦ R, we present a filter that takes (2O(d)(log n)4d−2log log n) time per query and modifies at most O(ε n d) function values (for constant d).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ailon, N., Chazelle, B., Comandur, S., Liu, D.: Estimating the distance to a monotone function. In: Proc. 8th RANDOM, pp. 229–236 (2004)
Agarwal, P., Erickson, J.: Geometric range searching and its relatives. Adv. Discret. Comput. Geom. 1–56 (1999)
Blum, M., Luby, M., Rubinfeld, R.: Self-testing/correcting with applications to numerical problems. In: Proc. 22nd STOC, pp. 73–83 (1990)
Fischer, E.: The art of uninformed decisions: A primer to property testing. Bull. EATCS 75, 97–126 (2001)
Goldreich, O.: Combinatorial property testing—A survey. In: Randomization Methods in Algorithm Design, pp. 45–60 (1998)
Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. J. ACM 45, 653–750 (1998)
Hoffmann, C.M., Hopcroft, J.E., Karasick, M.S.: Towards implementing robust geometric computations. In: Proc. 4th SOCG, pp. 106–117 (1988)
Halevy, S., Kushilevitz, E.: Distribution-free property testing. In: RANDOM-APPROX, pp. 302–317 (2003)
Parnas, M., Ron, D., Rubinfeld, R.: Tolerant property testing and distance approximation. ECCC TR04-010 (2004)
Reed, B.: The height of a random binary search tree. J. ACM 50, 306–332 (2003)
Ron, D.: Property testing. In: Handbook on Randomization, vol. II, pp. 597–649 (2001)
Rubinfeld, R., Sudan, M.: Robust characterization of polynomials with applications to program testing. SIAM J. Comput. 25, 647–668 (1996)
Salesin, S., Stolfi, J., Guibas, L.J.: Epsilon geometry: building robust algorithms from imprecise computations. In: Proc. 5th SOCG, pp. 208–217 (1988)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported in part by NSF grants CCR-998817, 0306283, ARO Grant DAAH04-96-1-0181.
Rights and permissions
About this article
Cite this article
Ailon, N., Chazelle, B., Comandur, S. et al. Property-Preserving Data Reconstruction. Algorithmica 51, 160–182 (2008). https://doi.org/10.1007/s00453-007-9075-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-007-9075-9