A Unifying Framework for Analysis of Spatial-Temporal Event Sequence Similarity and Its Applications

Round 1

Reviewer 1 Report

The manuscript tackles a challenging problem relevant to similarity (distance) measures for spatial-temporal event sequences. 

The paper has a major problem with the presentation and the structure.  Some sentences contain repeated terms, make unclear points or often make more than one point.  Some sentences are unnecessarily long which makes reading and understanding the article difficult.  Let us take the first paragraph for clarification: “event sequences are a form of data that can be mined for knowledge discovery.”  This sentence does not provide any useful information for the reader. When it is expected to have a support sentence in that paragraph to clear “what form of data?”, the authors talk about the frequent goals among researchers.  Similar problems can be found throughout the article.     

This paper lacks of both a thorough review of the literature and some deep comparisons with state-of-the-art methods. I would suggest adding a “Related Work” section and possibly comparing the proposed method with the existing work.

Definitions presented in the paper are not necessary. The same matrix called event matrix is defined four times because it can take four different input data types!

Author Response

Reviewer1

The manuscript tackles a challenging problem relevant to similarity (distance) measures for spatial-temporal event sequences. 

The paper has a major problem with the presentation and the structure.  Some sentences contain repeated terms, make unclear points or often make more than one point.  Some sentences are unnecessarily long which makes reading and understanding the article difficult.  Let us take the first paragraph for clarification: “event sequences are a form of data that can be mined for knowledge discovery.”  This sentence does not provide any useful information for the reader. When it is expected to have a support sentence in that paragraph to clear “what form of data?”, the authors talk about the frequent goals among researchers.  Similar problems can be found throughout the article.     

We have reviewed the paper carefully to shorten sentences and clarify the presentation. The introduction has been rewritten to improve clarity as well as other parts of the paper where reviewers indicated some redundancy or greater need for clarity.

This paper lacks of both a thorough review of the literature and some deep comparisons with state-of-the-art methods. I would suggest adding a “Related Work” section and possibly comparing the proposed method with the existing work.

Related literature on event sequence similarity is covered in the Introduction section. We did not include this as a separate section as this did not seem to match the journals typical sections of Introduction, Materials and Methods, Results and Discussion. If appropriate we would be happy to make a section 1.1 on Related Work. We do note that our evaluation section does test our method against several of the well know and still current state of the art methods for event sequence similarity.

Definitions presented in the paper are not necessary. The same matrix called event matrix is defined four times because it can take four different input data types!

We agree with the reviewer on this and have removed the previous definitions. The different cases now appear more simply as equations for producing the event sequence matrix for the different punctual (point) or interval event cases (with and without consideration of magnitude of events). Equation 2 remains as the general event sequence matrix representation that can accommodate any temporal granularity defined by user or a specific research problem.

 

Reviewer 2 Report

The paper introduced a framework representing spatial-temporal event sequences for similarity measures and clustering analysis.

The paper is well written. However, the major concern is the simplified representation of the spatial dimension in the framework. Specifically, how to handle spatial coordination? How to decide the spatial scale when measuring the distance?

In the Matrix representation of STES: the locations are represented as one-dimension rows. However, geographic locations should be two or three dimensions. Would a single row be sufficient?

The author also acknowledged that the temporal granularity is specified by users. What about geographic scales? And how to represent the spatial data in the STES matrix when the spatial data are from different geographic projections.

The performance of the proposed similarity measures is not evaluated in Section 3.2, only the execution speed is compared in Section 3.2.1.  What is the purpose of the 3.2.2 section? 

Please add more details about the clustering analysis in line 597.

Author Response

Reviewer2

The paper introduced a framework representing spatial-temporal event sequences for similarity measures and clustering analysis.

The paper is well written. However, the major concern is the simplified representation of the spatial dimension in the framework. Specifically, how to handle spatial coordination? How to decide the spatial scale when measuring the distance?

In this paper the role of the spatial dimension is essentially categorical. It is the location at which an event sequence is observed. The location is represented by a label but could be considered a point (location of a monitoring station), an area (county with a sequence of daily Covid cases), or potentially a volume.  Our future research is addressing spatial similarity metrics.

In the Matrix representation of STES: the locations are represented as one-dimension rows. However, geographic locations should be two or three dimensions. Would a single row be sufficient?

The rows represent spatial locations. As indicated in the above response the role of the spatial dimension is categorical and represented by a label although the spatial locations could in fact take different forms. Yes, one dimension or a label is sufficient to represent a location or place but with two or three dimensions we can localize a geographic location. This research does not involve the geographic processing of the locations.

