ostore.introspect
Class SemanticDistanceModel

java.lang.Object
  |
  +--ostore.introspect.SemanticDistanceModel

All Implemented Interfaces:

ContinuousModel, Model, QuickSerializable, SegmentedModel

public class SemanticDistanceModel

extends Object

implements ContinuousModel, SegmentedModel

Instrospective model that implements a semantic distance table (distance between events based on continuous time).

The table is structured as follows:

 (type_1) => (type_a1,dist_a1) (type_b1,dist_b1) ... (type_n1, dist_n1)
 (type_2) => (type_a2,dist_a2) (type_b2,dist_b2) ... (type_m1, dist_m1)
 ...
 (type_k) => (type_ak,dist_ak) (type_bk,dist_bk) ... (type_lk, dist_lk)
 

where each row contains the distances between type_i and types type_Ai. This implementation treats the distances as a sorted list (priority queue) and bounds the number of distances kept per row (see setMaxRelations(int)). Note that the distance values in the table are asymmetric.

This model supports the Model and SegmentedModel interfaces and can export and import Model.Deltas and SegmentedModel.Segments to incorporate into this model or remote ones.

A SemanticDistanceModel is parameterized by a SemanticDistanceModel.Filter. The filter determines how distance values in the semantic distance table are updated when (i) new observations are made and (ii) when we wish to incorporate a model Delta or Segment. Note that normal operation simply keeps an access history of record() calls until recalculate() is called. At that point, a Delta containing a table of only the new observations is created and incorporated into the model with add_delta().

IMPORTANT: Make sure the QuickSerializable objects used as observation keys implement both equals and hashCode.

Version:

$Id: SemanticDistanceModel.java,v 1.11 2003/11/17 23:52:43 emilong Exp $

Author:

Jeff Pang

See Also:

Time, Distance

Nested Class Summary

static class	SemanticDistanceModel.BoundedPrioQueue Implementation of a priority queue of tuples (sorted by priority) which throws away stuff at the end when it gets larger than bound.
static class	SemanticDistanceModel.Delta Implements Model.Delta for this model type.
static interface	SemanticDistanceModel.Filter A filter determines how to integrate new semantic distance values into the table.
static class	SemanticDistanceModel.Prediction Implements Model.Prediction for this model type.
static class	SemanticDistanceModel.Segment A Segment object contains the internal model state associated with a single state.
static class	SemanticDistanceModel.Table The actual semantic distance table.
static class	SemanticDistanceModel.TestType
static class	SemanticDistanceModel.Tuple A <QuickSerializable obs,Distance d, int num> tuple.

Nested classes inherited from class ostore.oil.Model

Nested classes inherited from class ostore.oil.SegmentedModel

Field Summary

static String	class_tag
static boolean	DEBUG

Constructor Summary

SemanticDistanceModel(InputBuffer buffer)

SemanticDistanceModel(int maxrelations, Time now, SemanticDistanceModel.Filter filter)
Construct a new model.

SemanticDistanceModel(Time now)
Construct a new model with default filter WeightedAvgFilter().

Method Summary

void	add_delta(Model.Delta d) Incorporate a Delta from a foreign source into our model.
protected void	add_delta(Model.Delta d, boolean save_times) Incorporate a Delta with the latest access times in the table.
void	add_segment(SegmentedModel.Segment segment) Incorporates the portion of the model contained in the specified Segment.
void	choose_segments(int num) Selects the most-relevant num segments to retain, discarding all others.
void	clear() Forget all observations recorded since the last call to clear or recalculate.
void	clear(int num) Forget the least-recent recorded observations.
SemanticDistanceModel.Segment	get_segment(QuickSerializable id) Obtain a segment that contains the distance information between id and other types.
int	getClients() Get the number of clients represented by this model.
SemanticDistanceModel.Table	getTable() Get the semantic distance table.
double	loglikelihood() Calculates the log-likelihood of all recorded observations.
static void	main(String[] args) Self test.
QuickSerializable[]	outliers() Returns the recent observations which the model assigns the lowest likelihood.
int	outstanding_observations() Return the number of observations recorded but not yet incorporated into the model.
Model.Prediction	predict(int horizon) Make a prediction based on current model parameters and observations.
Model.Delta	recalculate() Process recently recorded observations.
void	record(QuickSerializable obs) This method assumes the observation occurred at time now.
void	record(QuickSerializable[] obs) This method assumes the observations occurred at time now.
void	record(QuickSerializable[] obs, Time time) Record the observations and mark that they occurred at a particular time.
void	record(QuickSerializable obs, Time time) Record the observation and mark that it occurred at a particular time.
void	serialize(OutputBuffer buffer) Add the object to the buffer.
void	setClients(int clients) Set the number of clients represented by this model
void	setMaxRelations(int num) Set the maximum number of distances to keep for each observation type.
String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

DEBUG

public static final boolean DEBUG

See Also:

Constant Field Values

class_tag

public static final String class_tag

See Also:

Constant Field Values

Constructor Detail

SemanticDistanceModel

public SemanticDistanceModel(Time now)

Construct a new model with default filter WeightedAvgFilter().

SemanticDistanceModel

public SemanticDistanceModel(int maxrelations,
                             Time now,
                             SemanticDistanceModel.Filter filter)

Construct a new model.

