Opportunities for Spatial Database
Research in the Context ofPreference Queries[Keynote Speech]

Kyriakos Mouratidis
Singapore Management University
LocalRec 2023

Introduction• Paradigms to identify options of preference in a multiobjective setting:– Dominance-based: Skyline (and k-skyband)– Ranking by utility: Top-k query (input: preference vector w of dweights; utility of an option defined as the weighted sum of its
attributes)x2

Preference vector w = (0.2, 0.8)

r1 dominates r2
r1

Utility of option r = (x1, x2) defined as:U(r) = 0.2  x1 + 0.8  x2

r2

Top-k: the k options with highest utility

0x1

Skyline and Skyband• Skyline: all opts. thataren’t dominated• Includes top-1  w• k-skyband: all opts.
not dominated byk or more others• Includes top-k  w

x2
r3

r4
r2
r5

r10

r6

r11
r13

r14
r15

r1

r12

r7
r8
r9x1

Traditional top-k query• Top-k query: shortlists
top options from a setof alternatives• E.g. TripAdvisor.com– rate (and browse) hotels
according to price,cleanliness, location,
service, etc.

• A user’s criteria: price,cleanliness andservice, with different
weights

Weights could be captured
by slide-bars:PriceCleanService

Top-k as sweeping the data space• Assume all weights are positive• …and each option attribute is in range [0,1]• Example for d = 2 (showing: option space)x2• Sweeping line normal
1
to vector w
r3
r4• Sweeps from top-cornerr2
r10(1,1) towards origin
r5
r6• Order an option is metr11
 order in ranking!
– E.g. top-2 = { r1, r2 }• At current position:

 option above (below) theline, higher (lower) score than r2

r13

r14
r15

r12(1,1)
r1w

r7r8r9x1

1

Relationship to Convex Hull
• Convex Hull: The smallest convex polytopethat includes a set of points (options)• Fact: The top-1 option forx2
any query vector isr3
on the hull!
r4
r1– [Dantzig63]: LP text

r2

r10

r5

r6

r11
r13

r14
r15

r12

r7
r8
r9x1

Utility order and equivalent half-space• U(r1) = U(r2) a hyper-plane in pref. domain w2• U(r1) > U(r2) a half-space in pref. domain

h1-2U(r1) < U(r2)

U(r1) > U(r2)w1Top-k in High-D?
• Unless the data are very sparse or overly
correlated, top-k is meaningless in more than 56 dimensions!
• As d grows, the highest score across thedataset approaches the lowest score!
• I.e. ranking by score no longer offers
distinguishability  looses its usefulness• Behaviour very similar to nearest neighborquery, known to suffer from the dimensionality
curse8Top-k in High-D?
• IND data
• …of fixed cardinality n = 100K
• …we vary data dimensionality

9mIR problem• Tang, Mouratidis, Han: “On m-Impact Regions
and Standing Top-k Influence Problems”.
SIGMOD’21• m-Impact Regions Problem (mIR): Given anoption set D, a user set W, and a positive
integer m, the mIR problem is to compute themaximal region R in option space, inside whichany (existing or hypothetical) option r is in thetop-k set of at least m users
10

mIR example
Option set: hotels
Attributes (dimensions): Value, ServiceUser set includes 4 users
Option spacem=3→(a) Option set and User set
11

Algorithmic basis for mIR• Let ci be the top-k-th score for user wi in D
• r is in top-k set of wi  Uwi(r) ≥ ci
• …which is a half-space in the pref. space,called the impact half-space of wi• Basic idea:– produce the impact half-space for each user
– partition the pref. space by these half-spaces– report the partitions (cells) included in ≥ m impact
half-spaces– complexity……… O(|W|d)12

Algorithmic basis for mIR• Insert half-spaces one by one into a cell tree
• Early reporting and pruning possible• Still too slow
Early reporting
Early elimination

13

Snapshots of our methodology
Earlyreporting

Earlyelimination

14

Case study• TripAdvisor data (137,563 users and 1,850 hotels)• d = 2, k = 10, m = 0.5 |U|15

Marrying top-k with skyline• Mouratidis, Li, Tang: “Marrying Top-k with Skyline
Queries: Relaxing the Preference Input while
Producing Output of Controllable Size”. SIGMOD’21• Skyline: not personalized, no output-size control• Top-k: whether mined or user-input, w is only anestimate  too rigid ranking• Strong requirements:• Personalized• Output-size specified – (OSS)• Flexible preference specification
16

Previous operators

17

Fixed-region (appr. 1): r-skyband• Consider opts. r1, r2 and a region R in pref. domain• w in R, U(r1) > U(r2) : r1 r-dominates r2

w2• r-skyband: options r-dominated by <k others

Rw118

Fixed-region (appr. 2): Uncertain top-k• Given: region R in pref. space• UTK: report all possible top-k opts. when w  Rw2

Region R

0.25

p1, p2
p1, p6p2, p4

p1, p4
0.05

w1
0.05

Dataset

0.45

UTK output for k = 2(in preference space)Problem definition: ORD & ORU• Input: vector (seed) w, value k, desired output size m• ρ-dominance: a record ρ-dominates another if it has
higher utility  pref. vector within radius ρ from w• ORD: report the options that are ρ-dominated byfewer than k others, for the minimum ρ that producesm records in the output• Stopping radius ρ unknown to the algo. in advance• The user and application are both transparent to ρ
• ORU: report the options that are in top-k result for atleast one pref. vector within distance ρ from w, for theminimum ρ that produces m records in the output
20

Snapshots of our methodology

21Case study• NBA 2018-19 statistics (k = 2, m = 6)
w = (0.49, 0.51)
ORD/ORU report distinct
results from past
approaches (and fromeach other)

ORD/ORU report records
that are particularly strong
for alternative, very similar
preferences to the seed w
22Quantifying Dataset Competitiveness• Mouratidis, Li, Tang: “Quantifying theCompetitiveness of a Dataset in Relation to GeneralPreferences”. VLDBJ, to appear• Change of focus… to the dataset itself• Objective: assess its competitiveness w.r.t. different
possible preferences• We define measures of competitiveness, andrepresent them in the form of a heat-map in the pref.
space23Case study (TA)• TripAdvisor 1,850 hotels• d = 3 (loc/n, room, value)• Pref. space: simplex• Partition into cells• Focus on the fringe of D:– Use r-skyband• Utility-based measure– MaxMink– for-granted utility that anyof the possible top-k
hotels would have for any
preference in the cell

Utility-based heat-map
24

Applications• Market Analysis: hottest cells is where the market’s
strength lies
– i.e., the hotel market caters best for users who
prioritize value over room quality and location.
• Business Development: hottest cells indicate
market saturation– e.g., coldest cells may indicate sweet spots for a new hotel• Identifying outstanding options in the market• MaxMink can speed up top-k computation• First two applications benefit when the distribution (ora sample) of user preferences is known
25Competitiveness measures• Type I (utility-based): how satisfied the different user
types with the products available in D
• Type II (competition-based): how steep thecompetition among alternative products
|RKS|

#DR26

Snapshots of our methodology

27

Conclusion• We have overviewed the topic ofmulticriteria/preference querying and its many
relationships to spatial indexing/querying• We looked deeper into 3 specific examples (problemdefinitions)• Overall, we saw that a skillset typical to SIGSPATIAL
attendees may apply to an exciting, non-spatial
domain28

Thank you!

29