Time Series in Finance: the array database approach

Outline

• What are time series as used in business and finance?
• What do typical systems (FAME, S-PLUS, SAS, KSQL) do to support them?
  I include challenge queries for you to try against your favorite SQL or alternative database management system.
• What are the relevant strengths of each system?
• Is there an ideal time-series language?
• Fintime, a time series benchmark
  http://cs.nyu.edu/cs/faculty/shasha/fintime.html
• Which research in temporal data mining might help finance?
• Time series bibliography.
• Brief glossary of statistical concepts.

Scenario

• Group discovers the desirability of ``pairs trading.''
• The goal is to identify pairs (or in general groups) of stocks whose prices track one another after factoring in dividends.
  One can make money (lots was made in the 1980s), because, for example, if you know that the two banks Chase and Citibank track one another (their difference is a stationary process) and Chase goes up but Citibank doesn't, then buy Citibank and sell Chase. Unless there is a good external reason for the difference, that is. (This is simplistic: one needs a linear combination of the two price series (once the market factor is accounted = for (removed) and dividends included) to be stationary. But this is the idea.)
• Typical challenge queries from such an application:
  • Correlate the price histories of two stocks or in general among many stocks and options. (For most traders, returns are more interesting than prices, because they have better statistics: a stock that trends up over the years has an unstationary mean, but perhaps a stationary return. So, one performs correlations over ``returns.'' The return at time t is ln(price(t)/price(t-1)).)
  • Perform the correlation over certain time intervals to evaluate the stationarity.
  • The correlation might be weighted: recent history counts more than distant history

So, What's the Database Problem?

• The raw data comes in the form of ticks (stock, quantity, price) and can be stored in a relational database without a problem.
• The fundamental difficulty is that the relational model does not take advantage of the order of rows. Whereas one can perform an ``order by'' query and manipulate the data in some other language, one cannot natively manipulate the ordered data using select, from, and where.
  Arguably, this is good for data independence, but it is bad for time series.
• Realizing this, the traders curse a lot and tell their programmers to cobble something together. The programmers do so and create a piece of software that is part spreadsheet, part special purpose database, with lots of C++ code.
  Employment goes up.
• Note 1: Joe Celko shows how to bend SQL to the task of simulating order in his popular and excellent book The SQL Puzzle Book, published by Morgan Kaufmann. Usually, the bending results in a loss of efficiency. It also works only for special cases.
• Note 2: Object-relational systems address this issue by providing special data types and user-defined functions. My goal is to show the array database approach. The two are converging, but the array people have been at it longer and have some good ideas.

What Are Time Series

