The Library
S3 -TM : scalable streaming short text matching
Tools
Basık, Fuat, Gedik, Buğra, Ferhatosmanoglu, Hakan and Kalender, Mert Emin (2015) S3 -TM : scalable streaming short text matching. The VLDB Journal, 24 (6). pp. 849-866. doi:10.1007/s00778-015-0404-3 ISSN 1066-8888.
|
PDF
WRAP-scalable-streaming-short-text-matching-Ferhatosmanoglu-2015.pdf - Accepted Version - Requires a PDF viewer. Download (3189Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/s00778-015-0404-3
Abstract
Micro-blogging services have become major venues for information creation, as well as channels of information dissemination. Accordingly, monitoring them for relevant information is a critical capability. This is typically achieved by registering content-based subscriptions with the micro-blogging service. Such subscriptions are long-running queries that are evaluated against the stream of posts. Given the popularity and scale of micro-blogging services like Twitter and Weibo, building a scalable infrastructure to evaluate these subscriptions is a challenge. To address this challenge, we present the S 33 -TM system for streaming short text matching. S 33 -TM is organized as a stream processing application, in the form of a data parallel flow graph designed to be run on a data center environment. It takes advantage of the structure of the publications (posts) and subscriptions to perform the matching in a scalable manner, without broadcasting publications or subscriptions to all of the matcher instances. The basic design of S 33 -TM uses a scoped multicast for publications and scoped anycast for subscriptions. To further improve throughput, we introduce publication routing algorithms that aim at minimizing the scope of the multicasts. First set of algorithms we develop are based on partitioning the word co-occurrence frequency graph, with the aim of routing posts that include commonly co-occurring words to a small set of matchers. While effective, these algorithms fell short in balancing the load. To address this, we develop the SALB algorithm, which provides better load balance by modeling the load more accurately using the word-to-post bipartite graph. We also develop a subscription placement algorithm, called LASP, to group together similar subscriptions, in order to minimize the subscription matching cost. Furthermore, to achieve good scalability for increasing number of nodes, we introduce techniques to handle workload skew. Finally, we introduce load shedding techniques for handling unexpected load spikes with small impact on the accuracy. Our experimental results show that S 33 -TM is scalable. Furthermore, the SALB algorithm provides more than 2.5×2.5× throughput compared to the baseline multicast and outperforms the graph partitioning-based approaches.
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Microblogs, Twitter (Firm), Text messages (Cell phone systems) | ||||||
Journal or Publication Title: | The VLDB Journal | ||||||
Publisher: | Springer Berlin Heidelberg | ||||||
ISSN: | 1066-8888 | ||||||
Official Date: | December 2015 | ||||||
Dates: |
|
||||||
Volume: | 24 | ||||||
Number: | 6 | ||||||
Page Range: | pp. 849-866 | ||||||
DOI: | 10.1007/s00778-015-0404-3 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Date of first compliant deposit: | 29 September 2017 | ||||||
Date of first compliant Open Access: | 29 September 2017 | ||||||
Funder: | Türkiye Bilimsel ve Teknolojik Araştırma Kurumu | ||||||
Grant number: | EEEAG#111E217 and EEEAG#112E271 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year