undefined | Better HN

0 pointsbenreesman2y ago0 comments

Sure!

So in many, if not most, contemporary Information Retrieval (IR) problems, there is a total document set larger than could be explored on an interactive basis and so the data structures get laid out in such a way that with some probability north of a coin, you’ll find “better” documents in the “front” half. This is hand-waving a lot of detail away, so if you’d like me to go into some detail about multi-stage ranking, and compact posting lists and stuff I’m happy to do that in subsequent comment.

But it’s a useful fiction as a model and the key part is that there’s still “good” stuff in the “back” half: you’d like to consider everything if you had time.

A PID controller (again oversimplifying a bit) is charged with one primary task: given some observed quantity (temperature in a room) and some controlled quantity (how hard to run the AC), maintain the observed quantity as close to a target as possible via manipulating the controlled quantity.

If you hook one of these things up to an IR/search system (web search, friend search, eligible ads, you name it) where the observer quantity is e.g. the p95 or p99.9 latency of the retrieval, and the controlled quantity is how “deep” to go into the candidate set something magical happens: you always do something close to your best even as the macro load on the system varies.

That’s again a pretty oversimplified (to the point of minor technical inaccuracies) TLDR, but I think it makes the important point.

If you’d like more depth feel free to indicate that in a comment and I’ll do my best.

0 comments

nextaccountic2y ago

So basically you're using PID as a metaheuristic to guide an optimization process? (like particle swarm, simulated annealing, genetic algorithms, etc)

Or it's more like, it's being used to fine tune the parameters of another search procedure? And in principle you could use a neural net rather than PID (that would encode a surface that matches the latency vs search depth profile that you want)

edit: just figured out those two are the same thing; the PID is optimizing the search depth for a given target latency

mrfox3212y ago

It can be stated as follows:

The number of documents (denoted as N) to search over consumes resources and increases the overall latency of the search infrastructure. However, the amount of traffic ebbs and flows. Under periods of lower traffic, we likely can increase N to provide good search results without violating latency constraints. Conversely, high traffic periods likely requires lower values of N.

Let's then approximate system strain by p99 (or p99.XXX) latency.

Solution:

Use a PID controller to set N as a function of latency (p99, p99.5, etc.) of the cluster. This leads to the outcome where N reduces when p99 latency starts to spike (resource starvation), and increases when p99 is low.

adm_2y ago

Really interested if you can go into more detail about multi-stage ranking, compact posting lists and stuff.

srean2y ago

Ah thanks, now I have the context.Thanks again for replying.

j / k navigate · click thread line to collapse