基于层次概念格的分面导航

1、PAGE PAGE 9基于层次概念格的分面导航*何超，1982年生，男，江苏人，博士生。何超1,2，程学旗1，郭嘉丰11中国科学院计算技术研究所，北京，1001902中国科学院研究生院，北京，100190E-mail: hechao摘 要：分面导航是用户基于多维分类目录检索和浏览资源的主要方式之一。通过推荐与当前搜索结果相关的类别，帮助用户理解搜索结果，并有效避免查询结果为空。然而，目前的分面导航难以分析所推荐类别之间的深层语义。本文提出了一种层次概念格作为资源集的本体，它完整并简洁地描述查询结果间的包含关系。在此基础上，我们设计了一系列导航操作帮助用户基于层次概念格进行知识发现。为满足导航操

2、作的实时性，我们提出了格挖掘算法LMiner。它以自顶向下和深度优先方式遍历生成格；通过倒排索引当前已生成的极小节点，进行高效的节点冗余检查和边的增量计算。实验结果表明，LMiner的速度远快于现有算法，而索引却小得多。关键词：分面导航；层次概念格；频繁项集挖掘Using Hierarchical Concept Lattice to Support Faceted Navigation HE Chao, CHENG Xue-Qi, GUO Jia-FengKey Laboratory of Network Science and Technology, Institute of Comput

3、ing Technology, Chinese Academy of Sciences, Beijing 100190.E-mail: hechaoAbstract: Faceted navigation is prevalent for searching and browsing multi-faceted resources。It recommends only the categories whose refining result of current search result is not empty, in order to help users understand what

4、 current search result is related to and avoid the dead end in the process of navigation. However, current approaches for faceted navigation can hardly expose deep relations between the recommended categories. In this paper, a hierarchical concept lattice is proposed which fully and concisely expres

5、ses the set containment relation between all kinds of search results. A series of navigation operations are proposed to help knowledge discovery based on the lattice. To guarantee the real-time property of these operations, a lattice mining algorithm LMiner is proposed. It generates all the nodes in

6、 a top-down and depth-first traversal of the whole lattice. By indexing all the minimal generated nodes in an inverted list, LMiner can accomplish subsumption check and incremental edge construction efficiently. Experimental results demonstrate that LMiner is much faster than current approaches whil

7、e its index size is much less. Keywords: Faceted navigation; hierarchical concept lattice; frequent itemset mining1 引 言电子商务网站和数字图书馆通常采用多维分类树组织资源。对当前查询结果，用户选择新的类别对其细化或泛化。传统方式下，用户需要查看成百上千个类别，且细化结果常为空。分面导航(faceted navigation)只显示与当前查询结果相关的类别，以及它们对应当前查询结果中的资源个数7。伯克利大学的Flamenco项目首次实现了分面导航，利用“性别，出生地，国家，奖项，

8、年份”五个类别供用户查询浏览诺贝尔奖得主。例如，当用户查询“经济学奖”，性别类别中只显示“男性(55)”，因为所有55位获此奖者均为男性。通过这种查询结果分析，分面导航使得用户需要查看的类别数目大大降低，避免浏览过程中出现空结果，故成为主要的多维资源查询和浏览方式。目前的分面导航难以帮助用户发现与查询结果相关的类别之间的深层语义，如不同相关类别的细化结果可能存在的包含或相等关系，以及它们的不同组合对应的细化结果可能相同。另外，用户不清楚哪些查询的结果与当前结果相似（即资源集重叠程度高）。当数据规模庞大时，无法高效地帮助用户分析不同查询对应的资源集之间的关系，如它们的交集对应哪些相关类别，或哪些

9、查询的返回结果同时包含它们。简言之，目前的分面导航无法将不同查询结果之间的关系简洁有效地呈现给用户，并据此进行知识发现。我们提出了一种层次概念格作为资源集的本体，它完整并简洁地表达了查询结果间的包含关系。层次概念格是无环有向图。格中节点和查询结果一一对应，只保存对应查询结果的最细化语义。节点间的边表示它们之间存在极小细分/泛化关系。图1给出了某论文数据库的多维分类目录和每个资源所属类别，其层次概念格如图2所示。我们设计了一系列导航操作帮助用户基于层次概念格进行知识发现。例如，定位操作找出给定查询所对应的格中节点；语义范围操作给出当前查询结果的最细化分类语义和极泛化分类语义；放大和缩小操作基于用

