Entfernungsabfragen

Einfache Sprache

Def. Entfernungsabfragen

Es muss eine Distanzfunktion $\textrm{dist}$ definiert sein. Die Entfernungsabfragen $RQ(o,\varepsilon)$ gibt für ein Objekt $o$ und eine Distanz $\varepsilon$ alle Objekte zurück, die höchstens $\varepsilon$ entfernt von $o$ sind. Also

$$RQ(o,\varepsilon) = \{q\in\mathcal D\mid\textrm{dist}(q,o)\leq \varepsilon\}\;.$$

Einfachster Algorithmus löst das Problem als Squenzieller Scan. Dabei gibt $\textrm{getObject}(\mathcal D,i)$ das $i$-te Objekt der Datenbank $\mathcal D$ zurück.

	\begin{algorithm}
	\caption{Range query with squential scan}
	\begin{algorithmic}
	\Input $\textrm{Datenbank }\mathcal D, \textrm{Abfragenobjekt }q,\textrm{Entfernung }\varepsilon$
    \Procedure{RQ-SeqScan}{$\mathcal D,q,\varepsilon$}
    \State $r\gets \emptyset$
    \For{$i = 1$ to $n$}
	    \State $c = \mathrm{getObject}(\mathcal D, i)$
		\If{$\textrm{dist}(q,c)\leq\varepsilon$}
			\State $r \gets r\cup c$
        \EndIf	    
    \EndFor
    \return $r$
    \EndProcedure
	\end{algorithmic}
	\end{algorithm}