The author also acknowledged that the temporal granularity is specified by users. What about geographic scales? And how to represent the spatial data in the STES matrix when the spatial data are from different geographic projections.

The reviewer is correct that in order to address similarity among the spatial locations of event sequences a number of variables should be considered. For example, if similarity in spatial location relies on distance between locations, the coordinate reference systems would be required and would need to be the same.

The performance of the proposed similarity measures is not evaluated in Section 3.2, only the execution speed is compared in Section 3.2.1.  What is the purpose of the 3.2.2 section? 

Section 3.2.1 addresses just performance speed of the algorithm.  Section 3.2.2 is designed to test the accuracy of the similarity metric as well. Here we test how well the similarity metric performs on simulated data with specified levels of similarity, different patterns and different levels of noise.

Please add more details about the clustering analysis in line 597.

We added a reference to the clustering method used and some clarifying language. The last experiment uses our event sequence similarity approach to measure the similarity among sequences of precipitation events exceeding 1 inch at several monitoring stations along the Maine coast.  The clustering analysis uses these similarity measures as the basis for clustering the event sequences. The results show the emergence of five clusters (groupings of event sequences that are most similar). The heatmap and cluster dendrogram indicate that these clusters are in fact spatial clusters indicating that for this case, sequences that are close in space tend to be more similar. We have modified and added these sentences to the manuscript which we hope makes this clearer.

Reviewer 3 Report

The authors present unified matrix-based spatiotemporal event sequence representation (STES) combining punctual and interval-based events. The work investigates the formulation of an effective STES framework for long-term observation within a geospatial region and how similar events occur in proximity (i.e., spatially). Various similarity indexes for different situations (like binary timestamped events and interval events with time overlap) have been proposed to evaluate the performance. The similarity matrix is motivated by the Jaccard Similarity index. KNN classification is performed to match performance with other baseline distance similarity metrics.

Strength

• The key strength of the paper is its experimental evaluation. Real-world datasets from an environmental use case (temp and precipitation datasets) are used for identifying local and global event sequence similarities. In addition, a software repository is provided, which can be used to benchmark the work.
• The paper is technically sound, easy to read with required figures at appropriate places.
• Matrix-based event spatiotemporal representation is an innovative way for similarity modelling for long term event sequences.

Weakness and Suggestions

Minor Typos

• Fig 3 add … HML, abbreviations as high, medium, low.
• What is t (m<=t) in line 177?
• I would suggest club Eq. 2 and Eq. 3 under definition 1 to eliminate redundancy.
• Line 240 extra ‘)’
• Line 305- typo other should be lev(es_2j)

Major Cons/ Recommendations to improve the paper

• Most content in the paper is redundant, specifically in experiment sections. It’s good to have the performance of two datasets (i.e., temperature and precipitation), but there is no variety in datasets themselves. The datasets characteristically have the same configurations, i.e., real numbers from 20 sensor locations, which adds redundancy in the experiments.
• How the STES matrix handles the interclass similarity event sequences? The local and global similarity are currently based on same class event sequences (e.g., comparing precipitation data across different spatial locations for a given time window). What if a user wants to compare the event sequence patterns from different classes like (precipitation vs temperature etc.)?
• How will the STES matrix handle the non-real number data like strings? Furthermore, a lot of environment data also come in different formats like multispectral signals, images etc. In that scenario, the current threshold-based metrics are not applicable.
• The current STES matrix handles 2-dimensions, i.e., space and time. How will the matrix handle n-dimensions event sequence problems like space-time comparison for rain, temp, humidity etc.?
• Currently, it is assumed that data is already available and then a fixed size matrix is initialized. How will the STES matrix handle data which is continuously streaming? In the current scenario, the temp sensors will continuously be streaming data (sec., mins, hours etc.). How will the matrix evaluate the next (t_20+30) second?
• The experiments are performed on very small matrix size. It would be good to evaluate the similarity performance on a bigger matrix size as well (e.g., 100 spatial location* 100K readings).
• The windows used in the experiments are tumbling count windows of fixed size. How will the STES handle sliding window operation as the tumbling window may miss many similar event patterns?
• In Fig. 16, it seems the cosine distance metrics perform better than the proposed approach (both in accuracy and time used)? Any specific reason for that as it undermines the proposed method.
• Similar Comment for Fig. 18.
• The current work focuses on sequence temporal operation. What about other temporal operations like ‘conjunction’ and ‘disjunction’ event patterns over a given time window.
• Sequence operation itself comes with different selection strategies like ‘skip-till-any’ and ‘skip-till-next’. How will the STES handle such event sequence strategy?
• Of course, all the above comments can not be addressed in a single paper. Therefore, it is suggested to authors that a proper limitation and future work section be added to demarcate the current contributions and future work.

