Event hierarchies and memory organization for structured data retrieval

• US 20080281857A1
• Filed: 05/10/2007
• Published: 11/13/2008
• Est. Priority Date: 05/10/2007
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Dymetman, Marc
• Granted Patent: US 7,831,587 B2
• Time in Patent Office: Days
• US Class Current: 707/102
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures

Abstract

From a corpus of segments, a hierarchical index is derived that indexes high frequency events of a selected event type occurring in segments of the corpus at a frequency higher than or equal to a threshold frequency, and also indexes at least some low frequency events that occur in segments of the corpus at a frequency lower than the threshold frequency. The hierarchy relates events by an order structure in which coarser events subsume finer events. A query is processed respective to a queried event. The processing references information stored in the index relating to either (i) the queried event if the queried event is indexed or (ii) a coarser event that is indexed and that subsumes the queried event if the queried event is not indexed.

Claims

1. An indexing method comprising:

deriving from a corpus of segments a hierarchical index that indexes events of a selected event type occurring in segments of the corpus at a frequency higher than or equal to a threshold frequency, the hierarchy relating events by an order structure in which coarser events subsume finer events, the hierarchical index further indexing at least some low frequency events that occur in segments of the corpus at a frequency lower than the threshold frequency; and

processing a query respective to a queried event, the processing referencing information stored in the index relating to either (i) the queried event if the queried event is indexed or (ii) a coarser event that is indexed and that subsumes the queried event if the queried event is not indexed.

2. The indexing method as set forth in claim 1, wherein the query requests retrieval of segments that satisfy a predicate associated with the queried event, and the processing comprises:

(i) retrieving segments indicated in the index as satisfying the predicate if the queried event is indexed, or (ii) searching segments indicated in the index as satisfying a predicate associated with the coarser event to determine whether the searched segments satisfy the predicate associated with the queried event if the queried event is not indexed.

3. The indexing method as set forth in claim 1, wherein the query requests statistical information pertaining to the queried event, and the processing comprises:

(i) retrieving statistical information stored in the index relating to the queried event if the queried event is indexed, or (ii) processing segments indicated in the index as satisfying a predicate associated with the coarser event to compute the requested statistical information if the queried event is not indexed.

4. The indexing method as set forth in claim 1, wherein the selected event type includes a bag-of-one-or-more-words and the order structure defines a finer event as a bag of words containing all words of a coarser event plus at least one more word.

5. The indexing method as set forth in claim 1, wherein the selected event type includes a discontinuous ordered word sequence including two or more words and the order structure is defined as follows:

if an event a can be derived from an event b by omitting one or more words of the discontinuous ordered word sequence of event b, then event a is a coarser event respective to event b and event b is a finer event respective to event a.

6. The indexing method as set forth in claim 1, wherein the selected event type includes a discontinuous ordered word sequence including two or more words and the order structure is defined as follows:

if the discontinuous ordered word sequence of an event a is a prefix of the discontinuous ordered word sequence of an event b, then event a is a coarser event respective to event b and event b is a finer event respective to event a.

7. The indexing method as set forth in claim 1, wherein the selected event type includes a finite set of first-order logical formulas relating words.

8. The indexing method as set forth in claim 1, wherein the selected event type includes at least two different event types.

9. The indexing method as set forth in claim 1, wherein the selected event type includes a first event type, a second event type, and a conjunctive event type defined as a conjunction of an event of the first event type and an event of the second event type.

10. The indexing method as set forth in claim 9, wherein the low frequency events that are indexed in the hierarchical index include at least those low frequency events of the first event type or of the second event type that are not subsumed by any coarser low frequency events occurring in segments of the corpus at a frequency lower than the threshold frequency.

11. The indexing method as set forth in claim 1, wherein the low frequency events that are indexed in the hierarchical index include at least those low frequency events that are not subsumed by any coarser low frequency events occurring in segments of the corpus at a frequency lower than the threshold frequency.

12. The indexing method as set forth in claim 11, wherein the deriving comprises:

(0) initializing the corpus as an empty corpus;

(x) adding a selected segment to the corpus;

