Range Queries [KSR Wiki]

Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.
## 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:
<code python>
%%time
for place in query_numeric_index(places, population_idx, 10e6, 15e6):
    print(place['name'], place['population'])
</code>
++++

<nodisp 1>
++++Lösung|
<code python>
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')
</code>
++++
</nodisp>

### 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:

<code python>
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
</code>

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:
<code python>
node.left = build_tree(sorted_tuples, left_idx, ...)
node.right = build_tree(sorted_tuples, ..., right_idx)
</code>
++++

++++Lösung|
<nodisp 1>
<code python>
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)
</code>
</nodisp>
++++

**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.
++++




### 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:|
<code python>
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"< <B>key:</B> {id}<BR/><B>id:</B> {str(node.value)}<BR/><B>town:</B> {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
</code>
++++
#### 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.