最近k关键字查询

本文主要介绍一下关键字查询的一种,最近k关键字查询(Top-K Nearest Keyword Search, k-nk)。

问题定义

输入:图$G=(V,E)$,查询$Q=(v,q,k)$是一个三元组
输出:输出$k$个点,$A=${$u_1,\ldots,u_k$},根据$d(v,u_i)$的数值由小到大输出。需满足对于图中任意点$u\in V$,若$u\not\in A$, $d(v,u) \geq d(v,u_k)$。

研究意义

综合考虑了图的结构和关键字,可以有效发现图上的一些模式。

下述例子来自Qiao等人[1]

  1. 在社交网络上,寻找最近的k个朋友一起去郊游。
  2. 可以通过AND和OR操作,进行更复杂的操作(例如,喜欢郊游并且/或者喜欢摄影的最近k个朋友)
  3. 对于一对想买房的夫妻,可能会考虑附近3公里内有医院和学校,并且1公里内有学校的的房子。那么对于他们看上的房子,可以分解成3个k-nk问题来判断房子是否满足条件。

相关工作

相关的工作大致可以分成两类。第一类返回确切的解。第二类返回近似解。个人觉得比较好的有代表性的工作罗列如下,但好的工作不限于如下。

近似算法

SIGMOD2011: Tao[7]2011年的论文。在这篇论文之前knk很多工作都是做在路网或者空间图上的,这篇论文之后开始渐渐的做在一般图上的工作就多了起来。

WWW2012: Bahmani[3]提出了Partitioned Multi-Indexing. 这篇文章提出了利用distance oracles来对距离进行计算。这个算近似距离的算法有点像WSDM 2010[4]上的一篇paper,这一系列的论文有时候会称为oracle,有时候会称为sketch。这一类型的paper有很多,特别推荐大牛Cohen[5]的论文。

VLDB2013: Qiao等人[1]在最后的一个章节,提出了一般图上的k-nk查询。

SIGMOD2015: Jiang等人[2]提出了对于查询关键词频繁与否的优化算法(Forward Search(适用于低频) and Forward Backward Search(适用于高频))。

精确算法

VLDB2013: Qiao等人[1]提出的算法,这个算法主要是解决树上最近k关键字查询问题。

VLDBJ2017: Zhu等人[6]提出的算法,这篇论文没怎么细看过,目标应该是为了减少IO。应该是[1]的一个扩展。


  1. 1.Qiao, Miao, et al. Top-k nearest keyword search on large graphs. Proceedings of the VLDB Endowment 6.10 (2013): 901-912.
  2. 2.Jiang M, Fu A W C, Wong R C W. Exact top-k nearest keyword search in large networks[C]//Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. ACM, 2015: 393-404.
  3. 3.B. Bahmani and A. Goel. Bringing order to social search. In WWW, 2012.
    [5]
  4. 4.Das Sarma A, Gollapudi S, Najork M, et al. A sketch-based distance oracle for web-scale graphs[C]//Proceedings of the third ACM international conference on Web search and data mining. ACM, 2010: 401-410.
  5. 5.Cohen E. All-distances sketches, revisited: HIP estimators for massive graphs analysis[J]. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(9): 2320-2334.
  6. 6.Zhu Q, Cheng H, Huang X. I/O-efficient algorithms for top-k nearest keyword search in massive graphs[J]. The VLDB Journal, 2017, 26(4): 563-583.
  7. 7.Tao Y, Papadopoulos S, Sheng C, et al. Nearest keyword search in XML documents[C]//Proceedings of the 2011 ACM SIGMOD International Conference on Management of data. ACM, 2011: 589-600.