Author Response

Reviewer3

The authors present unified matrix-based spatiotemporal event sequence representation (STES) combining punctual and interval-based events. The work investigates the formulation of an effective STES framework for long-term observation within a geospatial region and how similar events occur in proximity (i.e., spatially). Various similarity indexes for different situations (like binary timestamped events and interval events with time overlap) have been proposed to evaluate the performance. The similarity matrix is motivated by the Jaccard Similarity index. KNN classification is performed to match performance with other baseline distance similarity metrics.

Strength

• The key strength of the paper is its experimental evaluation. Real-world datasets from an environmental use case (temp and precipitation datasets) are used for identifying local and global event sequence similarities. In addition, a software repository is provided, which can be used to benchmark the work.
• The paper is technically sound, easy to read with required figures at appropriate places.
• Matrix-based event spatiotemporal representation is an innovative way for similarity modelling for long term event sequences.

Weakness and Suggestions

Minor Typos

• Fig 3 add … HML, abbreviations as high, medium, low.

Thank you for pointing out these abbreviations. We have added them to the Fig 3 caption.

• What is t (m<=t) in line 177?

s and t are the row and column indexes for spatial locations and timestamps respectively in the raw data (time series) matrix (Equation 1); n and m are row and column indexes in the event sequence matrix (Equation 2). Due to some data reduction from eventization, n and m can both be less that s and t

 

• I would suggest club Eq. 2 and Eq. 3 under definition 1 to eliminate redundancy.

It is a good suggestion. In order to simplify the representation of the event sequence matrix and eliminate redundancy, we removed event matrix representations from Definition 1 to 4 and pointed to Equation 2 because Equation 2 is the general event sequence matrix representation for any temporal granularity defined by user or a specific research problem.

 

• Line 240 extra ‘)’

We corrected the misplaced ‘)’ and added ‘,’ at the end of b) timestamped……magnitude

• Line 305- typo other should be lev(es_2j)

Thank you for pointing it out. We have corrected it, from lev(es_1j to es_2j).

 

Major Cons/ Recommendations to improve the paper

• Most content in the paper is redundant, specifically in experiment sections. It’s good to have the performance of two datasets (i.e., temperature and precipitation), but there is no variety in datasets themselves. The datasets characteristically have the same configurations, i.e., real numbers from 20 sensor locations, which adds redundancy in the experiments.

The purpose of the implementation section with two datasets of precipitation and temperature is to demonstrate how to calculate pairwise similarities between event sequences formed in five situations. These two datasets represent typical time series which are usually real valued. They form the starting point to indicate how the different event types can be formed from them and result in the  five different types of STES: 1) STES composed of punctual (point) binary or categorical events, 2) STES composed of punctual (point) events considering the magnitude of event, 3) STES composed of interval (with start-end timestamps) binary events (without magnitude of event, 4) STES composed of interval events with consideration of event magnitude and internal variations within individual interval events, and 5) STES composed of interval events with consideration of event magnitude but without consideration of internal variations within individual interval events. Correspondingly, we compute local and global similarities between STES for these five situations.

• How the STES matrix handles the interclass similarity event sequences? The local and global similarity are currently based on same class event sequences (e.g., comparing precipitation data across different spatial locations for a given time window). What if a user wants to compare the event sequence patterns from different classes like (precipitation vs temperature etc.)?

While this paper only focuses on the spatial difference/similarity between the same class event sequences, the STES matrix can be extended to handle the interclass similarity between event sequences as long as pairwise event sequences have corresponding timestamps locked. Two situations: 1) for interclass event sequences represented as binary events the methods described in this paper can be directly applied to the interclass similarity, 2) if interclass event sequences are composed of events with magnitude (or values) the STES matrix can be used after normalization of both row and column for each class event sequence matrix.

• How will the STES matrix handle the non-real number data like strings? Furthermore, a lot of environment data also come in different formats like multispectral signals, images etc. In that scenario, the current threshold-based metrics are not applicable.

