Property-preserving data reconstruction

Nir Ailon, Bernard Chazelle, Seshadhri Comandur, Ding Liu

Research output: Contribution to journalArticlepeer-review

33 Scopus citations


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 (2 O(d)(log∈n) 4d-2log∈log∈n) time per query and modifies at most O(ε n d ) function values (for constant d).

Original languageEnglish (US)
Pages (from-to)160-182
Number of pages23
JournalAlgorithmica (New York)
Issue number2
StatePublished - Jun 2008
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics


  • Monotonicity testing
  • Sublinear algorithms


Dive into the research topics of 'Property-preserving data reconstruction'. Together they form a unique fingerprint.

Cite this