Inducing Source Definitions: System Demo

This is a simple offline demo, which demonstrates the capabilities of are source induction system to learn definitions for a new service based on a set of known services. For an explanation of the research work underpinning this demo, click here.

System Input

Input to the system consists of a mediated schema (a set of semantic types and domain relations), a set of source definitions, and a target source (for which the definition will be learnt). Input for a particular problem is shown below. The corresponding system input file found can be found here.

The Mediated Schema

Semantic Types:

zipcode
latitude
longitude
miles
streetnumber
street
apartment
city
state
areacode
timezone

Domain Predicates:

centroid(zipcode,latitude,longitude)
distance(latitude,longitude,latitude,longitude,miles)
address(streetnumber,street,apartment,city,state,zipcode)
phoneprefix(zipcode,areacode)
timezone(state,timezone)

Comparison Predicates:

<($miles,$miles)

The Sources

DistanceBetweenZips($zip1,$zip2,dist):- centroid(zip1,lat1,long1), centroid(zip2,lat2,long2), distance(lat1,long1,lat2,long2,dist).
InfoByZIP(city,state,$zip,area,tzone):- address(_,_,_,city,state,zip), phoneprefix(zip,area), timezone(state,tzone).

The Target Predicate

The Search

The system performs a best-first search through the space of plausible source definitions, evaluating each definition in turn by invoking the relevant sources. The different levels of search are shown below. At each level, the best performing partial definition is expanded and the score for each expanded definition is calculated (shown in front of the definition).

In the output below, the search is performed over combinations of the source predicates (rather than the domain predicates). Doing so eliminates the need to perform query reformulation, but would be far less efficient in domains where multiple known sources are providing the same or similar functionality. In this domain doing the search over the source predicates doesn't change the results.

Search Level 0

Expanding: .

0.0000000004: ZipCodesWithin(_,_,_,_).
0.0000000000: ZipCodesWithin(X0,_,X0,_).
0.0000000000: ZipCodesWithin(_,X1,_,X1).

Search Level I

Expanding: ZipCodesWithin(_,_,_,_).

0.0000000004: ZipCodesWithin(X0,_,_,_) :- DistanceBetweenZips(X0,X0,_).
0.0000407306: ZipCodesWithin(X0,_,X2,_) :- DistanceBetweenZips(X0,X2,_).
0.0000000012: ZipCodesWithin(X0,X1,_,_) :- DistanceBetweenZips(X0,X0,X1).
0.0000000294: ZipCodesWithin(X0,X1,X2,_) :- DistanceBetweenZips(X0,X2,X1).
0.0000000000: ZipCodesWithin(X0,_,_,X3) :- DistanceBetweenZips(X0,X0,X3).
0.4098005707: ZipCodesWithin(X0,_,X2,X3) :- DistanceBetweenZips(X0,X2,X3).
0.0000453453: ZipCodesWithin(X0,_,X2,_) :- DistanceBetweenZips(X2,X0,_).
0.0000353581: ZipCodesWithin(_,_,X2,_) :- DistanceBetweenZips(X2,X2,_).
0.0000000294: ZipCodesWithin(X0,X1,X2,_) :- DistanceBetweenZips(X2,X0,X1).
0.0000000294: ZipCodesWithin(_,X1,X2,_) :- DistanceBetweenZips(X2,X2,X1).
0.4534533053: ZipCodesWithin(X0,_,X2,X3) :- DistanceBetweenZips(X2,X0,X3).
0.0000000000: ZipCodesWithin(_,_,X2,X3) :- DistanceBetweenZips(X2,X2,X3).
0.0000000004: ZipCodesWithin(X0,_,_,_) :- InfoByZIP(_,_,X0,_,_).
0.0000348643: ZipCodesWithin(_,_,X2,_) :- InfoByZIP(_,_,X2,_,_).
0.0000029424: ZipCodesWithin(_,X1,_,X3) :- <(X1,X3).
0.0000053366: ZipCodesWithin(_,X1,_,X3) :- <(X3,X1).

Search Level II

Expanding: ZipCodesWithin(X0,_,X2,X3) :- DistanceBetweenZips(X2,X0,X3).

0.4464246062: ZipCodesWithin(X0,_,X2,X3) :- DistanceBetweenZips(X2,X0,X3), DistanceBetweenZips(X0,X0,_).
0.4584767796: ZipCodesWithin(X0,_,X2,X3) :- DistanceBetweenZips(X2,X0,X3), DistanceBetweenZips(X0,X2,_).
0.0002942908: ZipCodesWithin(X0,X1,X2,X3) :- DistanceBetweenZips(X2,X0,X3), DistanceBetweenZips(X0,X0,X1).
0.0002354326: ZipCodesWithin(X0,X1,X2,X3) :- DistanceBetweenZips(X2,X0,X3), DistanceBetweenZips(X0,X2,X1).
0.0002942908: ZipCodesWithin(X0,_,X2,X3) :- DistanceBetweenZips(X2,X0,X3), DistanceBetweenZips(X0,X0,X3).
0.4559481488: ZipCodesWithin(X0,_,X2,X3) :- DistanceBetweenZips(X2,X0,X3), DistanceBetweenZips(X0,X2,X3).
0.0002942908: ZipCodesWithin(X0,X1,X2,X3) :- DistanceBetweenZips(X2,X0,X3), DistanceBetweenZips(X2,X0,X1).
0.4559481488: ZipCodesWithin(X0,_,X2,X3) :- DistanceBetweenZips(X2,X0,X3), DistanceBetweenZips(X2,X2,_).
0.0002354326: ZipCodesWithin(X0,X1,X2,X3) :- DistanceBetweenZips(X2,X0,X3), DistanceBetweenZips(X2,X2,X1).
0.0002942908: ZipCodesWithin(X0,_,X2,X3) :- DistanceBetweenZips(X2,X0,X3), DistanceBetweenZips(X2,X2,X3).
0.4559481488: ZipCodesWithin(X0,_,X2,X3) :- DistanceBetweenZips(X2,X0,X3), InfoByZIP(_,_,X0,_,_).
0.3498496306: ZipCodesWithin(X0,_,X2,X3) :- DistanceBetweenZips(X2,X0,X3), InfoByZIP(_,_,X2,_,_).
0.0000588582: ZipCodesWithin(X0,X1,X2,X3) :- DistanceBetweenZips(X2,X0,X3), <(X1,X3).
0.9914075562: ZipCodesWithin(X0,X1,X2,X3) :- DistanceBetweenZips(X2,X0,X3), <(X3,X1).

The last candidate evaluated at search level II has the highest score at that level and is not improved upon by the next level of search (not shown). Thus it is returned by the best-first search algorithm. The definition can be rewritten (by giving more intuitive names to the variables), as:

ZipCodesWithin($zip1,$dist1,zip2,dist2) :- DistanceBetweenZips(zip2,zip1,dist2), <(dist2,dist1).

The description states that the source returns zip codes (zip2) which lie within a given radius (dist1) of the input zip code (zip1), along with the respective distances (dist2). This is indeed the correct definition for the target predicate.

For questions or comments regarding this demo please contact Mark Carman