Patent ID: 12216678

Reference will now be made to implementations, examples of which are illustrated in the accompanying drawings. In the following description, numerous specific details are set forth in order to provide a thorough understanding of the present invention. However, it will be apparent to one of ordinary skill in the art that the present invention may be practiced without requiring these specific details.

DETAILED DESCRIPTION OF IMPLEMENTATIONS

Some implementations of the present disclosure are directed to systems, methods, and user interfaces that enable users to search and glean for patterns in trends. The present disclosure extends the capabilities of general search to supporting intents that involve trends and their properties in line charts.

The disclosed system, also referred to herein as SlopeSeeker, detects analytical trend intents in the search queries and finds trends matching the specified quantifiable properties such as “sharp decline” and “gradual rise” in line charts.

Some implementations leverage quantified semantics of language to explore the nuances of trend patterns and their properties using natural language as the modality for expressing trend search queries.

As disclosed herein, SlopeSeeker integrates text with the search results, along with faceted browsing, to provide additional information and expressivity for navigating the search results. The disclosed system also builds upon search and natural language interface data analysis systems to support the exploration of trends with a comprehensive labeled semantic concept map of trends and their properties.

FIG.1illustrates an exemplary process100for exploring data trends in time series data, in accordance with some implementations. In some implementations, the process100is performed by a computing device200executing an application that includes a user interface. In some implementations, the process100is performed by a server system300executing a web application that includes a user interface module.

The process100includes receiving (112) a natural language input104directed to a dataset140that includes time series data. In some implementations, the natural language input104is received as text input via a search bar102of a user interface110. In some implementations, the natural language input is a voice command or any other type of user input.

The process100includes executing (114) queries against a search index130to retrieve labeled trend events. The process100includes determining (116) a respective composite score for each labeled trend event. The process100includes grouping (118) the labeled trend events into “buckets” based on respective chart identifiers. The process100includes determining (120) a respective total score for each “bucket,” and displaying (122), via the user interface110, one or more ranked charts124(e.g., ranked according to the total score). In some implementations, a displayed chart124includes a chart identifier126. In some implementations, the displayed chart124includes one or more annotations127corresponding to segments of the line chart whose time periods have the highest scoring matches. In some implementations, the annotated segments127are also visually emphasized (e.g., in a different color, or line thickness, or other visual emphasis) compared to other portions of the line chart. The chart124is displayed with an accompanying text snippet128describing up to three highest matches for the line chart. The emphasized chart segments and corresponding text snippets are interactively and bi-directionally linked. Hovering over a chart segment fades out any other emphasized segments and highlights the corresponding text in gray; hovering over a text snippet works similarly.

FIG.2Ais a block diagram of a computing device200, in accordance with some implementations. Various examples of the computing device200include a desktop computer, a laptop computer, a tablet computer, and other computing devices that have a display and a processor capable of running a data visualization application230. The computing device200typically includes one or more processing units (processors or cores)202, one or more network or other communication interfaces204, memory206, and one or more communication buses208for interconnecting these components. In some implementations, the communication buses208include circuitry (sometimes called a chipset) that interconnects and controls communications between system components.

The computing device200includes a user interface210. The user interface210typically includes a display device212. In some implementations, the computing device200includes input devices such as a keyboard, mouse, and/or other input buttons216. Alternatively or in addition, in some implementations, the display device212includes a touch-sensitive surface214, in which case the display device212is a touch-sensitive display. In some implementations, the touch-sensitive surface214is configured to detect various swipe gestures (e.g., continuous gestures in vertical and/or horizontal directions) and/or other gestures (e.g., single/double tap). In computing devices that have a touch-sensitive display214, a physical keyboard is optional (e.g., a soft keyboard may be displayed when keyboard entry is needed). The user interface210also includes an audio output device218, such as speakers or an audio output connection connected to speakers, earphones, or headphones. Furthermore, some computing devices200use a microphone220and voice recognition to supplement or replace the keyboard. In some implementations, the computing device200includes an audio input device220(e.g., a microphone) to capture audio (e.g., speech from a user).

In some implementations, the memory206includes high-speed random-access memory, such as DRAM, SRAM, DDR RAM, or other random-access solid-state memory devices. In some implementations, the memory206includes non-volatile memory, such as one or more magnetic disk storage devices, optical disk storage devices, flash memory devices, or other non-volatile solid-state storage devices. In some implementations, the memory206includes one or more storage devices remotely located from the processors202. The memory206, or alternatively the non-volatile memory devices within the memory206, includes a non-transitory computer-readable storage medium. In some implementations, the memory206, or the computer-readable storage medium of the memory206, stores the following programs, modules, and data structures, or a subset or superset thereof:an operating system222, which includes procedures for handling various basic system services and for performing hardware dependent tasks;a communications module224, which is used for connecting the computing device200to other computers (e.g., server300) and devices via the one or more communication interfaces204(wired or wireless), such as the Internet, other wide area networks, local area networks, metropolitan area networks, and so on;a web browser226(or other application capable of displaying web pages), which enables a user to communicate over a network with remote computers or devices;an audio input module228(e.g., a microphone module), which processes audio captured by the audio input device220. The captured audio may be sent to a remote server (e.g., a server system300) and/or processed by an application executing on the computing device200(e.g., the application230or the natural language processor234);an application230(e.g., SlopeSeeker). In some implementations, the application230includes:a graphical user interface110(e.g., the SlopeSeeker user interface as illustrated inFIGS.14B,18A-18G,19A-19D,20A,20B, and21A-21I) for a user to input natural language queries and display data visualizations (e.g., charts and line plots) and text snippets in response to the natural language queries;an interface manager232(seeFIG.14A), which receives natural language queries (e.g., via the SlopeSeeker user interface110), passes the queries to a parser236(e.g., a semantic parser) (and/or a natural language processor234) for processing, receives relevant documents from a search index130, and generates outputs that include charts, accompanying annotations, and/or text snippets;a natural language processor234, which processes natural language queries;a parser236(e.g., a semantic parser), as discussed below in Section V.C.;a visualization generator238, which generates and displays data visualizations (e.g., line charts) and accompanying annotations, and text snippets; andan optional ranking module240, which ranks labeled trend event results returned from the search index130. In some implementations, the ranking module240ranks the results based on how precisely the search term (e.g., natural language input query) matches the event labels of the document. In some implementations, the ranking module240ranks the results based on a visual saliency score of the labeled event.a search index130(e.g., a search engine such as Elasticsearch, or other search indexing frameworks such as Solr, Sphinx, or OpenSearch), which is described in further detail in Section V.D. In some implementations, the search index130includes:configuration settings242(e.g., configuration specifications), which define the requirements for analysis and indexing;an analysis module244, which processes query string tokens and retrieves the most relevant labeled events based on the degree of overlap between the set of query string tokens and the document string tokens; anda ranking module246, which ranks labeled trend event results returned from the search index130. In some implementations, the ranking module246ranks the labeled trend event results by computing a respective label score and a respective visual saliency score for each labeled trend event that was returned from the search index130;zero or more datasets or data sources140, which are used by the application230, the search index130, and/or the language model application258. In some implementations, the datasets/data sources140include time series data250. An example of time series data is data of stock prices over time. Other examples of time series data in other domains include healthcare trends, economic data trends, and climate patterns. The time series data includes labeled trend events252, such as a first labeled trend event252-1and a second labeled trend event252-2. In some instances, the time series data250includes 1000, 5000, 10,000, 50,000, or 100,000 labeled trend events.FIG.2Bshows a block diagram of a labeled trend event252-1in accordance with some implementations. In some implementations, a labeled trend event252-1corresponds to a portion of a line chart and is identified by a chart ID262-1, a start point264-1, an end point266-1, and set of one or more labels268-1. In some implementations, a user selects one or more datasets/data sources140(which may be stored on the computing device200or stored remotely) and input queries are directed to the selected dataset/data sources. In some implementations, a dataset or data source140includes a set of synonyms for data values, data field names, and/or trend analysis labels;APIs256for receiving API calls from one or more applications (e.g., a web browser226, an application230, a search index130, and/or a language model application258), translating the API calls into appropriate actions, and performing one or more actions; anda language model application258, which executes one or more large language models (LLMs).

Each of the above identified executable modules, applications, or sets of procedures may be stored in one or more of the previously mentioned memory devices, and corresponds to a set of instructions for performing a function described above. The above identified modules or programs (i.e., sets of instructions) need not be implemented as separate software programs, procedures, or modules, and thus various subsets of these modules may be combined or otherwise re-arranged in various implementations. In some implementations, the memory206stores a subset of the modules and data structures identified above. Furthermore, the memory206may store additional modules or data structures not described above. In some implementations, a subset of the programs, modules, and/or data stored in the memory206is stored on and/or executed by a server system300.

AlthoughFIG.2shows a computing device200,FIG.2is intended more as a functional description of the various features that may be present rather than as a structural schematic of the implementations described herein. In practice, and as recognized by those of ordinary skill in the art, items shown separately could be combined and some items could be separated. In addition, some of the programs, functions, procedures, or data shown above with respect to the computing device200may be stored or executed on a server system300.

FIG.3is a block diagram of a server system300, in accordance with some implementations. The server system300typically includes one or more processing units/cores (CPUs)302, one or more network interfaces304, memory314, and one or more communication buses312for interconnecting these components. In some implementations, the server system300includes a user interface306, which includes a display308and one or more input devices310, such as a keyboard and a mouse. In some implementations, the communication buses312include circuitry (sometimes called a chipset) that interconnects and controls communications between system components.

In some implementations, the memory314includes high-speed random access memory, such as DRAM, SRAM, DDR RAM, or other random access solid state memory devices, and may include non-volatile memory, such as one or more magnetic disk storage devices, optical disk storage devices, flash memory devices, or other non-volatile solid state storage devices. In some implementations, the memory314includes one or more storage devices remotely located from the CPUs302. The memory314, or alternatively the non-volatile memory devices within the memory314, comprises a non-transitory computer readable storage medium.

