Security Incident Tracking in Virtualized Linux Environment

Virtualized environment provides a heaven for malicious and criminal activities. It is expected that illegal activities in virtualized environments will be increased as virtualization gains its popularity. Meanwhile, numerous digital security and privacy laws and regulations have put business and organizations under obligations to prepare for auditing and legal investigations. Therefore, businesses must prepare for the responsiveness to unforeseen security incidents in virtualized environments. To establish forensics readiness for businesses and organizations, it is essential to identify what fingerprints are relevant and where they can be located, and whether all the needed fingerprints are available to reconstruct the incidents successfully. Also, fingerprint identification and locating mechanisms should be provided to guide potential forensics investigation in the future. Furthermore, mechanisms should be established to automate the security incident tracking and reconstruction processes. All these rely on the knowledge of security attacks and the fingerprints left by them. In this research, we will explore potential security exploitations and their corresponding fingerprints left in the virtualized Linux environment. Attacks are modeled as augmented attack trees and then are conducted against a simulated virtualized environment, which is followed by a forensic investigation. Finally, an evidence tree is built for each attack based on fingerprints identified within the system. With evidence tree, it is possible to identify sensitive fingerprints for each attack. Also, the evidence tree is expected to provide contextual information needed for automating forensics investigation of a security incident.

Security Incident Tracking in Virtual Linux Environment
Abstract Virtualized environment provides a heaven for malicious and criminal activities. It is expected that illegal activities in virtualized environments will be increased as virtualization gains its popularity. Meanwhile, numerous digital security and privacy laws and regulations have put business and organizations under obligations to prepare for auditing and legal investigations. Therefore, businesses must prepare for the responsiveness to unforeseen security incidents in virtualized environments. To establish forensics readiness for businesses and organizations, it is essential to identify what fingerprints are relevant and where they can be located, and whether all the needed fingerprints are available to reconstruct the incidents successfully. Also, fingerprint identification and locating mechanisms should be provided to guide potential forensics investigation in the future. Furthermore, mechanisms should be established to automate the security incident tracking and reconstruction processes. All these rely on the knowledge of security attacks and the fingerprints left by them. In this research, we will explore potential security exploitations and their corresponding fingerprints left in the virtualized Linux environment. Attacks are modeled as augmented attack trees and then are conducted against a simulated virtualized environment, which is followed by a forensic investigation. Finally, an evidence tree is built for each attack based on fingerprints identified within the system. With evidence tree, it is possible to identify sensitive fingerprints for each attack. Also, the evidence tree is expected to provide contextual information needed for automating forensics investigation of a security incident.

Introduction
Virtualization technology has been playing a key role in server virtualization and cloud computing 6,10,12 . It can be leveraged to achieve business benefits since it can provide huge benefits in many aspects such as reducing IT administrative time, facilitating data backup and recovery, being adaptive to business change, business continuity and disaster recovery, etc 10,12 . However, it also provides a heaven for malicious code to be executed, untrustworthy data to be processed, or illegitimate data to be stored by services inside the virtual environment 1,2,3,12,16,17 . Even though intensive efforts have been put to secure the virtualized environments, it is evident that cyber crime and fraudulent activity against virtualized environment will continue to thrive 3,12 . With rapid increase of the adoption of virtualization technology, we can expect to witness the increase of illegal activities in the cyber space. These security incidents not only result in substantial financial and operational losses, but also greatly hurt the confidence of customers, business partners and stakeholders. Meanwhile, over the last decade, government and industry bodies around the world have issued many laws and regulations, for example, The Basel Committee on Banking Supervision (Base II Accord), The Health Information Portability and Accountability Act of 1996 (HIPAA), Payment Card Industry Security Standard(PCISS), Sarbanes-Oxley Act (SOX), The Federal Information Security Management Act of 2002 (FISMA), and some others, to ensure the availability, integrity, and confidentiality of business data and the IT infrastructures. These mandates have placed pressures on businesses and organizations to take actions to ensure compliance with laws and regulations. Consequently, to minimize financial loss and be compliant with laws and regulations, businesses that host virtualized services must be prepared for the responsiveness to unforeseen security incidents.
Many intrusion/fraud prevention, detection, and tolerance mechanisms have been deployed by organizations and companies that have adopted cloud computing and virtualization technologies in order to secure their IT infrastructures and the sensitive data stored in information systems 3,12 . However, security incidents cannot be totally eliminated as shown by researchers 3,6 . It is evident that even with the state-of-the-art security prevention, detection, and tolerance mechanisms, the risk introduced by virtualization and especially cloud computing technologies cannot be completely avoided 3,12 . Consequently, intrusion/fraud deterrence, such as digital forensics investigation, has been recognized as a complement to traditional security protection techniques and provides another dimension of protection for the critical infrastructures of these vulnerable businesses 13,14,19,22,23 .
Digital forensics is the process of investigating computer devices and associated storage media to determine whether they have been used to commit a crime and/or gain unauthorized access 7,21,22 . Digital forensics involves the process of preservation, acquisition, analysis, discovery, documentation, and presentation of evidence 7,22 . The success of digital forensics is highly dependent on forensics readiness 21,22 , e.g., the availability of forensically-sound evidence that is able to stand up to legal scrutiny and that can be investigated in an efficient and effective way 15,21,22 . Forensic readiness is an increasingly important topic in forensic investigation and information assurance research 4,5,15,21,22,25 . Existing research efforts focus on the organization-level framework design for forensics readiness, such as policy design, implementation, and management. However, they did not address the investigation of security incidents in computer information systems 13 .
The overall goal of this research is to provide technical guidance to effectively and efficiently investigate security incidents that take place in virtualized Linux systems. There are a few challenging issues need to be addressed for virtualized Linux environments. First, the fingerprints left by attacks and frauds that are needed to reconstruct the incidents of attacks remain unclear to digital forensics and security professionals 13 . Second, many security incidents remain undetected due to the lack of sophisticated identification mechanisms. Third, many security incident investigations are not conducted due to the unaffordable effort needed to process the huge amount of the information kept in the system 15,22 . As discussed in our previous work 22 , one of the key is the establishment of evidence models for attacks. In this research, we will first examine potential security vulnerabilities virtualized Linux environment and attacks are then conducted against the virtualized Linux environment. Second, forensics investigation will be followed to identify and locate their corresponding fingerprints left in system. With fingerprints identified and located, evidence model will be developed for each attack. We expect that evidence models can be used to guide forensics investigation in the future. Furthermore, evidence models are expected to provide the contextual information for an incident tracking software, which may have the potential to automate the incident tracking in a virtualized computing environment or the cloud.

Research Method
The overview of research method is presented Fig. 1   First, virtual Linux environments will be designed to simulate different online business environment, which may be composed of the needed functional components of online businesses, such as web servers, file servers, email servers, as well as open source business information systems. Second, a systematic approach will be developed to model attacks and inside activities. The vulnerabilities of virtual Linux environments will be assessed and the corresponding threats will be identified. Threats will be systematically modeled by using attack trees 13, 20, 22 based on a set of known attacks exploiting the identified vulnerabilities existed in the online information system. Individual attacks are then modeled as augmented attack trees, on which each leaf node represents a specific attack operation. Third, the modeled attacks and inside activities will be conducted against the virtualized Linux environment and forensics investigation will be followed. Finally, once fingerprints are identified and located, they are used to manually reconstruct the crime scene to determine whether the attack itself can be reconstructed. If the attack or fraud cannot be reconstructed successfully, the attacking and forensics investigation process will be repeated with enhanced evidence logging. If the attack or fraud is reconstructed successfully, the fingerprints of each attack operation will be identified. The metadata of the fingerprints of each attack operation, such as log name, format, location, timestamps, and security features, etc. are composed into nodes, which will then become child nodes of the leaf nodes in the augmented attack tree. This entire process will finally result in an evidence tree for each attack studied. Fingerprints of sensitive operations of the evidence trees will be identified as incident identifiers and the evidence tree can provide the contextual information to reconstruct security incidents automatically.

