Space optimizations for total ranking
Douglass R. Cutting, Jan Ole Pedersen · 1997
Efficient ranking algorithms for similarity search use an inverted index to avoid scoring documents that have no overlap with the query. Nonetheless, partial scores must be maintained for a significant proportion of the collection. Previous work has focussed on heuristic partial ranking strategies to reduce the memory and time requirements at the cost of no longer computing the true ranks. We present two novel algorithms that efficiently compute the true total ranking with a fixed space requirement independent of the size of the collection.