Wander Join

Posted by Kaiyuan Chen on April 4, 2018

Wander Join: online aggregation via random walks

by Feifei Li et al.

Problem formulation:

Data aggregation:

It provides approximate answers for online queries; Data aggregation is any process in which information is gathered and expressed in a summary form, for purposes such as statistical analysis.

online aggregations for joins

Ripple join: repeatedly takes samples from each table by RR, and every time new tuple comes in, join with all other tuples.

Wander Join

Build a join relation tuples and sample ./img/404.png. Then sample by picking vertex in R1 at random and random walk to R3: by using Horvitz-Thompson estimator, we might remove biased overestimate in random walk.

With enough and unbiased sampling, we may get what we want.

After

I am literally crying because I have reviewed so many papers. I am studying matrices/data with missing observations and I have reviewed for hundreds of related papers. I do need time to post them here.