Parameters:

maxrelations - the max number of relations per key

now - the time this model was created (can be dynamically altered later with setMaxRelations)

filter - the filter used to recalculate semantic distance values.

SemanticDistanceModel

public SemanticDistanceModel(InputBuffer buffer)
                      throws QSException

Method Detail

serialize

public void serialize(OutputBuffer buffer)

Description copied from interface: QuickSerializable

Add the object to the buffer.

Specified by:

serialize in interface QuickSerializable

Parameters:

buffer - the output buffer to add the object to

record

public void record(QuickSerializable obs,
                   Time time)

Description copied from interface: ContinuousModel

Record the observation and mark that it occurred at a particular time.

Specified by:

record in interface ContinuousModel

Parameters:

obs - the observation

time - the time it occurred

record

public void record(QuickSerializable[] obs,
                   Time time)

Description copied from interface: ContinuousModel

Record the observations and mark that they occurred at a particular time.

Specified by:

record in interface ContinuousModel

Parameters:

obs - the observations

time - the time they occurred

record

public void record(QuickSerializable obs)

Description copied from interface: ContinuousModel

This method assumes the observation occurred at time now. (I.e., when the method was called)

Specified by:

record in interface ContinuousModel

Parameters:

obs - Any event, value, etc. that this Model understands.

record

public void record(QuickSerializable[] obs)

Description copied from interface: ContinuousModel

This method assumes the observations occurred at time now. (I.e., when the method was called)

Specified by:

record in interface ContinuousModel

Parameters:

obs - An array of events, values, etc., not necessarily all the same type, that this Model understands.

outstanding_observations

public int outstanding_observations()

Return the number of observations recorded but not yet incorporated into the model.

clear

public void clear(int num)

Description copied from interface: Model

Forget the least-recent recorded observations.

Specified by:

clear in interface Model

clear

public void clear()

Description copied from interface: Model

Forget all observations recorded since the last call to clear or recalculate.

Specified by:

clear in interface Model

loglikelihood

public double loglikelihood()

Description copied from interface: Model

Calculates the log-likelihood of all recorded observations. Only observations recorded since the last call to clear or recalculate are considered.

Specified by:

loglikelihood in interface Model

Returns:

a non-positive number equal to the logarithm of the probability of the observations (D) given the current model (M); log(p(D|M)). If no observations exist, it returns Double.NaN.

recalculate

public Model.Delta recalculate()

Description copied from interface: Model

Process recently recorded observations. The internal model parameters are updated to produce the model which maximizes the likelihood of the observations. Observations are forgotten after processing, as if clear were called. Different Models may provide different semantics for how prior parameters are included in the resulting ones. For instance, sufficient statistics may be added cumulatively, parameters may have finite moments, etc.

Specified by:

recalculate in interface Model

Returns:

A Delta storing the difference between the new model parameters and the old.

predict

public Model.Prediction predict(int horizon)

Description copied from interface: Model

Make a prediction based on current model parameters and observations.

Specified by:

predict in interface Model

Returns:

A Prediction, whose semantics depends on the particular subclass of Model.

outliers

public QuickSerializable[] outliers()

Description copied from interface: Model

Returns the recent observations which the model assigns the lowest likelihood. This method is useful both for standard outlier detections as well as for swapping in model segments using reverse lookup.

Specified by:

outliers in interface Model

Returns:

an array containing recent observations which the model did not expect.

add_delta

public void add_delta(Model.Delta d)

Incorporate a Delta from a foreign source into our model. Do not save the latest access times in the delta.

Specified by:

add_delta in interface Model

Parameters:

d - the delta

add_delta

protected void add_delta(Model.Delta d,
                         boolean save_times)

Incorporate a Delta with the latest access times in the table. This should be used to incorporate deltas we create to our own table.

Parameters:

d - the delta

save_times - save the latest access times in the delta in the model table.

add_segment

public void add_segment(SegmentedModel.Segment segment)

Description copied from interface: SegmentedModel

Incorporates the portion of the model contained in the specified Segment.

Specified by:

add_segment in interface SegmentedModel

Parameters:

segment - The Segment to add.

See Also:

SegmentedModel.choose_segments(int)

choose_segments

public void choose_segments(int num)

Description copied from interface: SegmentedModel

Selects the most-relevant num segments to retain, discarding all others.

Specified by:

choose_segments in interface SegmentedModel

Parameters:

num - The number of Segments to keep.

get_segment

public SemanticDistanceModel.Segment get_segment(QuickSerializable id)

Obtain a segment that contains the distance information between id and other types. This segment can be swapped to other SemanticDistanceModels.

Parameters:

id - the type from

Returns:

a segment containing the distances from id to other types. null if we don't know about id

getTable

public SemanticDistanceModel.Table getTable()

Get the semantic distance table.

Returns:

the semantic distance table of this model

setClients

public void setClients(int clients)

Set the number of clients represented by this model

getClients

public int getClients()

Get the number of clients represented by this model.

setMaxRelations

public void setMaxRelations(int num)

Set the maximum number of distances to keep for each observation type. The table keeps around the num semantically closest values for each observation type.

Parameters:

num - the new max number of distances.

toString

public String toString()

Overrides:

toString in class Object

main

public static void main(String[] args)
                 throws Exception

Self test.

Exception