10、户指定比例泛化和细化当前查询结果；相似操作基于用户指定比例查找相似节点；等等。因此，层次概念格是一张包含所有查询结果间关系的地图，导航操作方便用户对其浏览。为满足分面导航的实时性，我们进一步提出了格挖掘算法LMiner以进行格的生成与索引。LMiner采用自顶向下且深度优先方式遍历生成格中所有节点，并通过动态维护每个节点在当前已生成节点中的后继来同步生成边。利用倒排索引当前已生成的极小节点，高效地完成节点冗余检查和边的增量计算。当格生成后，该索引支持高效的格导航算法。最后，我们针对公开数据集进行了性能分析。实验结果表明，LMiner的速度远快于现有算法，而索引却小得多。图 1 论文数据库中多维

11、分类目录及每篇论文对应的类别Fig.1 A paper database2 层次概念格概念格(Concept Lattice) 6被广泛应用于基于对象和属性的本体构建。传统概念格无法处理类别层次关系。我们证明当类别间存在即层次关系时，所有查询结果构成格，称为层次概念格。在多维分类目录中，某类别可以是多个类别的超类或子类。故多维分类目录可表示为偏序集，其中C是所有类别，对类别u, v C，u c v当且仅当u 是v的子类。定义 1 类别集C 不可约 当且仅当u, v C (u v)，u和v互相独立。对任意不可约类别集X和Y，X C Y当且仅当 u Y， v X，满足v c u。图 2 层次概念格

12、(频繁阈值min_sup = 2)Fig.2 Hierarchical Concept Lattice易知C是不可约类别集之间的偏序关系。X C Y表明X对Y细分(或Y对X泛化)。记类别集C对应的不可约类别集为Cr=u : u C v C (v c u)。记资源集为T =: rid是资源标识 X为该资源所属的类别集 X不可约。故数据库可表示为二元组。类别集C的查询结果记为R(C)，易知R(C)= : T u C (X C u)。空类别集对应全体资源，即R( ) = T。定义 2 类别集X 是极泛化的当且仅当X不可约且Y C X，R(Y) R(X)。类别集X是极细化的当且仅当X不可约且Y C X

13、，R(Y) R(X)。因为不同查询得到的结果可能相同，故(查询)类别集和查询结果是多对一的关系。但是，极细化类别集和查询结果是一对一的关系。定理 1 令X 是极细化类别集。对任意不可约类别集Y，若R(X) = R(Y)，则X C Y。证明 假设X C Y不成立。 u Y，必有：(1) u与X中类别两两独立；或 (2) v X，u c v。对情况(1)，R(X) R(X u) = R(X) R(u) R(X) R(Y) = R(X)，推得R(X) = R(X u)。这与X是极细化类别集矛盾，故(1)不成立。对情况(2)，令C是X中所有大于u的类别构成的集合，则Z = X C u是不可约类别集。易

14、知R(C) R(u)。故R(X) = R(X C) C) = R(X C) R(C) R(X C) R(u) = R(Z)，即R(X) R(Z)成立。因为u Y，故R(u) R(Y)。又R(X) = R(Y)，故R(u) R(X)。显然，R(X C) R(X)。故 R(Z) = R(X C u) = R(X C) R(u) R(X) R(X) = R(X)，即R(Z) R(X)成立。因此，R(Z) = R(X)。因为Z C X，这与X是极细化类别集矛盾。综上所述，假设不成立，必有X C Y。性质 1 查询结果和极细化类别集是一一对应的。查询结果对应一个或多个极泛化类别集。性质 2 令X1和X2

15、分别是任意查询结果S1和S2的极细化类别集。则X1 C X2当且仅当S1 S2。某类别集C是频繁的当且仅当 |R(C)| min_sup (其中0 min_sup |T |)，即其查询结果的大小不小于给定阈值。令Q是所有频繁的极细化类别集。根据定理2，偏序集是完全格。令极细化类别集X满足R(X) = T，显然X Q。X和C r分别是该格的最大上界和最小下界，故是完全有界格。定理 2 对任意X1, X2, , Xk Q C r ，存在 Y，Z Q C r ，其分别为X1, X2, , Xk的最小公共上界和最大公共下界。证明 (1) 根据性质2，易知T的极细化类别集是X1, X2, , Xk的公共

