Hierarchical index involving prioritization of data content of interest

An example implementation may relate to an apparatus that may identify data content of interest from data in buffers, and may store index entries representing the identified data content in a hierarchical index having different performance levels. The apparatus may include a priority manager that maintains an index scoreboard that tracks where index entries are to be stored among the different performance levels of the hierarchical index based on predetermined polices that prioritize data content of interest or functions that use data content of interest.

BACKGROUND

Real time analytics may involve performing analytic processes, such as content recognition, on data as the data is being stored. The data may be temporarily buffered en route to being stored, to facilitate analysis by the analytic processes. When buffers fill, real time analytic processes may be transferred to background processing.

Throughout the drawings, identical reference numbers may designate similar, but not necessarily identical, elements. An index number “N” appended to some of the reference numerals may be understood to merely denote plurality and may not necessarily represent the same quantity for each reference numeral having such an index number “N”. Additionally, use herein of a reference numeral without an index may refer generally to any of those elements.

DETAILED DESCRIPTION

A real time analytics system may involve executing analytic processes on data of a data stream. In some cases, as data enters the system, the data may be buffered temporarily in data buffers prior to storage to allow the analytic processes to operate on the data. An example of an analytic process may include a content recognizer designed to search or monitor for certain patterns of interest in data. An analytic process may output a result that is stored in indices, such as content addressable memory or random access memory. When the data buffers fill, the analytic processes may be relegated to background processing and may degrade or frustrate the real time nature of the analytics system.

The systems and techniques of the present description may, in some example implementations, identify data content of interest from data in the buffers by way of analytic processes and may store index entries representing the identified data content in a hierarchical index having indices of different performance levels. Additionally, a priority manager may maintain an index scoreboard that tracks where index entries are to be stored among the different performance levels of the hierarchical index based on predetermined polices that prioritize data content of interest or functions that use data content of interest. The priority manager also may maintain a buffer scoreboard that tracks buffer priorities based on the highest priority analytic process that has not yet executed against each respective buffer, and the buffer scoreboard may in turn be used to approve data eviction from the buffers.

Accordingly, the systems and techniques of the present description may be useful for using data content identified or detected in the data stream to bias data placement in storage and index entry placement in an index, among other things. For example, data having popular or high value data content of interest, as deemed by a user or by machine learning, may be placed in a high performance storage tier or index for fast subsequent access. Additionally, owing at least in part to a buffer scoreboard as described herein, buffers may be recycled according to buffer priorities when insufficient buffers are available to receive new data.

Referring now to the figures,FIG. 1is a block diagram of an example system100. As will be described further herein, the system100may be useful for processing incoming data in real time (or near real time) to detect certain data content of interest that may guide real time (or near real time) decisions about what to do with the data. Subsequently, the system100may move the data to storage for further processing.

As used herein, the phrase “data content of interest” may refer to a particular pattern, characteristic, feature, etc. in the data. In some examples, a particular pattern, characteristic, feature, etc. may be deemed data content of interest by a user, based on the user's knowledge that such data content of interest may be linked to an analytic insight the user desires to extract or draw from the data. In some examples, the system100may dynamically establish new data content of interest based on machine learning or data mining.

In some implementations, the system100may be a computing system, such as a server, a desktop computer, a workstation, a laptop computer, a distributed computing system, a cloud computing system, a storage system (e.g., of a storage area network), etc. The system100may include an apparatus101, which may be deemed a sub-system of the system100in some cases.

The apparatus101may include buffers102-1through102-N (referred to generally or collectively as buffers102) to receive data103. Data103may be part of a data stream that includes plural sets of data103, arriving at the buffers102over the course of time. Each of the buffers102-1through102-N may receive a different set of data103from the data stream. A buffer controller144may control the flow of data to the buffers102(e.g., input/output control).

The apparatus101also may include an analytics engine104, a priority manager112, and an analytics engine scheduler140. In some implementations, the analytics engine104may include a plurality of analytics sub-engines105-1through105-N (referred to generally or collectively as analytics sub-engines105or sub-engines105). The apparatus101also may include a hierarchical index108for storing index entries106that may be used by various functions of the system100, as will be described herein.

The apparatus101also may include an index scoreboard114and a buffer scoreboard142, each of which may be used, for example, by the priority manager112to manage behavior of the buffers102, the analytics engine104, or the hierarchical index108, in relation to data content of interest, as will be described herein. In some implementations, the index scoreboard114and the buffer scoreboard142may be implemented as, for example, a database, a table, or other kinds of structured data set.

The system100may also include a placement engine120, a post-processor130, an insight engine150, or any combination of the foregoing. In some cases, the placement engine120, the post-processor130, or the insight engine150may be deemed “functions that use data content of interest,” by virtue of their respective functionality being influenced by or related to data content of interest.

Additionally, the system100may include a storage device, such as, a tiered storage system122, for storing data103. For example, the tiered storage system122may be to store data103released from the buffers102.

In other implementations, some of the foregoing components described as included in the apparatus101may be instead included in system100, outside of the apparatus101(e.g., in a different sub-system of system100). In other implementations, some of the foregoing components described as being included in system100may be included more particularly in apparatus101.

The analytics engine104, the analytics sub-engines105, the priority manager112, the placement engine120, the post-processor130, the analytics engine scheduler140, and the insight engine150may each include a series of instructions encoded on a machine readable storage medium and executable by a processor or processors (e.g., a microprocessor, an application specific integrated circuit (ASIC), a field programmable gate array (FPGA), and/or other hardware device suitable for retrieval and/or execution of instructions), and additionally or alternatively, may include one or more hardware devices including electronic circuitry or logic for implementing functionality described herein. The foregoing elements of the system100will now be described in greater detail.