Threat Modeling and Attack Generation
The attack tree approach first proposed by Schneier 18 is used to systematically analyze security threats and has been introduced as a systematic threat modeling approach in some research 20 . Attacks are modeled and represented by a tree structure where the root node represents the final goal, other interior nodes represent subgoals, and leaf nodes are attacking approaches to achieve the final goal 8,9,13 . Children of a node in the tree can be one of the two logical types: AND and OR. To reach the goal, all of its AND children, or at least one of its OR children, must be accomplished. Attack trees grow incrementally by time and they capture knowledge in a reusable form. First, possible attack goals must be identified. Each attack goal becomes the root of its own attack tree. Construction continues by considering all possible attacks against the given goal. These attacks form the AND and OR children of the goal. Next, each of these attacks becomes a goal and their children are generated. Fig.2 shows an example of an attack tree of the inside threat, "achieving the root privilege". In such an attack, the attacker is a regular user and has a lower access privilege to the target, and conducts a series of attacking operations to achieve the root privilege as the system user. Note that links that are connected with a line represents the "AND" relationship among the states or sub-goals, which are working together to achieve the same parent goal.

A Simulated Virtualized Linux Environment and Tools
A desktop PC is used to host the Ubuntu 10 virtual Linux environment, which requires large sized memory and hard disk. A wireless router will be used for network setup and a thumb drive will be used for data collection. The attack tool used for this research is BackTrack 5 R3, which is a tool suite installed on the Ubuntu Linux distribution aimed at digital forensics and penetration testing use. A major package provided by Backtrack is the Metasploit Framework, which is a suite of penetration tools that can be used for system and network penetration and security testing. A BackTrack 5 R3 Bootup Linux machine is setup as the attacking system.
External attacks and internal attacks 11,22 against the virtualized Linux environment are simulated in the following way. To study external attacks 22 , the attack machine with backtrack 5 and the victim machine with Linux virtual machine are deployed to different networks, and the attack machine is assumed to have no knowledge of the victim machine and the system security credentials, such as an account password, of the network the victim machine resides. To study internal attacks 22 , the attack machine with backtrack 5 and the victim machine with Linux virtual machine are deployed to the same network. Therefore, the attack machine has legitimate accesses to a subset of resources of the victim network. To study inside activities 11 , the attack machine with backtrack 5 and the victim machine with Linux virtual machine are deployed to the same network, and the attack machine has legitimate accesses to all the resources hosted in the virtual environment.

Attack I
Attack I is the Apache Range Header Denial of Service Attack, which targets on the Apache Web service installed in the virtualized Linux environment. In this research, Attack I is conducted against virtulized Linux server by using the MetaSploit console. The configuration and execution of the attack is shown in Fig. 3 Fig. 4.  For a small business, Apache web service is usually its first choice to host company website due to its low cost and low demand of knowledge and skills for deployment. Virtualization can further help to reduce the deployment cost and space requirement. A few vulnerabilities exists for Apache web service in Linux environment and Apache Range Header Denial of Service attack (apache_range_dos) is one of the most common attacks exploiting those vulnerabilities. This attack uses a range header that expresses multiple overlapping ranges, which forks processes and causes excessive memory and CPU resource consumption.

Attack II
Attack II is a privilege escalation attack 24 , which exploits a malfunctioning version of FTP server (version 2.3.4, named VSFTPD) installed in Linux environment. To detect whether there exists such VSFTPD service installed, a service fingerprinting scan is conducted by using Nmap (shown in Fig. 5). Once the malfunctioning version of the FTP server has been identified, the open door of the FTP server can be detected by using Metasploit (shown in Fig. 6). Then, Attack II is conducted as shown in Fig. 7, and the attack model of Attack II is shown in Fig. 8.

Results and Analysis
The logs at the victim machine were checked for each operation and the fingerprints were identified and located. With fingerprints of all operations identified and located, evidence tree were built for the attack. With the evidence tree, sensitive fingerprints for the attack may be identified and they can be used to detect or identify the existence of such an attack. Also, the evidence tree can provide contextual information to intelligent incident tracking software to help locate and identify fingerprints of each operation of the attack. Thus, incident tracking and reconstruction can be automated.

Evidence of Attack I
To identify and locate fingerprints of Attack I, the Access.log file on the target machine was examined. The Access.log file records all HTTP requests that have been sent to the server. For each of packet received at the server side, a corresponding response with a code of 206 is generated, which indicates that the server has partially responded to the HTTP GET request. To enable this, the request must have included a range of header field. In Attack I, the range header field contains overlapping ranges, which causes the server to fork the apache process and eventually exhausts all the resources at the server side. The logged evidence is shown in Fig. 9. Fig. 9.Raw fingerprints in the Access.log file The fingerprints of each operation of Attack I was identified and was then composed into a node, which becomes the child node of the corresponding operation node in the attack tree of Attack I. The resulted evidence tree is shown in Fig. 10. Since most of operations of Attack I are performed on the attacking machine, only two operations, i.e., the Nmap scanning operation and the exploit operation, will leave fingerprints on the target machine. For a successful implementation of Attack I, the victim machine can log a large number of packets sent from the attacker with the same user name, IP address of the attack machine, and timestamps, etc. The existence of a large number of HTTP packets sent from the same user can be considered as the sensitive fingerprints to identify Attack I.

Evidence of Attack II
To identify and locate fingerprints of Attack II, the vsftpd.log file on the target machine was examined. The Access.log file logs all packets that have been sent to the victim machine. The fingerprints of each operation of Attack II was identified and was then composed into a node, which becomes the child node of the corresponding operation node in the attack tree of Attack II. The resulted evidence tree is shown in Fig. 11. Since most of operations of Attack II are performed on the attacking machine, only two operations, i.e., the Nmap scanning operation and the ftp exploit operation, will leave fingerprints on the target machine. For a successful implementation of Attack II, the victim machine can log the privilege escalation packets that have been sent from the client, as well as IP address of the attack machine, timestamps, etc. The existence of FTP packets sent from the same user, however, cannot be considered as the sensitive fingerprints to identify Attack II, since they could be fingerprints left by a legitimate ftp user. Therefore, more fingerprints of the same operation of Attack II, e.g., the launch of command processor with system user privilege, should also be identified. The combination of the two pieces of fingerprints, i.e., ftp connect from a remote user and the launch of the cmd.exe process by the system user, can be considered as the sensitive fingerprints to identify attack II.  Fig. 11. Evidence tree of the Attack II.

Incident Identification and Reconstruction
To identify security incidents from the large amount of normal logged activities, the key is to find operations as the incident identifier for each incident. In Fig. 11, the identifier of this incident can be (cmd.exe  root user)  (client IP connect in vsflpd.log)). With the evidence tree and sensitive fingerprints of Attack II, an intelligent incident tracking software can detect and reconstruct Attack II in the following way. 1). The tracking software continuously examines the fingerprints located in the system and compare them with the sensitive fingerprints stored in the evidence model repository. 2). Once sensitive fingerprints match the incident identifier of Attack II, Attack II is identified. 3). All fingerprints of Attack II will be identified, located, and retrieved based on the contexture information defined in the evidence tree of Attack II. 4) The retrieved fingerprints will be correlated to reconstruct Attack II.

Educational Activities Enabled
Many undergraduate and graduate students have been involved in the research partially presented in this paper. The students will conduct security design, programming, testing of various applications installed, as well as ethical hacking and incident investigation in the virtualized Linux environments. All these will provide students with in-depth knowledge and skills in cloud computing and information assurance. More important, research results can be naturally integrated with the existing Computer Information Technology curriculum, which can benefit students in the CIT program at Purdue University Calumet (PUC) and students in the programs that have partnerships with PUC in the Midwest.

Conclusion
In this paper, a systematic approach has been proposed to develop the forensics readiness to fight against attacks and inside activities committed in virtualized Linux environments. This approach focuses on identifying, locating, and modeling fingerprints of external and internal attacks. Threat models were developed by using attack tree approach, and then these threat models were mapped to augmented attack trees by adding individual attack operations of corresponding attacks, which resulted in attack trees. In this paper, a total of two modeled attacks, an external attacks and an internal attack, were conducted against a virtualized Linux system. Forensics investigations were followed immediately after each attack, and fingerprints were then identified, collected, and mapped to an evidence tree for the attack. The resulted evidence trees are expected to provide essential information for attack investigation, by answering at least the following three key questions: what information is relevant to the studied attack, where related fingerprint items can be located, and what information each piece of fingerprint can indicate. Also, an evidence tree can provide the contextual information to correlate attack operations by examine the fingerprints they produce. Furthermore, the contextual information provided to an incident tracking software may have the potential of automating attack reconstruction.