16、上界。令Y1, Y2, , Ym为X1, X2, , Xk的所有公共上界。令查询结果S = R(i = 1.m Yi)的极细化类别集为Y。易知Y是频繁的，故Y Q。 i 1, m，S R(Yi)，故Y C Yi。所以Y是X1, X2, , Xk的最小公共上界。(2) 令查询结果S = R(i = 1.k Xi)中资源个数不小于给定阈值且Z是其极细化类别集。则 i 1, k，S R(Xi)。根据性质2，易知Z是X1, X2, , Xk的公共下界。令L是X1, X2, , Xk的任意公共下界，即 i 1, k，L C Xi，故R(L) R(Xi)。因此，R(L) i = 1.k R(Xi) = S

17、。由性质2，L C Z。所以Z是X1, X2, , Xk的最大公共下界。当S 中资源个数小于阈值时，易知C r是X1, X2, , Xk的最大公共下界。综上所述， Z Q C r ，Z为X1, X2, , Xk的最大公共下界。根据定理2，给定多个查询，存在最小的极细化查询，其结果同时包含每个给定查询的结果；也存在最大的极细化查询，其结果同时被每个给定查询的结果包含。给定频繁阈值min_sup = 2，图1中论文数据库对应的层次概念图如图2所示。3 基于层次概念格的分面导航3.1 导航操作层次概念格完整简洁地表达了查询结果间的关系，而用户的浏览过程就是在格中不同节点之间转移。我们提供如下操作帮助

18、用户提高浏览效率：(1) locate(C)：给定查询C，显示相应节点及其极细化类别集；(2) generator(N)：显示当前节点N对应的极泛化类别集；(3) expand(N, )：显示与当前节点N距离不超过的极远祖先节点；(4) refine(N, )：显示与当前节点N距离不超过的极远后代节点；(5) maxsim(N, )：显示与当前节点N有公共后代且与N距离不超过的极大节点(非N的祖先或后代)；(6) join(N 1, N 2, , N k) 显示节点N 1, N 2, ,和N k的最近公共祖先；(7) meet(N 1, N 2, , N k) 显示节点N 1, N 2, ,和

19、N k的最近公共后代。任意给定节点N 1和N 2，其距离为对应查询结果S1和S2的Jaccard距离，即dist(N 1, N 2) = 1 |S1S2|/|S1S2|。该距离满足三角不等式。locate操作帮助用户定位查询对应的节点，其保存的极细化类别集反映了查询结果的分类语义下界，其分类语义的上界由generator操作得到。expand和refine操作可以按比例细化和泛化，maxsim操作可以简化多个交替的细化泛化操作，它们使得用户更易控制细化和泛化的行为和粒度，逐步逼近潜在查询目的。join和meet操作可以用来分析多个历史查询。meet操作帮助用户了解多个查询结果的交集的分类语义，

20、而join操作分析它们同属什么类别。3.2 导航算法preds, succs, expand, refine, maxsim的实现比较直观，locate操作可基于格挖掘过程中生成的索性高效实现，meet可通过locate实现，不再赘述。性质 3 meet(N 1, N 2, , N k) = locate(i = 1.k Xi)，其中Xi是N i的极细化类别集。令N 是当前节点，其极细化类别集为X，其所有前驱节点的极细化类别集分别为P1, P2, , Pk。易知对任意不可约类别集G C X，G是N 的极泛化类别集当且仅当同时满足：(1) i 1, k，Pi C G不成立；(2) 对任意不可约类

21、别集Y C G， i 1, k，使得Pi C Y。因此，N 的所有极泛化类别集可按如下方式求得。令U = u : X是N 的极细化类别集 uC u C X，易知N 的任意极泛化类别集必为U的子集。初始化G = 。依次考察U的大小为|U|1到1的所有子集。令当前子集为C，约简得到其对应的不可约类别集Cr。如果Cr不大于等于任意Pi (i 1, k)，将其放入G；否则，C的任意子集都不再考察(即剪枝)。最后，G 中极大元素为N 的极泛化类别集。join(N 1, N 2, , N k)的实现如下。从格的根节点(对应所有资源T)开始往下走。令当前节点为NJ。若存在NJ的某后继节点NS，其极细化类别集

