An Ecient Sampling Alternative for Big Data Aggregation
Hadassa Daltrophe, Shlomi Dolev, Zvi Lotker · arXiv (Cornell University) · 2012
AbstractGiven a large set of measurement sensor data, in order to identify a simple function thatcaptures the essence of the data gathered by the sensors, we suggest representing the data by(spatial) functions, in particular by polynomials. Given a (sampled) set of values, we interpolatethe datapoints to de ne a polynomial that would represent the data. The interpolation ischallenging, since in practice the data can be noisy and even Byzantine, where the Byzantinedata represents an adversarial value that is not limited to being close to the correct measureddata. We present two solutions, one that extends the Welch-Berlekamp technique in the caseof multidimensional data, and copes with discrete noise and Byzantine data, and the otherbased on Arora and Khot techniques, extending them in the case of multidimensional noisy andByzantine data. Department of Computer Science, Ben-Gurion University, Beer-Sheva, 84105, Israel. Email: [email protected] supported by a Russian Israeli grant from the Israeli Ministry of Science and Technology and the RussianFoundation for Basic Research, the Rita Altura Trust Chair in Computer Sciences, the Lynne and William FrankelCenter for Computer Sciences, Israel Science Foundation (grant number 428/11), Cabarnit Cyber Security MAGNETConsortium, Grant from the Institute for Future Defense Technologies Research named for the Medvedi of theTechnion, MAFAT, and Israeli Internet Association