PaperlayerView exact revision on arXiv

Source-linked AI summary

Diversifying Top-K Results

Lu Qin, Jeffrey Xu Yu, Lijun Chang

arXiv:1208.0076v1cs.DB

TL;DR

Top-k search can return redundant results, and many existing diversification methods assume rankings are known in advance or are tailored to particular domains. This paper adds diversity-aware search and stopping functions to existing early-stopping top-k frameworks, with div-cut reported to find optimal results within seconds for k as large as 2,000.

  • Problem

    Top-k results can be redundant, while existing diversified-search methods often require rankings in advance or target specific domains.

    Source: §1 · p. 1

  • Method

    The framework extends early-stopping top-k algorithms with sufficient(), necessary(), and div-search-current(), and proposes div-astar, div-dp, and div-cut.

    Source: §1 · pp. 1–2

  • Results

    div-cut finds optimal diversified top-k results within seconds for k as large as 2,000.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Existing incremental and bounding top-k algorithms can be extended for diversified search while retaining early stopping.

    Source: §1 · p. 1

    The framework assumes that similarity between any two results can be decided, for example using a user-defined threshold.

    Source: §2 · p. 2

Abstract

from arXiv · show

Top-k query processing finds a list of k results that have largest scores w.r.t the user given query, with the assumption that all the k results are independent to each other. In practice, some of the top-k results returned can be very similar to each other. As a result some of the top-k results returned are redundant. In the literature, diversified top-k search has been studied to return k results that take both score and diversity into consideration. Most existing solutions on diversified top-k search assume that scores of all the search results are given, and some works solve the diversity problem on a specific problem and can hardly be extended to general cases. In this paper, we study the diversified top-k search problem. We define a general diversified top-k search problem that only considers the similarity of the search results themselves. We propose a framework, such that most existing solutions for top-k query processing can be extended easily to handle diversified top-k search, by simply applying three new functions, a sufficient stop condition sufficient(), a necessary stop condition necessary(), and an algorithm for diversified top-k search on the current set of generated results, div-search-current(). We propose three new algorithms, namely, div-astar, div-dp, and div-cut to solve the div-search-current() problem. div-astar is an A* based algorithm, div-dp is an algorithm that decomposes the results into components which are searched using div-astar independently and combined using dynamic programming. div-cut further decomposes the current set of generated results using cut points and combines the results using sophisticated operations. We conducted extensive performance studies using two real datasets, enwiki and reuters. Our div-cut algorithm finds the optimal solution for diversified top-k search problem in seconds even for k as large as 2,000.

1. INTRODUCTION

Top-k results can be redundant when similar items are returned, while existing diversified-search approaches often require all result rankings in advance or are specialized to particular domains. The paper presents a general framework that adds diversity-aware search and stopping functions to existing early-stopping top-k methods.

1. INTRODUCTION

  • Existing diversified-search methods often assume all result rankings are already available or address only specialized domains.These constraints motivate a general approach to diversified top-k search.Source: §1 · p. 1
  • The framework extends incremental and bounding top-k algorithms with sufficient(), necessary(), and div-search-current() functions.The functions support early stopping and search over the currently generated results.Source: §1 · p. 1
  • div-astar, div-dp, and div-cut solve the current-result-set search problem through A* search, component decomposition with dynamic programming, and cut-point decomposition.div-astar can be slow on large graphs; div-dp searches connected components independently, while div-cut further decomposes components.Source: §1 · p. 2
  • div-cut finds optimal diversified top-k results within seconds for k as large as 2,000.Source: §1 · p. 2

2. PROBLEM DEFINITION

The paper defines diversified top-k results as a score-maximizing subset of at most k results with no similar pair. Its diversity graph represents results as nodes and similarities as edges.

2. PROBLEM DEFINITION

  • A top-k result set contains k items whose scores are at least those of items outside the set.Source: §2 · p. 2
  • Two results are similar when their user-defined similarity exceeds threshold τ, with 0 < τ ≤ 1.Source: §2 · p. 2
  • Diversified top-k results contain at most k mutually dissimilar items and maximize their total score.The set may contain fewer than k results.Source: §2 · p. 2
  • The diversity graph represents each result as a node and connects two nodes exactly when their results are similar.Source: §2 · p. 2
  • Equivalently, the solution is a maximum-score independent set of at most k graph nodes.An independent set contains no adjacent nodes.Source: §2 · p. 2
  • For the sample graph, the optimal selection changes from v1 and v2 with score 18 at k=2 to v3, v4, and v5 with score 20 at k=3.Source: §2 · p. 2

3. TOP-K SEARCH FRAMEWORKS

General top-k algorithms commonly use incremental or bounding frameworks. They differ in result order and the condition used to stop searching.

3. TOP-K SEARCH FRAMEWORKS

  • Top-k search algorithms commonly fall into incremental and bounding frameworks.Source: §3 · p. 3
  • Incremental search generates results in non-increasing score order and stops after generating k results.It uses incremental-next() to produce the next highest-scoring result.Source: §3 · p. 3
  • Bounding search may generate results out of score order and stops when the current kth-largest score reaches the upper bound for unseen results.The bound is updated as results are generated.Source: §3 · p. 3