Estimating Time to Event from Tweets Using Temporal Expressions

Given a stream of Twitter messages about an event, we investigate the predictive power of temporal expressions in the messages to estimate the time to event (TTE). From labeled training data we learn average TTE estimates of temporal expressions and combinations thereof, and define basic rules to compute the time to event from temporal expressions, so that when they occur in a tweet that mentions an event we can generate a prediction. We show in a case study on soccer matches that our estimations are off by about eight hours on average in terms of mean absolute error.

Introduction
Textual information streams such as those produced by news media and by social media reflect what is happening in the real world. These streams often contain explicit pointers to future events that may interest or concern a potentially large amount of people. Besides media-specific markers such as event-specific hashtags in messages on Twitter 1 , these messages may contain explicit markers of place and time that help the receivers of the message disambiguate and pinpoint the event on the map and calendar.
The automated analysis of streaming text messages can play a role in catching these important events. Part of this analysis may be the identification of the future start time of the event, so that the event can be placed on the calendar and appropriate action may be taken by the receiver of the message, such as ordering tickets, planning a security operation, or starting a journalistic investigation. The automated identification of the time to event (TTE) should be as accurate and come early 1 http://twitter.com as possible. In this paper we explore a hybrid rulebased and data-driven method that exploits the explicit mentioning of temporal expressions to arrive at accurate and early TTE estimations.
The idea of publishing future calendars with potentially interesting events gathered (semi-) automatically for subscribers, possibly with personalization features and the option to harvest both social media and the general news, has been implemented already and is available through services such as Zapaday 2 , Daybees 3 , and Songkick 4 . To our knowledge, based on the public interfaces of these platforms, these services perform directed crawls of (structured) information sources, and identify exact date and time references in posts on these sources. They also manually curate event information, or collect this through crowdsourcing.
In this study we do not use a rule-based temporal tagger such as the HeidelTime tagger (Strötgen and Gertz, 2013), which searches for only a limited set of temporal expressions. Instead, we propose an approach that uses a large set of temporal expressions, created by using seed terms and generative rules, and a training method that automatically determines the TTE estimate to be associated with each temporal expression sequence in a datadriven way. Typically, rule-based systems do not use the implicit information provided by adverbs ('more' in 'three more days') and relations between non-subsequent elements, while machinelearning-based systems do not make use of the temporal logic inherent to temporal expressions; they may identify 'three more days' as a temporal expression but they lack the logical apparatus to compute that this implies a TTE of about 3 × 24 hours. To make use of the best of both worlds we propose a hybrid system which uses information about the distribution of temporal expressions as they are used in forward-looking social media messages in a training set of known events, and combines this estimation method with an extensive set of regular expressions that capture a large space of possible Dutch temporal expressions.
Thus, our proposed system analyzes social media text to find information about future events, and estimates how long it will take before the event takes place. The service offered by this system will be useful only if it generates accurate estimations of the time to event. Preferably, these accurate predictions should come as early as possible. Moreover, the system should be able, in the long run, to freely detect relevant future events that are not yet on any schedule we know in any language represented on social media. For now, in this paper we focus on estimating the starting time of scheduled events, and use past and known events for a controlled experiment involving Dutch twitter messages.
For our experiment we collected tweets referring to scheduled Dutch premier league soccer matches. This type of event generally triggers many anticipatory discussions on social media containing many temporal expressions. Given a held-out soccer match not used during training, our system predicts the time to the event based on individual tweets captured in a range from eight days before the event to the event time itself. Each estimation is based on the temporal expressions which occur in a particular twitter message. The mean absolute error of the predictions for each of the 60 soccer matches in our data set is off by about eight hours. The results are generated in a leave-one-out cross-validation setup 5 . This paper starts with describing the relation of our work to earlier research in Section 2. Section 3 describes the overall experimental setup, including a description of the data, the temporal expressions that were used, our two baselines, and the evaluation method used. Next, in Section 4 the results are presented. The results are analyzed and discussed in Section 5. We conclude with a summary of our main findings and make suggestions for the direction future research may take (Section 6).
Future-reference analysis in textual data has been studied from different angles. In the realm of information retrieval the task is more commonly defined as seeking future temporal references in large document collections such as the Web by means of time queries (Baeza Yates, 2005). Various studies have used temporal expression elements as features in an automatic setting to improve the relevance estimation of a web document (Dias et al., 2011;Jatowt and Au Yeung, 2011). Information relevant to event times has been the focus of studies such as those by Becker et al. (2012) and Kawai et al. (2010).
Our research is aimed at estimating the time to event of an upcoming event as precisely as possible. Radinsky et al. (2012) approach this problem by learning from causality pairs in texts from longranging news articles. Noro et al. (2006) describe a machine-learning-based system for the identification of the time period in which an event will happen, such as in the morning or at night.
Some case studies are focused on detecting events as early as possible as their unfolding is fast. The study by Sakaki et al. (2010) describes a system which analyzes the flow of tweets in time and place mentioning an earthquake, to predict the unfolding quake pattern which may in turn provide just-in-time alerts to people residing in the locations that are likely to be struck shortly. Zielinski et al. (2012) developed an early warning system to detect natural disasters in a multilingual fashion and thereby support crisis management. The quick throughput of news in the Twitter network is the catalyst in these studies focusing on natural disasters. In our study, we rather rely on the slower build-up of clues in messages in days before an event, at a granularity level of hours. Ritter et al. (2012) aim to create a calendar of events based on explicit date mentions and words typical of the event. They train on annotated open domain event mentions and use a rule-based temporal tagger. We aim to offer a more generic solution that makes use of a wider range of temporal expressions, including indirect and implicit expressions. Weerkamp and De Rijke (2012) study this type of more generic patterns of anticipation in tweets, but focus on personal future activities, while we aim to predict as early as possible the time to event of events that affect and interest many users.
Our estimations do not target time periods such as mornings or evenings but on the number of hours remaining to the event.
TTE estimation of soccer matches has been the topic of several studies. Kunneman and Van den Bosch (2012) show that machine learning methods can differentiate between tweets posted before, during, and after a soccer match. Estimating the time to event of future matches from tweet streams has been studied by Hürriyetoglu et al. (2013), using local regression over word time series. In a related study, Tops et al. (2013) use support vector machines to classify the time to event in automatically discretized categories. At best these studies are about a day off in their predictions. Both studies investigate the use of temporal expressions, but fail to leverage the utility of this information source, most likely because they use limited sets of less than 20 regular expressions. In this study we scale up the number of temporal expressions.

Experimental Set-Up
We carried out a controlled case study in which we focused on Dutch premier league soccer matches as a type of scheduled event. These types of games have the advantage that they occur frequently, have a distinctive hashtag by convention, and often generate thousands to several tens of thousands of tweets per match.
Below we first describe the collection and composition of our data sets (Subsection 3.1) and the temporal expressions which were used to base our predictions upon (Subsection 3.2). Then, in Subsection 3.3, we describe our baselines and evaluation method.

