Searching data streams has been traditionally very limited, either in the complexity of the search or in the size of the searched dataset. In this paper, we investigate the design and optimization of constructs that enable SQL to express complex patterns. In particular we propose the RSPS (recursive sequential pattern search) algorithm that inspired by the KMP (Knuth-Morris-Pratt) string matching algorithm and exploits the inter-dependencies between the elements of a sequential pattern to minimize repeated passes over the same data. Performance gains derived from a set of experiments and a sensitivity analysis for the RSPS are also discussed. Our experimental results demonstrate impressive speedup. 1.

The need to search for complex and recurring patterns in database sequences is shared by many applications. In this paper, we investigate the design and optimization of a query language capable of expressing and supporting efficiently the search for complex sequential patterns in database systems. Thus, we first introduce SQL-TS, an extension of SQL to express these patterns, and then we study how to optimize the queries for this language. We take the optimal text search algorithm of Knuth, Morris and Pratt, and generalize it to handle complex queries on sequences. Our algorithm exploits the interdependencies between the elements of a pattern to minimize repeated passes over the same data. Experimental results on typical sequence queries, such as double bottom queries, confirm that substantial speedups are achieved by our new optimization techniques.

The need to search for complex and recurring patterns in database sequences is shared by many applications. In this paper, we discuss how to express and support efficiently sophisticated sequential pattern queries in databases. Thus, we first introduce SQL-TS, an extension of SQL, to express these patterns, and then we study how to optimize search queries for this language. We take the optimal text search algorithm of Knuth, Morris and Pratt, and generalize it to handle complex queries on sequences. Our algorithm exploits the inter-dependencies between the elements of a sequential pattern to minimize repeated passes over the same data. Experimental results on typical sequence queries, such as double bottom queries, confirm that substantial speedups are achieved by our new optimization techniques.

The access patterns of the users of a web-site are traditionally analyzed in order to facilitate the user access to the site's information. In this study, however, a systematic approach is introduced in order to analyze the users' navigation paths to the advantage of the web-site owner. Briefly, as users navigate through a web-site, it seems that they are transparently filling a questionnaire designed a priori by the web-site owner. To achieve this, we first cluster the users who navigate similar paths employing the Path Mining algorithm. Next, the correlation between a set of target questions and the structure of the WWW-site is quantified. This has been done by borrowing the concept of channel from information theory. Finally, we compute the probability of a user's certain answer to each question, given the user's navigation path. The accuracy of the computed probabilities highly depends on the channel parameters. Hence, we describe a learning process based on a set of training data...