(t) discovering all events of the selected event type in the selected segment;

(a) determining whether each discovered event occurs in segments of the corpus including the selected segment at a frequency greater than or equal to the threshold frequency;

(n) based on the determining for each discovered event, updating an existing index entry or adding a new index entry; and

(b) repeating the operations (x), (t), (a), and (n) until all segments of interest have been added to the corpus.

13. The indexing method as set forth in claim 12, wherein the determining comprises:

conditional upon existence of an index entry corresponding to the discovered event, performing the determining based in information stored in the index for the index entry; and

conditional upon existence of a coarser index entry corresponding to an event that is coarser respective to the discovered event, performing the determining by analyzing segments associated in the index with the coarser index entry.

14. The indexing method as set forth in claim 12, further comprising:

(p) after termination of the operation (b), performing at least one information or segment retrieval operation using the index;

(q) after performing the retrieval operation (p), identifying one or more additional segments to be added to the corpus; and

(j) repeating the operations (x), (t), (a), (n), and (b) to add the one or more additional segments to the corpus.

15. An information system comprising a hierarchical index having a hierarchy relating events of a selected type by an order structure in which coarser events subsume finer events, the hierarchical index containing entries for all high frequency events of the selected type occurring in segments of a corpus at a frequency higher than or equal to a threshold frequency, the hierarchical index storing for each high frequency event at least one statistical datum.

16. The information system as set forth in claim 15, wherein the hierarchical index further contains entries for a subset of all low frequency events of the selected type that occur in segments of the corpus at a frequency lower than the threshold frequency.

17. The information system as set forth in claim 15, wherein the hierarchical index further contains entries for a subset of all low frequency events of the selected type that occur in segments of the corpus at a frequency lower than the threshold frequency, the subset including at least those low frequency events that are not subsumed by any coarser low frequency events, the hierarchical index storing for each event of the subset at least an identification of those segments of the corpus that satisfy a predicate associated with the low frequency event.

18. The hierarchical index as set forth in claim 17, further comprising:

a query processor configured to receive a query requesting information satisfying or retrieval of segments satisfying a query criterion, the query processor determining the information satisfying or retrieving zero or more segments satisfying the query criterion with reference to the index database.

19. The hierarchical index as set forth in claim 17, wherein the threshold frequency is different for different paths along the order structure.

20. The hierarchical index as set forth in claim 17, wherein the threshold frequency is the same for all paths along the order structure.

21. The hierarchical index as set forth in claim 17, wherein the hierarchical index stores for each high frequency event an identification of those segments of the corpus that satisfy a predicate associated with the high frequency event.

22. A method for identifying all high frequency events of a selected event type in a corpus, a high frequency event being an event occurring in a number of segments of the corpus higher than or equal to a threshold frequency, the method comprising:

(0) initializing the corpus as an empty corpus;

(x) adding a selected segment to the corpus;

(t) discovering all events of the selected event type in the selected segment;

(a) determining whether each discovered event occurs in segments of the corpus including the selected segment at a frequency greater than or equal to the threshold frequency;

(n) identifying any discovered event satisfying the determining operation (a) as a high frequency event; and

(b) repeating the operations (x), (t), (a), and (n) until all segments of interest have been added to the corpus, the repeating operation (b) utilizing identifications made in previous iterations of the operation (b) to accelerate the determining.

23. The method as set forth in claim 22, further comprising:

(a1) determining whether each discovered event in segments of the corpus including the selected segment (i) occur in segments of the corpus at a frequency lower than the threshold frequency and (ii) is not subsumed by any coarser events occurring in segments of the corpus at a frequency lower than the threshold frequency; and

(n1) identifying any discovered event satisfying the determining operation (a1) as a minimum low frequency event, the repeating operation (b) additionally repeating the operations (a1) and (n1).

24. The method as set forth in claim 23, further comprising:

storing an index including information pertaining to the high frequency events and the minimum low frequency events; and

responsive to a storage space occupied by the stored index increasing to an undesirable level, increasing the threshold frequency and readjusting the high frequency and minimal low frequency identifications based on the increased threshold frequency.