Data Sets
We harvested tweets from twiqs.nl 6 , a database of Dutch tweets collected from December 2010 onwards. We selected the six best performing teams of the Dutch premier league in 2011 and 2012 7 , and queried all matches in which these teams played against each other in the calendar years 2011 and 2012. The collection procedure resulted in 269,999 tweets referring to 60 individual matches. The number of tweets per event ranges from 321 to 35,464, with a median of 2,723 tweets. Afterwards, we restricted the data to tweets sent within eight days before the match 8 and eliminated all retweets. This reduced the number of tweets in our final data set to 138,141 tweets.
In this experiment we are working on the assumption that the presence of a hashtag can be used as proxy for the topic addressed in a tweet. Inspecting a sample of tweets referring to recent soccer games not part of our data set, we developed the hypothesis that the position of the hashtag may have an effect as regards the topicality of the tweet. Hashtags that occur in final position (i.e. they are tweet-final or are only followed by one or more other hashtags) are typically metatags and therefore possibly more reliable as topic identifiers than tweet non-final hashtags which behave more like common content words in context. In order to be able to investigate the possible effect that the position of the hashtag might have, we split our data in the following two subsets: FIN -comprising tweets in which the hashtag occurs in final position (as defined above); 84,533 tweets.
NFI -comprising tweets in which the hashtag occurs in non-final position; 53,608 tweets.
Each tweet in our data set has a time stamp of the moment (in seconds) it was posted. Moreover, for each soccer match we know exactly when it took place. This information is used to calculate for each tweet the actual time that remains to the start of the event and the absolute error in estimating the time to event.

Temporal Expressions
In the context of this paper temporal expressions are considered to be words or phrases which point to the point in time, the duration, or the frequency of an event. These may be exact, approximate, or even right out vague. Although in our current experiment we restrict ourselves to an eight-day period prior to an event, we chose to create a gross list of all possible temporal expressions we could think of, so that we would not run the risk of overlooking any items and the list can be used on future occasions even when the experimental setting is different. Thus the list also includes temporal expressions that refer to points in time outside the time span under investigation here, such as gisteren 'yesterday' or over een maand 'in a month from now', and items indicating duration or frequency such as steeds 'continuously'/'time and again'. No attempt has been made to distinguish between items as regards time reference (future time, past time) as many items can be used in both fashions (compare for example vanmiddag in vanmiddag ga ik naar de wedstrijd 'this afternoon I'm going to the match' vs ik ben vanmiddag naar de wedstrijd geweest 'I went to the match this afternoon'. The list is quite comprehensive. Among the items included are single words, e.g. adverbs such as nu 'now', zometeen 'immediately', straks 'later on', vanavond 'this evening', nouns such as zondagmiddag 'Sunday afternoon', and conjunctions such as voordat 'before'), but also word combinations and phrases such as komende woensdag 'next Wednesday. Temporal expressions of the latter type were obtained by means of a set of 615 seed terms and 70 rules, which generated a total of around 53,000 temporal expressions. In addition, there are a couple of hundred thousand temporal expressions relating the number of minutes, hours, days, or time of day; 9 they include items containing up to 9 words in a single temporal expression. Notwithstanding the impressive number of items included, the list is bound to be incomplete.
We included prepositional phrases rather than single prepositions so as to avoid generating too much noise. Many prepositions have several uses: they can be used to express time, but also for example location. Compare voor in voor drie uur 'before three o'clock' and voor het stadion 'in front of the stadium'. Moreover, prepositions are easily confused with parts of separable verbs which in Dutch are abundant.
Various items on the list are inherently ambiguous and only in one of their senses can be considered temporal expressions. Examples are week 'week' but also 'weak' and dag 'day' but also 'goodbye'. For items like these, we found that the different senses could fairly easily be distinguished whenever the item was immediately preceded by an adjective such as komende and volgende (both meaning 'next'). For a few highly frequent items this proved impossible. These are words like zo which can be either a temporal adverb ('in a minute'; cf. zometeen) or an intensifying adverb ('so'), dan 'then' or 'than', and nog 9 For examples see Table 1 and Section 3.3. 'yet' or 'another'. As we have presently no way of distinguishing between the different senses and these items have at best an extremely vague temporal sense so that they cannot be expected to contribute to estimating the time to event, we deciced to discard these. 10 In order to capture event targeted expressions, we treated domain terms such as wedstrijd 'soccer match' as parts of temporal expressions in case they co-occur with a temporal expression.
For the items on the list no provisions were made for handling any kind of spelling variation, with the single exception of a small group of words (including 's morgens 'in the morning', 's middags 'in the afternoon' and 's avonds 'in the evening') which use in their standard spelling the archaic 's and abbreviations. As many authors of tweets tend to spell these words as smorgens, smiddags and savonds we decided to include these forms as well.
The items on the list that were obtained through generation include temporal expressions such as over 3 dagen 'in 2 days', nog 5 minuten 'another 5 minutes', but also fixed temporal expressions such as clock times. 11 The rules handle frequently observed variations in their notation, for example drie uur 'three o'clock' may be written in full or as 3:00, 3:00 uur, 3 u, 15.00, etc. Table 1 shows example temporal expression estimates and applicable rules. The median estimations are mostly lower than the mean estimations. The distribution of the time to event (TTE) for a single temporal expression often appears to be skewed towards lower values. The final column of the table displays the applicable rules. The first six rules subtract the time the tweet was posted (TT) from an average marker point, heuristically determined, such as 'today 20.00' (i.e. 8 pm) for vanavond 'tonight'. The second and third rules from below state a TTE directly, again heuristically set -over 2 uur 'in 2 hours' is directly translated to a TTE of 2.

Evaluation and Baselines
Our approach to TTE estimation makes use of all temporal expressions in our temporal expression list that are found to occur in the tweets. A ). There can be other words in between these expressions. We consider the longest match, from left to right, in case we encounter any overlap. The experiment adopts a leave-one-out crossvalidation setup. Each iteration uses all tweets from 59 events as training data. All tweets from the single held-out event are used as test set.
In the FIN data set there are 42,396 tweets with at least one temporal expression, in the NFI data set this is the case for 27,610 tweets. The number of tweets per event ranges from 66 to 7,152 (median: 402.5; mean 706.6) for the FIN data set and from 41 to 3,936 (median 258; mean 460.1) for the NFI data set.
We calculate the TTE estimations for every tweet that contains at least one of the temporal expression or a combination in the test set. The estimations for the test set are obtained as follows: 1. For each match (a single temporal expression or a combination of temporal expressions) the mean or median value for TTE is used that was learned from the training set; 2. Temporal expressions that denote an exact amount of time are interpreted by means of rules that we henceforth refer to as Exact rules. This applies for example to temporal expressions answering to patterns such as over N {minuut | minuten | kwartier | uur | uren | dag | dagen | week} 'in N {minute | minutes | quarter of an hour | hour | hours | day | days | week}'. Here the TTE is assumed to be the same as the N minutes, days or whatever is mentioned. The rules take precedence over the mean estimates learned from the training set; 3. A second set of rules, referred to as the Dynamic rules, is used to calculate the TTE dynamically, using the temporal expression and the tweet's time stamp. These rules apply to instances such as zondagmiddag om 3 uur 'Sunday afternoon at 3 p.m.'. Here we assume that this is a future time reference on the basis of the fact that the tweets were posted prior to the event. With temporal expressions that are underspecified in that they do not provide a specific point in time (hour), we postulate a particular time of day. For example, vandaag 'today' is understood as 'today at 3 p.m., vanavond 'this evening' as 'this evening at 8 p.m. and morgenochtend 'tomorrow morning' as 'tomorrow morning at 10 a.m.'. Again, as was the case with the first set of rules, these rules take precedence over the mean or median estimates learned from the training data.
The results for the estimated TTE are evaluated in terms of the absolute error, i.e. the absolute difference in hours between the estimated TTE and the actual remaining time to the event.
We established two naive baselines: the mean and median TTE measured over all tweets of FIN and NFI datasets. These baselines reflect a best guess when no information is available other than tweet count and TTE of each tweet. The mean TTE is 22.82 hours, and the median TTE is 3.63 hours before an event. The low values of the baselines, especially the low median, reveal the skewedness of the data: most tweets referring to a soccer event are posted in the hours before the event. Table 2 lists the overall mean absolute error (in number of hours) for the different variants. The results are reported separately for each of the two data sets (FIN and NFI) and for both sets aggregated (FIN+NFI). For each of these three variants, the table lists the mean absolute error when only the basic data-driven TTE estimations are used ('Basic'), when the Exact rules are added ('+Ex.'), when the Dynamic rules are added ('+Dyn'), and when both types of rules are added. The coverage of the combination (i.e. the number of tweets that match the expressions and the rules) is listed in the bottom row of the table.

Results
A number of observations can be made. First, all training methods perform substantially better than the two baselines in all conditions. Second, the TTE training method using the median as estimation produces estimations that are about 1 hour more accurate than the mean-based estimations.
Third, adding Dynamic rules has a larger positive effect on prediction error than adding Exact rules. The bottom row in the table indicates that the rules do not increase the coverage of the method substantially. When taken together and added to the basic TTE estimation, the Dynamic and Exact rules do improve over the Basic estimation by two to three hours.
Finally, although the differences are small, Table 2 reveals that training on hashtag-final tweets (FIN) produces slightly better overall results (7.62 hours off at best) than training on hashtag-nonfinal tweets (8.50 hours off) or the combination (7.99 hours off), despite the fact that the training set is smaller than that of the combination.
In the remainder of this section we report on systems that use all expressions and Exact and Dynamic rules.
Whereas Table 2 displays the overall mean absolute errors of the different variants, Figure 1 displays the results in terms of mean absolute error at different points in time before the event, averaged over periods of one hour, for the two baselines and the FIN+NFI variant with the two training methods (i.e. taking the mean versus the median of the observed TTEs for a particular temporal expres-sion). In contrast to Table 2, in which only a mild difference could be observed between the median and mean variants of training, the figure shows a substantial difference. The estimations of the median training variant are considerably more accurate than the mean variant up to 24 hours before the event, after which the mean variant scores better. By virtue of the fact that the data is skewed (most tweets are posted within a few hours before the event) the two methods attain a similar overall mean absolute error, but it is clear that the median variant produces considerably more accurate predictions when the event is still more than a day away.
While Figure 1 provides insight into the effect of median versus mean-based training with the combined FIN+NFI dataset, we do not know whether training on either of the two subsets is advantageous at different points in time. Table 3 shows the mean absolute error of systems trained with the median variant on the two subsets of tweets, FIN and NFI, as well as the combination FIN+NFI, split into nine time ranges. Interestingly, the combination does not produce the lowest errors close to the event. However, when the event is 24 hours away or more, both the FIN and NFI systems generate increasingly large errors, while the FIN+NFI system continues to make quite accurate predictions, remaining under 10 hours off even for the longest TTEs, confirming what we already observed in Figure 1

Analysis
One of the results observed in Table 2 was the relatively limited role of Exact rules, which were intended to deal with exact temporal expressions such as nog 5 minuten '5 more minutes' and over  een uur 'in one hour'. This can be explained by the fact that as long as the temporal expression is related to the event we are targeting, the point in time is denoted exactly by the temporal expression and the estimation obtained from the training data (the 'Basic' performance) will already be accurate, leaving no room for the rules to improve on this.
The rules that deal with dynamic temporal expressions, on the other hand, have quite some impact.
As was explained in Section 3.2 our list of temporal expressions was a gross list, including items that were unlikely to occur in our present data. In all we observed 770 of the 53,000 items listed, 955 clock time rule matches, and 764 time expressions which contain number of days, hours, minutes etc. The temporal expressions observed most frequently in our data are: 12 vandaag 'today' (10,037), zondag 'Sunday' (6,840), vanavond 'tonight' (5167), straks 'later on' (5,108), vanmiddag 'this afternoon' (4,331), matchday 'match day' (2,803), volgende week 'next week ' (1,480) and zometeen 'in a minute ' (1,405).
Given the skewed distribution of tweets over the eight days prior to the event, it is not surprising to find that nearly all of the most frequent items refer to points in time within close range of the event. Apart from nu 'now', all of these are somewhat vague about the exact point in time. There are, however, numerous items such as om 12:30 uur 'at half past one' and over ongeveer 45 minuten 'in about 45 minutes') which are very specific and therefore tend to appear with middle to low frequencies. 13 And while it is possible to state an exact point in time even when the event is in the more distant future, we find that there is a clear 12 The observed frequencies can be found between brackets. 13 While an expression such as om 12:30 uur has a frequency of 116, nog maar 8 uur en 35 minuten 'only 8 hours and 35 minutes from now' has a frequency of 1. tendency to use underspecified temporal expressions as the event is still some time away. Thus, rather than volgende week zondag om 14.30 uur 'next week Sunday at 2.30 p.m.' just volgende week is used, which makes it harder to estimate the time to event.
Closer inspection of some of the temporal expressions which yielded large absolute errors suggests that these may be items that refer to subevents rather than the main event (i.e. the match) we are targeting. Examples are eerst 'first', daarna 'then', vervolgens 'next', and voordat 'before'.

