Notes@HKU by Jax

Ranking

Multidimensional data

Many data types are really tables of objects with several attributes, so each object can be expressed as a point in n-dimensional space.

Attributes can be numerical (ordinal) (age, salary), categorical (color), or binary (gender).

Basic queries

  • Range query: Find all objects in a given range of values for each attribute.
  • Distance query: Find all objects within a given distance d from a reference record.
  • Nearest neighbor query (kNN): Replaces the distance query's d bound with a number k of nearest neighbors to find (ranking)

Top-k queries

Top-k queries

Find the k best objects according to an aggregate function f. Attributes values are normalized to [0, 1] to avoid biasing the aggregate function.

Top-k generalizes kNN: kNN ranks by one attribute d, whereas top-k ranks by an aggregate function f of multiple attributes.

Relational table containing inforation about restaurants with attributes price, quality and location.

An example function can be f: sum(-price, quality, -spd(location, my_hotel)), which ranks restaurants by low price, high quality and close location.

Variants of top-k queries

  • Single table vs. ranked lists: data can be in one table, or sorted lists of each attribute.
  • Centralized vs. distributed: lists may sit on one machine or on different servers, and a merger combines them

Evaluation assumption

Most algorithms assumes f is:

  1. Distributive: f(x,y,z) = f(f(x,y), z), so partial results can be combined to get the final result (e.g. a sum function is distributive)
  2. Monotone: if x >= y then f(x, z) >= f(y, z), so if a record is worse than another in all attributes, it cannot be in the top-k.

Rank aggregation evaluations

Each attribute has its own ranked list, accessed sequentially and/or randomly.

Pros:

  • Works on any subset of attributes
  • Suits distributed data
  • Easy to implement

Cons:

  • Slower than index-based methods
  • Needs sorted inputs

Threshold algorithm (TA)

Consider multiple ranked lists with values attr[j][i] = (r_ji, v_r) where r_ji is the record and v_r is the value of the attribute j for that record.

TA process the ranked lists row by row. To find the best k records for an aggregate function f with n ranked lists:

  1. For row i, compute f(r_ji) for each n lists
  2. Maintain sorted return list topk[1..k]: r of top-k records
  3. Update threshold T=f(attr[1][i], ..., attr[n][i]) *
  4. Stop when f(topk[k]) >= T.

*: By monotonicity, any record not yet seen cannot have f(r) > T.

Consider following attr with k=2 and f: sum:

S1S2S3
c 0.9a 0.9c 0.9
d 0.8b 0.8a 0.9
b 0.6e 0.6b 0.8
e 0.3d 0.4d 0.6
a 0.1c 0.2e 0.5

Compute:

iAccessComputed (new)topkTStop?
1c, a, cf(c) = 2.0, f(a) = 1.9[c, a]0.9+0.9+0.9=2.7No (f(topk[2]) = 1.9 < T)
2d, b, af(d) = 1.8, f(b) = 2.2[b, c]2.5No (f(topk[2]) = 2.0 < T)
3b, e, bf(e) = 1.4[b, c]2.0Yes (f(topk[2]) = 2.0 <= T)

Returned: [b, c] with f(b) = 2.2, f(c) = 2.0.

No random access algorithm (NRA)

NRA also processes the ranked lists row by row, but it never performs random accesses. Since a record's full score is usually unknown, NRA maintains bounds for every record seen so far. To find the best k records for an aggregate function f with n ranked lists:

  1. For row i, read attr[j][i] for each of the n lists (sorted access only)
  2. For each record x seen so far, update the bounds *:
    • lb(x): f(x) with every unseen attribute set to the worst value (0)
    • ub(x): f(x) with every unseen attribute set to the last value seen in that list
  3. Maintain W[1..k]: r, the k records with the largest lb
  4. Stop when min lb(W) >= max ub(x) over all x not in W (an unseen record has ub = f(attr[1][i], ..., attr[n][i])).

*: By monotonicity, the score of x can never exceed ub(x) or fall below lb(x). NRA may stop without knowing the exact score of every record.

Consider following attr with k=2 and f: sum:

S1S2S3
c 0.9a 0.9c 0.9
d 0.8b 0.8a 0.9
b 0.6e 0.6b 0.8
e 0.3d 0.4d 0.6
a 0.1c 0.2e 0.5

Compute (bounds are [lb, ub]):

iAccessBounds (seen records)WStop?
1c, a, cc [1.8, 2.7], a [0.9, 2.7][c, a]No (min lb(W) = 0.9 < 2.7, unseen records have ub = 2.7)
2d, b, ac [1.8, 2.6], a [1.8, 2.6], d [0.8, 2.5], b [0.8, 2.5][c, a]No (1.8 < ub(d) = 2.5)
3b, e, bb 2.2, c [1.8, 2.4], a [1.8, 2.4], d [0.8, 2.2], e [0.6, 2.0][b, c]No (1.8 < ub(a) = 2.4)
4e, d, db 2.2, c [1.8, 2.2], a [1.8, 2.1], d 1.8, e [0.9, 1.5][b, c]No (1.8 < ub(a) = 2.1)
5a, c, eb 2.2, c 2.0, a 1.9, d 1.8, e 1.4[b, c]Yes (min lb(W) = 2.0 >= ub(a) = 1.9)

Returned: [b, c] (ties between lbs broken arbitrarily), with f(b) = 2.2, f(c) = 2.0.

NRA vs. TA

TANRA
Access typesSorted and randomSorted only
Stopping rulek-th best score ≥ Tmin lb in WkW_k ≥ max ub outside WkW_k
ScoresExact for each seen objectBounds, possibly never exact
OverheadCostly random accessesBound storage for all seen objects
Best whenRandom access is cheapRandom access is costly or impossible

Multidimensional indexing evaluations

On this page