Fairest Neighbors: Tradeoffs Between Metric Queries
Magnus Lie Hetland and Halvard Hummel
Highlight
- Unfairness measures can be used to search for tradeoffs between metric query objects
- Such queries work with existing metric index structures, e.g., based on overlap with or containment of balls
- For weighted ordered weighted averages, we can handle more general cases, such as having the query inside a ball
- Combined queries outperform running multiple separate queries to find the tradeoffs
Multifocal Queries
- Produce vector of query–object distances
- Apply some function to produce a combined distance, or remoteness
- Remoteness is compared to radius to determine membership
- Overlap with other regions can be determined, e.g., if the function is increasing and we use lower bounds
Multicriteria Decisions
- We seek fair tradeoffs between distances to the query objects
- Achievable with unfairness measures used in multicriteria decision making
- General and well-behaved examle: (weighted) ordered weighted average
WOWA and Linear Ambits
- Weighted ordered weighted average can be represented as a linear ambit
- A polyhedron of query–object distance vectors (i.e., in pivot space)
- We can efficiently determine intersection with this polyhedron
- For query-in-region: Arbitrarily large improvement over bounds produced by monotonicity alone
Experiments
- Two-object queries with OWA (wts. 1, 3) over LC. Fairest neighbors (k = 1 to 5), avgd. over 100 queries
- Synthetic: 100 000 uniformly random and clustered vectors, with dimensions 2…10. Real-world: The Colors, NASA and Listeria SISAP data sets
- Comparison: Search for each object individually, with sufficient radius to find the tradeoff object
- On average, a speedup of about 2 compared to double query and 4 compared to linear scan