Conclusions and Future Work
We have presented a method for the estimation of the TTE from single tweets referring to a future event. In a case study with Dutch soccer matches, we showed that estimations can be as accurate as about eight hours off, averaged over a time window of eight days. There is some variance in the 60 events on which we tested in a leave-oneout validation setup: errors ranged between 4 and 13 hours, plus one exceptionally badly predicted event with a 34-hour error.
The best system is able to stay within 10 hours of prediction error in the full eight-day window. This best system uses a large set of hand-designed temporal expressions that in a training phase have each been linked to a median TTE with which they occur in a training set. Together with these data-driven TTE estimates, the system uses a set of rules that match on exact and indirect time references. In a comparative experiment we showed that this combination worked better than only having the data-driven estimations.
We then tested whether it was more profitable to train on tweets that had the event hashtag at the end, as this is presumed to be more likely a meta- Figure 1: Curves showing the absolute error (in hours) in estimating the time to event over an 8-day period (-192 to 0 hours) prior to the event. The two baselines are compared to the TTE estimation methods using the mean and median variant. tag, and thus a more reliable clue that the tweet is about the event than when the hashtag is not in final position. Indeed we find that the overall predictions are more accurate, but only in the final hours before the event (when most tweets are posted). 24 hours and earlier before the event it turns out to be better to train both on hashtag-final and hashtag-non-final tweets.
Finally, we observed that the two variants of our method of estimating TTEs for single temporal expressions, taking the mean or the median, leads to dramatically different results, especially when the event is still a few days away-when an accurate time to event is actually desirable. The median-based estimations, which are generally smaller than the mean-based estimations, lead to a system that largely stays under 10 hours of error.
Our study has a number of logical extensions into future research. First, our method is not bound to a single type of event, although we tested it in a controlled setting. With experiments on tweet streams related to different types of events the general applicability of the method could be tested: can we use the trained TTE estimations from our current study, or would we need to retrain per event type?
Second, we hardcoded a limited number of frequent spelling variations, where it would be a more generic solution to rely on a more systematic spelling normalization preprocessing step.
Third, so far we did not focus on determining the relevance of temporal expressions in case there are several time expressions in a single message; we treated all occurred temporal expressions as equally contributing to the estimation. Identifying which temporal expressions are relevant in a single message is studied by Kanhabua et al. (2012).
Finally, our method is limited to temporal expressions. For estimating the time to event on the basis of tweets that do not contain temporal expressions, we could benefit from term-based approaches that consider any word or word ngram as potentially predictive (Hürriyetoglu et al., 2013).


extfieldsofstudy:
Mathematics
Computer Science

text:
Symmetric QR Algorithm with Permutations

In this paper, we present the QR Algorithm with Permutations that shows an improved convergence rate compared to the classical QR algorithm. We determine a bound for performance based on best instantaneous convergence, and develop low complexity methods for computing the permutation matrices at every iteration. We use simulations to verify the improvement, and to compare the performance of proposed algorithms to the classical QR algorithm.

I. INTRODUCTION
Let A be an NxN symmetric invertible matrix, spectral theorem states that the matrix can be diagonalised as follows: where Λ is a matrix with eigenvalues along the diagonals and V = [v 1 , v 2 , . . . , v N ] is a matrix with corresponding eigenvectors v 1 , v 2 , . . . , v N . QR algorithm is an iterative algorithm based on QR decomposition to find the eigenvalues and eigenvectors simultaneously and is as follows: Further, A ∞ = Λ, Q ∞ = I, and V = Q 0 Q 1 ...Q ∞ . For ease of analysis, we require in equation (3) that uppertriangular matrix R of QR factorization to contain positive values along the diagonal. This can be easily arranged by multiplying the row containing the negative value by '-1' and compensating the matrix Q. Such upper-triangular matrix R can be shown to be the upper-triangular Cholesky factor of the matrix A 2 .
For an introduction to the QR algorithm and a proof for convergence, and for modified algorithms: QR algorithm based on Hessenberg form and QR algorithm with shifts, refer [1] or [3].

