Computing and Information Systems - Theses
Permanent URI for this collection
Search Results
1 - 2 of 2
-
ItemLinking news and tweets( 2016)In recent years, the rise of social media such as Twitter has been changing the way people acquire information. Meanwhile, traditional information sources such as news articles are still irreplaceable. These have led to a new branch of study on understand- ing the relationship between news articles and social media posts and fusing information from these heterogeneous sources. In this study, we focus on techniques for linking news and relevant tweets. Specifically, given a set of news articles and a set of tweets, we aim to find a subset of relevant tweets for each article in the news set. We propose a super- vised linking algorithm that employs multiple features such as time, named entities and event phrases, which outperforms all the baseline methods in our experiments. Since humans can accurately determine whether a tweet is relevant to a news article, we study two types of crowdsourcing algorithms, namely validation algorithms and amendment algorithms. Validation algorithms put a news-tweet pair in the result set only if the pair is validated by the crowd in some way. We propose three validation algorithms, namely Highest, EP and EP+, all of which effectively collect relevant tweets while maintaining a high precision in the experiments. Amendment algorithms first use a machine-based approach to generate an initial set of results, and then improve the result set by asking the crowd informative questions. The amendment algorithms Half , HHalf and LHalf also demonstrate their effectiveness on improving the quality of the result sets in the experi- ments. We extend our study to social network subgraph matching algorithms, which can be used to i) improve the performance of our linking algorithms; ii) analyze and extract information from the news-tweet network or other social network graphs. We propose an efficient GPU algorithm, which significantly outperforms the state-of-the-art CPU al- gorithm in terms of running time in our experiments when the workload is heavy.
-
ItemA bit-vector solver based on word-level propagation( 2016)Reasoning with bit-vectors arises in a variety of applications in verification and cryptography. Michel and Van Hentenryck have proposed an interesting approach to bit-vector constraint propagation on the word level. Most of the operations are propagated in constant time, assuming the bit-vector fits in a machine word. In contrast, bit-vector SMT solvers usually solve bit-vector problems by bit-blasting, that is, mapping the resulting operations to conjunctive normal form clauses, and using SAT technology to solve them. This also means generating intermediate variables which can be an advantage, as these can be searched on and learnt about. Since each approach has advantages it is important to see whether we can benefit from these advantages by using a word-level propagation approach with learning. In this dissertation, we describe an approach to bit-vector solving using word-level propagation with learning. We provide alternative word-level propagators to Michel and Van Hentenryck, and we evaluate the variants of the approach empirically. We also experiment with different approaches to learning and back-jumping in the solver. Based on the insights gained, we propose a portfolio solver using machine learning which can enhance state-of-the-art solvers. We show that, with careful engineering, a word-level propagation based approach can compete with (or complement) bit-blasting.