• Time series = sequence of values usually recorded at regular increasing intervals
  (yearly, monthly, weekly, ... secondly).
  Regularity is critical: without regularity, moving averages, autocorrelations, and volatility would not make sense (e.g. if I have a sequence of daily price closings and then 1,000 values within one day, the moving average covering the entire sequence doesn't make much sense).
  Non-regular time series are also of interest (e.g. the history of stock splits), but we can say less about them.
• Time series also exhibit historicity: the past is an indicator of the future. That is why autoregression can be used to predict the future of sales and why the past volatility may predict future volatility.
• Notice that temporal logics, for example, use the fact that the i+1st value in a sequence is at a later time than the ith value, but assume neither regularity nor historicity. Temporal query languages are equally agnostic about this question.

System Support for Time Series

• We want to be able to create time series, manipulate them, keep them in persistent storage, and display them in reports.
• Time series have frequencies, but may not have values for every time instance at the stated frequency, e.g. business day has the frequency of a day but has no values on holidays or weekends.

  On the other hand, time frequencies with gaps can present problems in international markets. For example, some Asian stock markets are open on Saturdays. Different markets don't have the same holidays in general. One solution is to store values without gaps everywhere (i.e. every day).

• Then the question becomes: How to fill the gaps?
  The answer has to do with the kind of value stored.
• The values associated with each time are of two general types (we borrow this distinction from the FAME system):
  • level values stay the same from one period to the next in the absence of activity. For example, inventory is a level value, because inventory stays the same if you neither buy nor sell.
  • flow values are zero in the absence of activity. For example, expenses go to zero if you buy nothing.
• This distinction turns out to be important when interpolating missing values and for time scale conversion.

Operations on Time Series Data

• A typical framework is that of the FAME system, since it embodies an excellent understanding of the special properties of time series. FAME stands for forecasting, analysis and modeling environment
  FAME information systems, Ann Arbor Michigan.
  www.fame.com
• Data Preparation (i.e. interpolating and time scale conversion) -- curve-fitting
• Queries (e.g. moving averages and sums) -- aggregates over time.
• Forecasting (e.g. statistical or data mining-based extrapolation) -- regression, correlation, Fourier analysis, and pattern-finding.

Data Preparation

• Sometimes it is necessary to relate time series that don't have the same time frequencies, e.g. mine is days and yours is weeks.
• Converting one to the other depends on the kind of value one has.
  For example, if the daily time series denotes inventory level, then converting from daily to weekly simply entails taking the inventory level at the end of each week.
  On the other hand, if the daily time series denotes revenues (a flow type of value), then one must sum them up to get weekly revenues.
• Time conversion can force interpolation too, especially when graphing values. Typically, systems use various spline techniques such as a cubic spline to interpolate missing values.
• Interpolation can be more involved than mere curve-fitting, however as in the Black-Derman-Toy interpolation of the yield curve. So, users should be able to add in their own interpolation functions.

Query Types -- try these on your Database

• cumulative sum, e.g. year to date sales.
• moving averages, e.g. 30 day average of stock prices.
• nth best, e.g. 5th best sales region.
  median --- one in the middle
  rank -- associate ordinal to each value based on its sort order.
• discretize --- e.g. rank the revenues by whether they are in the top third, the middle third, or the bottom third.
  This implies discovering the boundaries and then using them in an update query.
• year-to-year comparisons --- e.g. balance of trade of this year vs. last.
• accounting functions --- e.g. average growth rate, amortization, internal rate of return and so on.
• statistical functions --- e.g. autocorrelation, and correlation between two series.

Forecasting

• Before the 1920s, forecasting meant drawing lines through clouds of data values. Yule invented the autoregressive technique in 1927, so he could predict the annual number of sunspots. This was a linear model and the basic approach was to assume a linear underlying process modified by noise. That model is often used in marketing (e.g., what will my sales of wheat be next month).
• Autoregression uses a weighted sum of previous values to predict future ones. There are also seasonal autoregressive models.
• These and other models are incorporated in time series products such as FAME, SAS and SPLUS.
• In options finance, the basic approach is to assume that the price of an equity is based on a random walk (Brownian motion) around a basic slope. The magnitude of the randomness is called the volatility. In a result due to Norbert Wiener (he worked it out to shoot down bombers over London), for this model, the standard deviation of the difference between the initial price and the price at a certain time t rises as the square root of time t.

Steps in a Typical FAME Session

• Specify frequency. Say monthly, starting at January 1, 1996 and ending at the current time.
• Create sales and expenses time series by importing these from a file or typing them in. Specify that these are flow type time series.
• Create a new time series:
  formula profit = sales - expenses.
• Create a fourth time series with weekly frequency on inventory. Specify that inventory is a level type time series.
• Convert the first three time series to a weekly frequency (by dividing the monthly values by 4.2 or by constructing a cubic spline to make the sales, expenses, and profits curve look smooth).
  This interpolation depends on knowing that sales and expenses are flow-type values.
• Now, use autoregression to predict future time series values.

S-Plus

• S-PLUS is an interpretive environment for data analysis, not specifically oriented towards time series, but based on vectors.
  http://www.mathsoft.com/splus/
  http://www.math.umbc.edu/~arghya/Splus/splus.html

  S-Plus is derived from the S language developed at ATT Bell Laboratories by Becker, Chambers and Wilkens, but development now belongs to MathSoft Inc.

• S-Plus has
  • standard statistical and mathematical functions, including anova, wavelets, bootstrapping to check for model overfitting, and so on.
  • graphics capabilities for visualization (user testimonials say this is a particular strong point).
  • combinatorial data mining (e.g. inference of classification trees and regression).
  • an object-oriented language allowing encapsulation and overloading. For example, objects of a certain class will have a special plot function.
• Applications in finance include statistical models for futures trading, e.g., correlation of Australian and US bonds, and other single or multi-sequence correlations.

S-Plus, some details

• A nice reference to the language on the web has been written by
  Carlos Alzola and Frank Harrell. It is entitled An Introduction to S-Plus and the Hmisc and Design Libraries ) at the University of Virginia. (Hmisc is a set of add-on functions that are truly miscellaneous.)
  http://fharrell.biostat.virginia.edu/s/index.html
