Worst Case Efficient Multidimensional Indexing

Vorrei sottoporvi un'idea su come affrontare il problema dell'indexing
multidimensionale.

Ho creato un piccolo blog perché si usa così, a quanto pare.
Per non obbligarvi a visitarlo, copio/incollo il contenuto (mi permetto
di lasciarlo in inglese).

(From http://wcemdi.blogspot.com/)
Let's assume that you have a set of points in the plane and that you
want to find all the points within a particular rectangle. How can you
do that efficiently?

Here is the abstract of my paper:

Let us consider the following problem.

Let U_1, U_2, ..., U_d be totally ordered sets and let U = U_1 x U_2 x
... x U_d, where d >= 2. Given a subset S = {s_1, s_2, ..., s_n} of U
and two points a = (a_1, a_2, ..., a_d) in U and b = (b_1, b_2, ...,
b_d) in U, find the set {(x_1, x_2, ..., x_d) in S | for each i in {1,
2, ..., d} a_i <= x_i <= b_i}. This paper presents an algorithm that can
solve this problem in space O(n log^(d-1) n) and time O(log^(d-1) n)
with a precomputation step (independent of a and b) taking time O(n
log^(d-1) n). Moreover, whenever the restrictions are imposed only on k
>= 2 coordinates, the search takes time O(log^(k-1) n + d - k).
If the space is two-dimensional, the problem consists in finding all the
points that are both in S and in the rectangle represented by a and b.
In this case the algorithm solves the problem in space O(n log n) and
time O(log n).
If S is dynamic the problem is more complex. Some ideas aimed at solving
the dynamic version of the problem are presented as well.

You can view and download (PDF) the document here:
http://www.scribd.com/full/3216858?access_key=key-1r88z590x620idm48g3n
http://www.scribd.com/doc/3216858/Worst-Case-Efficient-Multidimensional-Indexing

NOTE: I've just noted that scribd's renderer is not perfect. You should
click on the second link above and download the PDF file. Note also that
while Acrobat Reader renders the document correctly, other viewers (such
as SumatraPDF), have some problems.

Massimiliano Tomassoli
[ Auf dieses Posting antworten ]