The buffers102may be, for example, random access memory (RAM) coupled to a processor of the system100(or apparatus101), or special purpose buffers within an ASIC or an FPGA of the system100(or apparatus101). In some examples, the format of data103may be block, file, or object. In some implementations, the buffers102may release presently held data103to the tiered storage system122by way of the placement engine120, as will be described below, and the buffers102may subsequently receive new data103.

The hierarchical index108may have or may be made up of different performance levels110. In some implementations, the different performance levels110may be differentiated based on speed-related performance, particularly access speed or search speed. In some implementations, the different performance levels110may be indices (or indexing components) having different performance capabilities. For example, the different performance levels110may include a high performance level index and a low performance level index and a spectrum of indices there between. To illustrate, the different performance levels110may include, in order of descending performance, content addressable memory (CAM), random access memory (e.g., non-volatile or volatile memory), and storage (e.g., a hard disk drive, a solid state drive, a disk array, etc.). In another illustration, the different performance levels110may be classified by a hardware-software paradigm, including, for example, higher performance hardware-based indexing (e.g., CAM or a pattern matching hardware accelerator that uses memory-side acceleration, co-processor(s), an ASIC, an FPGA, a graphics processing unit, sorting networks, etc.) and lower performance software-based indexing (e.g., a B-Tree).

The hierarchical index108may store various types of index entries106(e.g., indexed data in the form of key-value pairs), such as results from the analytics engine104, results from the post-processor130, or placement rules used by the placement engine120. As will be discussed below with respect to the priority manager112, the index entries106may be placed in a performance level of the hierarchical index108, either in a first instance (e.g., by the analytics engine104) or by moving from another performance level, based on the index scoreboard114maintained by the priority manager112.

In some implementations, the apparatus101may include multiple hierarchical indices108. Similar performance levels in respective hierarchical indices may be deemed peer indices. Additionally, constituent indices of the multiple hierarchical indices (e.g., the different performance levels110) may be used to segregate data, such as index entries, based on type, content, etc. of the data. For example, results of the analytics engine104may be stored in one of the constituent indices and placement rules may be placed in another one of the constituent indices.

The tiered storage system122may have or may be made up of different tiers (or portions) that are differentiated by an attribute, such as performance (e.g., performance based on access speed), price, capacity, functionality, reliability, etc. For example, the different tiers may correspond to different types of storage devices, storage media, or storage technology constituting the tiered storage system122. To illustrate, tiers of the storage system122may include, from higher to lower performance (e.g., data access speed): persistent memory, a solid state drive (SSD), a hard disk drive (HDD), and a tape library. In some implementations, a tier of performance may correspond to a type of data to be stored therein, such as a video streaming tier suitable or optimal for streaming video data.

The analytics engine104may identify data content of interest from data103in the buffers102. For example, the analytics engine104may perform any number or variety of data analysis or data processing tasks on the data103in each of the buffers102, to identify therein (or detect, isolate, extract, etc.) data content of interest. In some implementations, the analytics engine104may be designed by a user (e.g., encoded to detect specific data content of interest) based on the user's knowledge that such data content of interest may be linked to an analytic insight the user desires. In some cases, because data103may be part of a data stream temporarily held in the buffers102, analysis of the data103by the analytics engine104may be deemed a real time (or near real time) process.

In examples where the analytics engine104includes a plurality of analytics sub-engines105, each of the analytics sub-engines105may similarly perform different data analysis or data processing tasks on data103in a buffer102, such as searching for or detecting different data content of interest from data103in a buffer102. In some implementations, at least some of the analytics sub-engines105may be prioritized, that is, some analytics sub-engines105may be deemed to have greater priority or importance by the user in view of the analytic insight the user desires. In some implementations, prioritization of the analytics sub-engines105may be dynamically adjusted during operation, as will be described below with respect to the analytics engine scheduler140. The priority of the analytics sub-engines105may be programmable in the analytics engine104.

The process whereby the analytics engine104or an analytics sub-engine105performs a data analysis or data processing task on data103in a buffer102may also be referred to as “executing” or “execution of” the analytics engine104or the analytics sub-engine105against data103in the buffer102, or more generally, against the buffer102. The analytics engine104or sub-engines105may generate a result after executing against a buffer102. Additionally, the analytics engine104or sub-engines105may accumulate execution statistics, such as a count of how many times data content of interest has been successfully identified, which may indicate a popularity of that data content of interest or the corresponding analysis task or engine.

Some example implementations of analytics engine104or sub-engines105will now be discussed. It should be understood that such implementations are by way of illustration only, and other types of analytics engines may be employed, depending for example on the analytic insight a user desires to extract from the data stream. For example, in some implementations, the analytics engine104or a sub-engine105thereof may include a content recognizer that searches for or monitors for a particular content pattern or patterns in the data103held in the buffers102. A content recognizer may be encoded with the content pattern(s) for which it searches, and the content pattern(s) may be related to, for example, text, images, or video. To illustrate, a text-based content recognizer may search for particular keywords, signatures, sentiments, form fields, or other text associated with a nature or characteristic of the data or other insight about the data. An image content recognizer may search for particular graphical content (e.g., pictures of a certain object). A video content recognizer may search for particular graphical content or motion patterns, for example. A result generated by a content recognizer may include a positive indication that a particular content pattern was recognized.

In some examples, a user may design the content recognizer to have a certain encoded content pattern, because the user is interested in extracting a certain insight from the data stream. For example, a user that is interested in current trends about food (e.g., restaurants, recipes, etc.) may design content recognizers to recognize images of food and text indicating positive and/or negative comments about food, and such content recognizers may be applied, for example, to data derived from social networks, blogs, and the like.

