Efficient mining of traversal patterns
Data & Knowledge EngineeringPublished 1 November 2001
Yongqiao Xiao, Margaret H. Dunham
Citations62
SJR quartileQ2
SJR score0.68
SNIP1.41
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The proposed algorithm is online, which allows the user to see the incremental results with respect to the scanned part of the database, and adapts to large databases through dynamic compressions and effective pruning.
Abstract
A new problem of mining traversal patterns from Web access logs is introduced. The traversal patterns are defined to keep duplicates as well as consecutive ordering in the sessions. Then an efficient algorithm is proposed. The algorithm is online, which allows the user to see the incremental results with respect to the scanned part of the database. The algorithm also adapts to large databases through dynamic compressions and effective pruning. Finally the algorithm is evaluated through experiments with real Web logs.
Keywords
Computer Science
Mining association rules between sets of items in large databases
14,720 Citations1993Rakesh Agrawal, Tomasz Imieliński +1 more
An efficient algorithm is presented that generates all significant association rules between items in the database of customer transactions and incorporates buffer management and novel estimation and pruning techniques.
Mining sequential patterns
5,115 Citations2002R. K. Agrawal, Ramakrishnan Srikant
Three algorithms are presented to solve the problem of mining sequential patterns over databases of customer transactions, and empirically evaluating their performance using synthetic data shows that two of them have comparable performance.
ACM SIGMOD RecordMining association rules between sets of items in large databases
4,475 Citations1993Rakesh Agrawal, Tomasz Imieliński +1 more
Linear pattern matching algorithms
1,810 Citations1973Peter Weiner
A linear time algorithm for obtaining a compacted version of a bi-tree associated with a given string is presented and indicated how to solve several pattern matching problems, including some from [4] in linear time.
An Efficient Algorithm for Mining Association Rules in Large Databases
1,598 Citations1995Ashoka Savasere, Edward Omiecinski +1 more
This paper presents an efficient algorithm for mining association rules that is fundamentally different from known algorithms and not only reduces the I/O overhead significantly but also has lower CPU overhead for most cases.
Journal of the ACMA Space-Economical Suffix Tree Construction Algorithm
1,518 Citations1976Edward M. McCreight
A new algorithm is presented for constructing auxiliary digital search trees to aid in exact-match substring searching that has the same asymptotic running time bound as previously published algorithms, but is more economical in space.
AlgorithmicaOn-line construction of suffix trees
1,465 Citations1995Esko Ukkonen
An on-line algorithm is presented for constructing the suffix tree for a given string in time linear in the length of the string, developed as a linear-time version of a very simple algorithm for (quadratic size) suffixtries.
Knowledge Discovery and Data MiningDiscovering Frequent Episodes in Sequences.
593 Citations1995Heikki Mannila, Hannu Toivonen +1 more
These two cases represent the only melanocytic neoplasms in Rhinoceridae reported in detail in the literature and are thought to be the first of their kind diagnosed in captivity.
IEEE Transactions on Knowledge and Data EngineeringEfficient data mining for path traversal patterns
540 Citations1998Ming-Syan Chen⋆, Jong Soo Park +1 more
The authors explore a new data mining capability that involves mining path traversal patterns in a distributed information-providing environment where documents or objects are linked together to facilitate interactive access and show that the option of selective scan is very advantageous and can lead to prominent performance improvement.
Lecture notes in computer scienceMining Access Patterns Efficiently from Web Logs
498 Citations2000Jian Pei, Jiawei Han +2 more
A novel data structure, called Web access pattern tree, or WAP-tree in short, is developed for efficient mining of access patterns from pieces of logs for access pattern mining.
Communications of the ACMWeb usage mining for Web site evaluation
297 Citations2000Myra Spiliopoulou
Making a site better fit its users by knowing about the needs of potential customers and the ability to establish personalized services that satisfy these needs is key to winning this competitive race.
Lecture notes in computer scienceColor Set Size problem with applications to string matching
168 Citations1992Lucas Chi, Kwong Hui
An optimal sequential solution of the color set size problem and string matching applications including a linear time algorithm for the problem of finding the longest substring common to at least k out of m input strings for all k between 1 and m is given.
Combinatorial pattern discovery for scientific data
149 Citations1994Jason Tsong-Li Wang, Gung‐Wei Chirn +4 more
This paper presents an example of combinatorial pattern discovery: the discovery of patterns in protein databases, which give information that is complementary to the best protein classifier available today.
Generalized suffix trees for biological sequence data: applications and implementation
102 Citations1994Bieganski, Riedl +2 more
This paper presents a new GST-based sequence alignment algorithm, called GESTALT, which finds all exact matches in parallel, and uses best-first search to extend them to produce alignments.
Research Portal (King's College London)Navigation Pattern Discovery from Internet Data
90 Citations1999AG Büchner, Matthias Baumgarten +3 more
A new algorithm called MiDAS is introduced that extends traditional sequence discovery with a wide range of web-specific features and allows the detection of sequences across monitored attributes, such as URLs and http referrers.
Mining association rules: anti-skew algorithms
82 Citations2002Jun-Lin Lin, Margaret H. Dunham
This work proposes several techniques which overcome the problem of data skew in the basket data, and employs prior knowledge collected during the mining process and/or via sampling, to further reduce the number of candidate itemsets and identify false candidate itemset at an earlier stage.
Java Servlets
41 Citations1998Karl Moss
This professional guide is all you need to get servlets up, running - and performing every trick in the book - in record time.
Medical Entomology and ZoologyWeb Usage Analysis and User Profiling: International WEBKDD'99 Workshop San Diego, CA, USA, August 15, 1999 Revised Papers
40 Citations2000Webkdd, Brij Masand +1 more
This paper focuses on the development of a generalization-Based approach to Clustering of Web Usage Sessions and the discovery of Interesting Usage Patterns from Web Data.
Lecture notes in computer scienceMaking Web Servers Pushier
26 Citations2000Bin Lan, Stéphane Bressan +2 more
A strategy for making Web servers "pushier" by identifying the typical access patterns for a set of documents on a Web server and deciding to push these documents to the browsers and proxy servers is presented and evaluated.