In some implementations, the memory314or the computer readable storage medium of the memory314stores the following programs, modules, and data structures, or a subset thereof:an operating system316, which includes procedures for handling various basic system services and for performing hardware dependent tasks;a network communications module318, which is used for connecting the server300to other computers via the one or more communication network interfaces304(wired or wireless) and one or more communication networks, such as the Internet, other wide area networks, local area networks, metropolitan area networks, and so on;a web server320(such as an HTTP server), which receives web requests from users and responds by providing responsive web pages or other resources;a web application330(e.g., the SlopeSeeker web application), which may be downloaded and executed by a web browser226on a user's computing device200. In general, a web application330has the same functionality as a desktop application230, but provides the flexibility of access from any device at any location with network connectivity, and does not require installation and maintenance. In some implementations, the web application330includes various software modules to perform certain tasks, such as:a user interface module110, which provides the user interface for all aspects of the web application330;an interface manager module332, which receives natural language queries (e.g., via user interface module110), passes the queries to a parser module336(and/or a natural language processor module334) for processing, receives relevant documents from a search index130, and generates outputs that include charts, accompanying annotations, and/or text snippets;a natural language processor module334;a parser module336(e.g., a semantic parser), as discussed below with reference to Section V.C.;a visualization generation module338, which generates and displays data visualizations (e.g., line charts) and accompanying annotations, and text snippets; andan optional ranking module340, which has the same functionality as the optional ranking module240.

In some implementations, the server system300includes a database350. In some implementations, the database350includes a search index130, which is described inFIG.2and Section V.D below. In some implementations, the search index130includes:configuration settings242(e.g., configuration specifications), which define the requirements for analysis and indexing;an analysis module244, which processes query string tokens and retrieves the most relevant labeled events based on the degree of overlap between the set of query string tokens and the document string tokens; anda ranking module246, which ranks labeled trend event results returned from the search index130. In some implementations, the ranking module246ranks the labeled trend event results by computing a respective label score and a respective visual saliency score for each labeled trend event that was returned from the search index130;

In some implementations, the database350includes zero or more datasets or data sources140, which are used by the web application330, the search index130, and/or the language model web application358. In some implementations, the datasets/data sources140include time series data250. The time series data includes labeled trend events252, such as a first labeled trend event252-1and a second labeled trend event252-2, as described inFIGS.2A and2B. In some implementations, a data source140includes synonyms254for data values, data field names, and/or trend labels.

In some implementations, the memory stores APIs356for receiving API calls from one or more applications (e.g., a web server320, a web application330, a search index130, and/or a language model web application358), translating the API calls into appropriate actions, and performing one or more actions.

In some implementations, the memory314stores a language model web application358that executes one or more LLMs.

Each of the above identified executable modules, applications, or sets of procedures may be stored in one or more of the previously mentioned memory devices, and corresponds to a set of instructions for performing a function described above. The above identified modules or programs (i.e., sets of instructions) need not be implemented as separate software programs, procedures, or modules, and thus various subsets of these modules may be combined or otherwise re-arranged in various implementations. In some implementations, the memory314stores a subset of the modules and data structures identified above. Furthermore, the memory314may store additional modules or data structures not described above.

AlthoughFIG.3shows a server system300,FIG.3is intended more as a functional description of the various features that may be present rather than as a structural schematic of the implementations described herein. In practice, and as recognized by those of ordinary skill in the art, items shown separately could be combined and some items could be separated. In addition, some of the programs, functions, procedures, or data shown above with respect to a server system300may be stored or executed on a computing device200. In some implementations, the functionality and/or data may be allocated between a computing device200and one or more servers300. Furthermore, one of skill in the art recognizes thatFIG.3need not represent a single physical device. In some implementations, the server functionality is allocated across multiple physical devices in a server system. As used herein, references to a “server” include various groups, collections, or arrays of servers that provide the described functionality, and the physical servers need not be physically colocated (e.g., the individual physical devices could be spread throughout the United States or throughout the world).

I. Crowdsourcing a Dataset of Text Labels with Visual Features

Relevant language describing visual features in charts can be useful for authoring captions and summaries about the charts to help with readers' takeaways. To better understand the interplay between concepts that describe visual features and the semantic relationships among those concepts (e.g., “steep increase” versus “gradual rise”), the inventors conducted a crowdsourced study to collect labels and visual feature pairs for univariate line charts. The motivation for crowdsourcing a labeled dataset of terms and visual features is two-fold: (1) capture semantic descriptions of different visual features in univariate line charts and (2) elucidate and quantify the relationships among those semantic descriptions.

FIG.4illustrates an annotation-collection tool interface400for performing the crowdsourced study, in accordance with some implementations. The tool interface400was implemented as a Typescript frontend and a Django backend attached to a PostgreSQL database, and includes a left portion402and a right portion404.

The left portion402of the interface400comprises 42 word labels consisting of: (i) words related to the basic shape descriptors, ‘up,’ ‘down,’ and ‘flat,’ (ii) adjectives that describe such shapes (e.g., ‘slow,’ ‘rapid,’) and (iii) words that describe the emergent shapes created by such regions (e.g., ‘plateau’ or ‘valley’). To find these word descriptors, the inventors leveraged the hierarchy of hypernyms and hyponyms from Wordnet, whose depth typically ranges up or down to two hierarchical levels (e.g., “up”→[‘increasing’, ‘ascending’]), as well as word2vec to identify related concepts such as “sharp” and “increasing.” In total, the list contained 8 nouns, 13 adjectives, and 21 verbs. While this list is not exhaustive, the inventors considered the set of words as a starting point for collecting nuanced language that describes common features found in line charts. The words were displayed in a randomized order in the interface for each participant to avoid positional bias.

The right portion404of the interface400displays 16 line charts shown in random order to each participant to mitigate any positional bias. The same charts were shown to all participants. The charts were generated in Chart.JS, showing years on the x-axis, ranging from 1960 to 2030. The title and its corresponding y-axis range were randomly assigned from one of the following topics: Average Income ($), Unemployment, Yards per Game, New Hire Referrals, Yearly Tourism, Rate of Inflation (%), Average House Price ($), Krakozhian Ducats per $US, Average Nightly Viewers, Economic Growth Rate (%), Gold Price ($/gram), Oil Price ($/barrel), Consumer Debt, Number of Wineries, Mortgage Rate (%), and Net Capital Flow ($). Each chart is a line graph constructed by connecting seven sequential line segments end to end. Each segment is randomly assigned one of nine different slopes: Up, Down, Flat with slopes [1, −1, 0], SteepUp, SteepDown, SteepFlat with slopes [3, −3, 0], Gentle Up, Gentle Down, Gentle Flat with slopes [0.5, −0.5, 0].

For the study, participants drag words from the left portion402over to visual features of the charts on the right portion404. The words are snapped to the nearest chart position. Words may be moved or deleted once they are attached to a chart. Individual words may be used on multiple charts and multiple times on a single chart. Multiple words can be dragged to the same feature in a chart. The chart identifier, the annotation, the position along the line graph where the annotation occurred, the date the annotation occurred, and a unique anonymous participant identifier were recorded.

The data collected was analyzed by determining “term co-occurrence” and “annotation clustering,” with the goal of discovering quantifiable relationships among the different annotation terms. Annotation co-occurrence enables one to understand how often different annotation terms are used to label the same visual feature. For each annotation, the co-occurrence of every other word is calculated as the average of per-segment % representation. For example, consider two segments that contain the annotation “quick.” If the term “fast” represents 50% of the annotations on the first segment and 30% of the annotations on the second segment, then the overall co-occurrence of “fast” with respect to “quick” is (50%+30%)/2=40%. Note that co-occurrence is not symmetric as “quick” may co-occur with different annotations than “fast.”

Annotations are clustered using hierarchical clustering and Ward's linkage calculated with Euclidean distance. These approaches tend to identify dense clusters while making a minimum number of assumptions about cluster size, shape, and count. Position matrix entries are assigned by segment co-occurrence. For example, if ‘quick’ and ‘fast’ co-occurred 10 times, then each would have the position on the other's axis. The matrix is then scaled so all values are in [0,1], and values of 1.0 are placed along the diagonal.

FIG.5illustrates various inter-word relationships and an average slope of annotations determined from the crowdsourced study, in accordance with some implementations.

Term co-occurrence analysis quantifies which words are typically present together. Agglomerative hierarchical clustering of term co-occurrence results in distinct groups, suggesting a high degree of semantic agreement among participants.

One of the goals of this work is to understand the hierarchical semantics of the visual feature/annotation pairs. Using line slope as a fundamental component of signal shape, the inventors analyzed the average slope associated with each annotation. As shown inFIG.5, slope analysis distributed the various annotation words across a broad continuum from steeply descending to steeply ascending. Not only does this suggest an empirically derived semantic hierarchy (e.g., “soaring” is a steeper increase than “taking off” while “tanking” is a steeper drop-off than “slumping”) the quantification of that hierarchy enables one to make concrete natural language recommendations when generating labels for previously unlabeled signals. The maximum possible slope range available for the charts is −3 to +3.

II. Automatic Labeling of Visual Features in Line Charts

Some implementations disclose two techniques-shape identification and slope identification—for automatic labeling of visual chart features according to the dataset of terms and visual features obtained from the crowdsourced study (see Section above). In some implementations, shape identification is useful for discovering concrete shapes such as “peak” and “valley.” In some implementations, slope identification is useful for describing how univariate data changes along the y-axis.

In this discussion, a univariate data set is referred to as a “signal” and the small annotated source signal whose shape the disclosed algorithm is looking for in a larger unlabeled signal is referred to as the “kernel.”

Shape identification tries to find a participant-annotated visual feature in a larger unlabeled signal.FIG.6illustrates automatic labeling of visual features in a line chart, in accordance with some implementations.FIG.6part A shows an example of finding a “bump” and an “upturn,” in accordance with some implementations. This shape identification approach is particularly applicable to finding visual features that are constructed from multiple segments (e.g., a “peak” consists of a rising segment followed by a falling segment).