In some examples, the analytics engine104or analytics sub-engines105thereof may include a clickstream analyzer, which may track mouse clicks, webpage or web asset accesses, etc. to provide insight into how people are interacting with a website. Results generated by a clickstream analyzer may include, for example, a number of accesses, a click log, and other web statistics.

Returning again to the analytics engine104in general, upon identification of data content of interest from data103in the buffers102, the analytics engine104may output and store, in the hierarchical index108, a result as an index entry or entries106related to or representing the identified data content of interest. Execution statistics of the analytics engine104also may be stored as index entries106. More particularly, an index entry106may be stored in a performance level of the hierarchical index108based on the index scoreboard114, as will be described further below with respect to the priority manager112. In examples where the analytics engine104may include a plurality of analytics sub-engines105, each of the analytics sub-engines similarly may store an index entry106in the hierarchical index108(or in a performance level thereof), such as an index entry106generated by a successful search by an analytics sub-engine105or from an execution statistic.

In some implementations, an index entry106from the analytics engine104may include at least a key and value pair. For example, a key of an index entry106may include an index entry type indicator and/or an identifier, and may be related to the origin of the index entry. The index entry type indicator may be a prefix of a key to distinguish the different types of index entries stored in the hierarchical index108(e.g., types including analytics engine results, post-processor results, placement rules). The value of an index entry106may include, for example, the result generated by the analytics engine104or a derivation thereof, and a value type indicator to distinguish multiple insights about the same data (e.g., the value type indicator may identify an analytics sub-engine, a data analysis task, or other function that generated the result/value).

The post-processor130may perform analysis on data103stored in the tiered storage system122or on index entries106stored in the hierarchical index108, and more particularly, may employ any machine learning technique, data mining technique, or the like to discover patterns in the data103or index entries106. Examples of techniques that may be employed by the post-processor103include association rule mining, statistical models, decisions trees, neural networks, hidden Markov models, etc. For example, in comparison to a content recognizer, the post-processor130may discover patterns without an explicit predefined notion of what to identify.

Patterns discovered by the post-processor130may be stored as index entries106in the hierarchical index108, and more particularly, stored in a performance level of the hierarchical index108based on the index scoreboard114, as will be described below. New data103received in the buffers102may subsequently be evaluated for presence of patterns previously discovered by the post-processor130, by comparing index entries106generated for the new data103against index entries representing the discovered patterns. In some implementations, the existence of discovered patterns in data103may trigger other data content driven actions, such as, for example, placement rules created for the placement engine120based on the discovered patterns, as will also be described below.

In an example, the post-processor130may analyze data103in the tiered storage system122to discover a high priority combination of different data content of interest. Similarly, the post-processor130may analyze index entries106in the hierarchical index108to discover high priority combinations of index entries generated for the same set of data103. For example, to discover a high priority combination, the post-processor130may include an association rule mining engine (implemented as, e.g., machine readable instructions or electronic circuitry) that performs at least some aspects of association rule mining. To illustrate, the association rule miner engine may calculate statistical values such as support and confidence for various combinations of different data content of interest evaluated by the analytics engine104(such combinations may be referred to as item sets, in association rule mining parlance) over plural sets of data103in the tiered storage system122(such plural sets of data may be referred to as transactions, in association rule mining parlance), and the association rule miner engine may deem combinations with high support and/or confidence values to be high priority combinations of data content of interest. High priority combinations may be stored as index entries106in the hierarchical index108.

The insight engine150may perform any variety of data analysis or data processing on data stored in the tiered storage system122or the hierarchical index108, as desired by a user of the system100. The data analysis or processing included in the insight engine150generally may be more time intensive or computationally intensive than analysis or processing performed by the analytics engine104, for example. In some instances, the insight engine150may operate on data stored in tiered storage system122in the background (i.e., in the background, relative to the real time processing of the analytics engine104). The user may configure the insight engine150to perform analysis or processing based on a particular insight the user wishes to draw out of the data stream. In some implementations, the insight engine150may generate a report to summarize the findings of the analytics engine140as tracked by the index entries106in the hierarchical index108. In some implementations, the insight engine150may be a security analysis platform (e.g., cybersecurity, threat management, etc.), a social network analyzer, a sentiment analyzer, etc.

An analytics engine scheduler140may be included in some implementations of apparatus101to keep track of which analytics sub-engines105(or tasks of the analytics engine104) are currently executing against each of the buffers102and which have already executed against each of the buffers102. The analytics engine scheduler140also may prioritize future execution of the analytics sub-engines105(or execution of plural tasks of the analytics engine104) against each of the buffers102. In some implementations, prioritized execution of the analytics sub-engines105may be based on a prioritization of the analytics sub-engines105that is pre-defined by a user (e.g., user defined minimum priority, maximum priority, and default priority) and/or may dynamically adjust based on success rates of the analytics sub-engines105. As an example, adjustment of a priority of a first analytics sub-engine (e.g.,105-1) may cause a responsive adjustment (e.g., an increase or decrease) of a priority of a second analytics sub-engine (e.g.,105-2). As another example, discovery of a high priority combination of data content of interest by the post-processor130, as described above, may cause the analytics engine scheduler140to adjust (e.g., increase) the priority of all analytics sub-engines105related to the data content of interest in the discovered combination.

In some implementations, the analytics engine scheduler140may sequence execution of the analytics sub-engines105based on the above-described prioritization of the sub-engines105. In some implementations, the analytics engine scheduler140may schedule sub-engines105to execute in parallel.