A. Cholesky Iteration
A closely related algorithm to QR algorithm is Cholesky iterations based on Cholesky decomposition, given as follows: Aravindh Krishnamoorthy is currently with Ericsson Modem Nuremberg GmbH working in the area of Wireless Communication. Contact e-mail: aravindh.krishnamoorthy@ericsson.com, aravindh.k@ieee.org.
The sets {A 0 , A 1 , A 2 , ...} and {B 0 , B 1 , B 2 , ...} are equivalent sets, and A k is the principal square root of the matrix B k . This relation can be used to study the convergence properties of QR algorithm through Cholesky iteration which is more tractable for analysis; for e.g. see [4].

B. Permutations
A permutation matrix P is a matrix containing a single '1' in every row and column, and zeroes elsewhere. Let P be the set of such matrices of order N, then the cardinality of set P is |P| = N ! A symmetric permutation P AP H on matrix A defined above, maintains the symmetry of the matrix. It can be easily verified that the permuted matrix has the same eigenvalues as the original matrix, and the eigenvectors are P V .

C. Terminology
The following special functions are used in this paper: • dsort : R N → R N takes a real vector of order N as input, and returns a vector with the elements of input sorted in descending order. • diag : C N xN → R N takes a symmetric matrix of order N as input, and returns a vector containing the diagonal elements of the matrix in the order along the main diagonal. • diagmat : R N → R N xN takes a real vector of order N as input, and returns a real matrix containing the elements of the input vector along the main diagonal, and zeroes elsewhere.
In the following section, we present the QR algorithm with permutations along with a theoretical bound on performance. In section III we discuss computation of the permutation matrices, in section IV we describe the simulation setup used to verify the performance of the algorithms. In section V we discuss the performance results for simulation runs involving positive-definite and symmetric matrices, followed by concluding remarks in section VI.

II. QR ALGORITHM WITH PERMUTATIONS
Applying a permutation P on equations (2, 3, 4) yields an iteration of QR algorithm as follows: showing that a permutation on the matrix A has an additional factor P H in the applied orthonormal matrix.

arXiv:1402.5086v1 [cs.NA] 20 Feb 2014
The effect of applying a permutation matrix on convergence can be intuitively understood when the QR algorithm is viewed as power iteration algorithm with a complete set of orthonormal basis-vectors instead of a single vector.
Let n-th column of the matrix Q k be q n = a n,1 v 1 +a n,2 v 2 + ... + a n,N v N , the convergence rate of the n-th eigenvalue λ n depends upon a n,n /a n,n−1 λ n /λ n−1 . With some luck, permutation changes the values a n,1 , a n,2 , ..., a n,N , such that it offers a better convergence compared to the original matrix.
Assume that P is a permutation matrix that can ensure an optimum arrangement of the basis-vectors of Q, then the permutation causes the maximum convergence in that QR algorithm's iteration. This optimal arrangement can also aid the convergence of repeated eigenvalues or eigenvalues close to each other. However, this convergence is only speeded up by a linear factor! Let A be an NxN symmetric invertible matrix as defined above, the QR algorithm with permutations with a permutation matrix P k at each iteration is given as follows: Further, A ∞ = Λ, Q ∞ = I, and In general, in the k-th iteration, the estimates of eigenvalue matrix Λ k , eigenvector matrix V k can be given as follows: The error in eigenvalue estimation E k for any algorithm can be given as follows: QR algorithm with permutations requires the following additional computation compared to the classical QR algorithm: 1) computation of the permutation matrix, 2) symmetric permutation of matrix A k before QR decomposition, 3) permutation of the matrix Q k before multiplication, if eigenvectors are desired.

A. Performance Bound
The performance of the algorithm depends on the selection of the permutation matrices, i.e. E k = f (A, P 0 , P 1 , ..., P k ).
A simple bound for E k can be given by requiring the best instantaneous convergence at every iteration. Therefore, the selection criterion for selecting the permutation matrix in the k-th iteration becomes: That is, the permutation matrix P k of the available permutation matrices of order N, which when used in the k-th iteration, causes the least error in eigenvalue estimation E k .

III. COMPUTING THE PERMUTATION MATRICES
Computing the permutation matrix P k is non-trivial. In this section we present two simple methods for computing the permutation matrices which compute them without iterating through the set P. Other methods for computing P k may be established easily, and their choice is a trade-off between convergence rate and computational complexity.

A. Diagonal Ordering
In this method, we choose the permutation matrix P k which orders the diagonal elements matrix A k in descending order of magnitude (absolute value). The MATLAB compatible pseudo-code to determine this permutation matrix is as follows:

B. Column Ordering
In this method, we choose the permutation matrix P k which orders the diagonal elements matrix B k = A 2 k in descending order. Such ordering also orders the columns of the matrix A k in descending order of their norm value.
This permutation matrix can be computed with a computational cost of N 2 for computing the N norm values of the columns of A k . The MATLAB compatible pseudo-code to determine this permutation matrix is P = diord(A * A).
Both diagonal ordering and column ordering methods do not preserve the shape of the matrix in subsequent QR iterations. Therefore, computational complexity reduction due to conversion to Hessenberg form cannot be applied with these two methods.
IV. SIMULATION SETUP In order to compare the performance of various algorithms, we use MATLAB based simulations. MATLAB compatible source code of the simulation is available from [7].
The average eigenvalue estimation error E 2 k equation (16) for 4x4 symmetric invertible matrices, each with 50 iterations are plotted. The first figure (1a) uses a random subset of size 10,000 of the set of symmetric matrices which includes positive-definite, negative-definite, and indefinite matrices. The second figure (1b) uses a random subset of size 25,000 of the set of positive-definite symmetric matrices.
Label 'QR' is the error plot for the classical QR algorithm, 'QRH' first converts the given matrix into Hessenberg (tridiagonal) form and then performs the classical QR algorithm, 'QRS' uses the QRH algorithm (A is in Hessenberg form) with shifts as given below (A 0 = A): Here the notation A k−1 (N, N ) refers to the (N,N)-th element of the matrix A k−1 .
Label 'DO' refers to the QR algorithm with permutations which uses diagonal ordering method for computing the permutation matrix at each iteration. 'CO' uses the column ordering method.
Label 'BIC' refers to the best instantaneous convergence bound as described in equation (17).

V. SIMULATION RESULTS
From figure (1a), we observe that permutations increase the convergence rate on an average for symmetric and positive definite matrices.
The best instantaneous convergence (BIC) bound shows the highest rate of convergence, showing that permutation has an effect of speeding up the convergence of QR algorithm. However, meeting this bound using the definition is not feasible as it requires prior knowledge of eigenvalues.
QR algorithm with permutations with diagonal ordering (DO) shows good convergence rate for positive-definite matrices, but saturates after the first few iterations on an average, for symmetric matrices in general. DO performs better than classical QR algorithm and variations for positive-definite matrices.
QR algorithm with permutations with column ordering (CO) shows good convergence rate for positive-definite matrices and in general for symmetric matrices. CO performs better than classical QR algorithm and variations for positive-definite matrices and in general for symmetric matrices.
Therefore, for positive-definite matrices, DO provides the best convergence rate, and for symmetric matrices in general, CO provides the best convergence at low complexity for calculation of permutation matrices, both providing a 2x convergence speedup.

VI. CONCLUSION
In this paper, we presented the QR algorithm with permutations that shows a significantly improved convergence rate compared to classical QR algorithm and variations. We determined a bound for performance based on best instantaneous convergence, and developed two low complexity methods for computing the permutation matrices at every iteration. We used simulations to verify that the performance bound is significantly improved upon using permutations, and compared the performance of QR algorithm with permutations using the two methods for computing permutation matrices.
We find that a 2x convergence speedup is obtained by using QR algorithm with permutations. Further, we find that the diagonal ordering provides the best trade-off for positivedefinite matrices, and column ordering provides best trade-off for symmetric matrices in general.