In this paper we have discussed the non-real number data for the univariate category through conversion to binary data, and ordinal values with letters. Future work will be extended to multivariate event sequences and we can handle strings as multivariate event sequences via the STES matrix as long as pairwise event sequences have corresponding sequential order. The purpose of using threshold-based eventization or event abstraction in this paper is to simplify demonstration scenarios of unification of different event types. For image data, image time series would need to undergo image processing steps such as feature extraction to obtain an event sequence. This would involve a complex eventization process beyond the scope of this paper but certainly an option for future work.

 

• The current STES matrix handles 2-dimensions, i.e., space and time. How will the matrix handle n-dimensions event sequence problems like space-time comparison for rain, temp, humidity etc.?

Similarly to above, this is a multivariate event sequences problem that we will conduct in future work. Our current thinking is to decompose n-dimensions to n STES univariate matrices as long as they are time-locked or have the same sequential order, then we can conduct interclass comparisons and compute spatial similarities between multivariate event sequences via weighted or unweighted indexing approaches.

 

• Currently, it is assumed that data is already available and then a fixed size matrix is initialized. How will the STES matrix handle data which is continuously streaming? In the current scenario, the temp sensors will continuously be streaming data (sec., mins, hours etc.). How will the matrix evaluate the next (t_20+30) second?

We agree that the framework described in this paper focuses on the available data. However, with some time lags or near real-time the STES can still handle the streaming data by continuously feeding it in the way a CEP (complex event processing) system does. We plan to continue to develop a better approach to handle the streaming data in the future. By incorporating some models of machine learning with the event patterns from the current datasets we can predict the next second event similarly as the CEP system does in near real-time. We thank the reviewer for this comment and note this as a future research topic in our conclusion section.

 

• The experiments are performed on very small matrix size. It would be good to evaluate the similarity performance on a bigger matrix size as well (e.g., 100 spatial location* 100K readings).

We use these small matrices for demonstrating how to calculate similarities between event sequences of different event types. We agree that it would be good to evaluate the similarity performance on a bigger matrix size. In the application example we do use 43 locations X 1826 temporal points for conducting clustering analysis. In addition, we have successfully applied the methods of this paper to another research on nationwide COVID-19 incidences at county level with the dataset of 2000+ locations X 140+ temporal points (days).

 

• The windows used in the experiments are tumbling count windows of fixed size. How will the STES handle sliding window operation as the tumbling window may miss many similar event patterns?

Technically, the STES is able to handle a dynamic sliding window operation with different sizes as local windows. This is subject to the studies in specific domains. For example, we can align the event sequences based on the first event occurrence at each location and disregard the actual temporal match-ups between event sequences. We can thus mimic the alignments of DNA or protein sequences. We thank the reviewer for this comment and note that it is a topic that needs another separate paper.

 

• In Fig. 16, it seems the cosine distance metrics perform better than the proposed approach (both in accuracy and time used)? Any specific reason for that as it undermines the proposed method.

Our method performs with the same accuracy or better as the algorithms we tested against including Cosine Distance but does show a time disadvantage. We added arguments for our method over others which we have added to the manuscript.

• Similar Comment for Fig. 18.

The same as above.

 

• The current work focuses on sequence temporal operation. What about other temporal operations like ‘conjunction’ and ‘disjunction’ event patterns over a given time window.

Other temporal logic operations like ‘conjunction’ and ‘disjunction’ event patterns will be studied in the future work.

 

• Sequence operation itself comes with different selection strategies like ‘skip-till-any’ and ‘skip-till-next’. How will the STES handle such event sequence strategy?

We haven’t worked on these selection strategies which are used in efficient pattern matching over event streams while processing event streams in a CEP system. We thank the reviewer for this comment and will consider to incorporate the STES into a CEP system in the future work.

 

• Of course, all the above comments can not be addressed in a single paper. Therefore, it is suggested to authors that a proper limitation and future work section be added to demarcate the current contributions and future work.

Your review has noted several very constructive extensions to the work which we appreciate but are not able to cover in this initial paper. We have made note of limitations in our current work and of these potential extensions for future work in the conclusion section of the paper.

Round 2

Reviewer 2 Report

thanks for revising the paper

Reviewer 3 Report

The authors have made necessary changes in the manuscript and given satisfactory remarks for the queries. Currently, limitations are discussed in the conclusion that made the section bigger. I suggest creating a separate section for ‘Limitation and Discussion’ before the ‘Conclusion and Future Work’ section for a better outline.