4. DIVERSIFIED TOP-K SEARCH

The framework extends incremental and bounding top-k search with stopping conditions and a search over the current result set. Three algorithms solve that current-set search, using A* and graph decompositions to find optimal diversified results.

4. DIVERSIFIED TOP-K SEARCH

  • The framework replaces the original stopping rules with sufficient and necessary conditions and invokes div-search-current() to search generated results for diversified top-k results.The necessary condition limits costly current-set searches; the original rules cannot be applied directly to diversified search.Source: §4 · p. 3
  • best(S) upper-bounds the optimal score by considering current diversified solutions and an allowance for unseen results based on their score upper bound u.The allowance is (k − i) × u for a current solution of size i; u is the last generated result’s score for incremental search and the unseen-results bound for bounding search.Source: §4 · pp. 3–4
  • div-search can stop only if the last generated result is empty, or the stated set-size threshold is met and the kth-largest score in S is at least u.The size threshold accounts for how many additional nodes may be needed to form a size-k solution from the last searched set S′.Source: §4 · p. 4
  • Finding diversified top-k results on the current set is NP-hard, and the simple greedy method can have arbitrarily poor quality without a constant-factor approximation guarantee.For the illustrated case, the greedy score is 199 versus 9,900 for the optimum.Source: §4 · p. 4
  • div-astar searches the whole result space with A* bounds, while div-dp decomposes connected components and combines their solutions using dynamic programming.div-cut further splits components at cut points, searches subgraphs under up to four conditions, and combines results using two operations.Source: §4 · p. 4

5. AN A∗BASED APPROACH

div-astar uses A* search over partial diversified solutions, prioritizing candidates by an estimated score upper bound. It reuses search state to find optimal solutions for multiple result-set sizes.

5. AN A∗BASED APPROACH

  • div-astar searches partial solutions in a max-heap ranked by estimated upper bound, returning the optimal solution for every size from 1 to k.Each heap entry stores a partial solution, its last processed position, its score, and its bound.Source: §5 · p. 5
  • astar-bound estimates an expansion ceiling by adding high-scoring eligible nodes while excluding nodes already selected or adjacent to selected nodes.The bound need not select the highest-scoring nodes if those nodes are adjacent to each other, so it remains an upper bound.Source: §5 · p. 5
  • Each expansion adds a later, nonadjacent node, updates its bound, and uses the resulting partial solution to update the best score for its size.The search stops when the heap is empty or its largest bound is no greater than the best score found so far.Source: §5 · p. 5
  • Searching k′ in decreasing order reuses heap entries for k′−1 after recalculating their bounds, avoiding reconstruction of the heap.The paper states that partial solutions in the heap can be reused when calculating the optimal solution for the next smaller size.Source: §5 · p. 5
  • In the example, div-astar finds score 20 for k=3 and score 18 for k=2, reusing the heap between searches.For k=2, the heap bounds are updated before the search continues.Source: §5 · p. 6

6. A DP BASED APPROACH

div-dp reduces the graph searched by div-astar by processing disconnected components separately and combining their results. It uses dynamic programming for combinations across components and selects the better result at each size when comparing results from the same subgraph.

6. A DP BASED APPROACH

  • To reduce div-astar’s exponentially growing search space, div-dp splits the diversity graph into disconnected components, searches each with div-astar, then combines results.The results from the components can be combined in arbitrary order using ⊕.Source: §6 · pp. 6–7
  • For disjoint subgraphs, ⊕ uses dynamic programming over size allocations to keep the highest-scoring feasible combination, running in O(k^2).For each total size, it considers how many nodes to select from each subgraph.Source: §6 · p. 6
  • The ⊕ operator is associative and commutative, so component results may be combined in any order.The overall approach uses these properties to combine each component’s results.Source: §6 · pp. 6–7
  • For results from the same subgraph, ⊗ keeps the higher-scoring solution at each size and runs in O(k).The operator compares the two candidates separately for each size.Source: §6 · p. 6
  • In the example with k=5, allocating 2 nodes to G1 and 3 to G2 scores 40, versus 38 for a 3-and-2 allocation.The 2-and-3 allocation is selected as the best solution in the example.Source: §6 · p. 7

7. A CUT POINT BASED APPROACH

Div-cut uses cut points to decompose the diversity graph, search subgraphs separately, and combine their results. Its cptree search handles each entry-graph at most four times under different inclusion assumptions.