• The S-Plus programming model is vector-oriented. Here are some typical statements:
  • sum(age < mean(age)) gives the count of people who are younger than the mean.
  • ageg <-- ifelse(age < 16, 'Young', 'Old') assigns to the vector ageg, a sequence of Young/Old values thus discretizing the data.
  • find positions of elements in a table that have the values of x, thus performing a select while maintaining order.
• So, one can create vectors, do statistics on them, and perform selection-style operations on them.
• The S-Plus implementation is also vector-oriented. In their case, this creates a performance discontinuity. S-Plus is slow for large databases, even for data that exceeds RAM size. Below RAM size, it is very fast. For this reason, S-PLUS is often used with SAS, because SAS has some data management capabilities as we'll see.

SAS

• SAS (www.sas.com) is a leading vendor of statistical databases. (Originally, it stood for Statistical Analysis System, but now the acronym stands for itself.)
• A SAS programmer interacts with the system by parametrizing varioius functions as the following example shows:

  proc forecast data=leadprd
  ar=1 /* number of autoregressive parameters to estimate */
  interval=month /* frequency of input time series */
  trend=1 /* fit a constant trend model */
  method=stepar /* use stepwise autoregressive method */
  out=leadout1 /* create output data set for forecasts */
  lead=12 /* number of forecast periods */
  outlimit
  outstd;
  var leadprod;
  id date; /* identification variable */
  run;

• In addition, SAS has an integrated, fairly complete, SQL dialect called Proc SQL.
• SAS has modules for data mining and data warehousing as well.
• To obtain support for time series data management in SAS, you purchase a library called ETS that enables you to do
  • interpolation,
  • econometric forecasting (e.g. maximum likelihood method)
  • financial analysis (analysis of fixed rate mortgages, adjustable rate mortgages etc.),
  • time series forecasting (exponential smoothing, ARIMA, dynamic regression).
• By reputation, SAS is harder to extend than S-Plus, but SAS programmers have become clever with the language over the years. The libraries are very rich.
• Bottom line: S-Plus is more flexible for special purpose problems and is fast for problems that fit into RAM. It also has great graphics. Combining the two works well if the application selects a subset of data and then works on it (like a loose-coupling expert system).

KDB

• KDB is a database system implemented on top of the K language environment (produced by Kx systems www.kx.com), an array language. Data structures (e.g. tables) can be interchanged between the two and functions can be called in both directions. A free trial version can be downloaded.
• KDB supports an SQL dialect called KSQL. KSQL is easy to learn (for anyone fluent in SQL) and carries over the speed and functionality of K to large data manipulation. KDB also supports most of standard SQL.
• The basic data structure in KSQL is the arrable (array-table) which is a table whose order can be exploited. In this way, it is very similar to S-Plus.
• Arrables are non-first-normal form objects: a field of a record can be an array. For example, an entire time series can be stored in a field.
• Like most modern SQLs, KSQL allows the inclusion of user-defined functions inside database statements. Unlike other SQL's KSQL allows functions to be defined over arrays as well as scalars.
• Like classical SQL, KSQL has aggregates, grouping, selections and string matching, and so on.
• KSQL adds many useful functions to SQL, permitting economical expression and often better performance by exploiting order. For example, finding the fifth highest value is a linear time operation in KSQL but requires a self-join in SQL, which is only sometimes linear time.
• KDB can function as a high performance distributed server with full recovery and distributed consistency. (KDB guarantees consistency by using ordered atomic broadcast and a replicated state machine design rather than two phase commit.)
• Some performance notes
  • KDB can do 40,000+ TPC/B transactions per second against a 100 megabyte database on a Pentium 2.
  • Typical real-world application (at Lehman Brothers): time series: keyed by instrument id, date.
    Data: 11 million rows, couple of hundred columns, typical query returns 7500 rows with 15 columns. 10 gigabytes.
    Query: is find all information having to do with a given set of instruments at a given date. This returns 7500 rows in less than a second.