In some implementations, the analytics engine scheduler140may schedule execution of the analytics sub-engines105based on dependencies between the sub-engines105. For example, the analytics engine scheduler140may cancel execution of a scheduled analytics sub-engine (e.g.,105-1) if, for example, a result from a previously executed analytics sub-engine (e.g.,105-2) obviates execution of the scheduled analytics sub-engine (105-1). To illustrate, a result of a previously executed analytics sub-engine (e.g.,105-2) may relate to high priority data content of interest and thus automatically trigger action from other functions that use the high priority data content of interest without completing execution by remaining scheduled analytics sub-engines. In another illustration, execution of a lower priority analytics sub-engine (e.g.,105-1) may produce cumulative or redundant data to the previously executed analytics sub-engine (e.g.,105-2), and so execution of the lower priority analytics sub-engine may be canceled. In some examples, the analytics engine scheduler140may confirm or trigger execution of another analytics sub-engine (e.g.,105-1), particularly if a previously executed analytics sub-engine (e.g.,105-2) failed to detect corresponding content of interest.

The placement engine120may move data103from the buffers102to the tiered storage system122according to placement rules. For example, to move data103, the placement engine120may transmit to the buffer controller144data movement commands derived from the placement rules. In some implementations, the placement rules may be related to or derived from a prioritization of data content of interest or a prioritization of functions that use data content of interest. The placement rules may inform the placement engine120to move data103from a buffer102to a lower or higher tier of the tiered storage system122, based on how the data103relates to data content of interest or functions that use data content of interest. In some implementations, the placement rules are stored as index entries in the hierarchical index108.

In some implementations, some placement rules, as they relate to a content-based prioritization, may be pre-defined by a user during design of the system100. For instance, an example placement rule may hold that certain analytics sub-engines have a higher priority than other analytics sub-engines (by user design), and accordingly, data103may be moved from a buffer102to a tier of the tiered storage system122having performance corresponding to the highest priority analytics sub-engine that successfully identified data content of interest in that data103. In other words, successful identification of data content of interest by a high priority analytics sub-engine may result in data storage in a high performance tier.

In some implementations, placement rules may be dynamically established by the system100based on data content-driven machine learning from the data103and/or index entries106such as results from the analytics engine104. For example, the post-processor130may discover patterns among stored data or index entries as described above, which may trigger the system100(or in some implementations, the post-processor130) to create a placement rule to move data exhibiting discovered patterns to a particular tier of the tiered storage system122(e.g., a highest performance tier).

In particular, in the example post-processor130above that discovers a high priority combination of different data content, a created placement rule may include a rule to move data103having a high priority combination of different data content of interest, from a buffer102to a high performance tier of the tiered storage system122. A rationale for creating a high priority combination-based placement rule may be that, in some cases, the high priority combinations are selected by the post-processor130as predictive of data that will be accessed frequently or in the near future, by virtue of having a higher confidence value (compared to other combinations). Such frequently accessed or soon-to-be accessed data should be stored accordingly in a higher performance tier of the tiered storage system122for fast access. Conversely, lower confidence values may identify combinations that predict data that is unlikely to be accessed and should be stored by a default placement rule in a lower performance tier of the tiered storage system122.

The priority manager112may maintain the index scoreboard114to track where index entries106are to be stored among the different performance levels110of the hierarchical index108, based on predetermined polices116that prioritize data content of interest or functions that use data content of interest.

In some implementations, the index scoreboard114itself may be stored in the hierarchical index108. Content of the index scoreboard114may include references to each of the index entries106stored and/or to be stored in the hierarchical index108, or may include the index entries106themselves. Additionally, for each reference to an index entry106, the index scoreboard114may include at least one of: a name of a function that generated that index entry106, a name of a function that can use that index entry106, an indication of how recently that index entry106was used, an index policy that applies to that index entry106, and any information relied upon by the index policy. The index policy included in the index scoreboard114may be selected from predetermined policies116encoded in the priority manager112by a user.

In operation, the priority manager112may decide which level of performance of the hierarchical index108to store an index entry106, by applying the index policy from the index scoreboard114that corresponds to the reference for that index entry106. The priority manager112also may refer to other information in the index scoreboard114that factors into the index policy. The priority manager112decision regarding which level of performance of the hierarchical index108to store an index entry106may direct or control the analytics engine104in storing the index entry106in a first instance (i.e., when the index entry106is first generated by the analytics engine104). The priority manager112decision also may direct or control the priority manager112itself or a controller attached to the hierarchical index108to move existing index entries106between performance levels of the hierarchical index108.

Examples of the policies116may be instructions or configuration data stored on a machine readable medium of the system100, and may include any of the following policies. In one implementation, a policy may prescribe keeping index entries106related to some type(s) of data content of interest in a high performance level index of the hierarchical index108. For example, a user may design a policy that deems index entries106of a particular value type indicator or index entries from a particular analytics engine104task or sub-engine105to be of high priority or interest and thus to be stored in a high performance level index of hierarchical index108.

In some implementations, one of the policies116may prescribe moving of demoting an index entry106over time to a low or next lower performance level index of the hierarchical index108(also referred to herein as a process of “aging” or being “aged”). In some examples, the time frame over which an index entry106is aged may be encoded by a user in the policies116or the priority manager112. In some examples, the time frame may be long (e.g., on the order of minutes to hours), medium (e.g., on the order of seconds to minutes), or short (e.g., on the order of seconds), depending on various considerations, such as the following. In some implementations, the time frame over which an index entry106is moved may be proportional to the popularity of data content of interest related to that index entry106(e.g., as indicated by the above described execution statistics). In some implementations, the time frame over which a particular index entry106is aged may be longer than other index entries, if the hierarchical index108contains a placement rule (used by or created by placement engine120) or a high priority combination (discovered by post-processor130) that involves data content of interest related to that index entry106. Additionally or alternatively, the priority manager112may dynamically adjust the time frame according to a performance aspect of system100, such as, for example, memory pressure, workload, remaining capacity of the hierarchical index108, or other aspects. Some policies also may use different time frames for different types of data content of interest or functions that use data content of interest.

