m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
path: root/presentation
diff options
context:
space:
mode:
Diffstat (limited to 'presentation')
-rw-r--r--presentation/presentation.md39
1 files changed, 13 insertions, 26 deletions
diff --git a/presentation/presentation.md b/presentation/presentation.md
index ec491e9..9652d3d 100644
--- a/presentation/presentation.md
+++ b/presentation/presentation.md
@@ -5,17 +5,17 @@
## Question Answering
* Fix a function $f : \mathcal{S} \times \mathcal{Q} \to \mathcal{A}$
-* A *preprocessing* algorithm that on input $S \in \mathcal{S}$ outputs an
- indexing structure $S'$ (doesn't need to be in $\mathcal{S}$).
-* An *answering* algorithm that on input $Q \in \mathcal{Q}$, together with
- $S'$, outputs $f(S, Q)$.
+* *preprocessing*: on input $S \in \mathcal{S}$ output an indexing structure
+ $S'$.
+* *answering*: on input $Q \in \mathcal{Q}$, $S'$ outputs $f(S, Q)$.
## Question Answering - Time Complexity
* Let $n = |S|$, $m = |Q|$.
-* If the preprocessing algorithm works in time $f(n)$ and the answering
- algorithm works in time $g(n, m)$, we notate the full algorithm's time
- complexity as $\langle f(n), g(n, m) \rangle$.
+* Preprocessing algorithm works in time $f(n)$
+* Answering algorithm works in time $g(n, m)$
+* Notate the full algorithm's time complexity as $\langle f(n), g(n, m)
+ \rangle$.
## Example: LCA
@@ -46,28 +46,15 @@ singletons.
# Prior Work
-## Naïve Solutions - Model Checking
-
-* Introduce unary relations $U_i$.
-* For question $\vec{W}$, label elements of $W_i$ with $U_i$.
-* If we can answer MSO model checking on trees in time $f(n)$, we can answer
- questions in $O(f(n))$.
-
-## Naïve Solution - Courcelle
+## Reduce to Model Checking
* Courcelle: MSO model checking over structures of bounded treewidth is
$O_{\varphi}(n)$.
-* So we can solve MSO query answering in $\langle O(1), O_{\varphi}(n) \rangle$.
-
-## Naïve Solution - Amarilli et al.
-
-* Amarilli et al.: algorithm that preprocess a tree in time $O_{\varphi}(n)$,
- then allows relabeling in time $O_{\varphi}(\log{n})$, answers model checking
- in $O(1)$ for the updated tree.
-* Preprocess tree according to Amarilli.
-* For a question $\vec{W}$, run an update for each vertex in $\vec{W}$, get the
- answer.
-* So an $\langle O_{\varphi}(n), O_{\varphi}(m \log{n}) \rangle$ solution.
+ * MSO query answering in $\langle O(1), O_{\varphi}(n) \rangle$.
+* Amarilli et al.: $O_{\varphi}(n)$ preprocessing, $O_{\varphi}(\log{n})$
+ relabeling.
+ * MSO query answering in $\langle O_{\varphi}(n), O_{\varphi}(m \log{n})
+ \rangle$.
## Kazana