KSQL Basics -- an extended example

• Create tables (arrables, really, but we'll conform to standard terminology, even though it's slightly inexact) either through K or within .t scripts. We will use .t scripts for now and will set up a simple trade database and then go through it line by line (you can copy out this file and run it, provided you also copy out newstat.k which will be given later).

  'trade.t'
  
  n:1000	# number of trades
  
  'generate'
  stock:([name:('Alcatel','Alstom','AirFrance','FranceTelecom','Snecma','Supra')]
   industry:('telecom','engineering','aviation','telecom','aviation','consulting'))
  
  trade:([]
   stock:n rand stock.name,
   price:50 + .25 * n rand 200,
   amount:100 * 10 + n rand 20,
   date:date['1998-01-01'] + n rand 365)
  
  trade:'date' asc trade
  
  show'trade'
  
  'last price (in time) by stock, month'
  'we get a vector and then take the last'
  t1:select last price by stock, date.month from trade
  
  
  'trade volume by month and industry'
  show select volume:sum amount * price 
   by date.month, stock.industry from trade
  
  '5 day moving avg price by stock, month'
  t3:select 5 avgs price 
  by stock, date.month
  from trade
  
  \\l newstat.k
  
  
  '5 day moving max price by stock, month'
  t4:select movingmax[5,price] by stock, date.month from trade
  
  

