Introduction
Some basic terminologies related to route prediction
Probabilistic generalized suffix tree
Suffix tree related work and literature
Algorithms | Complexity | Memory locality | Parallel | Probabilistic |
---|---|---|---|---|
McCreight [14] |
\(O(n)\)
| Poor | No | No |
Ukkonen [15] |
\(O(n)\)
| Poor | No | No |
Hunt [17] |
\(O(n^{2} )\)
| Good | No | No |
TRELLIS [30] |
\(O(n^{2} )\)
| Good | No | No |
TDD [28] |
\(O(n^{2} )\)
| Good | No | No |
ST-Merge [29] |
\(O(n^{2} )\)
| Good | No | No |
Wavefront [23] |
\(O(n^{2} )\)
| Good | Yes | No |
B2ST [31] |
\(O(n^{2} )\)
| Good | No | No |
ERA [13] |
\(O(n^{2} )\)
| Good | Yes | No |
Map-Reduce Ukkonen [22] |
\(O(n^{2} )\)
| Good | Yes | No |
Proposed PGST |
\(O(n^{2} )\)
| Good | Yes | Yes |
Suffix tree and generalized suffix tree basics
i | xi
| Suffix |
---|---|---|
1 |
x
1
|
\(e_{1} ,e_{1} ,e_{2} ,e_{3} ,e_{3} ,{\$}\)
|
2 |
x
2
|
\(e_{1} ,e_{2} ,e_{3} ,e_{3} ,{\$}\)
|
3 |
x
3
|
\(e_{2} ,e_{3} ,e_{3} ,{\$}\)
|
4 |
x
4
|
\(e_{3} ,e_{3} ,{\$}\)
|
5 |
x
5
|
\(e_{3} ,{\$}\)
|
6 |
x
6
| $ |
Proposed approach
Two phase probabilistic generalized suffix tree (PGST) construction basics
i | xi | Suffix | Count |
---|---|---|---|
1 | x1
|
\(e_{1} ,e_{2} ,e_{3} ,e_{4} ,{\$}\)
| 2 |
2 | x2
|
\(e_{2} ,e_{3} ,e_{4} ,{\$}\)
| 2 |
3 | x3
|
\(e_{3} ,e_{4} ,{\$}\)
| 4 |
4 | x4
|
\(e_{4} ,{\$}\)
| 4 |
5 | x5
|
\({\$}\)
| 4 |
6 | x6
|
\(e_{1} ,e_{5} ,e_{3} ,e_{4} ,{\$}\)
| 1 |
7 | x7
|
\(e_{5} ,e_{3} ,e_{4} ,{\$}\)
| 1 |
Distributed construction of PGST tree
i | xi
| Suffix | Count |
---|---|---|---|
1 | x1
|
\({\text{e}}_{1} ,{\text{e}}_{2} ,{\text{e}}_{3} ,{\text{e}}_{4} ,{\$}\)
| 1 |
2 | x2
|
\({\text{e}}_{2} ,{\text{e}}_{3} ,{\text{e}}_{4} ,{\$}\)
| 1 |
3 | x3
|
\({\text{e}}_{3} ,{\text{e}}_{4} ,{\$}\)
| 2 |
4 | x4
|
\({\text{e}}_{4} ,{\$}\)
| 2 |
5 | x5
|
\({\$}\)
| 2 |
j | yj
| Suffix | Count |
---|---|---|---|
1 | y1
|
\({\text{e}}_{1} ,{\text{e}}_{2} ,{\text{e}}_{3} ,{\text{e}}_{4} ,{\$}\)
| 1 |
2 | y2
|
\({\text{e}}_{2} ,{\text{e}}_{3} ,{\text{e}}_{4} ,{\$}\)
| 1 |
3 | y3
|
\({\text{e}}_{3} ,{\text{e}}_{4} ,{\$}\)
| 2 |
4 | y4
|
\({\text{e}}_{4} ,{\$}\)
| 2 |
5 | y5
|
\({\$}\)
| 2 |
6 | y6
|
\({\text{e}}_{1} ,{\text{e}}_{5} ,{\text{e}}_{3} ,{\text{e}}_{4} ,{\$}\)
| 1 |
7 | y7
|
\({\text{e}}_{5} ,{\text{e}}_{3} ,{\text{e}}_{4} ,{\$}\)
| 1 |
i | zj
| Key (k) | Values (v) | 〈K, 〈value_list〉〉 |
---|---|---|---|---|
1 | z1
|
\(e_{1} ,e_{2} ,e_{3} ,e_{4} ,{\$}\)
| 1, 1 | 〈\(e_{1} ,e_{2} ,e_{3} ,e_{4} ,{\$}\), 〈1, 1〉〉 |
2 | z2
|
\(e_{2} ,e_{3} ,e_{4} ,{\$}\)
| 1, 1 | 〈\(e_{2} ,e_{3} ,e_{4} ,{\$}\), 〈1, 1〉〉 |
3 | z3
|
\({\text{e}}_{3} ,{\text{e}}_{4} ,{\$}\)
| 2, 2 | 〈\(e_{3} ,e_{4} ,{\$}\), 〈2, 2〉〉 |
4 | z4
|
\(e_{4} ,{\$}\)
| 2, 2 | 〈\(e_{4} ,{\$}\), 〈2, 2〉〉 |
5 | z5
|
\({\$}\)
| 2, 2 | 〈\({\$}\), 〈2, 2〉〉 |
6 | z6
|
\(e_{1} ,e_{5} ,e_{3} ,e_{4} ,{\$}\)
| 1, 0 | 〈\(e_{1} ,e_{5} ,e_{3} ,e_{4} ,{\$}\), 〈1, 0〉〉 |
7 | z7
|
\(e_{5} ,e_{3} ,e_{4} ,{\$}\)
| 1, 0 | 〈\(e_{5} ,e_{3} ,e_{4} ,{\$}\), 〈1, 0〉〉 |
i | zj
| 〈K, 〈value_list〉〉 | 〈K, sum (values)〉 |
---|---|---|---|
1 | z1
| 〈\(e_{1} ,e_{2} ,e_{3} ,e_{4} ,{\$}\), 〈1, 1〉〉 | 〈\(e_{1} ,e_{2} ,e_{3} ,e_{4} ,{\$}\), 〈2〉〉 |
2 | z2
| 〈\(e_{2} ,e_{3} ,e_{4} ,{\$}\), 〈1, 1〉〉 | 〈\(e_{2} ,e_{3} ,e_{4} ,{\$}\), 〈2〉〉 |
3 | z3
| 〈\(e_{3} ,e_{4} ,{\$}\), 〈2, 2〉〉 | 〈\(e_{3} ,e_{4} ,{\$}\), 〈4〉〉 |
4 | z4
| 〈\(e_{4} ,{\$}\), 〈2, 2〉〉 | 〈\(e_{4} ,{\$}\), 〈4〉〉 |
5 | z5
| 〈\({\$}\), 〈2, 2〉〉 | 〈\({\$}\), 〈4〉〉 |
6 | z6
| 〈\(e_{1} ,e_{5} ,e_{3} ,e_{4} ,{\$}\), 〈1, 0〉〉 | 〈\(e_{1} ,e_{5} ,e_{3} ,e_{4} ,{\$}\), 〈1〉〉 |
7 | z7
| 〈\(e_{5} ,e_{3} ,e_{4} ,{\$}\), 〈1, 0〉〉 | 〈\(e_{5} ,e_{3} ,e_{4} ,{\$}\), 〈1〉〉 |
Route prediction
Route prediction related work and literature
Route prediction using probabilistic suffix tree (PST)
Implementation and evaluation
Map data-spatial road network data
-
Open layers (maps formed by fetching data from data base) and
-
Base map images (Google Map Images or OSM Map Images can be used).