Abstract:
A computer system for calculating a quantity from a set of input values. The computer system comprises a database that is configured to store a sequence of first input values x n  wherein n=1, 2, . . . i, wherein for any value of n, x n  lies between x n+1  and x n−1  in the sequence. Each value of x has associated with it a second input value y n , a conversion value p n  that is calculated from y n  according to a conversion algorithm, and an output value z n , wherein z n =z n−1 +p n . The database is configured to store the plurality of output values z n .

Description:
FIELD OF THE INVENTION 
       [0001]    The present invention relates to databases for storing data, and in particular to computer-implemented methods of constructing a database, storing data in the database, and/or methods of manipulating data stored in the database. 
       BACKGROUND OF THE INVENTION 
       [0002]    A database is a structure for storing and relating data within e.g., a computer system. Different database architectures exist depending on the intended usage. The primary use for general purpose databases is to manage and facilitate data entry and retrieval in relation to the relevant application. A recent trend has been the emergence of specialized database architectures optimized to work with specific application domains. 
         [0003]    Complex event processing (CEP) is a technology for low-latency filtering, correlating, aggregating, and/or computing on real-world event data. Such data is usually generated at high frequencies and so needs to be saved in an appropriate database to allow it to be evaluated, whether in real time, or at a later stage. Several specialized database products have emerged which attempt to store such data, which is generated in quantities that normally overwhelm general purpose databases. 
         [0004]    The following products are available for use in CEP applications, and provide different functionalities for manipulating CEP data. 
         [0000]    
       
         
               
               
               
             
           
               
                   
               
               
                 Product 
                 Description 
                 Technology 
               
               
                   
               
             
             
               
                 Vhayu velocity  
                 High performance proprietary  
                 Proprietary, non- 
               
               
                   
                 database optimized to work  
                 relational in-memory 
               
               
                   
                 with high-frequency financial  
                 database 
               
               
                   
                 market data 
                   
               
               
                 KX systems 
                 High performance database  
                 Optimized, column-based 
               
               
                 KDB+ 
                 to monitor real-time events  
                 database 
               
               
                   
                 and detect and report faults  
                   
               
               
                   
                 for data-intensive applications 
                   
               
               
                 StreamBase 
                 Event processing platform  
                 Integrated development 
               
               
                   
                 which allows for development  
                 environment along with 
               
               
                   
                 of applications that query and  
                 specialized compiler 
               
               
                   
                 analyze high-volume real-time  
                   
               
               
                   
                 data streams 
               
               
                   
               
             
          
         
       
     
         [0005]    These products aim to provide improvement of both underlying database technologies and processing capabilities. However, data storage and querying or retrieval of the data is still carried out according to conventional processes. While these databases are well-suited to performing traditional transaction-oriented operations, they do not provide an efficient means for allowing large amounts of contiguous data to be accessed and/or evaluated, other than standard querying methods. 
         [0006]    Such requests for large amounts of contiguous data are relevant to the provision of descriptive statistics where the importance of individual records is less than the overall description. Descriptive statistics are now becoming increasingly important especially for high-frequency high-volume data applications. 
         [0007]    The process of evaluating large contiguous datasets is central to responding to statistical descriptive data requests. 
         [0008]    The financial services community consists of data providers and clients. Data providers deal with both large institutional clients (e.g., banks) and smaller clients (e.g., retail investors). Dealing with the larger clients is either done directly or through 3rd party vendors (e.g., Vhayu) to provide them with all market data in order to allow for the construction of sophisticated and accurate statistical variables. However, at present this is not possible with smaller clients due to costs associated with the large bandwidth and computational requirement needed for delivering the complete market feed. Therefore, smaller clients are only provided with market snapshots or summaries, which only allow for variable approximations. 
       SUMMARY OF THE INVENTION 
       [0009]    In a first aspect, the present invention provides a database for storing data, which is configured to generate an intermediate description of the stored data, so as to allow more efficient manipulation of the stored data. 
         [0010]    More particularly, the first aspect of the present invention may provide a database that is configured to store a sequence of first input values x n  wherein n=1, 2, . . . i, 
         [0011]    wherein for any value of n, x n  lies between x n+1  and x n−1  in the sequence, and has associated with it: 
         [0012]    a second input value y n ; 
         [0013]    a conversion value p n  that is calculated from y n  according to a conversion algorithm; and 
         [0014]    an output value z n , wherein z n =z n−1 +p n ; 
         [0015]    the database being further configured to store the plurality of output values z n . 
         [0016]    The database is part of a computer system for calculating a quantity from a set of input values. 
         [0017]    The first input value x n  is generally a numerical value and is typically a time value. 
         [0018]    The second input value y n  may be a variable describing a financial transaction, e.g., price or volume of trade. 
         [0019]    The conversion value p n  may be equal to y n . In this case, the output value z n  stored in the database is the cumulative total of all the second input values y n  from 1 to n. Alternatively, the output value z n  may be e.g., 
         [0000]    
       
         
           
             
               
                 [ 
                 
                   
                     ∑ 
                     1 
                     n 
                   
                    
                   
                       
                   
                    
                   
                     y 
                     n 
                     2 
                   
                 
                 ] 
               
                
               
                   
               
                
               
                 or 
                  
                 
                     
                 
                 [ 
                 
                   
                     ∑ 
                     1 
                     n 
                   
                    
                   
                       
                   
                    
                   
                     
                       y 
                       n 
                     
                      
                     
                       y 
                       n 
                     
                   
                 
                 ] 
               
             
             , 
           
         
       
     
         [0000]    or the cumulative total of a different function p n  of the second input value y n . 
         [0020]    By providing a database in which the second input value y n  (e.g., the price of a stock) is stored in cumulative form within the output value z n  the database stores the second input value in intermediate form, i.e. pre-computed or partially-processed form. This means that, in general, fewer operations are required to generate descriptive data from the database of the first aspect of the present invention, than is the case for conventional databases, in which the data is stored in raw, unprocessed form. 
         [0021]    Thus, in a second aspect, the present invention provides a computer-implemented method of calculating a quantity from a set of second input values y n  corresponding to a portion of a sequence of first input values x n  extending from n=a to n=b, comprising extracting from a database according to the first aspect of the invention at least an output value z n , wherein n=b. 
         [0022]    In general, the method of the second aspect of the invention also includes the step of extracting from the database a further output value z n , wherein n=a. 
         [0023]    Using the method of the second aspect of the invention in combination with a database according to the first aspect of the invention, it is typically possible to calculate the following quantities through the retrieval from the database of the output value z b  corresponding to the end of the data sequence of interest, and optionally also the output value z a  corresponding to the start of the data sequence of interest: 
         [0000]    
       
         
               
               
             
           
               
                   
               
               
                 Function p n   
                 Descriptive statistics available 
               
               
                   
               
             
             
               
                 p n  = y n   
                 Sum 
               
               
                 p n = y n   
                 Mean average 
               
               
                 p n  = y n   2   
                 Variance 
               
               
                 p n  = x n  · y n    
                 Correlation of first input values and second input values 
               
               
                   
               
             
          
         
       
     
         [0024]    Therefore, according to the method of the second aspect of the invention, a range of descriptive statistics relating to a contiguous data sequence may be generated by retrieving just two output values from a database according to the first aspect of the invention. This reduces retrieval costs compared to using a conventional database, where typically all data values in the sequence of interest have to be retrieved. Hence the costs associated with I/O bus usage and/or network bandwidth utilisation tend to be lower for the method of the second aspect of the invention, as compared to conventional data evaluation methods. The computational costs associated with the method of the second aspect of the invention also tend to be lower than for conventional methods. 
         [0025]    The reduction in computational costs associated with the method of the second aspect of the invention may be especially relevant in financial applications. The method of the second aspect of the invention may allow all end-users of market data (whether large institutional clients or smaller clients such as retail investors) to generate highly accurate and complex descriptive variables, as required, even if they are not able to access the entire market feed. This is because only small amounts of data need to be sent to the client, and only minimal computation needs to be performed by the client. 
         [0026]    In particular, if multiple requests are made that relate to the same data series, the costs of setting up a database according to the first aspect of the invention will be rapidly amortised. Effectively, the database of the first aspect of the invention allows for embedding a major portion of the data description within the stored data itself and thus reduces overall costs on a per request basis when the database is interrogated using the method of the second aspect of the invention. 
         [0027]    The cost of generating descriptive statistics using the database of the first aspect of the present invention generally has a low dependency on the size of the data sequence of interest. This is in contrast to conventional databases, in which the cost of generating descriptive statistics is approximately proportional to the size of the data sequence of interest. 
         [0028]    By reducing the cost of generating descriptive statistics, the database of the first aspect of the invention also reduces the cost of comparative experimentation e.g., comparison of two data sequences of interest, such as the variation of stock price over two different time periods. 
         [0029]    Effectively, any descriptive statistic having an embedded summation operator may be generated by using the method of the second aspect of the invention in conjunction with the database of the first aspect of the invention. 
         [0030]    The conversion value p n  of the first aspect of the invention may be a highly complex variable computed from a plurality of raw data values. For example, the conversion value p n  may be a customised index that provides partially-processed input variables for inclusion in the output value z n , which is used in calculations in response to user requests. 
         [0031]    This pre-computation of a highly complex variable or customised index may allow a reduction in the amount of data to be retrieved from the database in response to a user query and may also reduce the number of computational steps to be carried out in response to each query. In particular, the pre-computed variable may be re-used to answer different user queries, thus increasing overall efficiency. 
         [0032]    The raw data values used for calculation of the pre-computed variable may be weighted statically or dynamically. That is, each raw value may be assigned a specific weight when constructing the pre-computed variable (static weighting) or the weight may vary with time (i.e. may be updated for each record). 
         [0033]    In the case of dynamic weighting, each weighted variable (or index) is expensive to produce, and so the cost savings associated with providing a pre-prepared index that can be re-used several times in response to user queries are particularly high. 
         [0034]    As an example, in the context of financial applications the concept of providing a conversion value p n  that is a complex function of a plurality of measured values can be used to construct a market capitalization weighted index of stock prices, where the weight of each stock in the index can change based on its changing market capitalization. Depending on usage of such an index, it could lead to a dramatic savings in both data and computational costs over performing index construction for each individual request. 
         [0035]    Pre-computation of data (to provide a conversion value p n  that is a complex variable) also allows for the execution of more complex multilevel operations which can be considered to be descriptions of descriptions. An additional financial applications example is that of construction of several indices each based on a set of stocks weighted according to their market capitalization (e.g., industrial companies index, telecommunications companies index). This would allow for combining indices (or even individual companies and indices) into different subsets in order to monitor their movement. 
         [0036]    In general, the database of the first aspect of the invention is configured to store values of x (the first input variable) that are evenly-spaced along the sequence of first input values, such that x n+1 −x n =x n −x n−1 . 
         [0037]    Typically, where x n  is a time value, the interval between successive time values is less than 0.5 s, preferably less than 0.1 s, most preferably less than 0.05 s. 
         [0038]    Typically also, the database is configured to store, e.g., a sequence of first values including over 1000 records, preferably over 10000 records. 
         [0039]    The database of the first aspect of the invention may be an adaptation of a conventional database. 
         [0040]    Many applications (e.g., the analysis of financial data) make use of time-series data which is continuously growing. In this case, an objective may be to find a subsequence of data in history that best matches the latest subsequence. In many cases, this search process has to be repeated for different subsequence lengths and/or locations. When the data is stored in a conventional database, each search process has to be started afresh, working from the raw data entered into the database. 
         [0041]    However, it has been found that in many cases, the process of matching subsequences consists of measuring the distance between corresponding records of the two individual subsequences and then taking the sum of these distance measures to obtain an end matching result. Since this operation has an embedded summation operator, it may be carried out using a suitably-configured database according to the first aspect of the invention, in conjunction with the method of the second aspect of the invention. 
         [0042]    More specifically, therefore, in some cases, the function p n  is a function of the distance between y n  and another second input value. The distance is typically a Euclidean distance, but may be another distance measure, such as Mahalanobis distance. 
         [0043]    Therefore, the database of the first aspect of the invention may be configured to calculate and store cumulative distance measures between e.g., a recent data sequence and a historical sequence. In this way, the distance between the subsequence of the recent data sequence and a corresponding subsequence of the historical data sequence may be calculated from the cumulative distance measures at the start and end of the subsequence. 
         [0044]    An advantage of using the invention for this application is that all requested subsequence sizes can be matched easily using only the difference between the start and end of the subsequence compared to all corresponding subsequences in the database. This greatly reduces the expense of having to perform distance measurements between individual records for every request. 
         [0045]    Although a substantial number of operations may have to be carried out to store cumulative values of the distance in the database, the retrieval and computing cost per request is low, as only two records need to be retrieved from the pre-computed data. The cost of building the database is therefore amortised rapidly with the number of requests processed. 
         [0046]    In some cases, the conversion value p n  is a function of both the second input value y n  and a further input value y′n associated with the first input value x n . For example, in some cases, p n =(y′n·y n ). In this case, the database of the first aspect of the invention may be used in conjunction with the method of the second aspect of the invention to determine the correlation of the second input value y n  with the further input value y′n corresponding to the portion of the sequence of first input values x n  of interest to the user. 
         [0047]    According to the method of the second aspect of the invention, data requests from the database of the first aspect of the invention consist of fetching the start and end of a required period of data. When a fetch/retrieval process is expensive due to latency (for example, when access to a database has to be requested or the data fetched over a network), it is advantageous to pre-fetch data in order to eliminate the latency overhead for additional fetch operations and to make use of temporal locality during caching. 
         [0048]    Therefore, the method of the second aspect of the invention may be adapted to include the further step of extracting additional values from the database that are adjacent to the value that is immediately of interest. These additional values may then be used in later calculations. 
         [0049]    The latency cost of retrieving multiple data values is close to that for retrieving a single value, and so the overall cost of retrieving multiple values is less than the cost of retrieving each value singly. The additional values are typically stored in a cache from which they may be extracted, as required, at a low latency cost. 
         [0050]    Advantageously, the multiple data values that are retrieved in a single fetch operation are a contiguous subsequence of data. This feature increases the efficiency savings associated with this adaptation of the method of the second aspect of the invention. 
         [0051]    The method of the second aspect of the invention, used in conjunction with the database of the first aspect of the invention may be particularly advantageous in the monitoring of banking operations, such as money transfers, and particularly in the detection of aberrant activity. 
         [0052]    Salient modes of fraud can be performed over longer periods of time using actions which are small in magnitude and long in terms of time period in order to hide amongst normal activity. Using the method of the second aspect of the invention, in conjunction with the database of the first aspect of the invention allows multiple mean averages to be monitored to detect any relative changes which may give evidence towards fraud. 
         [0053]    For example, the mean of transfers over the past five hours equaling the mean of the last hour could indicate normal activity, while any rise in the last hour&#39;s mean value would indicate possible fraud. Since we do not know the exact parameters or combinations of mean averages to monitor beforehand, a wide range of values must be explored. The ability to respond to different requests quickly and easily greatly facilitates this process. This approach can also be applied to different detection applications, e.g., exchange surveillance, which search for atypical activity based on historical determination of normal activity. 
         [0054]    As an extension to this application, many different sized mean averages could be monitored in parallel and in real-time. As mentioned, historical experimental evaluation of alternative mean sizes can also be performed easily and efficiently. These are both direct consequences of having cost-effective operations using the method of the second aspect of the invention in conjunction with the database of the first aspect of the invention. 
         [0055]    In general, in a database that is configured to store large amounts of data (over 1000 records and generally over 10,000 records), it is difficult for the user to access individual records. 
         [0056]    In general, the user of a database is primarily interested in the most recent records of the database. 
         [0057]    Therefore, in a third aspect, the present invention may provide a computer-implemented method of compiling a database at a time t, for storing previous values of a time-dependent variable, including the step of selecting a set of values of the time-dependent variable corresponding to a sequence of pre-determined time intervals measured back from time t. 
         [0058]    The database may be a database according to the first aspect of the present invention, but this is not essential. 
         [0059]    Typically, the time intervals for recently-entered records are more closely-spaced than the time intervals for older records. As a result, the database stores recent data with a high granularity, while more remote data is stored with a low granularity. 
         [0060]    In the case of e.g., a highly liquid financial market having high levels of data throughput per second, the database of the third aspect of the invention can be used to reduce the amount of data stored and subsequently sent to users. Intuitively, if a user is using this data at the millisecond level, his main interest will be in the most recent data, while a user who is interested in longer time periods (i.e. minutes, hours) will generally not require millisecond data precision. Therefore, the third aspect of the invention allows for handling of different client requests according to their needs (and/or constraints) in a more efficient manner. This reduces the total data sent by only sending what the user requires, thereby resulting in lower required network bandwidth and storage costs. 
         [0061]    In general, a database that is configured to store multiple inter-related sequences of data (such as, but not only, the database of the first aspect of the invention) will be subjected to sorting operations to monitor relative changes in the stored data. For example, the database may store specific market indicators for a set of financial instruments, and the data may be sorted according to the relative values of the market indicators. As the values of the market indicators change, further sorting operations will be required to update the database. 
         [0062]    Similarly, when a database is used to determine the extent of pattern matching between e.g., a recent data sequence and a historical data sequence the different matching results may be sorted to find e.g., the historical sequence that is the best match for the recent sequence. (Such pattern matching may be carried out using the database of the first aspect of the invention in conjunction with the method of the second aspect of the invention, but conventional databases and methods may also be used). 
         [0063]    However, such sorting operations may be expensive in terms of computational cost. Therefore, in a fourth aspect, the present invention may provide a computer-implemented method of sorting a dataset according to a predetermined sort criterion, comprising the steps of:
       traversing the dataset to determine if any values of the dataset are out of order according to the predetermined sort criterion, and   optionally sorting the dataset according to the predetermined criterion, if any values of the dataset are out of order.       
 
         [0066]    Thus, the computational cost of sorting the database is only incurred when the values of the dataset are out of order. If the values of the dataset are in order, the only cost that arises is the cost of traversing the data to determine this. 
         [0067]    This method is particularly effective in cases where the data (e.g., market indicators for financial instruments) has low volatility. In this case, sorting operations will rarely be required, and so use of the method may allow unnecessary sorting operations to be avoided, thus reducing overall computational cost. 
         [0068]    In particular, this method will be effective when the values of the dataset that determine the sort order (e.g., the market indicators of financial instruments) are calculated values determined as a function of a plurality of measured data values. Such calculated values typically have low volatility as they are relatively insensitive to changes in a single measured data value. This is especially the case if the values are calculated from data that is accumulated over long time periods. 
         [0069]    Such calculated values may be any one of the following:
       a) an average value of the measured data values;   b) the sum of the measured data values;   c) the maximum or minimum of the measured data values; or   d) the standard deviation of the measured data values.       
 
       Application Areas 
       [0074]    The invention is beneficial to applications that have data streams arriving continuously in a rapid manner with time-varying and unpredictable lengths. Traditional DBMS approaches with their limited memory are unsuitable for such applications which require rapid and continuous loading of data in addition to continuous querying and processing [M. Kontaki, A. N. Papadopoulos and Y. Manolopoulos, Adaptive similarity search in streaming time series with sliding windows,  Data  &amp;  Knowledge Engineering, Volume  63, Issue 2, (November 2007), Pages: 478-502]. An additional difficulty when attempting to perform standard analytic analysis to such data is the inability to obtain random access due to the continuous and unpredictable behavior of the data streams, which are only readable once or a limited number of times [P. Tsai, Mining top-k frequent closed itemsets over data streams using the sliding window model, Expert Systems with Applications: An International Journal, Volume 37, Issue 10, (October 2010), Pages: 6968-6973]. This requires modified analytic methods which provide fast answers to range queries that do not require multiple data scans. 
       Query Types 
       [0075]    The invention mechanism is capable of performing the following query types that are required for continuous data applications [F. Buccafurri and G. Lax, Approximating sliding windows by cyclic tree-like histograms for efficient range queries,  Data  &amp;  Knowledge Engineering , Volume 69, Issue 9 (September 2010), Pages: 979-997]:
       1. Point query: return the k-th data point of the data stream   2. Range query: return aggregate data within given time interval   3. Similarity query: return true whether a similar pattern occurs in the data stream [P. Capitani and P. Ciaccia, Warping the time on data streams,  Data  &amp;  Knowledge Engineering , Volume 62, Issue 3 (September 2007), Pages: 438-458]       
 
       Application Examples 
     Financial 
       [0079]    Market Transparency 
         [0080]    There is an increasing demand on financial market authorities to ensure their participants that their markets are fair and transparent. As trading volumes increase (hundreds of gigabytes per day in some markets), it becomes increasingly difficult to disseminate the data to all the participants. Only institutional and big investors can afford to have full access to such data. This by itself makes transparency a big issue when it comes to retail investors who cannot afford to receive such huge data. The difficulty is compounded when not only transactional data is required, but also more sophisticated data such as order movement and non-traditional execution information also becomes a necessity. What the invention allows for is the ability to present accurate aggregate data to all the participants upon which they can select their desired data using the customizable window sizes mechanism. This offers several advantages, first, computations are performed only once when storing the cumulative data. The user then requests the desired data range and receives only the start and end data elements which enable completion of the request. This results in a massive computational savings, especially with an increased number of users/requests since the upper bound on computation has been capped during data generation. Second, sending the user only the limits of the desired data range results in a huge reduction in bandwidth effectively placing a cap on the communications cost regardless of the data range request. Third, the ability to extract custom data ranges with no significant computational or bandwidth overhead allows for large amounts of simultaneous real-time analysis and experimentation. Fourth, allowing the participants to perform all their data queries without having to deliver the entire data range helps to protect the authorities&#39; data from unlawful usage or transfer. Finally, the invention provides a means for making the market fully transparent to all participants at the aggregational level, without disclosing all individual data ticks which are usually sold at high prices. 
       Telecommunications 
       [0081]    Network Traffic Monitoring 
         [0082]    Optimization of network utilization relies on the management of router and switch queues [E. Hernandez-Orallo and J. Vila-Carbo, Network queue and loss analysis using histogram-based traffic models,  Computer Communications , Volume 33, Issue 2 (February 2010), Pages: 190-201], [S. K. Tanbeer, C. F. Ahmed, B. Jeong and Y. Lee, Sliding window-based frequent pattern mining over data streams,  Information Sciences , Volume 179, Issue 227, November 2009, Pages 3843-3865]. In general, modeling a network consists of feeding traffic into finite sized queues at given service rates with the goal of determining information about queue utilization. Custom distributions and models are then used to model such traffic thus requiring the continuous determination of mean and volatility values. With increasingly larger networks, the amount of data generated and consequent computations increases, making it more difficult to tailor reports to individual user needs. The invention can make three major contributions to this problem:
       1. Currently fixed period monitoring reports (e.g., updated every 24 hours) are sent to users, this is due to the difficulty in constructing custom reports for each user based on their individual requirements. The invention allows for pre-computation and storage of data that can then be used by users to make their own custom reports, thereby alleviating the need for custom computation on a per-user level.   2. Statistical computations are easily transformable into cumulative computations and this allows for minimizing the amount of data and bandwidth usage per user request since only the end point data items of the required range need to be sent.   3. Increased data security for the provider since only data pertinent for the user request is sent rather than the entire data set.       
 
         [0086]    Intrusion Detection 
         [0087]    Information in data servers must be protected from network borne attacks [H. Li and S. Lee, Mining frequent itemsets over data streams using efficient window sliding techniques,  Expert Systems with Applications , Volume 36, Issue 2, Part 1, March 2009, Pages 1466-1477], [W. Wang, X. Guan and X. Zhang, Processing of massive audit streams for real-time anomaly intrusion detection,  Computer Communications , Volume 31, Issue 1 (January 2008), Pages: 58-72]. The two basic approaches consist of signature based detection where malicious behavior is detected by matching against previously stored prototypical attacks and anomaly detection where the profile of a normal user is maintained and an attempt is made to identify unacceptable deviation as a possible attack. The signature based approach can be adapted to make use of the invention&#39;s distance measurement mechanism where distances to a predefined set of signatures are recorded in real-time. The unique advantage of the invention is that not only distances to the complete signature are obtainable, but also distances to signature subsets are possible. This allows for quick experimentation and testing capabilities that do not require time consuming distance re-computation. Anomaly detection also benefits from the ability to perform calculations over data subsets. This is especially suitable for automated calibration approaches where multiple time periods can be measured simultaneously with no additional computation and vastly reduced bandwidth costs compared to a conventional approach. 
       Engineering 
       [0088]    Concrete Structures: 
         [0089]    Monitoring technology is used to track the performance of mass damping systems for tall concrete structures to enhance their damping and maintain their safety [J. M. W. Brownjohn, E. P. Carden, C. R. Goddard and G. Oudin, Real time performance monitoring of tuned mass damper system for a 183 m reinforced concrete chimney.  Journal of Wind Engineering and Industrial Aerodynamics  Vol. 8, No. 3, March 2010, pp. 169-179]. Accelerometers are connected to the structure and remotely monitored to provide real-time information to determine whether the structures displacement exceeds critical thresholds. A large-scale application of this monitoring technology over hundreds or even thousands of structures would require a unified data management system such as the invention in order to allow all users to perform their required monitoring tasks simultaneously. With the compute-once, use-by-many approach, it is possible to efficiently have many automated systems monitoring different phenomena simultaneously through the use of different sized windows and data combinations. In addition, the low bandwidth requirement resulting from the cumulative data storage structure means that the monitoring sites can be remotely located with little overhead communications cost. 
         [0090]    Drilling Optimization 
         [0091]    The goal is to optimize the drilling process to minimize cost while maintaining operational safety standards. This is done by continuously assessing the drilling process throughout the operation such that the overall rate of penetration is maximized based on cumulative footage drilled. The basic decision that must be made is to compromise between maximizing the utilization of the drill head and minimizing project down time due to a damaged drill head and the associated lead time to replace and order new parts. This is performed by continuously analyzing several variables such as weight on bit and rotary speed, applying such data to mathematical models and making a decision as late as possible to maximize bit head usage while not endangering progress of the drilling project. An advantage of a solution based on the invention is that time windows can be customized at any time with a negligible computational penalty. This is important when drilling through different geological formations, varying the drilling speed or even real-time calibration of models as work progresses and ensures the ability to perform comprehensive analysis regardless of the initial strategy. This also allows for evaluating several different models simultaneously using the same initial data. In addition, the low bandwidth requirement is an important feature especially when drilling in harsh remote areas where it is difficult to locate analysts and acquiring large bandwidth communication channels is often cost prohibitive. 
       Scientific Data Analysis 
       [0092]    Earthquake Prediction 
         [0093]    Early warning devices can provide a short warning before the arrival of major tremors based on the different propagation speeds of the various vibrations produced. This application is distinguished by large amounts of continuous data that need near instantaneous processing in order to be of value. Measurement centers can also make use of readings from neighboring centers in their effort to increase the detection time before an earthquake. Due to the large amount of data generated by each measurement device, this is prohibitively expensive for all but the largest centers. However, with the use of the invention as the data storage backbone, hundreds or even thousands of neighboring centers can share data making use of the low bandwidth requirement of the invention. In addition, the negligible calculation overhead for different sliding window sizes means that multiple levels of detection can be simultaneously performed in order to detect different size anomalies. This is important for experimentation since a large number of potential models can be simultaneously machine tested and potentially applied. 
         [0094]    Tropical Atmosphere Ocean 
         [0095]    In-situ environmental sensors are physically located in the environment they are monitoring and their time-series data is transmitted continuously to a single data repository [D. J. Hill and B. S. Minsker, Anomaly detection in streaming environmental sensor data: A data-driven modeling approach,  Environmental Modelling  &amp;  Software , Volume 25, Issue 9, September 2010, Pages 1014-1022]. There is a need for automated data quality assurance and control to detect and identify anomalous data that deviates significantly from historical patterns. Such anomaly detection can also be used in the field of adaptive monitoring where anomalous data indicates phenomena that may require further investigation. The invention can be used as the main data depository where the customizable sliding windows mechanism can be used to perform simultaneous data assurance tests, thereby adding an additional layer of sophistication for quality monitoring. In addition, the same mechanism can be used to simultaneously detect multiple abnormal phenomena or allow for straight forward changes in detection strategy with a no additional computational cost. An added advantage is the ability to serve other remote users with their data requests with only a minimal communications investment due to the low bandwidth data transmission mechanism. 
     
    
     DETAILED DESCRIPTION 
       [0096]    The following explanation and examples 1-8 demonstrate how a database according to the first aspect of the invention may be constructed and used to store data and provide information in response to user queries. 
         [0097]    In a first embodiment, a database is provided to store a sequence of time values. Each time value has associated with it one of a sequence of values of a variable y. The variable y may be, e.g., a variable describing a financial transaction, such as price or volume. 
         [0098]    The time values are arranged in sequence from the earliest time value to the most recent value, and the values are evenly spaced. For example, the difference between consecutive time values may be 0.5 s, 0.1 s, or 0.05 s. 
         [0099]    The database is configured to store over 1000 such time values. 
         [0100]    In a first embodiment, the database also stores the cumulative value of the y variable, i.e. the sum of the y variables corresponding to the time span from the first time value to the nth time value 
         [0000]    
       
         
           
             
               [ 
               
                 
                   ∑ 
                   1 
                   n 
                 
                  
                 
                     
                 
                  
                 y 
               
               ] 
             
              
             
                 
             
             . 
           
         
       
     
         [0000]    Therefore, each time value n has associated with it the sum of the y variables recorded from the earliest time value to this more recent time value. 
         [0101]    This allows the total quantity of variable y corresponding to the time period between time a and time b 
         [0000]    
       
         
           
             ( 
             
               i 
               . 
               e 
               . 
               
                   
               
                
               
                 
                   ∑ 
                   a 
                   b 
                 
                  
                 
                     
                 
                  
                 y 
               
             
             ) 
           
         
       
     
         [0000]    to be calculated by subtracting Σy at time (a) from τy at time (b). 
         [0102]    Thus, the user is able to calculate the cumulative total of variable y added to the database in a given time period by retrieving two data points Σy(a) and Σy(b) from the database and performing a single operation to subtract one value from the other. 
         [0103]    To calculate the mean average of the variable y in the time period between time a and time b, it is necessary to subtract Σy(a) and Σy(b) and to divide the result by the number of values in the subsequence extending from time a to time b. Thus, the user has to perform a single subtraction operation and a single division operation. 
         [0104]    ***In a comparative example, using a conventional database, the calculation of the cumulative total of variable y added to the database in a given time period would require all values of the variable y added to the database in that time period to be retrieved from the database and added to each other. 
         [0105]    Similarly, in another comparative example, the mean average of values stored in a conventional database is calculated by retrieving all those values, adding them to each other and dividing by the total number of values. 
         [0106]    In other embodiments of the first aspect of the invention, the database may store the cumulative value of a function of the variable y n  for each time period between 1 and n. For example, the database may store the cumulative value of y 2 . This allows, for example, the variance of the variable y to be calculated using the following formula 
         [0000]    
       
         
           
             Variance 
             = 
             
               
                 ( 
                 
                   
                     
                       ∑ 
                       a 
                       b 
                     
                      
                     
                         
                     
                      
                     
                       ( 
                       
                         y 
                         2 
                       
                       ) 
                     
                   
                   - 
                   
                     
                       ∑ 
                       a 
                       b 
                     
                      
                     
                         
                     
                      
                     
                       ( 
                       
                         y 
                         2 
                       
                       ) 
                     
                   
                 
                 ) 
               
               / 
               n 
             
           
         
       
     
         [0107]    Therefore, the variance of the variable y in the time period from time a to time b may be calculated by retrieving four values from the database: Σ(y 2 ) and Σ(y) for time=a, Σ(y 2 ) and Σ(y) for time=b. 
         [0108]    In another embodiment of the invention, the database stores a sequence of further input variables y′, each value of y′ being associated with one time value in the sequence of time values. 
         [0109]    In this case, the further input variables y′ may be stored in the database in the form of the cumulative value of [y′·y]. That is, the database stores the cumulative total of [y′·y] for each time value from the earliest time value to the nth time value: 
         [0000]    
       
         
           
             
               [ 
               
                 
                   ∑ 
                   1 
                   n 
                 
                  
                 
                     
                 
                  
                 
                   
                     y 
                     ′ 
                   
                   · 
                   y 
                 
               
               ] 
             
             . 
           
         
       
     
         [0000]    This allows the correlation of the variables y and y′ over the time period 
         [0000]    
       
         
           
             Correlation 
             = 
             
               
                 
                   
                     ( 
                     
                       b 
                       - 
                       a 
                     
                     ) 
                   
                    
                   
                     ( 
                     
                       
                         
                           ∑ 
                           1 
                           b 
                         
                          
                         
                             
                         
                          
                         
                           
                             y 
                             ′ 
                           
                           · 
                           y 
                         
                       
                       - 
                       
                         
                           ∑ 
                           1 
                           a 
                         
                          
                         
                             
                         
                          
                         
                           
                             y 
                             ′ 
                           
                           · 
                           y 
                         
                       
                     
                     ) 
                   
                 
                 - 
                 
                   
                     ( 
                     
                       
                         
                           ∑ 
                           1 
                           b 
                         
                          
                         
                             
                         
                          
                         
                           y 
                           ′ 
                         
                       
                       - 
                       
                         
                           ∑ 
                           1 
                           a 
                         
                          
                         
                             
                         
                          
                         
                           y 
                           ′ 
                         
                       
                     
                     ) 
                   
                    
                   
                     ( 
                     
                       
                         
                           ∑ 
                           1 
                           b 
                         
                          
                         
                             
                         
                          
                         y 
                       
                       - 
                       
                         
                           ∑ 
                           1 
                           a 
                         
                          
                         
                             
                         
                          
                         y 
                       
                     
                     ) 
                   
                 
               
               
                 
                   
                     
                       
                         
                           
                             
                               ( 
                               
                                 b 
                                 - 
                                 a 
                               
                               ) 
                             
                              
                             
                               ( 
                               
                                 
                                   
                                     ∑ 
                                     1 
                                     b 
                                   
                                    
                                   
                                       
                                   
                                    
                                   
                                     y 
                                     ′2 
                                   
                                 
                                 - 
                                 
                                   
                                     ∑ 
                                     1 
                                     a 
                                   
                                    
                                   
                                       
                                   
                                    
                                   
                                     y 
                                     ′2 
                                   
                                 
                               
                               ) 
                             
                           
                           - 
                           
                             ( 
                             
                               
                                 
                                   ( 
                                   
                                     
                                       ∑ 
                                       1 
                                       b 
                                     
                                      
                                     
                                         
                                     
                                      
                                     
                                       y 
                                       ′ 
                                     
                                   
                                   ) 
                                 
                                 2 
                               
                               - 
                               
                                 
                                   ( 
                                   
                                     
                                       ∑ 
                                       1 
                                       a 
                                     
                                      
                                     
                                         
                                     
                                      
                                     
                                       y 
                                       ′ 
                                     
                                   
                                   ) 
                                 
                                 2 
                               
                             
                             ) 
                           
                         
                       
                       · 
                     
                   
                 
                 
                   
                     
                       
                         
                           
                             ( 
                             
                               b 
                               - 
                               a 
                             
                             ) 
                           
                            
                           
                             ( 
                             
                               
                                 
                                   ∑ 
                                   1 
                                   b 
                                 
                                  
                                 
                                     
                                 
                                  
                                 
                                   y 
                                   2 
                                 
                               
                               - 
                               
                                 
                                   ∑ 
                                   1 
                                   a 
                                 
                                  
                                 
                                     
                                 
                                  
                                 
                                   y 
                                   2 
                                 
                               
                             
                             ) 
                           
                         
                         - 
                         
                           ( 
                           
                             
                               
                                 ( 
                                 
                                   
                                     ∑ 
                                     1 
                                     b 
                                   
                                    
                                   
                                       
                                   
                                    
                                   y 
                                 
                                 ) 
                               
                               2 
                             
                             - 
                             
                               
                                 ( 
                                 
                                   
                                     ∑ 
                                     1 
                                     a 
                                   
                                    
                                   
                                       
                                   
                                    
                                   y 
                                 
                                 ) 
                               
                               2 
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
             
           
         
       
     
       Example 1 
     Data Storage 
       [0110]    Taking the database of the first embodiment of first aspect of the invention, in which a cumulative value of the y variable is stored, the costs of building the database are set out below (compared to a comparative example for a conventional database): 
         [0111]    Cost of adding a new record=computational cost of adding new record to sum of all previous records+storage cost for storing new cumulative record. 
         [0112]    For conventional database, cost of adding a new record=storage cost for storing one more record (no computation cost) 
         [0113]    The storage cost is the cost of sending the record to the network memory (including the use of network bandwidth). 
         [0114]    The computational cost is the cost of the mathematical manipulation into the desired format. 
         [0115]    Therefore, data storage in the first embodiment of the present invention has associated with it the additional computational cost (relative to the comparative example of a conventional database) of adding the new record to the sum of all the previous records. The storage costs for the first embodiment may be marginally higher than those associated with a conventional database, due to the larger size of the cumulative values compared to raw data. For example, a two digit number (e.g., a raw data value) if held constant and accumulated for 100 seconds would result in a four digit number to the stored in the database. 
       Example 2 
     Data Manipulation 
       [0116]    In this example, the mean average of a series of data records is calculated from the database of the first embodiment of the first aspect of the invention. 
         [0117]    This requires the steps of:
       1. retrieving data records from the start and end of the series (retrieval cost=two fetch operations)   2. subtracting start record value from end record value (computational cost=one subtraction operation)   3. performing division by size of data (computation cost=one division operation)       
 
         [0121]    In a conventional database, this process would require the steps of:
       1. retrieving all data records in the series of interest (retrieval cost=n fetch operations)   2. performing summation over all retrieved records (computation cost=(n−1) addition operations)   3. performing division by size of data (computational cost=one division operation)       
 
         [0125]    Therefore, the database of the first embodiment of first aspect of the present invention has significantly lower retrieval costs when calculating a mean average of stored data, as well as lower computational costs at the time of performing the calculation. In general, these lower costs of data manipulation will tend to offset the slightly higher one-off costs associated with data storage. This is particularly the case if the request is continuously repeated. For example, if the database of the first embodiment of the invention is queried to obtain the mean of the last 100 data records, and to update this value each time a new record is entered, the realised computational and retrieval savings overcome the costs of the pre-computation overhead after calculating the first mean value, as compared to the conventional method. In addition, if the request was modified to cover the mean of the last 200 data records, the cost would not increase. 
       Example 3 
     Calculation of the Volume Weighted Average Price 
       [0126]    The volume weighted average price (vwap) of a stock is obtained by dividing the total transacted money value by the total transacted volume. The money value of a transaction is the volume of the transaction multiplied by the price. 
         [0127]    In a database according to a second embodiment of the first aspect of the present invention, the cumulative volume and the money value (the multiple of volume and price) are stored as a function of time. In this case, the vwap may be calculated by following the steps of:
       1. retrieving money value records from the start and end of the series of interest (retrieval cost=two fetch operations)   2. subtracting start record from end record (computational cost=one subtraction operation)   3. retrieving volume records from the start and end of the series of interest (retrieval cost=two fetch operations)   4. subtracting start record from end record (computational cost=one subtraction operation)   5. dividing the value obtained in step 2 by the value obtained in step 4 (computational cost=one division operation)       
 
         [0133]    Therefore the total cost of calculating the vwap is four fetch operations, two subtraction operations and one division operation. 
         [0134]    In a conventional database, this process would require the steps of:
       1. retrieving all money value records in the series of interest   2. performing a summation of all of the records obtained in step 1   3. retrieving all volume data records in the series of interest   4. performing a summation of all the records obtained in step 3   5. dividing the value obtained in step 2 by the value obtained in step 4.       
 
         [0140]    Therefore, as a comparative example, the total data cost of calculating the vwap using a conventional database is 2×n fetch operations (where n is the number of values in the data series of interest), 2×(n−1) addition operations and one division operation. 
       Example 4 
     Pattern Matching 
       [0141]    In a third embodiment, the database of the first aspect of the invention has six time periods, each time period having a sequence of five records, labelled 1-5. The database is configured to store the Euclidean distance between corresponding records from different time periods. The Euclidean distance is stored in cumulative form, according to the following formula: 
         [0000]    
       
         
           
             Cumulative 
              
             
                 
             
              
             Euclidean 
              
             
                 
             
              
             distance 
              
             
               : 
             
              
             
                 
             
              
             
               
                 
                   ∑ 
                   1 
                   r 
                 
                  
                 
                     
                 
                  
                 
                   
                     ( 
                     
                       
                         TA 
                         r 
                       
                       - 
                       
                         TB 
                         r 
                       
                     
                     ) 
                   
                   2 
                 
               
             
           
         
       
     
         [0000]    where r=the number of the record and TA is a first time period and TB is a second time period. 
         [0142]    Thus, the database stores the Euclidean distance between the 1st record in each of time period TA and time period TB. The database also stores the sum of the Euclidean distance between the 1st record in each of time period TA and TB and the second record in each of these time periods. Similarly, the database also stores further cumulative values covering the 1st-3rd records, the 1st-4th records and the 1st-5th records in these time periods. 
         [0143]    Similarly, the database also stores cumulative distance values corresponding to the distance between corresponding records of other time periods. 
         [0144]    The Euclidean distance between corresponding subsequences of records in different time periods is given by the following formula: 
         [0000]    
       
         
           
             Euclidean 
              
             
                 
             
              
             distance 
              
             
               : 
             
              
             
                 
             
              
             
               
                 
                   
                     ∑ 
                     1 
                     q 
                   
                    
                   
                       
                   
                    
                   
                     
                       ( 
                       
                         
                           TA 
                           r 
                         
                         - 
                         
                           TB 
                           r 
                         
                       
                       ) 
                     
                     2 
                   
                 
                 - 
                 
                   
                     ∑ 
                     1 
                     p 
                   
                    
                   
                       
                   
                    
                   
                     
                       ( 
                       
                         
                           TA 
                           r 
                         
                         - 
                         
                           TB 
                           r 
                         
                       
                       ) 
                     
                     2 
                   
                 
               
             
           
         
       
     
         [0000]    where the subsequence extends between records p and q. 
         [0145]    Therefore, the Euclidean distance between two corresponding subsequences in different time periods may be rapidly calculated from the stored cumulative distance values. 
         [0146]    The cumulative distance values are stored in the database and may be re-used in response to subsequent requests. 
         [0147]    Thus, the operations that must be carried out in response to a request for the distance between two corresponding subsequences in different time periods are:
       1. Fetch cumulative distance values corresponding to the start and end of the subsequence of interest and the two time periods of interest   2. subtract the cumulative value at the start of the subsequence from the cumulative value at the end of the subsequence.   3. calculate the square root of the difference between the two cumulative values.       
 
         [0151]    By contrast, in a comparative example using a conventional database, the distance between two subsequences is calculated directly in response to the user request, from the raw data stored in the database. Thus, the operations that have to be carried out in response to the user request are:
       1. Fetch 2n records (where n is the length of the subsequence)   2. n subtraction operations (performed with corresponding records from subsequences in different time periods)   3. n multiplication operations (to calculate the squares of the differences)   4. (n−1) addition operations   5. one square root operation       
 
         [0157]    Thus, the present example provides a significant saving in terms of data retrieval and computation cost incurred in response to a user request, compared with the comparative example of a conventional database. These savings will increase with the length of the subsequence of interest. 
         [0158]    Using this embodiment of the first aspect of the invention, pattern matching may be performed between a time period of interest (typically a recent time period) and other, more distant time periods, in order to find the historical time period that is the best match for the time period of interest. 
         [0159]    In this case, the Euclidean distance is calculated between the subsequence of interest and the corresponding subsequences in each of the historical periods of interest. A sorting operation is then performed to identify the historical data subsequences that have the lowest Euclidean distance from the subsequence at the time period of interest. 
         [0160]    It is clear that in this embodiment of the first aspect of the invention, a substantial number of operations have to be performed upon insertion of data into the database, to calculate and store the cumulative Euclidean distance. However, since this stored data can be re-used, the overhead per request will diminish as the number of requests grows. 
       Example 5 
     Data Pre-Fetching 
       [0161]    In general, data requests carried out using the method of the second aspect of the invention consist of fetching the start and end of the required period of data. When a fetch process is expensive due to latency (such as when accessing a database or fetching over a network) it may be advantageous to pre-fetch data in order to eliminate the latency overhead for additional fetch operations and to make use of temporal locality during caching. 
         [0162]    This example will demonstrate the pre-fetching concept with the following scenario. We are performing a continuous real-time request and are currently at time 105. The request consists of fetching both the start and end of the ten most recent cumulative values as the database is updated, e.g., to allow the mean average of the 10 most recent measured values to be calculated. 
         [0163]    In an embodiment of the method according to the second aspect of the invention, at the time of fetching from database A the first end cumulative value (corresponding to time 96), all the cumulative values up to e.g., the cumulative value corresponding to time 100 are also fetched and stored in a local cache B. The cumulative values are retrieved from the cache as required, for use in responding to subsequent requests, as the database is updated with cumulative values for time 106, 107 etc. 
         [0164]    The cost of retrieving a cumulative value from database A is α, while the cost of retrieving a cumulative value from the cache B is β. 
         [0165]    The cost of the fetching/retrieval operations for responding to successive requests each time the database is updated is therefore given by the following Table: 
         [0000]    
       
         
               
               
               
             
           
               
                   
               
               
                   
                   
                 latency  
               
               
                 Request 
                 Retrieval requirements 
                 cost 
               
               
                   
               
             
             
               
                 Mean average 
                 Fetch cumulative value for time 105 from  
                 2 × a + β 
               
               
                 from time  
                 database A; fetch cumulative values for times 
                   
               
               
                 96-105 
                 96-100 from database A (and store in cache B); 
                   
               
               
                   
                 fetch cumulative value for time 96 from cache B 
                   
               
               
                 Mean average 
                 Fetch cumulative value for time 106 from  
                 a + β 
               
               
                 from time  
                 database A; fetch cumulative value for time 97 
                   
               
               
                 97-106 
                 from cache B 
                   
               
               
                 Mean average 
                 Fetch cumulative value for time 107 from  
                 a + β 
               
               
                 from time  
                 database A; fetch cumulative value for time 98 
                   
               
               
                 98-107 
                 from cache B 
                   
               
               
                 Mean average 
                 Fetch cumulative value for time 108 from  
                 a + β 
               
               
                 from time  
                 database A; fetch cumulative value for time 99 
                   
               
               
                 99-108 
                 from cache B 
                   
               
               
                 Mean average 
                 Fetch cumulative value for time 109 from  
                 a + β 
               
               
                 from time  
                 database A; fetch cumulative value for time 100 
                   
               
               
                 100-109 
                 from cache B 
               
               
                   
               
             
          
         
       
     
         [0166]    This Table shows how when the first request is received, the cumulative values for time 96-100 are fetched from database A at a cost of α and stored in cache B. Cumulative value 96 is then fetched from cache B at a cost β and cumulative value 105 is fetched from database A at a cost α. The two cumulative values are used in this case to calculate the mean average of the measured records from time 96 to 105. 
         [0167]    The next calculation is performed after the database has been updated to include the most recent cumulative value for time 106. This value is retrieved from database A at a cost of a and the end value 97 is retrieved from the cache B at a cost β. 
         [0168]    This process is repeated until there are no more values stored in the cache, or until no more user requests for calculation are received. 
         [0169]    In this example, the total retrieval or fetching cost for providing the start and end values of the sequence as the database is updated is given by 6α+5β. 
         [0170]    By contrast, if the method of the second aspect of the invention is not adapted in this way, the total retrieval cost for fetching the start and end values of five sequences is 10 α (i.e. each of the 10 start and end values has to be fetched from the database A). 
         [0171]    Assuming that the latency cost α for fetching data from the database is significantly greater than the latency cost β for fetching data from the cache, then such pre-fetching greatly reduces the overall latency cost in responding to successive requests. 
       Example 6 
     Construction of a Database of Varying Granularity 
       [0172]    In this embodiment of the third aspect of the invention, all data received is stored in a primary database. A secondary database is also constructed, which stores records corresponding to pre-determined time intervals measured back from either:
       (i) the time of the most recent update of the database, or   (ii) the present time.       
 
         [0175]    If the time intervals are measured back from the time of the most recent update, the secondary database is updated every time a new record is entered. If the time intervals are measured back from the present time, the secondary database is updated e.g., every second. 
         [0176]    Thus, in one example, the secondary database stores records from 5 seconds, 30 seconds, 5 minutes, 30 minutes and 2 hours before the most recent update. In this way, the secondary database stores more records relating to recent data and fewer records relating to past data, i.e. the granularity of the database is greater for recent data than for past data. 
         [0177]    A possible structure for the secondary database is that a predefined percentage of data is provided at high granularity, while the rest is at low granularity. For example, referring to data taken from a total time period of 600 minutes (10 hours), the data recorded in that period may be stored as set out in the following Table: 
         [0000]    
       
         
               
               
               
             
           
               
                   
                   
               
               
                   
                 Time period extending back from present time 
                 Granularity 
               
               
                   
                   
               
             
             
               
                   
                 0-0.5 s 
                 milliseconds 
               
               
                   
                 0.5-5 s 
                 Half seconds 
               
               
                   
                  5-90 s 
                 Seconds 
               
               
                   
                 90 s-30 minutes 
                 Half minutes 
               
               
                   
                 30 minutes-10 hours 
                 minutes 
               
               
                   
                   
               
             
          
         
       
     
         [0178]    In this example, the storage space required for the secondary database is only approximately 5% that required for the primary database, in which all the data is stored at a granularity of milliseconds. 
       Example 7 
     Conditional Sorting 
       [0179]    In this example, a database stores data relating to financial instruments e.g., market indicators for each instrument. The data is sorted according to the values of the market indicators. As the market indicators are updated, the data values become out of order, and so re-sorting of the database is required. 
         [0180]    According to this embodiment of the fourth aspect of the invention, sorting of the data is carried out according to the following algorithm: 
         [0181]    for i=2 to n
       if x[i]&lt;x[i−1]   sort_instruments   return
 
where i is a financial instrument and x[i] is a market indicator for that instrument.
       
 
         [0185]    Thus, re-sorting of the database is only carried out when the financial instruments are out of order according to their market indicators. The computational cost of the re-sorting operation is limited to cases where the data is out of order, and otherwise, only the cost of traversing the data is incurred. 
         [0186]    For example, a database may be configured to store a market indicator relating to 10 financial instruments. The market indicator is updated every second, but the data is sorted on the basis of the 5 minute mean average of the market indicator. In this case, the database will be traversed every second (when the market indicator is updated) to determine if the values are still in order, and the data will only be resorted if the values are out of order. Due to the low volatility of the 5 minutes mean average, the data will rarely need re-sorting and so the computational costs relating to the sort operation will be reduced. 
         [0187]    Empirically, it has been found that the overall computational costs of running the database can be reduced by up to 50% when using the conditional sorting algorithm, as compared to a conventional sorting operation, where sorting is carried out each time the values in the database are updated. 
       Example 8 
     Market Indicators 
       [0188]    A database according to the first aspect of the invention may be used to generate descriptive financial indicators obtained by synthesising a complete order book from generally-available raw data. 
         [0189]    In this example, the database is used to provide the following data types for use in generating typical financial indicators: money value, volume, trades, price, return, return squared, return times index. An advantage of the database of this example is that it may also be used to provide other non-typical variables extracted from both the executed trades and order book updates, which have conventionally been of low interest due to their large number and insignificance on their own. However, the aggregate nature of the database where these variables may be represented using statistical measures over periods of time may provide meaningful insights that could not have been achieved by looking at the variables individually. Typical variables may be subjected to detailed decompositions such as decomposing executed trades into: normal/hidden/exception executed buy/sell trades. Order book changes may be used to decompose pending orders into: added/removed orders to the ask/bid side for each individual order book price level or any combination therein. The trades/orders decomposition may then used to specify the non-typical financial indicators. 
         [0190]    The process of synthesising the order book is set out below. 
       Synthesis of Level III (Complete Order Book) Using Level II Updates 
       [0191]    Normally Level III is available only to market makers and specialists. However, using the following approach this data can be synthesized using more generally available level II data messages. 
         [0000]    
       
                 
         
             
             
         
       
     
         [0192]    Message Format 
         [0193]    The following data fields are assumed to be available as input to the synthesis process and represent the minimal amount of information required to generate the financial indicators contained within this document. 
         [0000]    
       
         
               
               
               
               
               
             
           
               
                   
               
             
             
               
                 type (transaction/ 
                 symbol 
                 price 
                 volume 
                 sequence 
               
               
                 order book movement) 
               
               
                   
               
             
          
         
       
     
         [0194]    Support Data Structures 
         [0000]    
       
         
               
               
               
               
             
           
               
                   
               
               
                   
                   
                 description 
                 usage 
               
               
                   
               
             
             
               
                 tables 
                 fullOB_table 
                 Represents the latest  
                 contains the latest 
               
               
                   
                   
                 simulated order book  
                 level III order book 
               
               
                   
                   
                 containing all possible  
                   
               
               
                   
                   
                 price levels 
                   
               
               
                   
                 tempOB_table 
                 Represents the updated  
                 internally used only 
               
               
                   
                   
                 simulated order book  
                   
               
               
                   
                   
                 containing all possible  
                   
               
               
                   
                   
                 price levels 
                   
               
               
                   
                 inputOB_table 
                 Represents the actual  
                 contains the latest 
               
               
                   
                   
                 order book containing  
                 level II order book 
               
               
                   
                   
                 only the top (usually 5-10)  
                   
               
               
                   
                   
                 price levels 
                   
               
               
                   
                 inputTR_table 
                 Represents the latest  
                 contains the 
               
               
                   
                   
                 transaction received 
                 transaction 
               
               
                 lists 
                 change_list 
                 Represents the individual  
                 process log used as 
               
               
                   
                   
                 changes affecting the  
                 source for financial 
               
               
                   
                   
                 input order book 
                 indicators 
               
               
                 pointers  
                 fullOB_pointer 
                 Pointer to fullOB_table  
                 internally used only 
               
               
                   
                   
                 price level (initially points  
                   
               
               
                   
                   
                 to first element) 
                   
               
               
                   
                 inputOB_pointer 
                 Pointer to inputOB_table  
                 internally used only 
               
               
                   
                   
                 price level (initially points  
                   
               
               
                   
                   
                 to first element) 
                   
               
               
                   
                 level2_size 
                 usually 5 or 10 depending  
                 input parameter 
               
               
                   
                   
                 on exchange 
               
               
                   
               
             
          
         
       
     
         [0195]    All tables (except for inputTR_table) and lists exist for both bid and ask sides 
         [0196]    The process consists of maintaining a set of tables and lists for the full order book as a result of synthesizing the input order book which is filled by using market messages. 

 
         [0197]    Process 1 
         [0198]    This process is started upon classification of the input message as an order book movement. It consists of incorporating the message into the latest inputOB_table (level II), comparison to the latest fullOB_table (level III), generation of the new tempOB_table (level III) and the change list. The tempOB_table then becomes the latest fullOB_table and the change list becomes available for transaction messages. 
         [0199]    The following four step algorithm is executed to compare between the inputOB_table and the fullOB_table and perform any needed modifications. Note that all steps of the algorithm are applicable to either ask/bid tables/lists depending on the initial price match. Subsequent modifications to tables/lists/pointers are done for the matching side. 
         [0200]    Deleted Price 
         [0201]    Latest message indicates that old price level has been deleted from order book. 
         [0202]    Status
   price(fullOB_table, fullOB_pointer)&gt;price(inputOB_table, inputOB_pointer) (bid side)   price(fullOB_table, fullOB_pointer)&lt;price(inputOB_table, inputOB_pointer) (ask side)   
 
         [0205]    or
   inputOB_pointer→end and inputOB_pointer&lt;level2_size   
 
         [0207]    Update
   append [price(fullOB_table, fullOB_pointer), −vol(fullOB_table, fullOB_pointer)] to change_list   increment fullOB_pointer   
 
         [0210]    Added Price 
         [0211]    Latest message indicates that a new price level has been added to the order book. 
         [0212]    Status
   price(fullOB_table, fullOB_pointer)&lt;price(inputOB_table, inputOB_pointer) (bid side)   price(fullOB_table, fullOB_pointer)&gt;price(inputOB_table, inputOB_pointer) (ask side)   
 
         [0215]    or
   fullOB_pointer→end (or empty)   
 
         [0217]    Update
   append [price(inputOB_table, inputOB_pointer), vol(inputOB_table, inputOB_pointer)] to tempOB_list   append [price(inputOB_table, inputOB_pointer), vol(inputOB_table, inputOB_pointer)] to change_list   increment inputOB_pointer   
 
         [0221]    Same Price 
         [0222]    Latest message has no effect on this current price level in the order book 
         [0223]    Status
   price(fullOB_table, fullOB_pointer)=price(inputOB_table, inputOB_pointer)   
 
         [0225]    Update
   append [price(inputOB_table, inputOB_pointer), vol(inputOB_table, inputOB_pointer)] to tempOB_list   append [price(inputOB_table, inputOB_pointer), Δvol(inputOB_table, inputOB_pointer)] to change_list   increment fullOB_pointer   increment inputOB_pointer
 
update market status to “open” if both pointers point to top prices of the order book tables
   
 
         [0230]    Price Shifted Down 
         [0231]    Price level which is now lower than level2_size 
         [0232]    Status
   inputOB_pointer&gt;level2_size   
 
         [0234]    Update
   append [price(fullOB_table, fullOB_pointer), vol(fullOB_table, fullOB_pointer)] to tempOB_list   increment fullOB_pointer
 
Price levels may change when they move beyond the level 2 size limits, therefore upon their return they may not be completely accurate.
   
 
         [0237]    Process 2 
         [0238]    This process is started upon classification of the input message as a transaction. It will convert the input message to an inputTR_table and perform matches and modifications to the latest change_list. The change_list is thus a summary of all transactions and order book movements and is the main source of input for generation of the financial indicators. 
         [0239]    The algorithm consists of matching the inputTR_table to find the closest match in the change_list in terms of sequence number in addition to other status requirements mentioned below. Note that all steps of the algorithm are applicable to either ask/bid lists depending on the initial price match. Subsequent modifications to/lists are done for the matching side. 
         [0240]    Normal 
         [0241]    Status
   vol(inputTR_table)=vol(change_list)   price(inputTR_table)=price(change_list)   
 
         [0244]    or
   market status=open   
 
         [0246]    Update
   mark (price, vol) in change_list as a normal transaction   
 
         [0248]    If market status is open, determine the minimum bid/ask quantity at the top level then loop and mark all transactions until the sum of transactions is equivalent to the minimum quantity. 
         [0249]    Hidden 
         [0250]    Status
   price(inputTR_table)=price(change_list)   vol(inputTR_table)&gt;vol(change_list)   
 
         [0253]    Update
   mark (price, vol) in change_list as a hidden transaction   
 
         [0255]    Unclassified 
         [0256]    Status
   price(inputTR_table)=price(change_list)   vol(inputTR_table)&lt;vol(change_list)   
 
         [0259]    Update
   mark (price, vol) in change_list as a hidden transaction   
 
         [0261]    Note that there is a delay in determining whether an order book movement is a transaction, since we must wait until the transaction message is received before the status of the movement can be determined. This is a direct result of the manner in which the exchange processes such information. 
       Descriptive Financial Indicators 
       [0262]    Financial indicators are three-tuples composed of {data type, action, action type}. The following tables briefly describe what each of these tuples represent. Note that order can represent a traded order (executed) or a pending order (waiting in order book). 
         [0000]    
       
         
               
               
               
             
           
               
                   
               
               
                 data type 
                   
                 storage 
               
               
                   
               
             
             
               
                 money value 
                 sum of price times volume of orders 
                 cumulative 
               
               
                 volume 
                 sum of volume of orders 
                 cumulative 
               
               
                 trades 
                 sum of number of orders 
                 cumulative 
               
               
                 price 
                 volume weighted average price of orders  
                 cumulative 
               
               
                 return 
                 (price t  − price t-1 )/ price t-1 , 
                 cumulative 
               
               
                 return squared 
                 return times return 
                 cumulative 
               
               
                 return times index 
                 return times return of index 
                 cumulative 
               
               
                   
               
             
          
         
       
     
         [0000]    
       
         
               
               
               
               
             
           
               
                   
               
               
                 action 
                   
                   
                   
               
               
                   
               
             
             
               
                 traded 
                 order has  
                 normal 
                 trade which matches a price and  
               
               
                   
                 been executed 
                   
                 quantity from the current order book 
               
               
                   
                   
                 hidden 
                 non matching trade from either side  
               
               
                   
                   
                   
                 of order book, whose size is larger  
               
               
                   
                   
                   
                 than what is available 
               
               
                   
                   
                 exception 
                 non matching trade from either side  
               
               
                   
                   
                   
                 of order book, whose size is smaller  
               
               
                   
                   
                   
                 than what is available 
               
               
                 pending 
                 order is still  
                 all 
                 sum of added and removed  
               
               
                   
                 pending in  
                   
                 quantities to order book resulting in  
               
               
                   
                 order book 
                   
                 current state of order book 
               
               
                   
                   
                 added 
                 added quantities to order book 
               
               
                   
                   
                 removed 
                 removed quantities from order book 
               
               
                   
               
             
          
         
       
     
         [0000]    
       
         
               
               
               
             
           
               
                   
                   
               
               
                   
                 action type 
                   
               
               
                   
                   
               
             
             
               
                   
                 all 
                 all orders whether buy or sell 
               
               
                   
                 buy (bid)  
                 only buy orders (from bid side only if pending orders) 
               
               
                   
                 sell (ask) 
                 only sell orders (from ask side only if pending orders) 
               
               
                   
                   
               
             
          
         
       
     
         [0263]    Data types consist of all orders for a single instrument within a specific period of time that satisfy the following selection criteria depending on the desired action and action type: 
         [0000]    
       
         
               
               
             
               
               
               
               
             
               
               
               
               
               
             
           
               
                   
               
               
                   
                 action type  
               
             
          
           
               
                 action 
                 all 
                 buy 
                 sell 
               
               
                   
               
             
          
           
               
                 traded 
                 normal 
                 executed trades 
                 executed buy 
                 executed sell 
               
               
                   
                   
                   
                 trades 
                 trades 
               
               
                   
                 hidden 
                 executed trades 
                 executed buy 
                 executed sell 
               
               
                   
                   
                 which exceed 
                 trades which 
                 trades which 
               
               
                   
                   
                 those from the 
                 exceed those  
                 exceed those  
               
               
                   
                   
                 order book 
                 from the order  
                 from the order  
               
               
                   
                   
                   
                 book 
                 book 
               
               
                   
                 exception 
                 executed trades 
                 executed buy 
                 executed sell 
               
               
                   
                   
                 which are less 
                 trades which are 
                 trades which are 
               
               
                   
                   
                 than those from 
                 less than those 
                 less than those 
               
               
                   
                   
                 the order book 
                 from the order 
                 from the order 
               
               
                   
                   
                   
                 book 
                 book 
               
               
                 pending 
                 all 
                 pending trades 
                 pending buy 
                 pending sell  
               
               
                   
                   
                 in both sides of 
                 trades in bid side 
                 trades in ask  
               
               
                   
                   
                 order book 
                 of order book 
                 side of order  
               
               
                   
                   
                   
                   
                 book 
               
               
                   
                 added 
                 pending trades 
                 pending buy 
                 pending sell  
               
               
                   
                   
                 which have 
                 trades which  
                 trades which  
               
               
                   
                   
                 been added to 
                 have been  
                 have been  
               
               
                   
                   
                 both sides of 
                 added to bid side  
                 added to ask  
               
               
                   
                   
                 order book 
                 of order book 
                 side of order  
               
               
                   
                   
                   
                   
                 book 
               
               
                   
                 removed 
                 pending trades 
                 pending buy 
                 pending sell  
               
               
                   
                   
                 which have 
                 trades which  
                 trades which  
               
               
                   
                   
                 been removed 
                 have been  
                 have been  
               
               
                   
                   
                 from both sides 
                 removed from  
                 removed from  
               
               
                   
                   
                 of order book 
                 bid side of order  
                 ask side of  
               
               
                   
                   
                   
                 book 
                 order book 
               
               
                   
               
             
          
         
       
     
         [0264]    As an example, {money value, pending, bid} would represent the sum of price times volume of all orders for a specific instrument which are still pending in the bid side of the order book and represent waiting buy orders. 
         [0265]    Accumulation of changes that occur within a period of time (e.g., one second) and summarizing them using the aforementioned financial indicators is advantageous since a typical user viewing such data would not be able to monitor changes that occur in sub-second real-time in any case. It also results in a large decrease in the data cost upon delivery to the user (such a cost can be an I/O cost in addition to a bandwidth cost). 
         [0266]    While the invention has been described in conjunction with the exemplary embodiments described above, many equivalent modifications and variations will be apparent to those skilled in the art when given this disclosure. Accordingly, the exemplary embodiments of the invention set forth above are considered to be illustrative and not limiting. Various changes to the described embodiments may be made without departing from the spirit and scope of the invention. 
         [0267]    All references referred to above are hereby incorporated by reference.