• Here is the newstat.k file.

  / newstat.k
  
  / moving max of last num elements
  movingmax:{[num; vec]
  	minel: &/vec
  	vec: ((num-1) # minel), vec
  	size: #vec
  	indexes: (num-1) + !(size-(num-1))
  	findmax:{[n;v;i] |/v[(i-(n-1))+!n]}
  	:findmax[num;vec]'indexes
  }
  
  

Commentary on Part of trade.t

• The line

  t1:select last price by stock, date.month from trade
  

  performs a group by stock and year-month in the trade table. Mathematically, the by clause partitions the records based on distinct stock/year-month values, like a group by in SQL. What is different is that each partition is guaranteed to be ordered in the same way as in the table (arrable), in this case, by ascending order of date. For each partition corresponding to stock s and year-month x, the

   select last price 

  part will return s, x, and p where p is the price of the last record in the partition corresponding to s and x. Because the table is ordered by date, the last record will be the one with the most recent date.
• In the select statement

  show select volume:sum amount * price
   by date.month, stock.industry from trade
  

  
  (i) the date.month expression in the by clause gives each distinct year-month value in the date column. This is a big convenience in time series applications. The by clause groups by these year-month values.
• The lines

  '5 day moving avg price by stock, month'
  t3:select 5 avgs price by stock, date.month from trade
  

  use the avgs function which, given a vector (price for each stock in this case), returns a vector of the same length, computing a moving average. 5 avgs computes the five day moving average.
• The line

  \\l newstat.k
  

  loads one or more k functions from the file newstat.k, in this case a single moving maximum taking two arguments, a number and a vector.
• The line

  t4:select movingmax[5,price] 
   by stock, date.month from trade
  

  uses the movingmax function defined in the K file newstat.k to compute the 5 day moving maximum of prices grouped by stock and year-month. The movingmax function takes a scalar and a vector and that's exactly what the by clause delivers.

Two of our Challenge Queries using Vectors

• Dot product of prices offset by 10 days for each stock

  \dotprod:{[x;y] +/(x*y)}
  t4: select dotprod[(10 drop price), (-10 drop price)] 
   by stock from trade
  

• The 10th highest price for each stock

  t5: select last 10 first price 
   by stock from 'price' desc trade
  

• You should be able to do the rest assuming that you can put in arbitrary functions.

Is There an Ideal Time Series Language?

• The ability to treat sequences as first class objects on which one can do useful operations within the database system.
  FAME, S-Plus, SAS, and KSQL.
• The ability to treat multiple sequences together for correlations and other purposes.
  FAME, S-Plus, SAS, and KSQL.
• A basic collection of functions, e.g. aggregates, moving aggregates, statistics, cross-correlations, interpolation, etc.
  FAME, S-Plus, SAS, and KSQL.
• The ability to integrate user-defined functions into the query engine. My belief: user-defined functions are necessary for time series. There is no analogue to relational completeness that will satisfy all (or even most) time series applications. Prove me wrong if you can.
  KSQL and S-Plus; FAME and SAS to some extent.
• The main helpful database amenities include a rich relational vocabulary and the ability to work efficiently with disk- as well as RAM-resident data.
  KSQL, FAME and SAS.
• Treat time specially, e.g. be able to group by date.month or date.year of KSQL.
  FAME, SAS, S-Plus with libraries, and KSQL.
• Treat values appropriately, e.g. with the level and flow concepts of FAME.
  FAME, natively. The others require libraries.
• Give support for bitemporality (discussed next) at least as an extension.
  No system, natively.
• Object-relational database vendors have begun to field products with time-series extensions. It will be interesting to see how well they measure up.

The Bitemporal Challenge

• Even in finance, there is more to life than looking at flows and levels. Sometimes, one must do historical searches and understand the state of the enterprise in the past or future.
• Bitemporal = two times (Snodgrass, Ahn, Jensen, and others) (A very nice review paper was published in Information Systems:
  ``Semantics of Time-Varying Information Christian S. Jensen, Richard T. Snodgrass Information Systems, 21(4): 311-352 (1996) )
  The two times are valid time (when a fact holds) and transaction time (when the fact was asserted).
• Using this model, one can ask:
  What was Rick's salary on April 1, 1998?
  Suppose the answer was $1,500 per week, given the information we know now (i.e. according to the latest transaction). But somehow we sent Rick a check for much more. This gives rise to a new question:
  What did we believe on March 28, 1998 (when payroll printed out Rick's 100,000 dollar weekly check) about Rick's salary valid on April 1, 1998? Thus, we look at the transactions concerning Rick's salary that preceded March 29, 1998 and see what was asserted about Rick's salary as of April 1, 1998. If the asserted value was 100,000 dollars per week, then we know that the mistaken payment was due to a database error, not a payroll processing error.
  So, bitemporal databases are useful to track the cause of failures in operations.
• This example also shows their general usefulness for human resources applications, What is the job history of this candidate within the organization?
• Or the more challenging: How has the job history of this candidate been corrected?
• For trading applications, we can use bitemporality to track the correlations between predictions of earnings and price, What did we believe as of January of this year that first quarter earnings would be?
• Unitemporal example for those with SQL skill: Rick Snodgrass suggested the following example to test your system's temporal acumen. The salary of employees changes over time, usually in a positive direction. Each salary for an employee therefore has a time when it is valid, marked by starttime and endtime, the notion being that the salary becomes valid at starttime and ceases being valid at endtime. Your task is to compute the average salary over time as a set of rows having the average salary as well as the start and end times. Two consecutive intervals with the same average salary should be merged. Send me mail if you want to see a KSQL version.

FinTime a Financial Time Series Databases

The design of this benchmark is joint work with Kaippallim Jacob of Morgan Stanley (kjacob@ms.com) and its full description can be found at http://cs.nyu.edu/cs/faculty/shasha/fintime.html.
Here we present a summary of that benchmark.

Goal

The FinTime benchmark tries to model the practical uses of time-series databases in financial applications. The models suggested in FinTime reflect two frequently occurring cases in the financial industry, namely, a historical market data system and real-time price tick database. These models are quite similar to two well-studied models in the relational world, namely, decision support systems and OLTP systems. FinTime also suggests and defines metrics that capture three useful dimensions of any time-series system, namely, performance in a single-user mode, performance in a multi-user mode and the price to performance ratio.

Before deciding on a model, we have to examine the different parameters that determine a model for time-series system. The most important parameters that influence a time-series database system are:

1. Periodicity of data (Regular/irregular)
2. Density of data (Dense/Sparse)
3. Schedule of updates (periodic, continuous)
4. Types of queries (Simple/Complex)
5. Time interval between queries (Ad hoc/Batch)
6. Number of concurrent users (Few/Many)

Combinations of these factors will give rise to 64 possible models but for simplicity we can focus on the following commonly occurring cases in the financial industry