In some implementations, one of the policies116may prescribe storing an index entry106in a performance level of the hierarchical index108that is associated with a priority of a function that uses the data content of interest related to that index entry106(e.g., the policy manager112may identify the function, based on the name of the function in the index scoreboard114). For example, the association may be proportional, such that an index entry106relating to data content of interest used by a high priority function may be stored in a high performance level of the hierarchical index108. Associations other than proportionality may be employed as well,

In some implementations, one of the policies116may prescribe storing an index entry106in a performance level of the hierarchical index108that is commensurate with a popularity of data content of interest related to that index entry106. For example, the popularity of data content of interest may be determined from execution statistics, which, as described above, may be a count of how many times that data content of interest has been successfully identified. More particularly, a comparison of execution statistics stored in the hierarchical index108may generate a relative popularity between data content of interest. To illustrate, an index entry106related to a popular data content of interest may be stored in a high performance level of the hierarchical index108. In another example, the popularity may be determined from looking up, in the index scoreboard114, the indication of how recently that index entry106was used, and the policy may be to keep most recently used index entries106in a high performance level of the hierarchical index108and to move least recently used index entries to a lower performance level.

By virtue of placing index entries106in the hierarchical index108based on policies116that are related to data content of interest, index entries that are related to high priority or important types of data content (i.e., importance as regarded or surmised by a user or by the system via machine learning, etc.) may be quickly and efficiently accessed from the higher performance levels of the hierarchical index108.

In some implementations, the priority manager112also may maintain a buffer scoreboard142to track a buffer priority for each of the buffers102. The buffer scoreboard142may be used by the buffer controller144to manage the buffers102, according to an example manner described below, when there are or prior to there being insufficient free buffers102available to receive new data103(i.e., buffers102become full or are nearly full), which may frustrate the real time (or near real time) analysis performed by the analytics engine104. In such a situation, the buffer controller144may select a buffer or buffers for data eviction, that is, to move data from the selected buffer(s) to the tiered storage system122, even if sub-engines105(or analytics engine104tasks) scheduled by the analytics engine scheduler140have not executed against those selected buffer(s). The process of data eviction in this manner may also be referred to as “buffer recycling,” and the associated movement of data from the buffers102may be coordinated by the buffer controller144.

An example buffer scoreboard142may include, for each buffer102-1through102-N: flags to indicate whether respective analytics sub-engines105have been executed against the buffer (referred to herein as “analytics engine flags” for convenience), a count of the analytics sub-engines105currently executing against the buffer, and a flag to indicate whether the buffer is to be recycled (also referred to herein as a “recycle flag” for convenience). The buffer scoreboard142may be updated as analytics sub-engines105are executed against the buffers102.

As established by the priority manager112, buffer priority for a buffer102may be associated with a highest priority among analytics sub-engines105that have not yet executed against that buffer102(e.g., execution as indicated by the analytics engine flags in the buffer scoreboard142). For example, as described above with respect to the analytics engine scheduler140, at least some of the analytics sub-engines105may be prioritized, based on user knowledge for example. Accordingly, in an illustration, if the buffer scoreboard142indicates that high priority sub-engines have finished executing against a buffer (e.g.,102-1) but low priority sub-engines have not yet executed against that buffer102-1, the buffer priority of that buffer102-1may be deemed low by the priority manager112. By contrast, in the same illustration, if the buffer scoreboard142indicates that high priority sub-engines105have not yet executed against a buffer102-2, the buffer priority of that buffer102-2may be deemed high by the priority manager112. On balance, the buffer priority of the buffer102-2may be higher than the buffer priority of the buffer102-1. Buffer priorities may change as the flags of the buffer scoreboard142are updated. In some implementations, the priority manager112may maintain the buffer priorities in the buffer scoreboard142.

In operation, the buffer controller144may indicate to the priority manager112that data eviction is imminent due to full or nearly full buffers102, and in response, the priority manager112may approve data eviction for a buffer (or buffers) based on the buffer scoreboard142, and more particularly, based on rules related to buffer priorities and the buffer scoreboard142. In some implementations, the priority manager112may approve a buffer for data eviction if all of its analytics engine flags are set, thus indicating that no further analytics sub-engines105are scheduled to run against that buffer. In some implementations, the priority manager112avoids approving data eviction for buffers that have a buffer priority above a priority threshold that is configured in the priority manager112by the user. In some implementations, the priority manager112may approve a buffer for data eviction if its buffer priority is the lowest among all buffers102. If multiple buffers have the lowest priority among all buffers102, the priority manager112may break the tie by selecting the buffer with a larger number of analytics engine flags set.

In some implementations, the analytics engine scheduler140may check the buffer scoreboard142periodically, when scheduling analytics sub-engines150, or prior to executing scheduled analytics sub-engines150. For a buffer that is flagged for recycling according to the buffer scoreboard142, the analytics engine scheduler140may cancel pending execution of any scheduled analytics sub-engines105. In some implementations, the priority manager112may notify the analytics engine scheduler140when a buffer is flagged for recycling.

FIG. 2is a block diagram of an example system200to store index entries representing data content of interest in a hierarchical index, according to an implementation. In some implementations, the system200may be a computing system, such as a server, a desktop computer, a workstation, a laptop computer, a distributed computing system, a cloud computing system, etc. The system200may include an apparatus201, which may be deemed a sub-system of the system200in some cases.

