trending

README

go-trending

Trending algorithm based on the article Trending at Instagram. To detect trends an items current behavior is compared to its usual behavior. The more it differes the higher / lower the score. Items will start trending if the current usage is higher than its average usage. To avoid items quickly become non-trending again the scores are smoothed.

• Configurable and simple to use
• Use your own clock implementation, e.g. for testing or similar
• Use any time series implementation as backend that implements the TimeSeries interface

Details

Uses a time series for each item to keep track of its past behavior and get recent behavior with small granularity. Computes the Kullback-Leibler divergence between recent behavior and expected, i.e. past, bahavior. Then blends the current item score with its past decayed maximum score to get the final score.

Examples

Creating a default scorer

import "github.com/codesuki/go-trending"

...

scorer := trending.NewScorer()

Creating a customized scorer

Parameters

• Time series: is used for creating the backing TimeSeries objects
• Half-life: controls how long an item is trending after the activity went back to normal.
• Recent duration: controls how much data is used to compute the current state. If there is not much activity try looking at larger duration.
• Storage duration: controls how much historical data is used. Trends older than the storage duration won't have any effect on the computation. The time series in use should have at least as much storage duration as specified here.

import "github.com/codesuki/go-trending"

...
func NewTimeSeries(id string) TimeSeries {
    // create time series that satisfies the TimeSeries interface
    return timeSeries
}

...

scorer := trending.NewScorer(
    WithTimeSeries(NewTimeSeries),
    WithHalflife(time.Hour),
    WithRecentDuration(time.Minute),
    WithStorageDuration(7 * 24 * time.Hour),
)

Using the scorer

import "github.com/codesuki/go-trending"

...

scorer := trending.NewScorer()

scorer.AddEvent("id", time)
// add more events. maybe using an event stream.

...

trendingItems := scorer.Score()

Documentation

GoDoc is located here

License

go-trending is MIT licensed.

Documentation

Index

• type Option
  • func WithClock[K comparable](clock timeseries.Clock) Option[K]
  • func WithCountThreshold[K comparable](threshold float64) Option[K]
  • func WithHalfLife[K comparable](halfLife time.Duration) Option[K]
  • func WithMaxResults[K comparable](maxResults int) Option[K]
  • func WithRecentDuration[K comparable](recentDuration time.Duration) Option[K]
  • func WithScoreThreshold[K comparable](threshold float64) Option[K]
  • func WithSlidingWindow[K comparable](creator SlidingWindowCreator[K]) Option[K]
  • func WithStorageDuration[K comparable](storageDuration time.Duration) Option[K]
  • func WithTimeSeries[K comparable](creator TimeSeriesCreator[K]) Option[K]
• type Score
• type Scorer
  • func NewScorer[K comparable](options ...Option[K]) Scorer[K]
  • func (s *Scorer[K]) AddEvent(id K, time time.Time)
  • func (s *Scorer[K]) Score() Scores[K]
• type Scores
  • func (s Scores[K]) Len() int
  • func (s Scores[K]) Less(i, j int) bool
  • func (s Scores[K]) Swap(i, j int)
• type SlidingWindow
• type SlidingWindowCreator
• type TimeSeries
  • func NewMemoryTimeSeries[K comparable](id K) TimeSeries
• type TimeSeriesCreator

Types

type Option

type Option[K comparable] func(*options[K])

func WithClock

func WithClock[K comparable](clock timeseries.Clock) Option[K]

func WithCountThreshold

func WithCountThreshold[K comparable](threshold float64) Option[K]

func WithHalfLife

func WithHalfLife[K comparable](halfLife time.Duration) Option[K]

func WithMaxResults

func WithMaxResults[K comparable](maxResults int) Option[K]

func WithRecentDuration

func WithRecentDuration[K comparable](recentDuration time.Duration) Option[K]

func WithScoreThreshold

func WithScoreThreshold[K comparable](threshold float64) Option[K]

func WithSlidingWindow

func WithSlidingWindow[K comparable](creator SlidingWindowCreator[K]) Option[K]

func WithStorageDuration

func WithStorageDuration[K comparable](storageDuration time.Duration) Option[K]

func WithTimeSeries

func WithTimeSeries[K comparable](creator TimeSeriesCreator[K]) Option[K]

type Score

type Score[K comparable] struct {
	ID          K
	Score       float64
	Probability float64
	Expectation float64
	Maximum     float64
	KLScore     float64
	Count       float64
	RecentCount float64
}

type Scorer

type Scorer[K comparable] struct {
	// contains filtered or unexported fields
}

func NewScorer

func NewScorer[K comparable](options ...Option[K]) Scorer[K]

func (*Scorer[K]) AddEvent

func (s *Scorer[K]) AddEvent(id K, time time.Time)

func (*Scorer[K]) Score

func (s *Scorer[K]) Score() Scores[K]

type Scores

type Scores[K comparable] []Score[K]

func (Scores[K]) Len

func (s Scores[K]) Len() int

func (Scores[K]) Less

func (s Scores[K]) Less(i, j int) bool

func (Scores[K]) Swap

func (s Scores[K]) Swap(i, j int)

type SlidingWindow

type SlidingWindow interface {
	Insert(score float64)
	Max() float64
}

type SlidingWindowCreator

type SlidingWindowCreator[K comparable] func(K) SlidingWindow

type TimeSeries

type TimeSeries interface {
	IncreaseAtTime(amount int, time time.Time)
	Range(start, end time.Time) (float64, error)
}

func NewMemoryTimeSeries

func NewMemoryTimeSeries[K comparable](id K) TimeSeries

type TimeSeriesCreator

type TimeSeriesCreator[K comparable] func(K) TimeSeries