Digital Chronofiles of Life Experience

Technology has brought us to the point where we are able to digitally sample life experience in rich multimedia detail, often referred to as lifelogging. In this paper we explore the potential of lifelogging for the digitisation and archiving of life experience into a longitudinal media archive for an individual. We motivate the historical archive potential for rich digital memories, enabling individuals’ digital footprints to contribute to societal memories, and propose a data framework to gather and organise the lifetime of the subject.

Introduction
Earlier societies have left legacies informing us of their actions. Society has a need to record and document its events and has used whatever means possible. From Newgrange, Stonehenge and the Pyramids in Egypt, to the headstones on Easter Island, we are left with clues from a distant society. In many ways these societies created durable objects that tell a story that transcends time and sometimes these legacies leave us with a mystery to be solved in modern times. Historically the interaction and communication between individuals bore witness to events, and such material is today studied by historians and archivists. Whether stone carvings, exchange of letters, recorded phone calls, or the eyewitness details, this is what leaves the historical trace and forms the basis of the historical record.
As technology evolved, so too have the recording tools; hammer and stone, pen and paper, have been replaced by computers and digital recording devices. The ease at which we can create the historical trace is ever increasing and our ability to create an evidence of me has no bounds. Continual advancement in sensing technologies has lead us this point at which it becomes possible, should one wish, to continually record all of life activities into a personal media-rich archive, or as we refer to it in this paper, a personal chronofile. This process is called lifelogging and can quickly generate terabytes of information about the individual, in particular using wearable sensors and cameras, which are already flourishing on the consumer market [7].
Compare this to the most detailed life chronicle from the past, the Dymaxion Chronofile [18] where Richard Buckminster-Fuller documented his activities in detail day-by-day into a lifetime archive. Buckminster-Fuller referred to his archive as a "very accurate record of a human being", consisting of 140,000 papers and 1,700 hours of audio and video. It is our conjecture that as lifelogging becomes a normative activity, archivists will have access to rich and unimaginably detailed records of many such individuals, not just those with the time or resources to manually curate a lifetime archive. These chronofiles would provide a first-hand, non-interpreted account of the past from people whose lifelogs provide a direct connection to historical activities and events.
In this paper we suggest that the chronofile generation process of lifelogging can revolutionise the concept of the historical archive. With minimal overhead, any individual will be able to maintain a chronofile. There are many challenges to be solved along the way, some of them documented in this paper, but the early adopters have shown that this is possible and as the benefits of lifelogging become apparent, it is likely to become the norm, rather than the exception. We propose a model of life-long personal chronofile management that takes the onus off manual curation, storage, and access to the digital objects by employing a set of transformation rules that filter or modify the digital objects.

Personal Lifelogging
Lifelogging represents a phenomenon whereby individuals can digitally record their own daily lives in varying amounts of detail and for a variety of purposes. It offers great potential to mine or infer valuable knowledge about life activities. An example of a lifelog archive is shown in Figure 1, in which the activities of the lifelogger (a sequence of about 3,000 images) on the 29th May 2006 are organised automatically into a small set of logical events. Typically, early adopters to lifelogging considered it to be an activity for their own benefit. If lifelogging becomes more pervasive, one can imagine that many users would be willing to share aspects of their lifelog [17] with friends and family while alive or with archivists and researchers when passed away.
Lifelogging becomes possible as a result of three parallel advances in technology. Firstly, sensors are becoming cheap, reliable, robust, power-efficient and portable. There are many low-cost devices such as the OMG Autographer or the Narrative Clip that capture thousands of images per day. Digital audio recorders can record in detail 24/7 audio, a new generation of wearable video cameras can capture much of a day in high definition. Even our mobile phones include enough sensors to digitally lifelog our activities. It is now possible to gather a mediarich representation of our activities in detail that is previously unimaginable. Secondly, the cost of storing and transmitting large quantities of data from sensors and cameras has decreased. From [7] we know that we can currently store 6-8 years of wearable camera images on a $100 hard drive. Thirdly, we have new search and artificial-intelligence techniques to allow us to convert large volumes of raw sensor data into meaningful semantic information that can derive new and aggregated knowledge from this data. All these three technological advancements have brought us to this point: the advent of the era of the lifelogged individual.  [12] There are many potentially life enriching benefits that could encourage an individual to engage in lifelogging, such as the potential for better self-awareness leading to longer and more active lifespans, new personalised healthcare applications, enhanced methods of learning, increased productivity in the workplace, increased independence, or mobility for people suffering from various memory and cognitive impairments, and new forms of offline and online social interaction [7]. It is considered that as these benefits become apparent, that lifelogging will become a normative activity.
Many use-cases of lifelogging have been proposed, for example, to assist the lifelogger in tasks such as personal healthcare, memory reminiscence [3], and browsing a digital record of past activities [12]. There is now real potential that we are on the cusp of an era of, what Gordon Bell and Jim Gemmell refer to as total capture [2]. In fact, this has already begun with the market availability of lifelogging devices.

Lifelogs as Societal Records
We know from [14, p.139] that "all events have their witnesses, their memory: the trace" and that witness is born through communication of events. The tools we employ for communication today far outweigh the pen and paper of yesterday. Chronofiles promise a new dimension to witness, memory and trace. Consider if you will, a historian in 2114; he will have access to vast chronofile archives from the deceased first generation of lifeloggers. He will have access to orders of magnitude more information about the individual than we are currently gathering in 2014. The events, as before, will be witnessed and memorised, but the form they leave in the trace is so much richer in a world of lifelogging. Mis-interpretation of events and generating historical narrative based on only snapshots of historical communications will be a problem of the past.
One example is the story [15] of the sinking of the "Olong" and the subsequent misinterpretation of events and witness accounts. Human error and distant reporting of a chaotic scene taking place far from land where a sinking boat and a father gesturing the Navy to take his child becomes the story of desperate refugees willing to use all means possible to force the Navy to rescue them, including risking the lives of their children by throwing them overboard. This event has been documented and analysed in detail. Witness statements and logs are placed within a kind of system-centric approach to documenting, which means that the story is documented from societies point of view, placed in system so that we can learn more about society. The story is about a group of people trying to make it to Australia for a better life, but we are missing the story about the individual. The individual's search for a better life, the journey, the sinking and what subsequently happened to the individuals is lost. The true story lies distributed in peoples memory and portions of this story die as memories fade. The story of the individual takes second place to society's story. In the era of chronofiles the story about the individual does not have to be a footnote in a formal document.

Data Formats
While most historians will find lifelogging a treasure trove of information, it will also certainly pose problems in terms of long term preservation that may not be obvious yet. When it comes to electronic material it is already clear that archivists have a lot of trouble maintaining collections of electronic material. The reason for this is the short lived timespan that some file formats have and their evolutionary nature. Today we even have trouble correctly interpreting some word-processing documents from twenty years ago.

A Life Digitised
To understand the potential sources of knowledge and evidence contained in chronofiles, we can look to the early adopters and the data that they store. The manually generated chronofile of Richard Buckminster-Fuller, that we mentioned earlier, is a detailed first-hand record of a life lived. It is unlikely that there are many others willing to put in so much effort. Recent early adaptors, such as Bell [1] and Mann [13] show the potential of what can be captured for a basic first-generation chronofile and they motivate the necessity for chronofiles to be generated automatically by wearing a small set of non-intrusive sensing devices. These first generation chronofiles, which are called lifelogs, are simple data capture, storage, processing, and interaction frameworks that store the data in fixed formats and do not take into consideration the archival challenges of longterm storage and curation of the data. Figure 2 shows an example architecture of a first generation, widely deployable lifelog that is concerned with capturing rich data about the user experiences; organising and enriching it to make it usable for the individual; and finally supporting pervasive access via current access devices.