The apparatus201may include buffers202(e.g.,202-1through202-N), an analytics engine204, and a priority manager212. The buffers202may be analogous in many respects to the buffers102ofFIG. 1. For example, the buffers202may receive incoming data203.

The analytics engine204may be analogous in many respects to the analytics engine104ofFIG. 1. The analytics engine204may identify data content of interest from data203in the buffers202, and may store index entries206representing the identified data content in a hierarchical index208having indices of different performance levels210. The index entries206, the hierarchical index208, and the indices of different performance levels210may be analogous in many respects to the index entries106, the hierarchical index108, and the different performance levels110ofFIG. 1, respectively.

The priority manager212may maintain an index scoreboard214that tracks where index entries206are to be stored among the different performance levels210of the hierarchical index208based on predetermined polices216that prioritize data content of interest or functions that use data content of interest. The priority manager212, the index scoreboard214, and the predetermined policies216may be analogous in many respects to the priority manager112, the index scoreboard114, and the predetermined policies116ofFIG. 1, respectively.

FIG. 3is a flowchart of an example method300for storing index entries in a hierarchical index, according to an implementation. Method300may be implemented in the form of executable instructions stored on a machine readable storage medium and executed by at least one processor and/or in the form of electronic circuitry. For example, method300may be executed or performed by the system100or any components thereof (including apparatus101). Various other suitable components and systems may be used as well, such as components of the system200and apparatus201.

In some implementations of the present disclosure, one or more blocks of method300may be executed substantially concurrently or in a different order than shown inFIG. 3. In some implementations of the present disclosure, method300may include more or less blocks than are shown inFIG. 3. In some implementations, one or more of the blocks of method300may, at certain times, be ongoing and/or may repeat.

The method300may begin at block302, and continue to block304, where prioritized analyzers (e.g., analytics sub-engines105) search data (e.g.,103) in buffers (e.g.,102) for data content of interest. At block306, index entries (e.g.,106) may be stored, by the analyzers for example, in a hierarchical index (e.g.,108) with (made up of) indexing components of different performance levels (e.g.,110). The index entries (e.g.,106) may represent data content of interest identified by the searching performed at block304.

At block308, a priority manager (e.g.,112) may maintain an index scoreboard (e.g.,114) that indicates where index entries (e.g.,106) are to be stored among the indexing components (e.g.,110) based on predetermined polices (e.g.,116) that involve prioritization of data content of interest or functions that use data content of interest.

At block310, the priority manager (e.g.,112) may maintain buffer priorities, each of the buffer priorities being proportional to a highest priority among analyzers (e.g.,105) that have not yet searched a corresponding buffer (e.g.,102) for data content of interest. The buffer priorities may be useful in coordinating buffer recycling or data eviction. The method300may end at block312.

FIG. 4is a flowchart of an example method400for storing index entries in a hierarchical index, according to another implementation. Method400may be implemented in the form of executable instructions stored on a machine readable storage medium and executed by at least one processor, and/or may be implemented in the form of electronic circuitry. As with method300, method400may be executed or performed by the system100or any components thereof (including apparatus101). In some implementations of the present disclosure, one or more blocks of method400may be executed substantially concurrently or in a different order than shown inFIG. 4. In some implementations of the present disclosure, method400may include more or less blocks than are shown inFIG. 4. In some implementations, one or more of the blocks of method400may, at certain times, be ongoing and/or may repeat.

The method400may begin at block402, and continue to perform asynchronous processes. For example, the method400may include a process that includes blocks404,406,408,410,412,414,415,416,418, and another process that includes blocks420,422,424.

The process beginning at block404will first be described. At block404, a buffer controller (e.g.,144) may check if any buffers (e.g.,102) are available to receive new data (e.g.,103). For example, a buffer may be available if it is not already holding data. If a buffer or buffers are available (“YES” at block404), the available buffer receives incoming data103at block408.

If insufficient buffers are available to receive new data (“NO” at block404) because all or nearly all of the buffers102are already holding data, the method may proceed to block406. At block406, a priority manager112, may select a buffer or buffers for data eviction (also referred to as buffer recycling) based on a buffer scoreboard (e.g.,142) that includes buffer priorities and counts of analyzers that have searched each of the buffers. For example, as described above with respect toFIG. 1, the priority manager112may select for data eviction a buffer having a lowest buffer priority according to the buffer scoreboard142, and ties in priority may be broken by selecting the buffer with a larger count of analyzers. The buffer controller may move data out of the selected buffer and into a storage device, such as a tiered storage system (e.g.,122), thus freeing the selected buffer to receive new data at block408. In some implementations, the buffer controller may move data into a tier of a tiered storage system according to placement rules, where some placement rules may differ for some data content of interest.

At block410, an analyzer (e.g.,104or105) may run or execute against data received in the buffer at block408, to identify or detect data content of interest in the data. An example analyzer may be a content recognizer. If the analyzer successfully identified or detected data content of interest, the analyzer may generate an index entry representing that data content of interest.

At block412, the analyzer may store the index entry (e.g.,106) generated at block410in a hierarchical index (e.g.,108). More particularly, the hierarchical index may include indexing components having different performance levels (e.g.,110), and the analyzer may store the index entry in a particular one of the index components according to an index scoreboard (e.g.,114).

At block414, the priority manager may maintain the index scoreboard based on predetermined policies (e.g.,116) that involve prioritization of data content of interest or functions that use data content of interest. In some implementations, the index scoreboard may be maintained with updates at block412in response to recently stored index entries or in response to changes in the system100(e.g., memory pressure may affect rules governing how fast certain index entries are moved to lower performance levels of the hierarchical index). In some implementations, the priority manager112may maintain the index scoreboard by moving existing index entries in the hierarchical index to different performance levels, based on a policies attached to those index entries in the index scoreboard.

