Index for efficient argmax(w.x) query ~ 20d

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!

Topic data-indexing-techniques indexing

Category Data Science

1
answered at

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.

About

Geeks Mental is a community that publishes articles and tutorials about Web, Android, Data Science, new techniques and Linux security.