CODEWITHSUNDEEP
sqloracle-databasequery-optimization
user2010422
user2010422

Reputation: 51

Manhattan distance with n dimensions in oracle

I have a table with around 5 millions rows and each row has 10 columns representing 10 dimensions. I would like to be able when a new input is coming to perform a search in the table to return the closest rows using Manhattan distances. The distance is the sum of abs(Ai-Aj)+abs(Bi-Bj)... The problem is that for the moment if I do a query, it does a full scan of the entire table, to calculate the distances from every rows, and then sort them to find the top X.

Is there a way to speed the process and make the query more efficient?

I looked at the distance function online for the SDO_GEOMETRY, but I couldn't find it for more than 4 dimensions.

Thank you

Upvotes: 5

Views: 794

Answers (2)

Xophmeister
Xophmeister

Reputation: 9211

If you are inserting a point A and you want to look for points that are within a neighbourhood of radius r (i.e., are less than r away, on any metric), you can do a really simply query:

select x1, x2, ..., xn
from   points
where  x1 between a1 - r and a1 + r
and    x2 between a2 - r and a2 + r
...
and    xn between an - r and an + r

...where A = (a1, a2, ..., an), to find a bound. If you have an index over all x1, ..., xn fields of points, then this query shouldn't require a full scan. Now, this result may include points that are outside the neighbourhood (i.e., the bits in the corners), but is an easy win to find an appropriate subset: you can now check against the records in this subquery, rather than checking against every point in your table.

You may be able to refine this query further because, with the Manhattan metric, a neighbourhood will be square shaped (although at 45 degrees to the above) and squares are relatively easy to work with! (Even in 10 dimensions.) However, the more complicated logic required may be more of an overhead than an optimisation, ultimately.

Upvotes: 2

Atilla Ozgur
Atilla Ozgur

Reputation: 14701

I suggest using function based index. You need this distance calculated, therefore pre calculate it using function based index.

You may want to read following question and it links. Function based index creates hidden column for you. This hidden column will hold manhanttan distance , therefore sorting will be easier.

Thanks for @Xophmeister's comment. Function based index will not help you for arbitrary point. I do not know any sql function to help you here. But if you are willing to use machine learning data mining algorithm.

I suggest cluster your 5 million rows using k-means clustering. Lets say 1000 cluster center you found. Put this cluster centers to another table. By definition clustering , your points will be assigned to cluster centers. Because of this you know which points are nearest to this cluster center, say cluster (1) contains 20.000 points, ... cluster ( 987) contains 10.000 points ...

Your arbitrary point will be near to one cluster. You find that your point is nearest to cluster 987. Run your sql , using only points which belongs to this cluster center, that 10.000 points.

You need to add several tables/columns to your schema to make this effective. If your 5.000.000 rows changes continuously, you need to run k-means clustering again as they change. But if they are fairly constant values, one clustering per week or per month will be enough.

Upvotes: 0

Related Questions