TL;DR
This paper introduces "k-best suffix arrays," a novel data structure that extends standard suffix arrays by incorporating a second sorting criterion: popularity. This allows for efficient retrieval of the k most popular matches for a given substring, a common need in applications like web search and e-commerce, with lookup times ranging from logarithmic to square root of the corpus size.
What Problem Does This Paper Address?
Imagine you have a massive dictionary of items, each with a "popularity" score (like search query frequency or product sales). You want to find the k most popular matches for a given search term. A standard suffix array is great for finding all occurrences of a substring quickly (sublinear time), but it only sorts lexicographically. This means if you have many matches, you'd still have to sort them by popularity yourself, which can be slow. The paper addresses the challenge of efficiently finding the k most popular matches directly, without a separate sorting step, especially when the number of matches is large (an "embarrassment of riches").
Methods
The core innovation is the "k-best suffix array," which builds upon the concept of standard suffix arrays. A standard suffix array sorts all suffixes of a text lexicographically. The k-best suffix array, however, sorts suffixes based on two criteria: lexicographical order and popularity. This is achieved using a construction inspired by k-d trees. The sorting process alternates between lexicographical and popularity-based splits at different levels of the data structure.
For lookups, the algorithm performs a modified binary search. When encountering a lexicographical split, it behaves like a standard suffix array lookup. However, at popularity splits, it prioritizes searching the more popular half first. If the desired matches aren't found there, it then searches the less popular half. This strategy aims to quickly narrow down the search space to the k most popular results.
Datasets
The paper describes an empirical study using sub-corpora extracted from a 150 MB collection of 8 million queries from Microsoft's live.com logs. These queries were sorted by popularity. The authors also mention using a "random sample" of queries and then replacing them with substrings of random size for another experiment. No new benchmarks were introduced; existing log data was used.
Key Insights and Ideas
- Dual Sorting for Relevance: The fundamental insight is that for many real-world applications, relevance isn't just about exact matches but also about popularity. Combining lexicographical and popularity sorting directly into the index is key.
- "Embarrassment of Riches" Problem: The paper highlights that standard suffix arrays struggle when there are many matches. K-best suffix arrays are specifically designed to handle this scenario efficiently.
- K-d Tree Analogy: The alternating split strategy, similar to k-d trees, is a clever way to partition the search space based on multiple dimensions (lexicographical and popularity).
- Popularity Splits as Shortcuts: When popularity splits effectively separate relevant from irrelevant matches, the search time can be significantly reduced, approaching logarithmic complexity.
Key Results
The empirical study demonstrated that the k-best suffix array lookup time varies from O(log N) to O(sqrt N), where N is the corpus size.
- The worst-case lookup time (when the query string is not in the index) was shown to be O(sqrt N), fitting the theoretical prediction.
- Typical scenarios (simulated by random query samples) showed considerably faster lookup times, closer to the best-case scenario.
- The paper also mentions that k-best suffix arrays have been used in autocompletion applications, with experimental results (shown as triangles) indicating very fast lookup times for this specific use case.
Limitations and Future Work
- Worst-Case Performance: While the average case is good, the worst-case lookup time is O(sqrt N). The paper suggests that in practical applications, popularity splits are effective enough that the typical performance is much closer to O(log N).
- Implementation Complexity: The paper notes that the provided code is "simple to describe" but acknowledges that "more efficient implementations that avoid unnecessary qsorts" exist.
- Future Work: The paper doesn't explicitly detail future work, but the success in autocompletion suggests further exploration in interactive search and recommendation systems would be a natural extension. The theoretical analysis of the complexity based on the effectiveness of popularity splits also opens avenues for more refined theoretical work.
Summary updated