Re: Canonical DB
From: Dmitry A. Kazakov <mailbox_at_dmitry-kazakov.de>
Date: Sat, 24 Jun 2006 10:59:44 +0200
Message-ID: <1xfv2bo493b8d.1e6zcglw36ulm.dlg_at_40tude.net>
>
> Checking if I am understanding you:
>
> We have two tuples,
> T1(X1, Y1) and T2(X2, Y2), and
> md(T1, T2) defined as |X1 - X2| + |Y1 - Y2|
> Sorting will not help reducing the
> complexity of the md computation.
>
> Ah, I see.
> How about general/specialized?
Date: Sat, 24 Jun 2006 10:59:44 +0200
Message-ID: <1xfv2bo493b8d.1e6zcglw36ulm.dlg_at_40tude.net>
On Sat, 24 Jun 2006 00:18:31 +0200, mAsterdam wrote:
>> mAsterdam wrote: >> >> Imagine that the tuple is (X,Y) where X are streets and Y are avenues. Your >> problem space has Manhattan distance. Linear sorting this table >> fundamentally cannot help you to get out of O(n) pitfall, because whatever >> order on the tuples you define it will not be a distance in 2D. The fact >> that (X,Y) are indeed facts (no pun), does not help us here.
>
> Checking if I am understanding you:
>
> We have two tuples,
> T1(X1, Y1) and T2(X2, Y2), and
> md(T1, T2) defined as |X1 - X2| + |Y1 - Y2|
> Sorting will not help reducing the
> complexity of the md computation.
Complexity of operations defined in terms of md() [spatial operations]. The most obvious is the nearest neighbour search: for a given tuple T find a tuple T* for which md(T,T*) reaches the minimum on the table. (If T is unknown in advance, no linear sort of tuples can help). A more nasty thing is: find all tuples {Ti} for which md(T,Ti) < D.
>> To express the meta-ideas behind relational and what >> some RM guys call "ad-hoc b**t."
>
> it-bucke ? Nah. No clue :-)
(:-)) >>>ISTM local vs. global is within the navigational realm, so >>>inappropriate for comparisons of computations with navigational >>>vs. relational structures. >> >> I didn't meant scopes of variables. Though they are a case. I meant global >> in a more general context: scope, effect, visibility.
>
> Ah, I see.
> How about general/specialized?
Well, yes, but it is different. General rather refers to a class of problems, handled in some general way. Global does to uniformity of the given problem. Though it is based on some generalization made before: "all data are tuples" or "Foo is defined on all instances of the class."
-- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.deReceived on Sat Jun 24 2006 - 10:59:44 CEST