1

I'm looking for a spatial index that can efficiently find the most extreme n points in a certain direction, i.e. for a given w, find x[0:n] in the dataset where x0 gives the largest value of w.x and x1 the second largest value of w.x, etc... . Is there a name for this type of query? What would be an efficient data structure to use? x might have around 20 dimensions.

Thankyou!

user1158559
  • 151
  • 3

1 Answers1

2

The query is called a 'top-k' query, and you can answer it quickly using the ranking cube approach. http://www1.se.cuhk.edu.hk/~hcheng/paper/vldb06_rankcube.pdf

The paper does not derive the time complexity.

user1158559
  • 151
  • 3
  • Turns out that there are various methods for doing this, most of which rely on assumptions about w or the data. I think I've derived a really simple way of converting the problem into a k nearest neighbor search. I'll post about it after I've tested it and found out whether it's actually something well known. – user1158559 May 31 '15 at 23:37