## Range Queries
In der Ortsdatenbank möchten wir alle Orte finden, deren Bevölkerung grösser oder kleiner als ein beliebiger Schwellenwert ist. Wir wollen einen Index erstellen, der für alle möglichen Schwellenwerte funktioniert und schnell ist.
### Aufgabe 4a
Wie stellen wir das am besten an, so dass die Abfrage nach einem Bereich effizient ist? Können wir etwas ähnliches machen wie oben mit Dictionaries? Diskutiert in Gruppen!
### Aufgabe 4b
Implementiert eine effiziente Abfrage für _Range Queries_. In `allCountries.zip` gibt es 95 Entitäten, die zw. 10M-15M Einwohner haben, davon 12 Städte.
++++Hinweise|
* Könnte Binärsuche helfen?
* Wie würde der Index dafür aussehen?
* Schreibe eine Funktion `def build_integer_range_index(dataset, attribute)`, die einen Index erstellt!
* verwende `tqdm`!
* Schreibe eine Funktion `def query_numeric_index(dataset, idx, lower, upper)`, die den Index durchsucht und die richtigen Einträge aus dem Dataset liefert!
* verwende `yield`!
Wenn alles funktioniert, sollte das folgende Snippet die gewünschten Einträge liefern:
%%time
for place in query_numeric_index(places, population_idx, 10e6, 15e6):
print(place['name'], place['population'])
++++
++++Lösung|
from tqdm.auto import tqdm
# Create the index.
def build_integer_range_index(dataset, attribute):
index = []
for id, entity in tqdm(dataset.items()):
# Only include entities that specify a population (no mountains and lakes, please)
try:
value = int(entity[attribute])
if value > 0:
index.append((value, id))
except ValueError:
pass
index.sort() # Sort first by population, then id
return index
def query_numeric_index(dataset, idx, lower, upper):
# Use bisect instead of implementing binary search ourselves:
import bisect
# Use operator.itemgetter(0) to extract the population from the (pop, id) tuple.
import operator
# The index of the smallest entity in idx greater or equal than lower.
lower_index = bisect.bisect_left(idx, lower, key=operator.itemgetter(0))
# The index of the smallest entity in population_idx greater than upper.
upper_index = bisect.bisect_right(idx, upper, key=operator.itemgetter(0))
for index_key in range(lower_index, upper_index):
yield dataset[idx[index_key][1]]
%time population_idx = build_integer_range_index(places, 'population')
++++
### Aufgabe 4c
Statt Binärsuche könnten wir auch einen Binären Suchbaum (_Binary Search Tree_ - [[wp>Binary_search_tree|BST]]) verwenden. Jeder Knoten (_Node_) des Baums speichert eine Stadt mit ihrer Bevölkerungszahl als Schlüssel (_Key_) und der dazugehörigen `geonameid` als Wert (_Value_). Dazu hat jeder Knoten noch zwei Unterknoten: Im Knoten `left` werden alle Knoten mit kleineren Keys gespeichert, im Knoten `right` werden alle Knoten mit grösseren Keys gespeichert.
[[http://magjac.com/graphviz-visual-editor/?dot=digraph%20BST_Pop%20%7B%0A%20%20%20%20rankdir%3DTB%3B%20ordering%3Dout%3B%0A%09node%20%5Bshape%20%3D%20circle%3B%20width%3D1%3B%20fixedwidth%3Dtrue%5D%3B%0A%0A%20%20%20%20Seoul%5Blabel%3D%3Cpop%3A%2010349312%3CBR%2F%3E%5CN%3E%5D%0A%20%20%20%20Moscow%5Blabel%3D%3Cpop%3A%2010381222%3CBR%2F%3E%5CN%3E%5D%0A%20%20%20%20Wuhan%5Blabel%3D%3Cpop%3A%2010392693%3CBR%2F%3E%5CN%3E%5D%0A%20%20%20%20Tianjin%5Blabel%3D%3Cpop%3A%2011090314%3CBR%2F%3E%5CN%3E%5D%0A%20%20%20%20Karachi%5Blabel%3D%3Cpop%3A%2011624219%3CBR%2F%3E%5CN%3E%5D%0A%20%20%20%20S%C3%A3o_Paulo%5Blabel%3D%3Cpop%3A%2012400232%3CBR%2F%3ES%C3%A3o%20Paulo%3E%5D%0A%20%20%20%20Chengdu%5Blabel%3D%3Cpop%3A%2013568357%3CBR%2F%3E%5CN%3E%5D%0A%20%20%20%20%0A%0A%20%20%20%20Tianjin%20-%3E%20Moscow%20%5Blabel%3Dleft%5D%3B%0A%20%20%20%20Tianjin%20-%3E%20S%C3%A3o_Paulo%20%5Blabel%3Dright%5D%3B%0A%20%20%20%20Moscow%20-%3E%20Seoul%20%5Blabel%3Dleft%5D%3B%0A%20%20%20%20Moscow%20-%3E%20Wuhan%20%5Blabel%3Dright%5D%3B%0A%20%20%20%20S%C3%A3o_Paulo%20-%3E%20Karachi%20%5Blabel%3Dleft%5D%3B%0A%20%20%20%20S%C3%A3o_Paulo%20-%3E%20Chengdu%20%5Blabel%3Dright%5D%3B%0A%0A%7D%0A|{{:talit:pasted:20230827-221805.png?nolink&500}}]]
Ein Knoten sieht in Python zum Beispiel so aus:
class Node:
"""A tree node, also represents an entire (sub-)tree."""
def __init__(self, key, value):
self.key = key
self.value = value
self.left = None
self.right = None
Aufgabe: Schreibe eine Funktion `def build_tree(sorted_tuples, left_idx, right_idx)`, die aus einer sortierten Liste von Tupeln `(population, geonameid)` einen Baum baut, der den obigen Bedingungen genügt.
++++Hinweise|
* Das Wurzel-Element ist idealerweise das Element in der Mitte zwischen `left_idx` und `right_idx` (Median), dann sind beide Subtrees ungefähr gleich gross, der Baum ist _balanciert_.
* Rekursion ist praktisch: Schaffe einen neuen Knoten `node = Node(key, value)`, anschliessend rufe die Funktion für den linken und rechten Subtree auf:
node.left = build_tree(sorted_tuples, left_idx, ...)
node.right = build_tree(sorted_tuples, ..., right_idx)
++++
++++Lösung|
def build_tree(sorted_tuples, left=None, right=None):
"""Builds a binary search tree from a sorted tuple list."""
left = left if left is not None else 0
right = right if right is not None else len(sorted_tuples) - 1
# Stop when the given range is empty.
if left > right:
return None
median = (left + right) // 2
element = sorted_tuples[median]
node = Node(element[0], element[1])
node.left = build_tree(sorted_tuples, left, median - 1)
node.right = build_tree(sorted_tuples, median + 1, right)
return node
population_tree = build_tree(population_idx)
++++
**Suche im BST**
Wie können wir im Suchbaum ein Element finden? Wir steigen im Baum vom Wurzelknoten her ab, und wenden uns jeweils links oder rechts, je nachdem, ob der Key kleiner oder grösser als der gewünschte Wert ist.
Schreibe eine Funktion `bst_search(node, key)`, die den Value des gewünschten Knotens zurückgibt. Wie sieht die rekursive Variante davon aus?
Wie könnte eine (rekursive) Funktion aussehen, die alle Values zurückgibt, die zwischen zwei Grenzen stehen (_range query_)?
++++Hinweise:|
* Generators kommen auch bei der Rekursion elegant zum Tragen:
* Wenn das Element des Nodes der Query entspricht, können wir es direkt mit `yield` zurückgeben.
* Der rekursive Aufruf hingegen gibt ja wieder um einen Generator zurück, nicht ein einzelnes Element. Einen anderen Generator können wir mit `yield from` in unseren Generator integrieren.
* Die Reihenfolge sollte der Sortierung des Baums gehorchen: zuerst der linke Teilbaum, dann das Knotenelement, dann der rechte Teilbaum.
++++
++++Lösung|
def tree_search(node, lower, upper):
"""Traverses tree in-order from lower to upper key."""
if node is None:
return # reached the bottom of the tree
if lower <= node.key:
# return elements on our left
yield from tree_search(node.left, lower, upper)
if lower <= node.key <= upper:
yield node.value # return this node's value
if node.key <= upper:
# return elements on our right
yield from tree_search(node.right, lower, upper)
import time
start = time.time()
for geonameid in tree_search(population_tree, 10e6, 15e6):
entity = places[geonameid]
print(entity['name'], entity['population'])
elapsed = time.time() - start
print(f"took {elapsed:.2g}s")
++++
### Graph Visualization ###
Visualisiere einen von dir gebauten Baum mit [[https://graphviz.org/|Graphviz]]. Experimentiere zuerst mit dem [[http://magjac.com/graphviz-visual-editor/?dot=graph%20%7B%0A%20%20%20%20A%20--%20B%3B%0A%20%20%20%20A%20--%20C%3B%0A%20%20%20%20B%20--%20D%3B%0A%20%20%20%20B%20--%20E%3B%0A%20%20%20%20C%20--%20F%3B%0A%20%20%20%20C%20--%20G%3B%0A%7D/|Online-Editor]], um ein Gefühl dafür zu kriegen, wie ein Baum aussehen könnte. Verwende anschliessend das `graphviz` Package in Python wie folgt.
Beachte:
* Einen neuen Graph erzeugen wir mit `graph = graphviz.Digraph('Graph Title')`.
* In Graphviz werden zuerst Knoten (_nodes_) erstellt
* `graph.node('A')`
* `graph.node('B')`
* Kanten (_edges_) werden zwischen zwei Knoten eingefügt, diese werden über ihre Id identifiziert:
* `graph.edge('A', 'B')`
* Rekursion wäre wieder mal hilfreich...
++++Lösung:|
def render_tree(graph, node, nuller=""):
"""Renders the tree in graphviz."""
if node is None:
# In order to have separate Nil-nodes, we need to create artificially
# named nodes with unique names. We use the 'nuller' parameter to create
# these, which is the left/right-path down from the root.
graph.node(nuller, "", shape="point")
return nuller
id = str(node.key)
graph.node(id, f"< key: {id}
id: {str(node.value)}
town: {towns[node.value]['name']} >")
left_key = render_tree(graph, node.left, nuller + "l")
graph.edge(id, left_key)
right_key = render_tree(graph, node.right, nuller + "r")
graph.edge(id, right_key)
return id
dot = graphviz.Digraph("Population Search Tree")
render_tree(dot, tree)
dot
++++
#### Christmas Challenge
Style deinen BST als Christmas Binary Search Tree!
Ideen:
* [[https://graphviz.org/doc/info/shapes.html#polygon|Node Shapes]]
* Mcircle anyone?
* es gibt auch Custom Shapes...
* `color` Attribut
* Background Image...
[[http://magjac.com/graphviz-visual-editor/?dot=graph%20%7B%0A%20%20%20%20bgcolor%3Dlightblue%0A%20%20%20%20node%20%5Bstyle%3Dfilled%2C%20color%3Dtransparent%2C%20style%3Dradial%5D%0A%20%20%20%20A%20%5Bshape%3Dstar%2C%20fillcolor%3D%22gold%3Abrown%22%5D%3B%0A%20%20%20%20node%20%5Bshape%3Dtriangle%2C%20fillcolor%3D%22green%3Adarkgreen%22%5D%0A%20%20%20%20A%20--%20B%3B%0A%20%20%20%20A%20--%20C%3B%0A%20%20%20%20node%20%5Bshape%3Dcircle%2C%20fillcolor%3D%22red%3Adarkred%22%5D%0A%20%20%20%20B%20--%20D%3B%0A%20%20%20%20B%20--%20E%3B%0A%20%20%20%20C%20--%20F%3B%0A%20%20%20%20C%20--%20G%3B%0A%7D|Idee]]
Yes (courtesy of Laurin):
{{:talit:spatial:pasted:20231218-185336.png?nolink&800}}
## Spatial Algorithms
Bevölkerungszahl, Geburtstage etc. sind einfach, weil die Bevölkerungszahl und Zeit skalare, also eindimensionale Grössen sind. Aber wie können wir einen zweidimensionalen Index schaffen, der uns alle Elemente liefert, die innerhalb eines Rechtecks von Längen- und Breitengraden liegen?
* [[wp>Quadtree]]
* [[wp>Range Tree]]
* [[wp>K-d_tree]]
* [[https://s2geometry.io/|S2 Library]]
### Auftrag 11. September 2023
Versuche, einen K-d-Tree zu bauen. Clone dazu das [[https://github.com/tkilla77/ksr_talit_indexing]] Jupyter Notebook und entwickle es weiter.