In some implementations, a shape discovery algorithm for identifying a kernel signal's shape within a larger unlabeled signal includes the steps of:1. Begin with an unlabeled signal in which it is likely to find a visual feature.2. Collect all 112 (16 line plots*7 segments/plot) annotatable segments and the annotations associated with them.3. For each segment, build a five-segment kernel signal consisting of the annotated segment and two segments on each side of that annotated segment. Note that kernels near the edge may consist of fewer than five segments. For each such kernel signal, create shallow and deep variants of it where the normalized variant heights range from [0.1,1.0] in units of 0.1.4. For each variant, perform normalization, smoothing, and take the first derivative. Employ standard Savitzky-Golay smoothing with a smoothing factor proportional to the kernel size for efficient smoothing and derivation.5. Normalize the unlabeled signal and apply Savitzky-Golay smoothing and derivation.6. Calculate a windowed-mean-absolute-error (MAE) by sliding the kernel past the unlabeled signal, much like convolution. The window size is parameterizable to allow the algorithm to search for visual features of different sizes.7. Accrue these errors for every variant of every kernel.8. For every kernel, calculate MAE z-scores.9. Filter the stored MAE scores using two user-adjustable sensitivity criteria: the maximum acceptable MAE score and the maximum acceptable z-score. Retain any point that falls below either threshold.10. Mark points that meet the criteria threshold. The presence of points indicates that a visual feature is found in the chart.11. Merge adjacent qualifying points into larger annotated regions

In addition to the least-errors shape identification approach taken above, the quantified slope semantics shown inFIG.5provide an additional tool for visual feature identification. Specifically, the quantified slope semantics help identify specific relationships among line slope, hedge words, and the hedge word's semantic modifiers. For example, FIG.5shows a rough hierarchy of single-word slope descriptions from which one might decide to label a line as “soaring” rather than “growing.” However, if verb annotations and their adjective modifiers are considered as a single unit that encodes line-slope information, it becomes much more precise. For example, “taking off” in the context of “gradual” has an average slope of only 0.7, but “taking off” in the context of “quick” has a much steeper average slope of 2.7. Using this information along with word co-occurrence data for the specific <adjective><verb> pairs, the different regions of the analyzed signals can be annotated. This is illustrated inFIG.6at parts C and D.

In some implementations, selecting an <adjective><verb> annotation for a given chart region uses the following protocol:1. Determine the slope of a given region using Ramer-Douglas-Peuker piecewise-linear decomposition.2. Find all <adjective><verb> pairs whose average slope falls within a window (default=0.5) of the desired slope.3. From that set, select the <adjective><verb> pair with the highest annotation co-occurrence. The window in step 2 allows one to use annotation co-occurrence to select more commonly used expressions like “fast tanking” instead of “stagnant accelerating.”

One of the goals of this work is to quantify relationships between visual features and annotations.FIG.5,FIG.6part C, andFIG.6part D show that these terms do, in fact, work together to encode specific slope information that can be used to automatically annotate a univariate signal. Among terms, annotation clustering shows that terms tend to cluster in semantically intuitive ways. Collectively, these findings support the hypothesis that quantitative analysis of semantic labels is capable of generating visual feature labels that are not only human-accessible but also quantitatively accurate. Providing language descriptors for accurately describing data insights can provide useful “guard rails” and guidance as data summary generation becomes prevalent with the use of large language models (LLMs).

III. Visual Feature Integration with LLMs

Some implementations combine the discovered semantic labels discussed above with additional information from the data set to form LLM queries. For example, some instances use a specific stock symbol “ALK” and the dates of the discovered visual feature to ask the GPT 3.5 LLM the templated question, “What happened between <Jul. 8, 2014> and <Jul. 9, 2014> that caused the stock symbol <ALK> to <tank>?”

In this example, the specific LLM response is shown inFIG.6part B. An interesting aspect of LLM integration is that the responses implicitly integrate additional data into the user's investigation. For example, no data involving share price, earnings reports, or even the company name is explicitly linked to the chart.

The models do have limitations around higher-order numeric reasoning and context. For example, inFIG.6part B, while the LLM provided several reasons for the stock price decline, it missed the key fact that there was a stock split. Custom-trained GPT models can potentially bridge this gap in higher-order analytical reasoning by incorporating additional knowledge. In addition to summary generation, other utilities for these custom LLMs can explore the automatic enrichment of additional descriptors for the dataset.

In some implementations, annotations and summaries describing visual features in charts can be used as metadata in search interfaces to find pre-authored charts based on search queries such as, “find me the sales chart that has a spike in 2009, followed by a gradual decline,” or in a voice assistant to ask for real-time notifications about data-“Hey Voice Assistant, tell me if this stock tanks.” The work can also provide language prompts to LLMs to support sketching interfaces used for generating data stories.

IV. Creation and Utilization of Quantified Semantic Label Dataset for Trends

To support an expressive analytical experience for exploring relevant trends in a time series dataset, having a quantifiable understanding of the semantics of the trends is useful. For example, while describing a stock price as “slumping” intuitively corresponds to a less severe decline than “crashing,” quantifying the nuanced differences between these terms enable visual data analysis tools to more easily leverage the words' expressive power.

Some implementations disclose creating a dataset of quantified semantic labels for trend descriptor words, which are in turn used in conjunction with a search index to return precise search results to an analyst.

Crowdsourced experiments were conducted to create the dataset of trend descriptors with quantified semantics. These experiments were designed to collect trend labels associated with precise, isolated slopes. Various trend descriptor types were treated differently with slight modifications to the experimental design depending on whether the data collection is for singleton slope labels (e.g., “falling”), slope labels with modifiers (“fast falling”), or multi-line trend shapes (e.g., “peak”).

The crowdsourced dataset was subsequently operationalized by applying new trend descriptor labels to unlabeled time series data—in this case, stock prices over time.

Some implementations apply a novel visual saliency scoring algorithm to the labeled stock data to help boost perceptually prominent trend descriptor results during search. The final stock data with labeled trends was subsequently used to populate the search index for the SlopeSeeker tool.

IV.A. Quantified Semantic Label Dataset Collection & Analysis

The inventors designed and conducted three crowdsourced experiments (referred to hereinafter as Experiment 1, Experiment 2, and Experiment 3) to collect a dataset of quantified semantics for trend descriptor words. The details of the experiments are described in U.S. Provisional Patent Application No. 63/543,070, filed Oct. 7, 2023, titled “Search Tool for Exploring Quantifiable Trends in Line Charts,” which is incorporated by reference herein in its entirety.

Briefly, the goal of Experiment 1 was to estimate a slope distribution for every label, where each label is a single trend descriptor word. The goal of Experiment 2 was to assess the impact of modifier adverbs on the quantified semantics of two-word trend descriptor phrases (e.g., “falling slowly”). The goal of Experiment 3 was to gather labels for different shapes found in time series data. For Experiment 3, a shape is defined as a pair of connected line segments with varying degrees of (1) inclination angle between the two lines and (2) overall 360° rotation or orientation.

FIGS.7A,7B, and7Cshow the results of the crowdsourced experiments.

FIG.7Ashows the 41 labels that were investigated in Experiment 1 and, for each label, a one-dimensional Kernel Density Estimation (KDE) indicating a probability density for the respective label over the range of −90° to 90°. Peak probability density was used to sort the labels from the most negative angle (steepest down) to the most positive angle (steepest up) from the top left to the bottom right, respectively.

KDE is a common tool for estimating the probability density function of a random variable without making assumptions about the nature of the distribution (e.g., that it is normal). As such, KDE is a useful tool for estimating the slope distributions for each label. Gaussian kernels are a common choice for smoothing KDE datapoints as the shape is symmetric, it has well-understood mathematical properties, and, notably, the ‘bandwidth’ KDE parameter can be interpreted as the Gaussian standard deviation.

FIG.7Bshows the KDE distributions of Experiment 2's compound labels over the range of −90° to 90°. Peak probability density was used to sort the labels from the most negative angle (steepest down) to the most positive angle (steepest up) from the top left to the bottom right, respectively.

Experiment 2 also enabled the overall scaling effect each modifier adverb had on each label's associated angle to be computed. For example, consider a crowdsourced data point from a single participant in Experiment 2 indicating that the “anchor” angle associated with the label “dropping” is approximately −48°. A subsequent Experiment 2 data point from the same participant indicates that the angle associated with the compound label “sharply dropping” is −88°. In this case, the scalar effect of the modifier “sharply” is calculated to be −88/−48=1.8. The slope difference between “dropping” and “sharply dropping” can thus be quantified: “sharply dropping” is 1.8 times steeper than simply “dropping” for this participant. As shown inFIG.7B, in general, “slowly” reduces slope steepness by a factor of 0.4, “gradually” reduces slope steepness by a factor of 0.6, and “quickly” and “sharply” increase slope steepness by factors of 1.3 and 1.5, respectively.

FIG.7Cshows respective two-dimensional KDE plots for shape labels that were investigated in Experiment 3.

IV.B. Quantifying Semantic Relationships

The Cambridge Dictionary defines synonym, hyponym, and hypernym as:Synonym: “a word or phrase that has the same or almost the same meaning as another word or phrase in the same language”Hyponym: “a word whose meaning is included in the meaning of another words”Hypernym: “a word whose meaning includes a group of other words”

These definitions lead to the notion of a semantic hierarchy. Consider the data shown inFIG.8, which is a scatter plot showing implicit semantic hierarchies. The x-axis shows the angle range to which the label has been assigned by experiment participants and the y-axis indicates the width of the inter-quantile range (IQR) of the label angle distributions. Labels with a broader “definition” (applicable to more angle ranges) are at the top and labels with narrower “definitions” are at the bottom. Stated another way, each label is represented by the inter-quantile range (IQR) (the middle 50% of its probability density) of its angle assignments.

Taking the data inFIG.8and the definitions of above, semantic relationships can be derived in the following manner:Synonym: Two words are synonyms if their distributions (or by proxy, their IQRs) are approximately the same.Hyponym: A word is a hyponym of another word if its IQR is subsumed by the other word's IQR.Hypernym: A word is a hypernym of another word if its IQR subsumes the other word's IQR
IV.C. Labeling Events in Time-Series Data

In some implementations, after establishing the KDE distributions for both slope labels and shape labels, these distributions are used to label new time series data represented as raw, univariate input signals. Temporal stock price data is used as an exemplary dataset, and relevant portions of temporal stock price data are annotated with labels such as “sharply climbing” and “cliff.”

An exemplary algorithm for label assignment is as follows: decompose the input signal into linear segments, calculate angles and rotations over those segments, use those angles and rotations to index into the KDEs from Experiments 1, 2, and 3, and discover appropriate labels.

