Updatable Indices for Efficient, Generalised Top-k Queries [Extended Abstract]

The way that we interact with databases has changed. The ubiquitous textbook example of finding employees with salaries over 60K and ages under 30 no longer reflects a typical use case in modern applications; instead, users are interested in books, movies, music, documents, services, and users that are similar to another object that they have in mind. This sort of similarity search is often implemented by means of a top-k query, wherein each tuple is assigned a score and the tuples with the k highest scores are reported back to the user. The nature of the databases we query has changed as well, growing to Internet-scale, yet our expectation is for instantaneous results. Thus, this needle-in-a-haystack problem requires intelligent algorithms and data structures: naive solutions do not suffice. Furthermore, most repositories of data grow indefinitely as users add more content. This puts a strain on the design of the data structures, because if they do not handle insertions well, they quickly become obsolete. Al-though the literature on top-k queries is rather quite dense, there are still gaps in terms of this modern-day usage, especially in terms of designing indices wit