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.

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!

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

%%time
for place in query_numeric_index(places, population_idx, 10e6, 15e6):
    print(place['name'], place['population'])

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')

Statt Binärsuche könnten wir auch einen Binären Suchbaum (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.

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

node.left = build_tree(sorted_tuples, left_idx, ...)
node.right = build_tree(sorted_tuples, ..., right_idx)

Lösung

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:

Visualisiere einen von dir gebauten Baum mit Graphviz. Experimentiere zuerst mit dem 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"< <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

Style deinen BST als Christmas Binary Search Tree!

Ideen:

• Node Shapes
  • Mcircle anyone?
  • es gibt auch Custom Shapes…
• color Attribut
• Background Image…

Idee

Yes (courtesy of Laurin):

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?

• Quadtree
• Range Tree
• K-d_tree
• S2 Library

Versuche, einen K-d-Tree zu bauen. Clone dazu das https://github.com/tkilla77/ksr_talit_indexing Jupyter Notebook und entwickle es weiter.