标题：泛化kNN和天际线问题

Abstract

kNN和天际线查询都是多维向量的重要查询方式。

• kNN可以自定义距离函数，对各个维度可以有不同的权重，但是要预定义好的。
• 天际线查询不需要预定义距离函数，对于任意单调的距离函数都可以生效，但是返回的结果集特别大。

本文提了一个叫eclipse的运算符，可以泛化这两类问题。用户可以对各维度定义粗粒度的，定制的权重，还可以控制返回结果的数量。1NN和天际线查询，都是Eclipse的特例。
进一步提供了一个索引算法。

I. Introduction

首先介绍下kNN和skyline查询。我们首先把Query移到原点。

• 首先是kNN，我们用的距离函数2倍的distance+1倍的价格，按各个维度分别算出和原点的距离，再乘以权重。如下表中p1的距离是最近的。如果用一个斜率为-2的直线来表征的话，直线穿过一个点，对应的y轴截距就是距离值。

  
  image.png
• skyline要返回和原点距离最近的一批点。注意，这一批点中，没有任何一个点在所有维度都比另一个点近。如下图，p4在p2和p3的右上，明显远于这两个点，所以不能返回。p1,p2,p3，这三个点，互相判断不出来谁远谁近，因为没有权重，所以全部返回。
  • 进一步注意，对于所有斜率为0 ——> 的直线，所产生的1NN结果，skyline query都可以包括其中。换句话说，只要排列的属性权重一个比一个大就可以了（递增）。
    image.png

由于KNN搜索过于刻板要求提供全部权重，skyline又过于宽泛，因此本文提出eclipse查询。就是斜率既不是无穷大的范围，也不是一个单值，而是一个区间。如下图。

image.png

III. Transformation-based Algorithms

【未完待续】