Data Storage Requirements
The lifelogs being captured today already provide detailed knowledge about the minutiae of life in 2014, with many potential sources of information that can be included. The list of sources from [7] includes passive visual capture devices that take up to 4,000 images per day or short-durations of video, passive capture audio to record the sounds of life, personal biometrics to understand the physical state of the individual, mobile device context to understand the individuals place in the environment, the communications of the individual, the content they create and consume, their environmental context, media consumption, and any annotations to that content. To illustrate the variety of data sizes and quantities, a summary table of a selection of lifelog data is shown in Table 1. In this table we include the annual storage requirements as well as a lifetime (85 years) storage requirement. 4 All this data is inherently unmanageable if left to the individual. The huge data volumes involved require the development of a suite of organisation and search tools that allow the individual to gain benefit from the lifelogging process. At present, these search tools, described in more detail in [7] allow for the conversion of a raw chronofiles into a manageable set of digital objects. To take a human memory analogy, these roughly align with the idea of an event in the life of a human (see the event list in Figure 1). The digital objects then act as the unit of observation and retrieval for the chronofile. In order to be located by a search mechanism, these events need to be enriched with appropriate metadata, indexed by search tools and made available via an appropriate interaction mechanism (e.g., Google Glass for the lifelogger or a desktop archive search tool for an archivist).
With the exception of digital video data, one can easily imagine storing a lifelog of an individual indefinitely. Because at current capture rates, it requires about 1 TB per year to capture wearable camera photos from an off-the-shelf  Table 1. An illustration of the data quantities and data sizes for a selection of chronofile data in 2014, over a day, year and a lifetime (using 85 year lifespan and 16 hour days) 5 Mega Pixel wearable camera, along with various other continually sampling sensor data (e.g., accelerometer, GPS, and audio snippets). Consider the Autographer wearable camera. If one wore it for an 85 year lifespan, the storage requirements of six photos per minute would only require ten of today's hard drives. Today, it is therefore feasible to store this data permanently and provide direct non-interpreted knowledge about individuals.
Although the data produced by lifeloggers today is manageable with current technologies, information technology seemingly has a tendency to follow an exponential pathway of advancement. We have already seen this in Moore's Law for CPU transistor densities, Kryder's Law [4] for disk storage, and in Kurzweil's Law of Accelerating Returns [11] for general information technology advancement. Assuming lifelogging archive sizes follow similar growth curves, a capture rate of one Terabyte per year today has the potential to become 1 Zettabyte of data per year by 2045, or 1 Geopbyte by 2075. 5 Some might argue that ever growing storage device capacities coupled with efficient compression algorithms will adequately support any future storage demands of personal lifeloggers. Others argue the contrary; that the modern society already produces way more data than available storage can handle. In particular, IDC [5] already predicted in 2007 that the 255 Exabytes of information created and replicated that year was for the first time to surpass the 246 Exabytes aggregate storage capacity available globally. Also, they predicted that the gap between disk demand and supply would just be larger. Some years later, their prediction may be correct.

Curation
Expecting an individual to curate their chronofile in a fine-grained manner to fit within available storage space, to migrate to new file formats, to address potential legal and privacy issues, is not realistic. Even today, the early adopters see chronofile archives as a form of data dump into which all possible data is stored, either because it is too troublesome to manually curate the data, or because it is considered more prudent to keep all data on the chance that it could potentially be useful at some point in the future. Therein lies the problem that we foresee; the chronofile needs to be self-organising. We therefore propose a model for chronofiles, based on the Gardi model [6] we proposed for multimedia collections, which iterates over data sources temporally and applies higher-order information transformation rules directly on the stored digital objects. Gardi was positively evaluated for security video archives, home video, recordings and a very early stage visual lifelog.
In previous work, we have successfully applied such application specific data curation techniques for a concrete lifelog scenario in the sports domain. A lightweight lifelogging service was built and deployed for head coaches as part of elite soccer performance development. Soccer arenas and training grounds are populated with stationary [9] and portable cameras [8], and mobile devices provide support for hindsight annotations of sequences worth capturing. This also includes prototypes with Google Glasses used on the field by coaches. This way, coaches determine after a certain event has unfolded whether to permanently store this or not, and, if so, touches the cellular screen. Experience from a complete soccer series in Norway for a specific team over a year indicates that about 5% of video footage from complete games are persisted this way and made use of for analytics and feedback procedures. The other 95% of the video footage rendered useless with regard to events worth examining, can still be stored somewhere for archival purposes or permanently deleted. We conjecture similar techniques have broad applicability for personal chronofiles and long-term preservation.

Privacy
Since we do not envision that chronofiles will be curated by individual users, we suggest that policies regarding use and curation will be of concern. This implies that chronofiles also have the potential to be damaging if accessed inappropriately during the individual's life, or if accessed insensitively after death. Consider the case of the Norwegian explorer Fridtjof Nansen; he was an explorer, a scientist, a diplomat, a humanitarian and Nobel Peace Prize laureate. In 2011 a book was published detailing explicit exchanges between Nansen and his much younger partner. His once private collection had been put on display. This resulted in a change in the perception of Nansen, and is testament to the fact that the story the archive tells about a person can be damaging. A chronofile, assessed after an individual's death may contain deeply personal data.
Hence the need for automatic curation to ensure privacy and reputation would be very necessary. Privacy regulations and personal privacy constraints must be properly supported by the software hosting and maintaining these chronofiles. This must be provided for the computer-illiterate as a rule, not exception. Also, the chronofiles will be stored and maintained in a virtual network, not a centralised physical digital library, including enterprise silos, public services, specialised cloud providers, and even private utilities.

Chronofiles Transformation Model
Based on the ideas and discussions listed above, we propose an approach for lifelong and post-life management of personal chronofile data. Our model extends the basic lifelogging architecture described in Section 3 with the the concept of lifecycles of lifelog data using a set of transformation rules that operate over the chronofile data as needed, as illustrated in Figure 3. These transformation rules, in their present form, are classified as: These data transformations can be independent tools that are automatically executed as required by the chronofile management software and permanently 6 For more information on transformation rules for lifelogs, see the initial set in [6]. 7 Privacy and the Right to Privacy are concepts that vary across time and jurisdiction.
In many cases, it may be more appropriate that the chronofile applies access-time, rather than permanent transformations on the data modify the data. There would also be access-time transformations, the aim of which is to limit what a user can see, while maintaining the integrity of the underlying data. For example privacy restrictions on lifelog data may require the chronofile to hide private or intimate content from some or all viewers, or display transformations which format chronofile data to take advantage of whatever access mechanism is being employed. We have embarked on building a series of systems targeting long-term virtual storage infrastructure for early-stage personal chronofiles [6,10,16]. Our fundamental approach is to add self-contained and autonomic meta-code to the data collections or individual data items complementing traditional meta-data of today. In this way, expressive transformation or curation rules live alongside the data to be curated and can be maintained over a long timespans.

Conclusion
A traditional and important source of information when archivists and historians try to piece together the story of someones life is the subjects own diary. Combined with the contents of exchanges of information (letters) and other sources, the historian will carefully analyse and create an understanding of a person. In the traditional archive sense, there are few people that have their entire lives documented. The chronofile changes everything-forever. In many ways the chronofile reduces the influence of historians on the historical narrative. Historians will no longer have to fill gaps by matching various information pieces together, guessing and interpreting. This has the potential to give the individual a lot more control of how history will view them, but also the potential to have personal data examined. On the other hand the sheer volume of material requires the development of new tools and opens for many new exciting research areas for historians. Both inter and intra chronofile analysis will provide historians with an ability to understand the path-of-life in a manner that we have never been able to before.
We have discussed the data lifelogging that can generate and motivated why this could be a very useful data source for historians and archivists. We considered how lifelogs operate today and look forward to a time when the data quantity and richness of a lifelog will be orders of magnitude greater than today. We then proposed a model for chronofiles that allows them to grow and be managed by software, yet still maintain detailed representations of life activities and migrate automatically to latest formats, so that they are available for the lifelogger, and later the historians and archivists. Chronofiles gives the individual the ability to decide in advance what material should be available and to whom. Perhaps chronofiles will allow historians of the future to trace certain life-events of the individual and better understand their consequences for society as a whole. The analysis of multiple chronofiles within in social sciences setting may lead to a much better and deeper understanding of human behaviour. Chronofiles have the potential to positively impact on the life of the individual, the historian and society as a whole.