At block415, the priority manager may maintain a buffer scoreboard (e.g.,142). In some implementations, the buffer scoreboard may track buffer priorities of the buffers. In some implementations, buffer priority may be proportional to a highest priority among analyzers that have not yet searched that buffer for data content of interest. Moreover, the priority manager may update portions of the buffer scoreboard with new information based on execution of analyzers at block410, which in turn may impact buffer priority (e.g., based on changes of the highest priority of unexecuted analyzers).

In some implementations, the apparatus101may include multiple analyzers that may execute against the buffer, either sequentially, in parallel, or in accordance with inter-analyzer priority dependencies. Execution of multiple analyzers may be managed or scheduled by a scheduler (e.g.,140). At block416, if the scheduler determines that all scheduled analyzers have executed against the buffer (“YES” at block416), control passes to418. If the scheduler determines that scheduled analyzer(s) have yet to be executed against the buffer (“NO” at block416), control may return to block410to continue executing the scheduled analyzer(s).

At block418, a placement engine (e.g.,120) may move data from the buffer to the tiered storage system according to placement rules that prioritize data content of interest or functions that use data content of interest. In some implementations, the buffer controller may move data from multiple buffers to the tiered storage system at block418. The placement rules may be similar in many regards to the placement rules described above with respect toFIG. 1.

The process including blocks420,422,424will now be described. At block420, a post-processor (e.g.,130) may identify a high priority combination of data content of interest that co-exist in data. For example, the combinations of data content of interest may be identified from index entries in the hierarchical index or from data stored in the tiered storage system. In some implementations, the post-processor may include an association rule miner engine that implements at least some aspects of association rule mining to perform block420, such as calculating support and/or confidence values for different combinations of data content of interest, although the post-processor may also employ other machine learning techniques, data mining techniques, etc.

At block422, the post-processor may create a new placement rule to move data exhibiting the combination identified at block420. For example, in some implementations, the new placement rule may prescribe moving data from a buffer to a high performance tier of the tiered storage system, by virtue of prominent combinations being deemed an important insight by a user, for example. At block424, the post-processor or the priority manager may store the new placement rule created at block422as an index entry in the hierarchical index. In some implementations, the placement rule stored at block424may be used by blocks406and418when transferring data from buffer(s) to the tiered storage system.

After block418and block424, the method may end at block426. However, it should be understood that the method400may be repeated as new data is received as part of a data stream.

FIG. 5is a block diagram illustrating a data content analysis system500that includes a machine readable medium encoded with example instructions to store index entries in a hierarchical index. In some implementations, the data content analysis system500may serve as or form part of the apparatus101or, more generally, the system100inFIG. 1. In some implementations, the data content analysis system500may include at least one processor502coupled to a machine readable medium504.

The processor502may include a single-core processor, a multi-core processor, an application-specific integrated circuit, a field programmable gate array, and/or other hardware device suitable for retrieval and/or execution of instructions from the machine readable medium504(e.g., instructions506,508,510,512) to perform functions related to various examples. Additionally or alternatively, the processor502may include electronic circuitry for performing the functionality described herein, including, but not limited to, the functionality of instructions506,508,510, and/or512. With respect to the executable instructions represented as boxes inFIG. 5, it should be understood that part or all of the executable instructions and/or electronic circuits included within one box may, in alternate implementations, be included in a different box shown in the figures or in a different box not shown.

The machine readable medium504may be any medium suitable for storing executable instructions, such as random access memory (RAM), electrically erasable programmable read-only memory (EEPROM), flash memory, hard disk drives, optical discs, or the like. In some example implementations, the machine readable medium504may be a tangible, non-transitory medium, where the term “non-transitory” does not encompass transitory propagating signals. The machine readable medium504may be disposed within the data content analysis system500, as shown inFIG. 5, in which case the executable instructions may be deemed “installed” or “embedded” on the data content analysis system500. Alternatively, the machine readable medium504may be a portable (e.g., external) storage medium, for example, that allows the data content analysis system500to remotely execute the instructions or download the instructions from the storage medium. In this case, the executable instructions may be part of an “installation package.” As described further herein below, the machine readable medium504may be encoded with a set of executable instructions506,508,510,512.

Instructions506, when executed by the processor502, may store index entries in a hierarchical index with indexing components of different performance levels, the index entries representing data content of interest identified by analyzers executed against data in buffers. Instructions508, when executed by the processor502, may determine where index entries are to be stored among the indexing components of the hierarchical index, based on predetermined polices that involve prioritization of data content of interest or functions that use data content of interest. Instructions510, when executed by the processor502, may maintain a buffer scoreboard to track a buffer priority for each of the buffers. In some implementations, the buffer priority of each buffer may be proportional to a highest priority among analyzers that has not yet executed against the buffer. Instructions512, when executed by the processor502, may move data from the buffers to a tiered storage system according to placement rules related to data content of interest.

FIG. 6diagram of an example data content analysis system600that includes a machine readable medium encoded with example instructions to identify or create a new placement rule and to evict data. In some implementations, the data content analysis system600may serve as or form part of the apparatus101or, more generally, the system100inFIG. 1. The data content analysis system600includes a processor602and a machine readable medium604, which may be analogous in many respects to the processor602and the machine readable medium604, respectively. The machine readable medium604may be encoded with a set of executable instructions606,608,610. Additionally or alternatively, the processor602may include electronic circuitry for performing the functionality described herein, including, but not limited to, the functionality of instructions606,608,610.

