LSII: An indexing structure for exact real-time search on microblogs
LSII: An indexing structure for exact real-time search on microblogs
复制标题
DOI：
10.1109/icde.2013.6544849
复制
发表时间：
2013-04
期刊：
影响因子：
--
通讯作者：
Lingkun Wu;Wenqing Lin;Xiaokui Xiao;Yabo Xu
中科院分区：
文献类型：
--
作者：
Lingkun Wu;Wenqing Lin;Xiaokui Xiao;Yabo Xu
由于用户创建新微博的速度太快，导致效率问题，因此为实时搜索建立微博索引是一项挑战。现有方法以查询准确性为代价来解决这个效率问题，因为它们要么（i）从索引中排除很大一部分微博以降低更新成本，要么（ii）主要通过微博的时间戳（而没有充分考虑其与查询的相关性）来对微博进行排名以实现仅附加索引插入。因此，现有方法返回的搜索结果不能满足用户对及时和高质量搜索结果的需求。为了弥补这一不足，我们提出了日志结构的倒排索引（LSII），微博上的精确实时搜索的结构。LSII的核心是一系列大小呈指数级增长的倒排索引，新的微博（i）首先插入到最小的索引中，（ii）随后以批量方式移动到较大的索引中。批量插入机制导致每个新微博的小摊销更新成本，而不会显着降低查询性能。我们提出了一个全面的研究LSII，探索各种设计方案，以取得查询和更新性能之间的良好平衡。此外，我们提出了扩展的LSII，以支持个性化的搜索，并利用多线程的性能提高。大量的实验证明了LSII的效率与实验上的真实的数据。
Indexing microblogs for real-time search is challenging given the efficiency issue caused by the tremendous speed at which new microblogs are created by users. Existing approaches address this efficiency issue at the cost of query accuracy, as they either (i) exclude a significant portion of microblogs from the index to reduce update cost or (ii) rank microblogs mostly by their timestamps (without sufficient consideration of their relevance to the queries) to enable append-only index insertion. As a consequence, the search results returned by the existing approaches do not satisfy the users who demand timely and high-quality search results. To remedy this deficiency, we propose the Log-Structured Inverted Indices (LSII), a structure for exact real-time search on microblogs. The core of LSII is a sequence of inverted indices with exponentially increasing sizes, such that new microblogs are (i) first inserted into the smallest index and (ii) later moved into the larger indices in a batch manner. The batch insertion mechanism leads to a small amortize update cost for each new microblog, without significantly degrading query performance. We present a comprehensive study on LSII, exploring various design options to strike a good balance between query and update performance. In addition, we propose extensions of LSII to support personalized search and to exploit multi-threading for performance improvement. Extensive experiments demonstrate the efficiency of LSII with experiments on real data.