22、大于等于每个Ni (i 1, k)的极细化类别集，则向下走到NS；否则，NJ即为N 1, N 2, , N k的最小公共上界。4 格挖掘算法L-Miner当数据库较大时，在用户浏览过程中动态生成格的代价太高，如计算当前查询结果的极细化类别集就需要扫描一遍数据库。为满足实时性，需要预先生成格。LMiner采用一棵类别集枚举树以自顶向下且深度优先方式生成格节点，同时进行边的增量计算。4.1 基于类别集枚举树的格增量计算图3描述了对应图1数据库的类别集枚举树生成过程。树节点和格节点一一对应。每个树节点表示为三元组，fci是极细化类别集，supp是其对应资源集的大小，ref_seq是收缩对序列，序列中

23、每个元素为二元组，满足：ref_item可将X的查询结果细化为较小结果trans。根节点N 1的supp为6，即所有资源数目。因为所有类别中只有a, c, f对应所有资源，而a是c的超类，所以N 1的极细化类别集为c, f。其余类别b, d, e, g, h的查询结果分别为1, 3, 4, 5, 2, 4, 5, 6, 2, 4, 5, 6, 1, 3, 5, 6, 1, 2, 3, 4, 5，资源数均小于6，故均为根节点的收缩对。图 3 类别集枚举树Fig.3 An enumeration tree for category sets对当前节点Ni，依次考察其每个收缩对Rj。若任何已生成的树

24、节点的资源集都不等于Rj.trans（即冗余检测 subsumption check），则生成Rj对应的Ni的新孩子节点Nk，其对应资源集为trans。值得注意的是，该枚举树是深度优先生成的，故只有Nk所在的子树均已生成后才会考察其父节点Ni中Rj后的收缩对。Nk的supp为|Rj.trans|。Nk的极细化类别集和可通过考察Ni中Rj后的每个收缩对与Rj的关系得到。图3中树节点生成顺序和其标识符大小一致。N 1的第一个孩子N2对应其第一个收缩对，其trans和后面的收缩对的交分别为4, 5, 4, 5, 1, 3, 5和1, 3, 4, 5。由此可见，d, e, g可将N2细化为更小（且不小

25、于阈值的）资源集，而h无法将其细化为更小。因此，N 2的极细化类别集为类别集N1.fci b h (=c, f, b, h)对应的不可约类别集c, b, h(图中以圆圈标识)。同理，N2的第一个收缩对对应其第一个孩子N3。该收缩对与其后收缩对的交分别为4, 5和5。故N3.fci为N2.fci d e(=c, b, h, d, e)的不可约类别集b, h, e，且N3的收缩对序列为空(因为min_sup = 2)。接下来考察N2的第二个收缩对，它的trans和N2相同，故冗余，不生成新节点。不断执行上述过程直至遍历生成整棵枚举树。根据18，在上述过程中：(1) 收缩对序列的初始顺序可以任意；(

26、2) 若当前考察的收缩对其trans包含或等于其后某收缩对R的trans，则可以删除R（因为它必冗余）。4.2 基于倒排索引的冗余检测和节点后继维护枚举树的节点生成顺序和前序遍历一致，但输出顺序和后序遍历一致。令Q为所有格节点，而G为所有已生成的格节点（注意格节点和树节点一一对应）。我们维护枚举树中当前路径上每个节点N在G中的后继，记为N.succs(G)。根据枚举树的生成过程知，当N输出时，N.succs(G) 即为N在Q中后继。因此，格节点的后继节点在它对应的树节点输出时即完全确定。令枚举树中当前路径为N i0N i1的N ij，记所有已生成节点为G ij。记N (u|X) 为对应查询X