7. A CUT POINT BASED APPROACH

  • At most four div-astar searches per entry-graph, under different cut-point inclusion assumptions, are combined using ⊕ and ⊗ operations.This lets loosely connected subgraphs be considered separately.Source: §7 · p. 7
  • Each cptree node represents a cut point and stores its entry-graph, left-graph, subnodes, and results for solutions that exclude or include that cut point.Search computes these two results bottom-up.Source: §7 · pp. 7–8
  • Div-cut first separates disconnected components and compresses each graph, then uses div-astar directly without cut points or cptree search when cut points exist.The resulting component solutions are combined with ⊕.Source: §7 · p. 7
  • A node can be removed without changing the optimal solution when an adjacent node scores at least as highly and covers its neighbors and itself.The proof replaces the removed node with the qualifying adjacent node without reducing score or breaking feasibility.Source: §7 · p. 7
  • When a cut point is included, its adjacent graph nodes are removed before combining feasible subgraph results; the two inclusion states are joined with ⊗.The algorithm combines results from different graph components with ⊕.Source: §7 · p. 8
  • The cptree is built recursively from cut points, choosing a root that minimizes the largest remaining component and grouping other components into left-graphs or subtrees.Cut points are computed with Tarjan’s algorithm in time linear in graph size.Source: §7 · p. 8

8. PERFORMANCE STUDIES

The experiments compare div-astar, div-dp, and div-cut on enwiki and Reuters while varying k, similarity threshold τ, and keyword frequency. Across demanding settings, div-cut handles cases where div-dp or div-astar cannot produce results and often uses less time and memory.

8. PERFORMANCE STUDIES

  • The tests use enwiki’s 11,930,681 articles and Reuters’ 21,578 news documents, recording total search time and peak memory while varying k, τ, and kfreq.Enwiki uses threshold-algorithm aggregation for multi-keyword queries; Reuters tests single-keyword queries scanned incrementally.Source: §8 · pp. 9–10
  • At k = 2,000 on enwiki, div-dp cannot generate a result, while div-cut finds the optimal solution within 15 seconds using less than 200KB memory.The diversity graph’s largest component grows with k, but cut points still decompose it into smaller subgraphs.Source: §8 · p. 10, Figure 13 · p. 10
  • At τ = 0.4 on enwiki, div-dp cannot generate a result, while div-cut finds the optimal solution within 15 seconds using less than 1MB memory.At this low threshold, many results are similar and the diversity graph’s largest component is large.Source: §8 · p. 10
  • For large k on enwiki, div-dp is more than 2 times slower and uses 10 times more memory than div-cut; at kfreq = 2, div-cut finishes in less than 10 seconds using less than 500KB.When varying kfreq, neither processing time nor memory shows an obvious trend to increase or decrease.Source: §8 · pp. 10–11, Figure 15 · p. 11
  • On Reuters, div-cut and div-dp finish in less than 0.1 seconds using less than 1KB at k = 120, when div-astar cannot generate a result.For large k, div-cut and div-dp perform almost equally below k = 900; at k = 2,000, the passage reports a comparison between div-dp and div-dp, so no winner is inferred.Source: §8 · p. 11, Figure 16 · p. 11
  • At τ = 0.4 on Reuters, div-dp takes more than 500 seconds and 500MB, while div-cut finds the optimal solution in less than 5 seconds using less than 200KB.As τ decreases, div-dp’s time and memory rise sharply while div-cut remains stable.Source: §8 · p. 11, Figure 17 · p. 11
  • On Reuters while varying kfreq, div-cut is faster and uses less memory than div-dp in all cases; div-astar is much slower and uses much more memory than both.The gap between div-dp and div-cut for large k is smaller than on enwiki, which the authors relate to the datasets’ different sizes and similarity probabilities.Source: §8 · p. 11, Figure 18 · p. 11

9. RELATED WORK

Related work spans traditional top-k query methods, diversity-aware ranking, and maximum weight independent set. The paper distinguishes its size-constrained problem and incrementally generated diversity graph from prior exact independent-set approaches.

9. RELATED WORK

  • Traditional top-k methods either generate results one by one through Lawler’s procedure or use heuristic generation with an upper bound to stop early, including Fagin et al.’s approach.The first category includes applications to top-k Steiner trees, communities, and graph r-cliques.Source: §9 · pp. 11–12
  • Diversified top-k work combines relevance and redundancy in ranking, often by reranking a top-l list greedily; Angel and Koudas instead couple a one-step method with the threshold algorithm [9].Other work studies varied settings, including diversified document monitoring, prestige nodes, and query recommendation.Source: §9 · p. 12
  • The problem can be viewed as a size-k-constrained maximum weight independent set, which is NP-hard; cited exact approaches do not impose that size constraint or use a fully materialized diversity graph.Source: §9 · p. 12

10. CONCLUSION

The paper formalizes diversified top-k search using similarity among results and proposes a framework for extending existing top-k approaches with early stopping. It reports three algorithms for searching the current generated result set and performance studies of those algorithms.

10. CONCLUSION

  • The paper formally defines diversified top-k search by considering the similarity of the search results themselves.Source: §10 · p. 12
  • The framework extends most existing early-stop top-k query-processing solutions using sufficient(), necessary(), and div-search-current().Source: §10 · p. 12
  • The paper gives three algorithms for div-search-current() and reports extensive performance studies of its algorithms.Source: §10 · p. 12
Loading 1208.0076v1…