Abstract:

 
 
Property Testing deals with the following question: Distinguish using as few
reads to the input as possible, and preferably in a sublinear running time
to match, between inputs that satisfy a given property and inputs that are
far from any possible input satisfying the property.
 
The talk will survey some of the ideas and history of Property Testing, and
will then move to describe new research on the applicability of Property
Testing for speeding up database query evaluation algorithms.
 
When evaluating a database operation, such as a natural join, the operation
can be speeded up tremendously if the relations (database files) are
guaranteed to be sorted (monotone non-decreasing) over the relevant
attributes. However, it is not feasible to maintain the stored relations in
a sorted state.
 
We define a new measure of near-sortedness, that has the following three
features: (a) Relations that are nearly-sorted to some degree occur
naturally and commonly enough in database relations to be relevant. (b) Such
relations still admit a significant speed-up in database query evaluation,
using a special sorting algorithm that we analyze for this case. (c) The
near-sortedness measure admits a very fast algorithm that approximates it
for a given relation, akin to a Property Test, allowing us to quickly choose
whether to use the new special case algorithm for the query, or default to
the slower traditional general case algorithm.
 
This is joint work with Sagi Ben Moshe, Mani Fischer, Yaron Kanza, Arie
Matsliah and Carl Staelin.