Before executing the steps of the algorithm, the x and y axes of the temporal stock data need to be normalized to roughly the same scale. Otherwise, the angle and rotation calculations would be meaningless. There is no “correct” mathematical relationship or shared scale to be established between the stock price in dollars (or any other non-temporal measure) (e.g., y-axis) and time (e.g., x-axis). To resolve this, two observations were made:(1) The quality of “steepness” is, to a large degree, perceptual and anchored to both the time range that is analyzed and the size and shape of the chart. For example, a multi-month sea level drop viewed over one year might be perceived as “gradual,” but that same drop viewed over 1000 years on a chart of the same size would be perceived as “sudden”.(2) Participants labeled angles in a user interface with an aspect ratio of 1:1, meaning that the visual space was “square.”

With these observations in mind, the input signal was transformed in two ways before data analysis. First, both the x-axis and the y-axis were normalized to span the range [0.0, 1.0]. Second, both axes were scaled by the aspect ratio of the final labeled chart (e.g., 3:1 in the case of this study). This approach provided data with axis units that were comparable (important for proper slope calculation), informed by the viewer's chart presentation, and respectful of the participant's original aspect ratio while performing labeling.

Following the axis normalization, temporal stretches of data are identified and labeled. First, the input signal was decomposed into consecutive linear segments using the Ramer-Douglas-Peucker algorithm (e.g., as implemented in the rdp python package (https://pypi.org/project/rdp/). Epsilon values for the Douglas et al. algorithm were empirically chosen as 0.03, 0.1, and 0.2 to provide three different decomposition resolutions.

For single-segment temporal stretches, the slope of the segment was calculated, and used to index into all the single-label (Experiment 1) or compound-label (Experiment 2) one-dimensional KDEs. The label whose KDE returned the highest probability density was chosen as the label for that segment. Because the KDE models are a continuous surface (e.g., one-dimensional for Experiments 1 and 2, and two-dimensional for Experiment 3) and use Gaussian kernels, which have infinite support, a non-zero probability density will be returned for all points on the real line. Thus, any point-even a point that is far away from all labels and should not be assigned a label-will always return a non-zero probability density score, resulting in some (possibly inappropriate) label. To resolve this, labels with the lowest scores were filtered out by taking the set of all segment labels (one label per segment), sorting them by their probability density, and filtering out the bottom 25%. The remaining 75% of labels were used for the SlopeSeeker database (e.g., in the database350).

FIG.9illustrates examples of segment labeling with single labels, in accordance with some implementations. The three sub-charts correspond to the three levels of linearization. For clarity, only the top 25% of labels are shown in this example.

FIG.10illustrates examples of segment labeling with compound labels, in accordance with some implementations. The three sub-charts correspond to the three levels of linearization. For clarity, only the top 25% of labels are shown in this example.

A similar process was adopted for two-segment (shape) temporal stretches. The angle and rotation of each shape was first calculated, and then used index into all the 2D label (Experiment 3) KDEs. The label whose KDE returned the highest probability density was chosen as the label for that shape. The set of all shape labels (one label per shape) are sorted by their probability density, and the top 75% of labels are used for the SlopeSeeker database.

FIG.11illustrates examples of shape labeling, in accordance with some implementations. The three sub-charts correspond to the three levels of linearization. For clarity, only the top 25% of labels are shown in this example.

Superlatives. In some instances, a user may use superlative descriptors (e.g., “maximum”, “minimum”, “highest point”, etc.) to search for particular features in line charts. With such descriptors, the user evidently wants to retrieve the single highest or lowest value throughout the time frame of the data. In some implementations, to support the querying of superlative features in the dataset, applicable superlative labels are generated. Using the time-series data of stock prices as an example, for each stock, the highest and lowest values are identified over the length of the time series data. Then, the event consisting of 15 days both before and after the maximum or minimum is incorporated into the event label to facilitate ease of viewing, as illustrated inFIG.12.FIG.12shows a line chart1200that is output by the SlopeSeeker system in response to a user query (e.g., maximum stock price”) that includes a superlative descriptor “maximum,” in accordance with some implementations. Segment1202of the chart corresponds to the event where the stock price was the highest.

IV.D. Visual Saliency Scoring

Line chart annotations that emphasize the most visually prominent features of the chart are more effective at helping readers glean meaningful takeaways. To operationalize this concept during search, a way to quantify the visual saliency of each labeled trend event within its chart was established. Otherwise, it would be difficult to identify the most relevant results for a given search query when several matching results could have the same labels based on slope.

Consider the example ofFIG.13, which shows a line chart1300that is output by the SlopeSeeker system in response to a user query that includes the terms “gradually increasing.” Although both segment1302and segment1304of the chart correspond to events that match the user query (e.g., based on slope), the event that occurred during 2016 (i.e., corresponding to segment1304) intuitively appears more prominent and impactful than the event in 2015 (segment1302).

The rationale behind the visual saliency scoring approach is to view each trend event as a vector that covers some of the encompassing chart's visual space in both the x direction (i.e., the temporal duration of the trend) and in the y direction (i.e., the data value delta over the course of the trend).

In some implementations, an exemplary algorithm for computing visual saliency is as follows:for each trend result (single-segment slopes): doCompute the x vector component as the ratio of the entire time range taken up by the trend.Compute the y vector component as the ratio of the entire data value range taken up by the trend.Take these two vector components and use the Pythagorean theorem to compute the L2 norm.end for

In some implementations, the visual saliency is determined using Equation 1 below:

Visual⁢Saliency⁢Score=(xeventend-xeventstartxchartmax-xchartmin)2+(yeventend-yeventstartychartmax-ychartmin)2(1)

Intuitively, trends described by words like “tanking” will mostly be short in x, in which case the most visually salient results will have the largest change in y. On the other hand, trends described by words like “flatline” are likely to have little change in y, and so their visual salience will mostly depend on the duration in x. However, an intuitive correspondence between trend labels and their visual span in x or y does not need to hold for the scoring to provide a useful quantification of visual saliency. Consider again the two events inFIG.13, both labeled as “gradually increasing.” The event during 2016 is longer temporally (i.e., xeventend−xeventstartis greater) and spans a larger value range (i.e., yeventend−yeventstartis greater), therefore giving it a higher saliency score.

For multi-segment shapes, we compute the y vector component using the maximum and minimum values of y over the duration of the shape event rather than the start and end values. More precisely, we use, yeventmax−yeventminin Equation (1) above rather than, yeventend−yeventstart.

In with some implementations,

The final labeled stock data that was loaded into the protype SlopeSeeker tool contains 8,353 data points (labeled events) for 100 different stocks. The time period for each stock is a three-year period from the start of 2014 to the end of 2016, and each labeled event covers some subset of this time span.

Although the example is described with respect to stock data, it will be apparent to one of ordinary skill in the art that the processes to create labeled events as disclosed herein are equally applicable to time-series data in other domains such as healthcare (e.g., Covid cases over time), economic data trends (e.g., employment rates or unemployment rates over time), and climate patterns.

V. SlopeSeeker Tool

According to some implementations of the present disclosure, the SlopeSeeker system is developed as a search tool to operationalize the dataset of quantified semantic trend labels (e.g., as discussed in Section IV).

V.A. Architecture Overview

FIG.14Aillustrates the SlopeSeeker system architecture, in accordance with some implementations. After the user enters a query1402, the input1404is passed to an interface manager232, which in turn passes the raw query1406to a natural language parser236. The query is then processed (1408) and the processed search terms are used to write queries to a search index130(e.g., an Elasticsearch index or other search indexing frameworks such as Solr, Sphinx, or OpenSearch). The search index130returns relevant “documents”1410(and their respective scores) to the interface manager232, which generates the system output1412of charts and accompanying annotations. A “document” as used herein refers to a labeled trend event.

In some implementations, the SlopeSeeker system is implemented as a web-based application using Python and a Flask backend connected to a React.js frontend. For data storage and retrieval, Elasticsearch, a robust distributed search platform built on the open-source Apache Lucene, is employed. The platform offers scalability of data, real-time indexing for fast querying, and is adept at handling text-heavy and diverse datasets. In some implementations, a RESTful API is employed for easy integration with SlopeSeeker.

V.B. Interface

FIG.14Billustrates a user interface110for the SlopeSeeker system, in accordance with some implementations. The user interface110is designed to provide an experience similar to that of using a search engine. On startup, the user is presented with a search bar102(e.g., a natural language input box) (also labeled as “1” inFIG.14B), enabling the user to search for a trend of interest. When results are not exact matches to the user input, a notification box1422(labeled as “2” inFIG.14B) informs the user which terms are not being matched exactly. The user interface110includes a side bar1424(labeled as “3” inFIG.14B) that allows the user to optionally filter the results to include only specific labels that are of interest. The text box filter in the side bar1404is nested hierarchically by individual semantic concepts. For instance, “soaring” is a parent of both “slow soaring” and “fast soaring.” Results appear as tiles1430(e.g., tile1430-1and tile1430-2) in a region1426below the search bar102(labeled as “4” inFIG.14B). Each tile1430corresponds to one stock and shows a line chart1432of the stock price over time (e.g., line chart1432-1for the stock FSLR and line chart1432-2for the stock ILMN), the stock ticker1434, the number of matches1436for that input query for that stock, and a text description1438(e.g., text snippet) describing up to three highest matches for that stock. The time periods corresponding to those highest scoring matches are also emphasized in a different color on the line chart. The emphasized chart segments and corresponding text snippets are interactively and bi-directionally linked. Hovering over a chart segment will fade out any other emphasized segments and will highlight the corresponding text in gray; hovering over a text snippet works similarly. If a stock has more than three matches, the user can expand the tile (e.g., via selection of user-selectable affordance1440) to show a list of the rest of the matches, which can also be hovered over to display on the line chart.

V.C. Semantic Parser

Given the premise of SlopeSeeker is to demonstrate the utility of the quantified semantic trends dataset in the context of a search tool, the present disclosure describes examples that focus on supporting the interpretation of queries to search for trends within an exemplary dataset that includes labeled trend events for stock data. It will be apparent to one of ordinary skill in the art that the processes to create labeled events as disclosed herein are equally applicable to time-series data in other domains.

In some implementations, the SlopeSeeker system includes a semantic parser (e.g., parser236or parser module336) for parsing trends that contain semantic labels, attributes, and temporal filter attributes. The semantic parser converts natural language inputs into structured representations, allowing for explicit reasoning, reduced ambiguity, and consistent interpretation. The semantic parser also provides the convenience of better traceability and are performant for structured tasks. In some implementations, the semantic parser is combined with one or more large language models (LLMs) (e.g., LLM(s)258or LLM(s)358). In some implementations, in the combined semantic parser/LLM setup, the semantic parser is used for structured tasks and the LLMs are used for open-ended tasks in the context of a more comprehensive analytics tool.

In some implementations, the semantic parser is implemented using Python's open-source NLP library, SpaCy, which employs compositional semantics to identify tokens and phrases based on their semantics to create a valid parse tree from the input search query. The semantic parser takes as input the individual tokens in the query and assigns semantic roles to these tokens. The semantic roles are one of four categories: (1) event_type (e.g., single event or multi-sequence event), (2) trend_terms (e.g., “tanking” and “plateau”), (3) attr (e.g., data attributes, data fields, or data field names, such as stock ticker symbols and company names), and (4) date range (e.g., absolute date ranges and relative data ranges).

In some implementations, the tokens and their corresponding semantic roles are translated into a machine-interpretable form that can be processed to retrieve relevant search results in SlopeSeeker. Using an input search query “Show me when Alaska Airlines was tanking before November 2016” as an example, the parser output is as follows:{‘event\_type’: ‘single’,‘trend\_terms’: [‘tanking’],‘attr’: ‘alaska airlines’,‘date\_range’: {‘lt’: ‘2016 Nov. 1’} #“before November 2016”}
V.D. Search Framework

After producing the labeled data for the stock prices (see discussion above), each labeled trend event (considered a “document” for the search scenario disclosed herein) is added to the search index, wherein indexed documents are first retrieved and then ranked according to a match score. In some implementations, the search index130(e.g., Elasticsearch) includes built-in scoring logic that is combined with a visual saliency score to produce a scoring mechanism tailored to the use case described herein. Finally, matching documents are grouped by their parent chart for presentation to a user (e.g., as tiles1430in the user interface110).

In some implementations, SlopeSeeker supports different types of queries beyond single trend events, including event sequences and more long-term, and global descriptors.

V.D.1. Indexing

The indexing phase creates indices for each of the documents in a dataset along with their metadata. Each document (i.e., a labeled event, corresponding to a portion of a line chart identified by a chart ID, start point, end point, and set of labels) is represented as a document vector diwhere:
={d1,d2, . . . ,dn}

In some implementations, n-gram string tokens are stored from these document vectors to support both partial (e.g., inexact) matches and exact matches at search time:
={s1,s2, . . . ,sn}
where si=ε(di) for an encoding function ε that converts each document vector into a collection of string tokens.

In some implementations, the search index130performs synonym and edge n-gram processing according to specification in the search index settings.

In some implementations, the search index130is configured to retrieve labeled trend events based on exact and partial (e.g., inexact) matches between the query tokens and the labeled data. A retrieved labeled trend event can be an exact match to at least one token (e.g., a user types “tanking” and a matching document would contain that word) or an inexact match to at least one token. An inexact match occurs when a search result is returned as a result of support for synonyms or edge n-gram matches.

An example of a synonym match is when a user types in the word “plummeting” and no labeled event contains that word “plummeting,” but at least one labeled event contains the word “tanking,” and the specification for the search index settings has specified that “plummeting” and “tanking” are synonyms.

An edge n-gram match occurs when the user only partially types in a search term and the search index can guess what the user means based on these first few letters. For instance, if the user types “dro”, the search index would return documents that contain “dropping”.

The original vectors D and encoded tokens S are stored in the semantic search engine index by specifying the mapping of the content, which defines the type and format of the fields in the index. The “content” refers to the raw event label for each document. For example, a label for an event could be “tanking.” The “mapping” specifies how the content will be processed and interpreted by the search index130for storage as fields in the index. “Fields” are different ways of storing copies of documents' data in the search index130so that documents can be retrieved in various ways. The “type” (e.g., text type) and “format” of each field determines how it is stored and how documents can later be matched to search queries. For instance, a synonym field can take the label of “tanking” and map it to the synonym “plummeting” based on synonym specifications (e.g., specified in the search index settings), allowing this same document to be retrieved by user searches for either “tanking” or “plummeting.” As another example, an edge n-gram field can take the same label of “tanking” and map it to shortened sub-strings of that label, such as ‘tan’, so that searching these sub-strings will also retrieve that document.

In other words, each semantic trend label and its associated stock data are stored as tokens in the search index in multiple processed formats (i.e., in different fields), enabling fast and flexible retrieval at search time. This indexing enables full-text search on the labels in the index, supporting exact-value search, fuzzy matching to handle typos and spelling variations, and n-grams for multi-word label matching. A scoring algorithm, tokenizers, and filters are specified as part of the search index settings. These settings specify how the matched documents are scored with respect to the input query, as well as the handling of tokens, including the conversion of tokens to lowercase and the addition of synonyms from a thesaurus.

FIG.15shows a code snippet for a search index configuration, in accordance with some implementations. The scripted similarity in the search index configuration defines a custom scoring mechanism for ranking search results based on term frequency (tf), inverse document frequency (idf), and normalization. The search index configuration also incorporates synonym expansion and edge n-grams for more flexible and comprehensive search results. A synonym file “synonyms_final.txt” is used to expand or replace terms.

The contents of the synonym file are illustrated inFIGS.17A and17B, in accordance with some implementations. Using the first line ofFIG.17Aas an example, the term “subsiding” has synonyms “lessening,” “lessen,” “relaxing,” “casing,” and “abating.” Thus, in some implementations, a natural language query that includes the term “subsiding” would cause the search index to return the same set of labeled trend events as another natural language query that includes the term “easing.”

FIG.16illustrates a code snippet for defining the properties of fields within an index mapping in the search index, in accordance with some implementations.

V.D.2. Search (Individual Documents)

The search phase can be conceptualized as having two steps-retrieval and ranking. For retrieval, consider a user input query q that is represented as a query vector q with query tokens q1, q2, . . . , qj. {circumflex over (q)} is encoded into string tokens using the same encoding function ε from indexing, such that ŝ=ε({circumflex over (q)}). The search retrieval process then returns the most relevant r document vectors={d1, d2, . . . , dr} based on the degree of overlap between the set of query string tokens ŝ and the document string tokens in. As used herein, the “degree of overlap” refers to the magnitude of the set intersection (i.e., number of common tokens) between the set of query tokens and the set of document string tokens. The “most relevant” documents (i.e., labeled trend events) are a predefined number of labeled trend events (e.g., 1000, 800, 500, or 200) that have the greatest “degree of overlap” out of all documents.

In some implementations, the scoring function rmaxmaximizes search relevance as follows:
{d1,d2, . . . ,dr}=rmax i∈{1,2, . . . ,n}|s∩si|

For search inputs that contain both a noun/verb descriptor (e.g., “decline”) and a modifying adjective (e.g., “fast”), SlopeSeeker subsequently filters out partially matching documents that contain only the adjective. For example, this would prevent a query of “fast decline” from returning documents labeled “fast increase” as partial matches. More formally, if ŝ contains at least one token that matches a noun/verb descriptor in at least one document, then every matching document dimust contain that descriptor in its set of string tokens si. However, users may still enter search queries consisting only of an adjective and see documents where that adjective is paired with a variety of noun/verb descriptors.

After retrieval, SlopeSeeker ranks document results (labeled trend event results) based on two components. The first component is how precisely the search term matches the event labels of the document, which is computed by the search index130according to the index and search settings. Consider a document with a single event label. In this example, a scoring scheme is utilized where this document's score is the frequency with which the search terms occur in its label, divided by the length of its label. This means that events with longer labels (e.g., those with modifying adjectives like “slow” or “fast”) will be scored higher than events with shorter labels if and only if the additional tokens accounting for the added length match the search terms.

Consider a document d1with the label “slow climbing.” For a user search of “slow climbing”, the score for the

212≈0.5⁢7⁢7,
so the score tor d1tor this search would be 0.577. In this example, the numerator has value 2 because there are two search terms “slow” and “climbing” that match the user search input. The value of the denominator is 12 because there are 12 letters in the label.

Now consider that there is also another hypothetical document d2with the label “climbing,” and imagine that the user searches for stocks that were “climbing”. The label score for d1will be

112≈0.289
(because there is one search term “climbing” that matches the search input) while the label score for d2will be

18≈0.3⁢5⁢4,
demonstrating how longer labels with the same number of matching tokens are penalized for being less precise matches.

The second scoring component is the visual saliency score of the labeled event (Section IV.D). The visual saliency score quantifies the perceptual prominence of a trend event. It is specifically designed for the search scenario to favor the most visually salient events, motivated by prior research showing that text annotations corresponding to visually salient features of line charts are most effective at driving reader takeaways. The final composite score used to rank events in the results is then the product of the search index (e.g., Elasticsearch index, or other search indexing frameworks such as Solr, Sphinx, or OpenSearch) component and the visual saliency component.

The visual saliency component of scoring is most important when there are a large number of matching results for a user query. Consider a case where a user is interested in “stocks that increased.” There could feasibly be very many document results with a label of “increasing” which will all have identical (or at least very similar) search index scores (e.g., Elasticsearch scores). However, these results are not likely to all be of equal interest to the user. For instance, a short three-day increase in stock price is probably less interesting, both visually and in terms of the analytical task at hand, compared to a three-month increase during which much more stock value was gained. Note that these could both have similar slopes and thus identical labels. The visual saliency scoring component thus serves as a tiebreaker to boost results with greater prominence and relevance over others that share identical labels.

V.D.3. Bucketing

The indexed data and result scoring (discussed above) are at the level of the labeled trend event (e.g., document), where each labeled trend event is a labeled slope segment. Any individual chart (e.g., stock) could have multiple matching events for a query. It is for this reason that in SlopeSeeker's interface, events are not presented individually but are placed into buckets at search time based on their chart identifier (e.g., stock key). Events within a bucket are sorted by their composite score. Buckets themselves are also scored; the final score for each bucket is the sum of the composite scores of its individual events, and buckets are presented in sorted order according to this final score.

In accordance with some implementations of the present disclosure, this scheme is designed to create an experience akin to standard “document search,” where more matches in a bucket bump that bucket higher in the results.

V.D.4. Sequence Queries

A sequence query includes of a list of trend events in a specified order. Each of the trend events can be a single word or multi-word. Since this type of query is not straightforward to support natively in the search index130(e.g., Elasticsearch) based on the way the data is indexed, sequence query results are constructed as follows. First, each individual constituent event is run through the search index130as its own single-word or multi-word query but not yet bucketed. Then, sequences are constructed by taking these results and doing an SQL join based on chart identifier and start/end dates. In some implementations, a tunable parameter is included to allow for some temporal delay between adjacent events.

As disclosed herein, some implementations also provide partial matching support for sequences. In particular, two types of sub-sequences are supported: edge sub-sequences (e.g., for “up, flat, down”: “up”; “up, flat”) as well as other in-order sub-sequences (e.g., for “up, flat, down”: “flat”; “down”; “flat, down”).

In some implementations, due to the construction of sequence results requiring custom logic, a custom scoring scheme for sequences and partial sequence matches is defined. At first, each sequence's score is assigned to be the sum of the composite scores of its constituent segments. Although partial matching sequences have fewer constituent components and will thus generally have lower composite scores than full matches, the inventors found it beneficial to additionally down-weight the composite scores of partial sequence matches.

In some implementations, the custom scoring scheme for sequence queries is based on the following formula:

score0(ls⁢e⁢qlq^+offsetseq)2

In the formula above, score, is the un-penalized score, lsegis the number of events in the sequence being scored, and l{circumflex over (q)}is the number of events in the query, and offsetseqis the number of sequential events missing from the beginning of the sequence compared to the query.

This custom scoring scheme applies two different penalties. First, longer sub-sequences (lseq≈l{circumflex over (q)}) are penalized and scored higher than shorter ones (lseq<l{circumflex over (q)}). For example, if the user is interested in stocks with the pattern “up, flat, down” which has length three, a sub-sequence of length two (e.g., “up, flat”) will be scored higher than a sub-sequence of length one (e.g., “up”) because it matches more constituent events of the sequence. Second, a non-edge sub-sequence (with a large offset) will be penalized to be scored lower than an edge sub-sequence (with zero offset). Continuing with the same example, the sub-sequence “up, flat” has zero offset because it begins at the same place as the initial query pattern, but “flat, down” has an offset of one since begins starts one event later in the sequence. Intuitively, sub-sequence partial matches that begin similarly to the desired sequence from the query should be scored higher than those that end similarly to the desired sequence. Finally, after applying any score penalties to the sequence results and any partial results, all results are bucketed, and the bucket scores are computed as before.

VI. Exemplary Use Case Scenarios

FIGS.18A to18Gprovide a series of screenshots illustrating how the SlopeSeeker system allows a user to search for specific trends and data based on the quantified language of a natural language queries, in accordance with some implementations.

InFIG.18A, a user inputs a natural language query1802(e.g., “stocks that fell slowly”) into the search bar102(e.g., natural language inbox box).FIG.18Billustrates that, in response to receiving the natural language query, the user interface110displays results (e.g., as tiles1804) corresponding to the query. Each of the results includes a respective chart1806(e.g., a line plot) showing stock prices over time. A respective chart1806can include one or more highlighted segments1808(e.g., visually emphasized segments, or segments that are encoded in a different color compared to the rest of the chart), corresponding to one or more specific events on the chart. In the example ofFIG.18B, each of the one or more specific events is an instance of falling stock prices, in which the respective segment is a segment of the chart with a negative slope.

FIG.18Cillustrates that when a user hovers (1810) the mouse over a highlighted event on a chart, the corresponding textual annotation1812is also highlighted. InFIG.18D, when a user hovers (1814) the mouse over a textual annotation, the portion of the chart corresponding to the textual annotation (i.e., segment1801-1) is visually emphasized while the rest of the events on the chart (e.g., corresponding to segment1808-2) are visually de-emphasized.

Referring back toFIG.18B, it can be observed that most of the instances of “slow falling stocks” identified by the computing system200correspond to segments of the line charts whose slopes are slightly negatively inclined (i.e., not a steep decline). In some instances, in response to a natural language query, the user interface can display a result that has an opposite meaning (or a partial match) to the semantics of the user query. For example,FIG.18Bshows that the chart corresponding to the stock ticker1805“ALK” includes a segment1808-6with a steep decline for the time period Jul. 9, 2014 to Jul. 10, 2014 (i.e., the vertical or near-vertical line segment).

FIG.18Eshows a user modification to the query via the natural language input box102. In this example, a user modifies the query from “stocks that fell slowly” (1802) to “stocks that fell fast” (1816). In response to receiving the modified query, the user interface displays an updated set of charts of stock prices over time, in which each of the charts includes one or more respective segments corresponding to fast falling stock prices. Compared to the results inFIG.18B, the segments of the line charts inFIG.18Ehave slopes that are more negatively inclined (e.g., with a more negative gradient). Thus, by detecting a change in a modifier from “slow” to “fast” in the input query, the computing system can update its search to identify trends in the time series data that corresponds to the updated modifier.

In some instances, a user can use terms that have different semantics. For example,FIG.18Fillustrates user input of a natural language query1818(e.g., “stocks that are climbing”) into the natural language input box. In response to the natural language query, the user interface110displays a notification box1422indicating that there are no exact matches to the query1818(e.g., “climbing”), and displays a set of charts1820with highlighted portions showing instances of stock prices gradually climbing over time. The visually emphasized portions of the charts inFIG.18Fcorrespond to respective time periods, identified by the computing device, in which a respective stock price experiences a relatively slow and steady increase over a longer period of time (e.g., at least 3 months, 6 months, or 9 months over a three-year timespan).FIG.18Fshows that the chart1820-3corresponding to stock ticker MLM and the stock corresponding to stock ticker HUM are highlighted over the entire duration that the charts span (e.g., three years).

FIG.18Gillustrates results that are displayed in response to a natural language query1822“stocks that were soaring,” in accordance with some implementations. The instances of “soaring” correspond to segments of the line graphs with steeper slopes over shorter periods of time compared to the results inFIG.18F,

FIGS.19A to19Dare a series of screenshots illustrating building sequence queries, in accordance with some implementations. A sequence query refers to a series of events that are identified in a single line graph.

InFIG.19A, a user inputs a term1902(e.g., a single word) “up” in the natural language input box. In response to the user input, the notification box1422displays a notification that there is no exact match for the word “up.” The notification further indicates that the computing device has identified synonyms or partial matches for the word “up,” which are shown in red in the results. In this example, the computing device identifies words (e.g., adjectives) such as “soaring” (1904), “accelerating” (1906) and “climbing” (1908), and/or words with modifiers such as “slow soaring,” “gradual accelerating,” and “fast climbing” to be synonymous with the term “up.”

Suppose that a user is interested to see stocks whose prices went up then down. InFIG.19B, the user enters a query1910“up, down” into the natural language input box102. In response to receiving the query, the user interface displays events that match the query. Each of the events corresponds to a pair of line segments corresponding to a time period where the stock price increased and then decreased. Each pair of line segments consists of a first line segment1912, corresponding to a stock price increase, and a second line segment1914contiguous to the first line segment, corresponding to a stock price decrease. In some implementations, as illustrated inFIG.19B, the user interface displays the respective first line segments using a first color encoding (e.g., red, orange, or black) and displays the respective second line segments using a second color encoding that is distinct from the first color encoding.

InFIG.19C, there is a user interaction (1918) (e.g., a mouse hover action) with a textual annotation (e.g., the text portion “slow soaring then slumping from Dec. 16, 2014 to Jul. 8, 2015) corresponding to the chart in tile1916. In response to the user interaction, the portion of the line graph (segment1912-1and1914-1) corresponding to the textual annotation is visually emphasized, whereas other portions of the chart (e.g., including other events identified by the computing device as matching the query “up, down”) are visually de-emphasized.

InFIG.19D, the user builds on the previous query by inputting a term (e.g., “up”) after the previous search terms, thus creating a query1920with a tuple of terms “up, down, up.” In response to receiving the query, the user interface displays a set of charts that have portions exhibiting a “price increase, price decrease, and price increase” trend. For example, one of the charts identified by the computing device is a chart1922, corresponding to stock ticker FLSR, that includes a portion corresponding to three segments (e.g., contiguous segments, or non-contiguous segments based on a tunable parameter as described in method2300) over the time period March 2014 to June 2014, in which the stock price soared, then slumped, then sharply accelerated. In the example ofFIG.19D, line segments corresponding to the first stock price increase are encoded with a first color, line segments corresponding to the stock price decrease are encoded with a second color distinct from the first color, and line segments corresponding to the second stock price increase are encoded with a third color that is distinct from both the first and second colors.

FIGS.20A and20Bare screenshots illustrating the use of the SlopeSeeker system to search for more global trends that may not correspond to a single slope within a segment of a trend, in accordance with some implementations.

FIG.20Aillustrates an example where a user inputs a query2002“stocks that are volatile.” In response to this query, the user interface displays charts corresponding to stock tickers FSLR and ALXN with highlighted portions corresponding to respective longer time periods (e.g., for at least one year over the three-year duration of the chart) in which the stock prices exhibit a longer period of volatility (e.g., instead of highlighting one particular slope of the chart).

FIG.20Billustrates another example in which a user searches for “stocks that are consistent” over time (e.g., where there is very little deviation over the broad longer-term trend. In response to this user query, the user interface displays two charts. Each of the charts includes a respective highlighted portion corresponding to a time period where the stock price was consistent.

FIGS.21A to21Iare a series of screenshots illustrating user interactions with the SlopeSeeker user interface, in accordance with some implementations.

InFIG.21A, the user interface110receives the user input2102“Show me when stocks were surging.”FIG.21Bshows that the user interface populates with result tiles2104-1,2104-2,2104-3, and2104-4, each corresponding to one stock, showing the stock price chart and textual annotations of when each event of interest occurred. In some implementations, a user can interact with the side bar1424to filter the results to a subset of results (e.g., to the type(s) of surging behavior that the user would like to see). For example, the user might only be interested in gradual surges (FIG.21C) or more sharp ones (FIG.21D).

In some instances, the user can further filter the results by modifying the natural language input query, such as “Show me when stocks were surging in 2016” (2106) as illustrated inFIG.21E.

In some instances, the user can further filter the results by modifying the natural language input query to specify a specific stock like “Monsanto,” as illustrated in the natural language input query2108“Show me when Monsanto was surging in 2016” as illustrated inFIG.21F.

In some instances, a user can also search for multi-line segment shapes. For example,FIG.21Gshows the query2110“Show me when stocks fell off a cliff in 2015” that is input by a user, whereasFIG.21Hshows another natural query2112“Show me when stocks hit a trough.” In both of these instances, the user interface displays results of stock prices that identify segments corresponding to when stock prices fell sharply (FIG.21G) or reached a low point (FIG.21H).

In some implementations, the system and user interface disclosed herein enable searching of arbitrary sequences of trend events.FIG.21Iillustrates results displayed on the user interface in response to a natural language query2114“show me when stocks went up then down, then back up.” The notification box1422informs the user that there are no exact matches for the terms “up” or down,” but there are related concepts that are shown on the side bar. The results show three sequences where the trend “up, down, up” as well as partial sequences where they exist otherwise.

VII. Exemplary Use Case Scenarios

FIGS.22A to22Dprovide a flowchart of a method2200for analyzing data trends, in accordance with some implementations. The method2200is also called a process.

The method2200is performed (2202) at a computing device200having a display212, one or more processors202, and memory206. The memory206stores (2204) one or more programs configured for execution by the one or more processors202. In some implementations, the operations shown inFIGS.1,4,5,6,7A to7C,8,9,10,11,12,13,14A,14B,15,16,17A,17B,18A to18G,19Ato19D,20A,20B, and21A to21I correspond to instructions stored in the memory206or other non-transitory computer-readable storage medium. The computer-readable storage medium may include a magnetic or optical disk storage device, solid state storage devices such as Flash memory, or other non-volatile memory device or devices. In some implementations, the instructions stored on the computer-readable storage medium include one or more of: source code, assembly language code, object code, or other instruction format that is interpreted by one or more processors. Some operations in the method2200may be combined and/or the order of some operations may be changed. In some implementations, some of the operations in the method2200may be combined with other operations in the method2300.

The computing device receives (2206) a first natural language input specifying one or more search terms directed to a dataset. The dataset comprises a set of (e.g., a plurality of) time series data. In some implementations, the computing device receives the first natural language input via a search102(e.g., a natural language input box) of a user interface110. In some implementations, the first natural language input is a verbal input or any other user input.

The computing device, in response to receiving the first natural language input, parses (2208) the first natural language input into one or more tokens.

The computing device assigns (2210) a respective semantic role to each of the one or more tokens.

In some implementations, the respective semantic role for each token comprises (2212) a predefined category of a plurality of categories. In some implementations, the plurality of categories includes (2214) two or more of: an event type (e.g., single or multi-sequence), a trend term (e.g., “tanking,” “plateau,” “steep increase,” or “accelerating”), an attribute (e.g., one or more data fields and/or data values of data fields), and a date range (e.g., absolute or relative date ranges).

In some implementations, the plurality of categories includes (2216) the event type. The event type is one of: a single event or a multi-sequence event.

The computing device translates (2218) (i) the one or more tokens and (ii) one or more semantic roles assigned to the one or more tokens into one or more queries (e.g., into a machine-interpretable form that can be processed to retrieve relevant search results).

Referring toFIG.22B, the computing device executes (2220) the one or more first queries against a search index (e.g., search index130) to retrieve (from the search index) a plurality of labeled trend events. In some implementations, the search index is a search database, an Elasticsearch index, or other search indexing frameworks such as Solr, Sphinx, or OpenSearch. Each labeled trend event (i) corresponds (2222) to respective portion (that is less than all) of a respective line chart of a set of line charts (e.g., line graphs, line plots) representing the time series data and (ii) has a respective chart identifier.

The retrieved labeled trend events can be exact matches to at least one token (e.g., the user types “tanking” and a matching document would contain that word) or inexact matches to at least one token. An inexact match occurs when a search result is only returned as a result of support for synonyms or edge n-gram matches. A synonym match could be if the user types in “plummeting” and no documents contain that word, but documents do contain “tanking” and the specification for the search index settings has specified that “plummeting” and “tanking” are synonyms. An edge n-gram match occurs when the user only partially types in a search term but the search index can guess what the user means based on these first few letters. For instance, if the user types “dro”, the search index would return documents that contain “dropping”. The synonym and edge n-gram processing are performed by the search index according to specification in the search index settings (see, e.g.,FIG.15).

In some implementations, each labeled trend event of the plurality of labeled trend events is (2224) identified by a respective chart ID262-1, a respective start point (in time)264-1, a respective end point (in time)266-1, and a respective set of (one or more) semantic labels268-1.

In some implementations, a labeled trend event includes one (i.e., a single) semantic label. In some implementations, a labeled trend event includes two or more semantic labels. For example, if a trend event corresponds to a steep fall in stock price, it can be labeled [“tanking”, “falling”, “slumping”], from the most to the least precise order.

In some implementations, each labeled trend event of the plurality of labeled trend events is (2226) a respective labeled slope segment of a respective line chart in the set of line charts.

In some implementations, each line chart in the set of time series line charts is (2228) a plot of data values of a data field (or changes in data values of a data field) over a predefined timespan.

In some implementations, each line chart in the set of line charts has (2230) the same time span. For example, in some implementations, each line chart in the set of line charts can have the same length of time, such as 6 months, 1 year, or 3 years. In some implementations, each line chart in the set of line charts can span the same time duration, such as from January 2021 to December 2023.

In some implementations, the search index stores (2232) (i) first vector representations corresponding to the plurality of labeled trend events (e.g., as a plurality of document vectors={d1, d2, . . . , dn}), (ii) second vector representations corresponding to a plurality of encoded tokens (encoded n-gram string tokens), and (iii) respective mapping relationships between the first vector representations and the second vector representations.

In some implementations the retrieved plurality of labeled trend events includes (2234) a first labeled trend event corresponding to an exact match of the one or more tokens. As an example, a user types “tanking” and the first labeled trend event contains the word “tanking.”

In some implementations the retrieved plurality of labeled trend events includes (2236) a second labeled trend event corresponding to an inexact match of the one or more tokens. An inexact match occurs when a search result is only returned as a result of support for synonyms or edge n-gram matches. As an example, a synonym match can be when a user inputs the term “plummeting” and no documents contain that word, but documents do contain “tanking” and the specification for the search index settings has specified that “plummeting” and “tanking” are synonyms. An edge n-gram match occurs when the user only partially types in a search term and Elasticsearch can guess what the user means based on these letters. For instance, if the user types “dro”, the search index will return documents that contain “dropping”.

In some implementations, the computing device, in accordance with a determination that no exact match exists between the retrieved plurality of labeled trend events and the one or more tokens, generates (2238) and displays a notification (e.g., in a notification box1422) indicating that there is no exact match for the one or more terms. The computing device displays (e.g., in a side bar1424of the user interface110), one or more user-selectable text labels corresponding to synonyms of the one or more terms.

With continued reference toFIG.22C, the computing device determines (2240), for each labeled trend event, a respective composite score.

The computing device individually assigns (2242) each of the plurality of labeled trend events to a respective group according to the respective chart identifier (see, e.g., Bucketing process in Section V.D.3). Each group (i) includes one or more respective labeled trend events and (ii) corresponds to one respective line chart in the set of line charts. Each group includes at least one labeled trend event. The number of groups is less than or equal to the number of line charts in the set of line charts.

The computing device sorts (2244), for each group of the one or more groups, the one or more respective labeled trend events within the respective group according to respective composite scores corresponding to the one or more respective labeled trend events.

In some implementations, the respective composite score for each labeled trend event is computed (2246) (e.g., by the search index130or by the computing device200) based on (1) a respective label score representing an extent to which the one or more search terms match respective labels of the plurality of labeled trend events and (2) a respective visual saliency score (the visual saliency score quantifies the perceptual prominence of a trend event).

In some implementations, for each labeled trend event, the respective composite score is (2248) a product (i.e., multiplication) of the respective label score and the respective visual saliency score.

In some implementations, the respective label score is computed (2250) according to (i) a frequency with which the search terms occur in the respective labeled trend event and (ii) a label length of the respective labeled trend event.

In some implementations, determining (2252), for each labeled trend event, the respective composite score includes computing the respective visual saliency score according to (1) a temporal duration of the respective portion of the respective line chart relative to the predefined timespan and (ii) a first difference in the data values of the data field over the temporal duration relative to a second difference in the data values of the data field over the predefined timespan.

Referring toFIG.22D, the computing device determines (2254), for each group (e.g., bucket) of the one or more groups, a respective final score. The final score for each group (e.g., bucket) is the sum of the composite scores of its individual events, and buckets are presented in sorted order according to this final score. Groups (or buckets) are only created if they have labeled trend events that would fit into them. In other words, there are no empty buckets, and so each bucket inherently has a score greater than zero.

The computing device ranks (2256) the one or more groups according to one or more determined final scores.

The computing device retrieves (2258), from the dataset, data corresponding to a first subset of (e.g., one or more) line charts having the respective chart identifiers of the ranked groups in accordance with the ranking.

In some implementations, the computing device, after retrieving the data corresponding to the first subset of line charts, generates (2260), for each line chart in the first subset of line charts, a respective text description describing a predefined number (e.g., up to three five, or seven) of events that matches the one or more search terms, including annotating (e.g., color-encoding or label-encoding) respective words in the respective text description that matches (e.g., partially or fully matches) the one or more search terms.

The computing device generates (2262) the first subset of line charts. For example, the computing device individually generates each line chart of the first subset of line charts.

The computing device annotates (2264) (e.g., via color-encoding or label-encoding) respective segments of the first subset of line charts that correspond to the labeled trend events.

The computing device displays (2266) one or more line charts of the first subset of line charts as annotated.

In some implementations, displaying the one or more of the first subset of line charts as annotated includes (2268) displaying the respective text snippet with each line chart in the one or more line charts.

In some implementations, the computing device displays (2270) the annotated respective words with a different visual characteristic from other words in the respective text description.

In some implementations, the computing device displays (2272) the annotated respective segments with a different visual characteristic from other segments of the one or more line charts.

FIGS.23A to23Eprovide a flowchart of a method2300for analyzing data trends, in accordance with some implementations. The method2300is also called a process.

The method2300is performed (2302) at a computing device200having a display212, one or more processors202, and memory206. The memory206stores (2304) one or more programs configured for execution by the one or more processors202. In some implementations, the operations shown inFIGS.1,4,5,6,7A to7C,8,9,10,11,12,13,14A,14B,15,16,17A,17B,18A to18G,19Ato19D,20A,20B, and21A to21I correspond to instructions stored in the memory206or other non-transitory computer-readable storage medium. The computer-readable storage medium may include a magnetic or optical disk storage device, solid state storage devices such as Flash memory, or other non-volatile memory device or devices. In some implementations, the instructions stored on the computer-readable storage medium include one or more of: source code, assembly language code, object code, or other instruction format that is interpreted by one or more processors. Some operations in the method2300may be combined and/or the order of some operations may be changed. In some implementations, some of the operations in the method2300may be combined with other operations in the method2200.

The computing device receives (2306) (e.g., via a search bar102or a natural language input box of a user interface, or via a verbal input, or any other user input) a natural language input specifying a plurality of search terms directed to a dataset. The plurality of search terms includes a first search term and a second search term. The second search term is subsequent to the first search term in the natural language input. The dataset comprises a set of (e.g., a plurality of) time series data.

In some implementations, the natural language input does not have another trend term between the first search term and the second search term. Using the natural language input “Show me when Acme stocks went up, then flat, then down before 2020” as an example, in some instances, the first term is “up”, and the second term is “flat”. In some instances, the first term is “flat”, and the second term is “down. In some implementations, In this example, the parser236(or the parser module336) identifies the trend terms as [‘up’], [‘flat’], and [‘down’]. The parser determines that the natural language input is a multi-sequence event type based on the number of trend terms. In the case of multi-sequence event type, the number of trend terms in the natural language input is great than one. In the case of single event type, the number of trend terms in the natural language input is exactly equal to one.

In some implementations, the plurality of search terms specified in the natural language input includes (2308) a third search term.

The computing device, in response to (2310) receiving the natural language input, and in accordance with a determination that the first search term and the second search term (e.g., where each of the first and second search terms can be a single-word or a multi-word) specify a first sequence of data trends (e.g., in a specific order), (i) executes, for the first search term, one or more first queries against a search index to retrieve a first set of (one or more) labeled trend events; and (ii) executes, for the second search term, one or more second queries against the search index to retrieve a second set of (one or more) labeled trend events. Each labeled trend event in the first and second sets of labeled trend events (i) corresponds (2312) to respective portion (that is less than all) of a respective line chart of a set of line charts (e.g., line graphs, line plots) representing the time series data and (ii) has a respective chart identifier.

Referring toFIG.23B, in some implementations, each labeled trend event of the plurality of labeled trend events is (2316) a respective labeled slope segment of a respective line chart in the set of line charts.

In some implementations, each line chart in the set of line charts has (2318) the same time span. For example, each line chart in the set of line charts can have the same length of time, such as 6 months, 1 year, or 3 years. As another example, each line chart in the set of line charts can have the same time duration, such as from January 2021 to December 2023.

In some implementations, the first sequence of data trends is (2322) specified by the first search term, the second search term, and the third search term. In some instances, the third search term is subsequent to the second search term. In some instances, the third search term precedes the first search term. Going back to the example natural language input “Show me when Acme stocks went up, then flat, then down before 2020,” in one example, the first search term is “up,” the second search term is “flat,” and the third search term is “down.” In another example, the third search term is “up,” the first search term is “flat,” and the second search term is “down.”

In some implementations, the determination that the first search term and the second search term specify the first sequence of data trends includes parsing (2324) (e.g., using a semantic parser, such as parser236or parser module336) the natural language input including the first search term and the second search term into a plurality of tokens, including assigning (i) a first semantic role to a first token corresponding to the first search term and (ii) a second semantic role to a second token corresponding to the second search term; and determining, based on the assigned first and second semantic roles, that the first search term and the second search term specify the first sequence of data trends.

In some implementations, parsing the natural language input includes determining (2326) that an event type corresponding to the natural language input is a multi-sequence event type.

With continued reference toFIG.23C, the computing device constructs (2328) one or more sequences of labeled trend events based on the retrieved first and second sets of labeled trend events.

In some implementations, constructing the one or more sequences of labeled trend events based on the retrieved first and second sets of trend events includes: for each sequence of labeled trend events, joining (2330) (e.g., via a SQL join) a respective first labeled trend event corresponding to the first search term and a respective second labeled trend event corresponding to the second search term, according to (i) a respective chart identifier corresponding to the respective first labeled trend event and the respective second labeled trend event and (ii) respective start and end dates of the respective first labeled trend event and the respective second labeled trend event.

In some implementations, a tunable parameter is included to allow for some temporal delay (or a temporal interlude) between adjacent events. The tunable parameter allows for “a temporal interlude between adjacent events in a sequence,” the length of which is chosen as appropriate for the data and context. For example, the “tunable parameter” can be set to one day, three days, one week, or any amount of time a user would like to allow between events for them to still be considered a sequence. This means that a sequence search for “up, down” would return sequences composed of an “up” event followed by a “down” event with an allowance for an intervening day, week, etc. between the end of the “up” event and the start of the “down” event. The temporal delay can be an arbitrarily long or short temporal delay. In practice, the amount of temporal delay can be selected based on what is appropriate for the data and domain.

In some implementations, the computing device, in accordance with a determination that the constructed one or more sequences of labeled trend events are partial sequence matches of the natural language input, determines (2332), for each sequence of the one or more sequences, a respective sequence score based at least in part on (i) a number of events in the respective sequence and (ii) a respective sequence offset (the respective sequence offset is the number of sequential events missing from the beginning of the sequence compared to the query).

Going back to the example natural language input “Show me when Acme stocks went up, then flat, then down before 2020,” where the user is interested in stocks with the pattern “up, flat, down” which has length three, a sub-sequence of length two (e.g., “up, flat”) will be scored higher than a sub-sequence of length one (e.g., “up”) because it matches more constituent events of the sequence. Second, a non-edge sub-sequence (with a large offset) will be penalized to be scored lower than an edge sub-sequence (with zero offset). Continuing with the same example, the sub-sequence “up, flat” has zero offset because it begins at the same place as the initial query pattern, but “flat, down” has an offset of one since begins starts one event later in the sequence. Intuitively, sub-sequence partial matches that begin similarly to the desired sequence from the query should be scored higher than those that end similarly to the desired sequence. Finally, after applying any score penalties to the sequence results and any partial results, all results are bucketed, and the bucket scores are computed as before.)

Referring now toFIG.23D, in some implementations, after constructing the one or more sequences of labeled trend events, the computing device determines (2334), for each sequence of the one or more sequences, a respective sequence score by aggregating (summing) one or more respective composite scores corresponding to one or more respective labeled trend events in the respective sequence.

In some implementations, for a respective labeled trend event in the respective sequence, the computing device determines (2336) a respective composite score for the respective labeled trend event based on (1) a respective label score representing an extent to which a respective search term matches respective labels of the plurality of labeled trend events and (2) a respective visual saliency score. The visual saliency score quantifies the perceptual prominence of a trend event.

In some implementations, the respective composite score is (2338) a product (e.g., a multiplication) of the respective label score and the respective visual saliency score.

In some implementations, determining the respective composite score includes computing (2340) the respective label score according to (i) a frequency with which the first search terms occur in the respective labeled trend event and (ii) a label length of the respective labeled trend event.

In some implementations, each line chart in the set of time series line charts is a plot of data values of a data field (or changes in data values of a data field) over a predefined timespan. Determining the respective composite score includes computing (2342) the respective visual saliency score according to (1) a temporal duration of the respective portion of the respective line chart relative to the predefined timespan and (ii) a first difference in the data values of the data field over the temporal duration relative to a second difference in the data values of the data field over the predefined timespan.

The computing device assigns (2344) each sequence of labeled trend events, of the one or more sequences of labeled trend events, into one or more groups according to the respective chart identifier.

The computing device determines (2346), for each group of the one or more groups, a respective final score.

In some implementations, the respective final score for each group of the one or more groups is (2348) an aggregation of one or more respective sequence scores, from one or more respective sequences of labeled trend events, in the respective group.

With continued reference toFIG.23E, the computing device ranks (2350) the one or more groups according to one or more determined final scores.

The computing device retrieves (2352), from the dataset, data corresponding to a subset of (one or more) line charts having the respective chart identifiers of the ranked groups in accordance with the ranking.

The computing device generates (2354) the subset of line charts.

The computing device annotates (2356) (e.g., via color-encoding or label-encoding) respective segments of the subset of line charts that correspond to the sequences of labeled trend events; and

The computing device displays (2358) one or more line charts of the subset of line charts as annotated.

The methods disclosed herein comprise one or more steps or actions for achieving the described method. The method steps and/or actions may be interchanged with one another without departing from the scope of the claims. In other words, unless a specific order of steps or actions is required for proper operation of the method that is being described, the order and/or use of specific steps and/or actions may be modified without departing from the scope of the claims.

As used herein, the term “plurality” denotes two or more. For example, a plurality of components indicates two or more components. The term “determining” encompasses a wide variety of actions and, therefore, “determining” can include calculating, computing, processing, deriving, investigating, looking up (e.g., looking up in a table, a database or another data structure), ascertaining and the like. Also, “determining” can include receiving (e.g., receiving information), accessing (e.g., accessing data in a memory) and the like. Also, “determining” can include resolving, selecting, choosing, establishing and the like.

The phrase “based on” does not mean “based only on,” unless expressly specified otherwise. In other words, the phrase “based on” describes both “based only on” and “based at least on.”

As used herein, the term “exemplary” means “serving as an example, instance, or illustration,” and does not necessarily indicate any preference or superiority of the example over any other configurations or embodiments.

As used herein, the term “and/or” encompasses any combination of listed elements. For example, “A, B, and/or C” entails each of the following possibilities: A only, B only, C only, A and B without C, A and C without B, B and C without A, and a combination of A, B, and C.

The terminology used in the description of the invention herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the invention. As used in the description of the invention and the appended claims, the singular forms “a,” “an,” and “the” are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will also be understood that the term “and/or” as used herein refers to and encompasses any and all possible combinations of one or more of the associated listed items. It will be further understood that the terms “comprises” and/or “comprising,” when used in this specification, specify the presence of stated features, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, steps, operations, elements, components, and/or groups thereof.

The foregoing description, for the purpose of explanation, has been described with reference to specific embodiments. However, the illustrative discussions above are not intended to be exhaustive or to limit the invention to the precise forms disclosed. Many modifications and variations are possible in view of the above teachings. The embodiments were chosen and described in order to best explain the principles of the invention and its practical applications, to thereby enable others skilled in the art to best utilize the invention and various embodiments with various modifications as are suited to the particular use contemplated.