27、u的节点，其中X是节点X的极细化类别集。若X u不频繁，则N (u|X) 为空。节点之间的偏序关系定义为其极细化类别集之间的偏序关系。图4(b)给出了N 7生成后已挖掘格结构的变化情况。可见，除新节点N 7和其父节点N 5外，其余节点的后继不发生变化。性质 4 令N i(j+1) 是N ij的新孩子，对应N ij的收缩对。此时路径上各节点的后继为：(1) k 0, j1，Nik.succs(Gi(j+1) = N ik.succs(G ij)；(2) N i(j+1).succs(Gi(j+1) = maxN (u|X) : X N ij.succs(G ij)；(3) Nij.succs(G

28、i(j+1) = N ij.succs(G ij) N i(j+1).succs(Gi(j+1)。图 4 当前路径上节点为黑色，已输出节点为白色。(b)和(c)分别是生成N 7和N8后的格结构。Fig.4 The nodes in current path are black, while those already outputted are white.冗余检测(subsumption check)可通过如下方式实现。令当前树节点为X，所有已生成的节点为G，X中待检测的收缩对为。是冗余的当且仅当Y X .succs(G)，N (u|Y)非空且其supp等于|S|。例如，当对N8的收缩对进行

29、冗余检测时，只需查验N8此时的后继N4和N6被h细化后能否得到1,3,5。因为h N4.fci，所以N (h|N4)= N4。又N4.supp = 3，由定理5，该收缩对是冗余的。综上所述，待解的关键操作是：给定节点X和类别u，确定N (u|X)。令M是格中所有极小节点（即无后代），X为X的极细化类别集。易知N (u|X)非空仅当Y M，Xu v : YC v，其中Y是Y的极细化类别集。若上述Y 存在，从它出发，沿着格每次往上走一步，必遇到节点N (u|X)。令当前所在位置为节点Z。依次检验Z的每个前驱节点P直至满足：Xu v : PC v，P是P的极细化类别集。若存在，则从Z走到P；否则，Z

30、即为N (u|X)。因此，我们只需用倒排表索引M：Y M， v v : YC v（Y是Y的极细化类别集），将Y 的标识符添加到倒排表里v的列表中。表1 数据集特征Tab.1 Dataset Characteristics数据集名称总资源个数总类别个数平均类别数 最多类别数chess3,196763737connect67,5571304343mushroom8,1241192323pumsb49,046211374745 实验分析本节通过实验分析我们提出的格挖掘算法LMiner的运行速度和索引大小。运行环境为Lenovo启天M7000，双核2.93GHz CPU，2GB内存，Ubuntu 9.

31、04操作系统。代码用C+编写。我们采用UCI KDD Archive /中的公开数据集chess, connect, mushroom和pumsb，其中每条记录对应一个资源，每个项集对应一个类别。频繁项集挖掘算法中广泛采用这些数据集进行性能分析。表1列举了每个数据集的总资源个数、总类别个数、每个资源对应的平均类别数和最多类别数。尽管大量的频繁闭项集挖掘可用来计算格节点 11, 16 15, 18，但只有CHARM-L 18同时高效地计算边。因此，对比算法选择CHARM-L。以下各图的min_sup指给定阈值占所有资源数的比例。4.1 索引大小LMiner用倒排表索引目前已生成的所有极小节点的极

32、细化类别集，而CHARM-L用倒排表索引所有已生成的节点极细化类别集。因此，二者的索引大小之比可估计为格中极小节点数目除以所有节点数目。图5表明LMiner的索引远小于CHARM-L的索引。例如，在chess中，当min_sup为60%时，极小节点数为3323，而所有节点数为98393，故LMiner的索引大小约占CHARM-L的索引大小的3.4% (3323/98393)。在connect (min_sup = 65%)、mushroom (min_sup = 1%)和pumsb (min_sup = 65%)中，该比例分别为3.2% (1587/49705)、13.1% (6768/516

33、40)和3.4% (18182/496070)。图 5 表1中数据集在不同min_sup下的格中节点数(#FCI)和极小节点数(#MFI)。Fig.5 The number of all the nodes and all the minimal nodes in the lattices.4.2 格挖掘速度LMiner和CHARM-L的节点生成方式是一致的，即对同样的收缩对排序方式，所有节点的生成顺序相同。它们的主要区别在于冗余检测和边增量生成采用了不同的数据结构和算法。我们考察了三种收缩对排序方式，表示按其细化类别的标识符大小排序，表示按其细化结果的大小升序排序，表示按其细化结果的大小降序

34、排序。对于每个格，我们测试了LMiner和CHARM-L在这三种序下的挖掘时间，结果如图6所示。图 6 表1中数据集在不同min_sup下的格挖掘速度。Fig.6 The time of mining the lattices corresponding to different min_sup values in each dataset.可以看出：(1) LMiner对序的变化不敏感，而CHARM-L在序下的速度明显慢于其它序；(2) LMiner在任意序下的速度均快于或接近于CHARM-L在特定序下达到的最快速度，且随着格的增加，前者远快于后者；(3) 随着格大小增加(即min_sup减

35、小)，LMiner的挖掘时间缓慢增长，而CHARM-L在各种序下均快速增长。图 7 考察每个收缩对时需访问的平均节点数。Fig.7 The average number of accessed nodes in examining an shrinking pair.图7描述了序下LMiner和CHARM-L在考察每个收缩对时所需访问的平均节点数。在chess中，随着格节点数从5084 增加到98393，LMiner所需访问的平均节点数从13缓慢增加至21，而CHAMR-L则从58快速增加到257。在connect中，随着格节点数从8253增加到49705，LMiner所需访问的平均节点数从1

36、4缓慢增加至19，而CHAMR-L则从159快速增加到659。在mushroom中，随着格节点数从4885增加到51640，LMiner所需访问的平均节点数从13缓慢增加至15，而CHAMR-L则从31快速增加到120。在pumsb中，随着格节点数从8510增加到496070，LMiner所需访问的平均节点数从9缓慢增加至26，而CHAMR-L则从47快速增加到752。因此，LMiner随着格的增大具有良好的可扩展性。6 相关工作分面导航在工业界和学术界都得到了广泛应用，如Flamenco 7、SIMILE ()和Haystack ()。目前的研究主要集中两方面。第一，推荐给用户更有针对性的动

37、态目录。早期的动态目录显示所有对应非空细分结果的类别，导致类别数过多。文献12 在生成动态目录前会向用户提问，根据用户的回答推荐类别。文献8基于个性化推荐类别。文献1, 5, 17 将分面导航和联机分析处理相结合。文献14自动给出对应当前搜索结果的最小长度类别集，从而提高浏览效率。第二，多维分类目录的自动生成。类别之间的层次关系可以有效减少用户的浏览代价。文献3, 4分别利用监督和无监督学习的方法从文本数据库中提取多维分类目录。文献9采用无监督学习方法自动构建多维分类目录来组织用户提供的关键字。其它的相关研究包括，文献10, 13利用分面导航帮助用户浏览半结构化的RDF数据；文献2提出一种能适

38、应不同屏幕大小的分面导航方式。7 结论本文提出了一种新的分面导航方式实现搜索结果理解。其主要贡献包括：(1) 提出了描述所有查询和查询结果之间关系的本体，层次概念格。(2) 提出了基于层次概念格的导航操作，用以知识发现。(3) 提出了格挖掘算法LMiner，并基于公开数据集进行了广泛深入的性能分析。进一步的工作包括原型系统实现，个人信息或行业网站的资源管理，等。参 考 文 献O. Ben-Yitzhak, et al, “Beyond basic faceted search,” Proc. Intl Conf. Web Search and Web Data Mining (WSDM 08)

39、, pp. 33-44, 2008. R. Dachselt et al. “FacetZoom: a continuous multi-scale widget for navigating hierarchical metadata,” Proc. 26th SIGCHI Conf. Human Factors in Computing Systems (SIGCHI 08), pp. 1353-1356, 2008. W. Dakka, P. Ipeirotis, and K. Wood, “Automatic construction of multifaceted browsing

40、interfaces,” Proc. 14th Intl Conf. Information and Knowledge Management (CIKM 05), pp. 768-775, 2005. W. Dakka and P.G. Ipeirotis, “Automatic Extraction of Useful Facet Hierarchies from Text Databases,” Proc. Intl Conf. Data Engineering (ICDE 08), pp. 466-475, 2008. D. Dash, et al, “Dynamic faceted

41、search for discovery-driven analysis,” Proc. 17th Intl Conf. Information and Knowledge Management (CIKM 08), pp. 3-12, 2008.B. Ganter and R. Wille, Formal Concept Analysis: Mathematical Foundations, Springer, Heidelberg, 1999.M. Hearst, “Clustering versus Faceted Categories for Information Explorati

42、on,” Commun. of the ACM, vol. 49, no. 4, pp. 59-61, 2006.J. Koren, Y. Zhang and X. Liu, “Personalized interactive faceted search,” Proc. 17th Intl Conf. World Wide Web (WWW 08), pp. 477-486, 2008. X. Ling, et al, “Mining multi-faceted overviews of arbitrary topics in a text collection,” Proc. 14th ACM SIGKDD Intl Conf. Knowledge Dis-covery and Data Mining (KDD 08), pp. 497-505, 2008. E. Oren, R. Delbru and S. Decker, “Extending faceted navigation