Name
Abstract | ||
|---|---|---|
A novel index structure based on the generalized suffix tree (PIGST) is proposed. Combined with post lists, PIGST can answer both structural and content queries. The distinct paths in an XML collection are mapped into strings. The construction algorithm of the PIGST for the path strings is presented based on the modification and improvement of a well-known suffix tree construction algorithm that only requires linear time and space complexity. The query process merely needs m character comparisons for direct containment queries, where m is the length of a query string. An efficient processing method for the indirect containment queries that avoids the inefficient tree traversal operation is also presented. Experiments show that PIGST outperforms earlier approaches. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.is.2005.10.001 | Inf. Syst. |
Keywords | Field | DocType |
linear time,indexation,space complexity | Data mining,Tree traversal,Query string,XML,Computer science,Theoretical computer science,Generalized suffix tree,Suffix tree,Time complexity,Compressed suffix array,Database | Journal |
Volume | Issue | ISSN |
32 | 2 | 0306-4379 |
Citations | PageRank | References |
3 | 0.38 | 20 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zuo-Peng Liang | 1 | 5 | 0.79 |
| Kongfa Hu | 2 | 38 | 9.26 |
| Ning Ye | 3 | 3 | 0.38 |
| Yisheng Dong | 4 | 245 | 20.54 |