Instructions606, when executed by the processor602, may identify a high priority combination of data content of interest that co-exist in data. For example, instructions606may include instructions to perform at least some parts of association rule mining to identify such combinations (e.g., by calculating support values and/or confidence values for different combinations of data content of interest). Instructions608, when executed by the processor602, may create a new placement rule to move data exhibiting the identified combination (e.g., identified by instructions606) from a buffer to a high performance tier of the tiered storage system. Instructions610, when executed by the processor602, may evict data from the buffers based on a buffer scoreboard.

FIG. 7illustrates example index contents700of a hierarchical index (e.g.,108) according to one example implementation. As will be described below, the index contents700may include index entries (e.g.,106, included directly or included indirectly by mapping, pointers, etc.) and index scoreboard information (e.g.,114).FIG. 7may illustrate index contents700used by a system in the context of an interactive web content store, such as a bldg. The system may include analyzers or analytics sub-engines, such as a clickstream analyzer that identifies content representing web users' actions (deemed to be very valuable for immediate application decision making by a user, in this example), an image1 recognizer that recognizes pictures of food, an image2 recognizer that recognizes pictures of kittens, a video recognizer that recognize videos of crowds, and a text1 recognizer that recognizes positive comments about food.

In the index contents700, information in the Key column includes a key type (e.g., “Object” or “Result” inFIG. 7) paired with an identifier number. An “Object” key type may indicate that the row relates a set of buffered data for which a related index entry was generated. A “Result” key type may indicate that an action (e.g., a placement action) is to be triggered if a recognizer detects the paired value.

In the index contents700, information in the Value column includes a value type (e.g., “Result”, “Accesses”, “Place” inFIG. 7) paired with a value. The value type may reflect a function that either generated the value or a function that can use the value. For example, a “Result” value type may refer to an insight generated by an analytics engine and stored as an index entry in a hierarchical index, an “Accesses” value type may refer to insight into a number of accesses of a data stored as an index entry in the hierarchical index, and a “Place” value type may refer to a placement rule stored in the hierarchical index. The Key and Value columns may represent or map to index entries (e.g.,106) stored in a hierarchical index (e.g.,108), or alternatively, the Key and Value columns may be the index entries (e.g.,106) themselves.

In the index contents700, information in the Function column indicates the function that either generated the value (e.g., “Image1 Recognizer”, “Image2 Recognizer”, “Text1 Recognizer”, “Clickstream Analyzer”, “Statistics” inFIG. 7) or a function that can use the value (e.g., “Placement Engine” inFIG. 7). Information in the Recent Access column indicates whether the Value was recently accessed or the Function was recently used. Information in the Index Policy column sets forth the policy by which an index entry (e.g.,106) corresponding to that row of the index contents700will be placed in the hierarchical index. For example, a Least Recently Used (LRU) policy may be used to move or demote index entries that have not been accessed recently to a lower performance level of the hierarchical index (i.e., the “aging” process discussed above with respect to policies116). In some implementations, the Function column and the Recent Access column may form aspects of an index scoreboard (e.g.,114). In some implementations, the Index Policy column also may form an aspect of the index scoreboard (e.g.,114), and may be derived from or represent predetermined policies (e.g.,116) encoded in a priority manager (e.g.,112).

In the present illustration, the index contents700indicates that Object 1 was recognized as an image of a kitten with15accesses, Object 2 is a clickstream log, and both Objects 3 and 4 were recognized as containing positive text and images of food. Object 3 was accessed 100 times, and Object 4 has not been accessed much.

The rows of the index contents700with “Result” Key types are placement rules to be effected by a Placement Module as noted in the Function column (such as placement engine120). Specifically, the rows with “Place:Image1+Text1=Top” Value type illustrate a high priority combination of positive text comments and images of food, discovered by association rule mining, for example. The placement rule may trigger the placement engine to place data containing such a combination in a “Top” or highest performance tier of a tiered storage system (e.g.,122) for faster read access. For example, such a placement rule may apply to Object 4, even though Object 4 has not been accessed often yet.

The row of the index contents700with “Place:Click Log=Top” Value type may be a rule established when the system was configured by a user, which indicates that all click logs generated by a clickstream analyzer should trigger placement in a high performance tier of a tiered storage system. The row with “Place:Video=Stream” is a placement rule for video content identified by the video recognizer.

The index contents700may be managed by a priority manager (e.g.,112) according to the following example policies. Index entries related to certain data content of interest should be kept at a highest performance level of the hierarchical index (e.g., Object 2, a click log, is kept “high” in the present illustration). Index entries may be moved over time to a low performance level index of the hierarchical index, where index entries are moved over a short time period by default unless overridden by other policies. For example, the “Place:Video=Stream” placement rule may age according to a default quick aging rule (LRU short), whereas the “Place:Image1+Text1=Top” placement rule may age with a long LRU time frame because discovered combinations are deemed important by the user. Index entries for objects related to important placement rules may move to a low performance level over a medium time frame (e.g., Objects 3 and 4 have LRU Medium aging because they are related to important placement rules). According to the foregoing policies, shaded entries in the contents700, namely the entries with Keys “Object:1” and “Result:Video” have been aged or moved to a lower performance level of the hierarchical index.

In view of the foregoing description, it can be appreciated that analytic processing of a data stream, such as content recognition, may be accelerated by storing index entries generated by the analytic processing in a an appropriate performance level of an hierarchical index based on the content of the data stream detected by the analytic processing. Moreover, high value data that has data content of interest or combinations of data content of interest may be discovered in time to place that high value data in a high performance portion of a tiered storage system. In some cases, the systems and techniques described above may be deemed to be data content driven implementations for biasing information and data placement in hierarchical indexing systems and tiered storage systems.