Theses supervised by Prof. Dr. Özgür Ulusoy
16 theses · İhsan Doğramacı Bilkent University
Crowd: Ajan tabanlı sosyal ağ simülasyonuna yönelik bir çerçeve ve uygulamaları
To observe how individual behaviors shape the actions of a broader community, agent-based modeling and simulation (ABMS) has been widely adopted by researchers in social sciences, economics, and epidemiology. While simulations can be executed on general-purpose ABMS frameworks, these tools are not specifically designed for social networks and, therefore, provide limited features, increasing the effort required for complex simulations. In this thesis, we first introduce Crowd, a social network simulator that adopts the agent-based modeling methodology to model real-world phenomena within a network environment. Designed to facilitate easy and quick modeling, Crowd supports simulation setup through YAML configuration and enables further customization through user-defined methods. Other features of Crowd include no-code simulations for diffusion tasks, interactive visualizations, data aggregation, and chart drawing facilities. Designed in Python, Crowd also supports generative agents that rely on LLMs for agents' decisions and connects easily with Python's libraries for data analysis and machine learning. Secondly, we present three case studies to illustrate the application of the framework, including generative agents in epidemics, influence maximization, and networked trust games. Finally, we design and implement a simulation that combines generative agents with social networks to analyze the effects of agents' personalities and social connections in the context of building energy modeling.
Orman yangınlarını algılamak için sıs destekli kablosuz sensör ağlar
Fog computing is a new paradigm that aims to extend the concept of cloud com- puting to the edge of the network, providing the end users network with extra storage and processing power. One big contribution of Fog computing is in the context of Wireless Sensor Networks (WSNs). WSNs consist of cheap, battery powered and simple processing devices that make it fall short in handling rel- atively complex processes.Therefore, applying fog computing to WSNs will fill the gap between the cloud and the network and by that, it will enable computa- tionally extensive operations which were earlier possible only at the cloud side. In our work, we exploit the processing power provided by the Fog to minimize the power consumption of WSNs for forest fire detection through the use of data mining techniques. The Fog layer uses the data generated by the network such as temperature, humidity, rain, etc., to train a model that predicts the proba- bility of forest fires. Next, the Fog layer uses this model to predict the mode of operation of the network based on the current condition of the environment. While a high predicted probability of forest fire results in an increased activity of the WSN, a low fire probability results in a reduced network activity. As a result, our proposed model optimizes the energy consumption within the WSN and improves the detection time of forest fires.
Mobil veri kümelerini birleştirmeye doğru
With the proliferation of smart phones integrated with positioning systems and the increasing penetration of Internet-of-Things (IoT) in our daily lives, mobility data has become widely available. A vast variety of mobile services and applications either have a location-based context or produce spatio-temporal records as a byproduct. These records contain information about both the entities that produce them, as well as the environment they were produced in. Availability of such data supports smart services in areas including healthcare, computational social sciences and location-based marketing. We postulate that the spatio-temporal usage records belonging to the same real-world entity can be matched across records from different location-enhanced services. This is a fundamental problem in many applications such as linking user identities for security, understanding privacy limitations of location based services, or producing a unified dataset from multiple sources for urban planning and traffic management. Such integrated datasets are also essential for service providers to optimise their services and improve business intelligence. As such, in this work, we explore scalable solutions to link entities across two mobility datasets, using only their spatio-temporal information to pave to road towards unifying mobility datasets. The first approach is rule-based linkage, based on the concept of k-l diversity --- that we developed to capture both spatial and temporal aspects of the linkage. This model is realized by developing a scalable linking algorithm called ST-Link, which makes use of effective spatial and temporal filtering mechanisms that significantly reduce the search space for matching users. Furthermore, ST-Link utilizes sequential scan procedures to avoid random disk access and thus scales to large datasets. The second approach is similarity based linkage that proposes a mobility based representation and similarity computation for entities. An efficient matching process is then developed to identify the final linked pairs, with an automated mechanism to decide when to stop the linkage. We scale the process with a locality-sensitive hashing (LSH) based approach that significantly reduces candidate pairs for matching. To realize the effectiveness and efficiency of our techniques in practice, we introduce an algorithm called SLIM. We evaluated our work with respect to accuracy and performance using several datasets. Experiments show that both ST-Link and SLIM are effective in practice for performing spatio-temporal linkage and can scale to large datasets. Moreover, the LSH-based scalability brings two to four orders of magnitude speedup.
İlişkisel veri tabanlarında derin akıllı arayüzler üzerine
Relational databases is one of the most popular and broadly utilized infrastructures to store data in a structured fashion. In order to retrieve data, users have to phrase their information need in Structured Query Language (SQL). SQL is a powerfully expressive and flexible language, yet one has to know the schema underlying the database on which the query is issued and to be familiar with SQL syntax, which is not trivial for casual users. To this end, we propose two different strategies to provide more intelligent user interfaces to relational databases by utilizing deep learning techniques. As the fi rst study, we propose a solution for keyword mapping in Natural Language Interfaces to Databases (NLIDB), which aims to translate Natural Language Queries (NLQs) to SQL. We defi ne the keyword mapping problem as a sequence tagging problem, and propose a novel deep learning based supervised approach that utilizes part-of-speech (POS) tags of NLQs. Our proposed approach, called DBTagger (DataBase Tagger), is an end-to-end and schema independent solution. Query recommendation paradigm, a well-known strategy broadly utilized in Web search engines, is helpful to suggest queries of expert users to the casual users to help them with their information need. As the second study, we propose Conquer, a CONtextual QUEry Recommendation algorithm on relational databases exploiting deep learning. First, we train local embeddings of a database using Graph Convolutional Networks to extract distributed representations of the tuples in latent space. We represent SQL queries with a semantic vector by averaging the embeddings of the tuples returned as a result of the query. We employ cosine similarity over the final representations of the queries to generate recommendations, as a Witness-Based approach. Our results show that in classi cation accuracy of database rows as an indicator for embedding quality, Conquer outperforms state-of-the-art techniques.
Effective and explainable mechanisms for natural language interface in databases
Yapılandırılmış Sorgu Dili (SQL) İlişkisel Veritabanı Yönetim Sistemlerinde yapısal şekilde depolanan veriye erişmek ve görüntülemek için sıkça kullanılan bir araçtır, ancak SQL'in temelinde var olan karmaşıklıklar, sorgularını doğal dil sorgusu olarak ifade edebilen sıradan kullanıcılar için engeller oluşturmaktadır. Biz bu engelleri aşmak için iki farklı çözüm öneriyoruz; açıklanabilir yapay zeka arayüzüne sahip bir Veritabanına Doğal Dil Arayüzü (NLIDB) boru hattı ve anlamsal arama stratejisi. İlk çözüm verilen doğal dil sorgusu SQL'e çevirmek için bir anahtar kelime eşleyici ile beraber SQL çevirme algoritmaları kullanan bir NLIDB boru hattı sunmaktadır. Önerilen boru hattı kullanıcıya açıklanabilir yapay zeka arayüzü ile sunulmakta, böylece kullanıcı, oluşturulan sorguyu anlamlandırabilmektedir. Yaklaşımımız iki son teknoloji sistemle karşılaştırılmıştır; NALIR+ ve Pipeline+. Yaklaşımımız imdb, scholar ve yelp veri kümelerinde sırasıyla tek tablo içeren SELECT-JOIN sorguları için \%88.9, \%100 ve \%60.0 ve çoklu tablo içeren SELECT-JOIN sorguları için \%68.6, \%87.0 and \%83.6 çeviri doğruluğuna erişerek NALIR+'yı geride bırakmaktadır. Yaklaşımımız imdb ve scholar veri kümesinde Pipeline+'dan daha iyi fakat Pipeline+ yelp veri kümesinde biraz daha iyi bir performans göstermektedir. İkinci çözüm bilgi çekme tabanlı yöntemler kullarak verilen sorgu için alakalı olan veritabanı satırlarını çeken bir anlamsal arama yaklaşımı önermektedir. Önerilen yaklaşım, her bir satır ve değerin düğümlerle, bu satır ve değerler arasındaki ilişkinin de kenarlarla temsil edildiği bir çizge kullanmaktadır. Sorgu ve veritabanı satırları Çizge Evrişimsel Ağlar kullanılarak vektör temsillerine dönüştürülmektedir. Bu vektör temsilleri üzerinde bir benzerlik hesaplaması gerçekleştirilmekte ve veritabanı satırları sorgu ile alakalarına göre sıralanmaktadır. Bu benzerlik hesaplaması için kosinüs ben-zerliği kullanılmıştır. Yaklaşımımız Spider veri kümesinden college şeması ile test edilmiştir ve \%42.8 ilk-5 doğruluğu elde edilmiştir.
Çevrimiçi sosyal ağlarda yanlış bilgi yayılımının modellenmesi ve azaltılması üzerine
Misinformation on the internet and social media has become a pressing concern due to its potential impacts on society, undermining trust and impacting human decisions on global issues such as health, energy, politics, terrorism, and disasters. As a solution to the problem, computational methods have been employed to detect and mitigate the spread of false or misleading information. These efforts have included the development of algorithms to identify fake news and troll accounts, as well as research on the dissemination of misinformation on social media platforms. However, the problem of misinformation on the web and social networks remains a complex and ongoing challenge, requiring continued attention and research. We contribute to three different solution aspects of the problem. First, we design and implement an extensible social network simulation framework called Crowd that helps model, simulate, visualize and analyze social network scenarios. Second, we gamify misinformation propagation as a cooperative game between nodes and identify how misinformation spreads under various criteria. Then, we design a network-level game where the nodes are controlled from a higher perspective. In this game, we train and test a deep reinforcement learning method based on Multi-Agent Deep Deterministic Policy Gradients and show that our method outperforms well-known node-selection algorithms, such as page-rank, centrality, and CELF, over various social networks in defending against misinformation or participating in it. Finally, we promote and propose a blockchain and deep learning hybrid approach that utilizes crowdsourcing to target the misinformation problem while providing transparency, immutability, and validity of votes. We provide the results of extensive simulations under various combinations of well-known attacks on reputation systems and a case study that compares our results with a current study on Twitter.
Tümce kökenli konu modelleme
Fast augmentation of large text collections in digital world makes inevitable to automatically extract short descriptions of those texts. Even if a lot of studies have been done on detecting hidden topics in text corpora, almost all models follow the bag-of-words assumption. This study presents a new unsupervised learning method that reveals topics in a text corpora and the topic distribution of each text in the corpora. The texts in the corpora are described by a generative graphical model, in which each sentence is generated by a single topic and the topics of consecutive sentences follow a hidden Markov chain. In contrast to bag-of-words paradigm, the model assumes each sentence as a unit block and builds on a memory of topics slowly changing in a meaningful way as the text flows. The results are evaluated both qualitatively by examining topic keywords from particular text collections and quantitatively by means of perplexity, a measure of generalization of the model. Keywords: probabilistic graphical model, topic model, hidden Markov model, Markov chain Monte Carlo.
Sosyal faktörlerin mobil yerel aramalara entegrasyonu
As availability of internet access on mobile devices develops year after year, users have been able to make use of mobile internet and search services while on the go. Location information on these devices has enabled mobile users to utilize local search applications for discovering places and activities around them. Although mobile local search is a kind of search activity, it is inherently different than general web search. Mobile local search focuses on local businesses and points of interest, instead of web pages as in general web search. Moreover, users' context has a significant effect on their decision process. In previous studies, ranking signals and user context have been investigated on a small set of features. We extend ranking signals and user context in mobile local search with using data of location-based social networks. We developed a mobile local search application, Gezinio, and collected a data set of local search queries. Gezinio helps users to issue local queries and see various kinds of social information about local businesses around them. We built ranking models and investigated how social features affect decision process of users. We show that social features influence users' click decisions and they can be utilized by ranking models to improve the local search experience. Additionally, we propose different social features for different query categories.
Sıralama amaçlı öğrenme algoritmaları kullanarak eğitim tabanlı arama motoru optimizasyonu
Web search is one of the most popular internet activities among users. Due to high usage of search engines, there are huge data available about history of user search issues. Using query logs as a source of implicit feedback, researchers can learn useful patterns about general search behaviors. We employ a detailed query log analysis provided by a commercial educational vertical search engine. We compare the results of our query log analysis with the general web search characteristics. Due to difference in terms of search behavior between web users and students, we propose an educational ranking model using learning to rank algorithms to better reflect the search habits of the students in the educational domain to further enhance the search engine performance. We introduce novel features best suited to the educational domain. We show that our model including educational features outperforms two baseline models which are the original ranking of the commercial educational vertical search engine and the model constructed using the state of the art ranking functions, up to 14\% and 11\%, respectively. We also employ different learning to rank models for different clusters of queries and the results indicate that having models for each cluster of queries further enhances the performance of our proposed model. Specifically, the course of the query and the grade of the user issuing the query are good sources of feedback to have a better model in the educational domain. We propose a novel \textit{Propagation Algorithm} to be used for queries having lower frequencies where information derived from query logs is not enough to exploit. We report that our model constructed using the features generated by our proposed algorithm performs better for singleton queries compared to both the educational learning to rank model we introduce and models learned with common features introduced in the literature.
Eğitsel arama ve soru cevaplandırmanın geliştirilmesi
Students use general web search engines (GSEs) as their primary source of research while trying to find answers to school related questions. Although GSEs are highly relevant for the general population, they may return results that are out of education context. Another rising trend; social community question answering websites (CQ&A) are the secondary choice for students who try to get answers from other peers online. We focus on discovering possible improvements on educational search by leveraging both of the two information sources. The first part of our work involves Q&A websites. In order to gain contextual and behavioral insights, we extract the content of a commonly used educational Q&A website with a scraper we implement. We analyze the content in terms of user behavior and try to understand to what extent the educational Q&A differs from the general purpose Q&A. In the second part, we implement a classifier for educational questions. This classifier is built by an ensemble method that employs several regular learning algorithms and retrieval based ones that utilize external resources. We also build a query expander to facilitate classification. We further improve the classification using search engine results. In the third part, in order to find out whether search engine ranking can be improved in the education domain using the classification model, we collect and label a set of query results retrieved from a GSE. We propose five ad-hoc methods to improve search ranking based on the idea that the query-document category relation is an indicator of relevance. We evaluate these methods on various query sets and show that some of the methods significantly improve the rankings in the education domain. In the last part, we focus on educational spell checking. In educational search systems, it is common for users to make spelling mistakes. Actual query logs of two commercial search engines in the education domain are analyzed in terms of spelling mistakes using 5 well-known spell correction software that are not education specific and lack the terms that are used in the education field. It is shown that by extending the spell-check dictionary of one of them, even with a small-sized education oriented word-list, one can improve the precision, recall and F1 values of a spell-checker.
Arama motorlarının verimliliğini artırmak: Odaklanmış tarama, arama ve indeks budama stratejileri
Search engines are the primary means of retrieval for text data that is abundantly available on the Web. A standard search engine should carry out three fundamental tasks, namely; crawling the Web, indexing the crawled content, and finally processing the queries using the index. Devising efficient methods for these tasks is an important research topic. In this thesis, we introduce efficient strategies related to all three tasks involved in a search engine. Most of the proposed strategies are essentially applicable when a grouping of documents in its broadest sense (i.e., in terms of automatically obtained classes/clusters, or manually edited categories) is readily available or can be constructed in a feasible manner. Additionally, we also introduce static index pruning strategies that are based on the query views.For the crawling task, we propose a rule-based focused crawling strategy that exploits interclass rules among the document classes in a topic taxonomy. These rules capture the probability of having hyperlinks between two classes. The rule-based crawler can tunnel toward the on-topic pages by following a path of off-topic pages, and thus yields higher harvest rate for crawling on-topic pages.In the context of indexing and query processing tasks, we concentrate on conducting efficient search, again, using document groups; i.e., clusters or categories. In typical cluster-based retrieval (CBR), first, clusters that are most similar to a given free-text query are determined, and then documents from these clusters are selected to form the final ranked output. For efficient CBR, we first identify and evaluate some alternative query processing strategies. Next, we introduce a new index organization, so-called cluster-skipping inverted index structure (CS-IIS). It is shown that typical-CBR with CS-IIS outperforms previous CBR strategies (with an ordinary index) for a number of datasets and under varying search parameters. In this thesis, an enhanced version of CS-IIS is further proposed, in which all information to compute query-cluster similarities during query evaluation is stored. We introduce an incremental-CBR strategy that operates on top of this latter index structure, and demonstrate its search efficiency for different scenarios.Finally, we exploit query views that are obtained from the search engine query logs to tailor more effective static pruning techniques. This is also related to the indexing task involved in a search engine. In particular, query view approach is incorporated into a set of existing pruning strategies, as well as some new variants proposed by us. We show that query view based strategies significantly outperform the existing approaches in terms of the query output quality, for both disjunctive and conjunctive evaluation of queries.
Tam eleman indeksi kullanarak xml anahtar sözcük aramanın verimlilik ve etkililiği
In the last decade, both the academia and industry proposed several techniques to allow keyword search on XML databases and document collections. A common data structure employed in most of these approaches is an inverted index, which is the state-of-the-art for conducting keyword search over large volumes of textual data, such as world wide web. In particular, a full element-index considers (and indexes) each XML element as a separate document, which is formed of the text directly contained in it and the textual content of all of its descendants. A major criticism for a full element-index is the high degree of redundancy in the index (due to the nested structure of XML documents), which diminishes its usage for large-scale XML retrieval scenarios.As the first contribution of this thesis, we investigate the efficiency and effectiveness of using a full element-index for XML keyword search. First, we suggest that lossless index compression methods can significantly reduce the size of a full element-index so that query processing strategies, such as those employed in a typical search engine, can efficiently operate on it. We show that once the most essential problem of a full element-index, i.e., its size, is remedied, using such an index can improve both the result quality (effectiveness) and query execution performance (efficiency) in comparison to other recently proposed techniques in the literature. Moreover, using a full element-index also allows generating query results in different forms, such as a ranked list of documents (as expected by a search engine user) or a complete list of elements that include all of the query terms (as expected by a DBMS user), in a unified framework.As a second contribution of this thesis, we propose to use a lossy approach, static index pruning, to further reduce the size of a full element-index. In this way, we aim to eliminate the repetition of an element's terms at upper levels in an adaptive manner considering the element's textual content and search system's ranking function. That is, we attempt to remove the repetitions in the index only when we expect that removal of them would not reduce the result quality. We conduct a well-crafted set of experiments and show that pruned index files are comparable or even superior to the full element-index up to very high pruning levels for various ad hoc tasks in terms of retrieval effectiveness.As a final contribution of this thesis, we propose to apply index pruning strategies to reduce the size of the document vectors in an XML collection to improve the clustering performance of the collection. Our experiments show that for certain cases, it is possible to prune up to 70% of the collection (or, more specifically, underlying document vectors) and still generate a clustering structure that yields the same quality with that of the original collection, in terms of a set of evaluation metrics.
Büyük ölçekli arama motorlarında önbellekleme teknikleri
Large scale search engines have to cope with increasing volume of web content and increasing number of query requests each day. Caching of query results is one of the crucial methods that can increase the throughput of the system. In this thesis, we propose a variety of methods to increase the efficiency of caching for search engines.We first provide cost-aware policies for both static and dynamic query result caches. We show that queries have significantly varying costs and processing cost of a query is not proportional to its frequency. Based on this observation, we develop caching policies that take the query cost into consideration in addition to frequency, while deciding which items to cache. Second, we propose a query intent aware caching scheme such that navigational queries are identified and cached differently from other queries. Query results are cached and presented in terms of pages, which typically includes 10 results each. In navigational queries, the aim is to reach a particular web site which would be typically listed at the top ranks by the search engine, if found. We argue that caching and presenting the results of navigational queries in this 10-per-page manner is not cost effective and thus we propose alternative result presentation models and investigate the effect of these models on caching performance. Third, we propose a cluster based storage model for query results in a static cache. Queries with common result documents are clustered using single link clustering algorithm. We provide a compact storage model for those clusters by exploiting the overlap in query results. Finally, a five-level static cache that consists of all cacheable data items (query results, part of index, and document contents) in a search engine setting is presented. A greedy method is developed to determine which items to cache. This method prioritizes items for caching based on gains computed using items' past frequency, estimated costs, and storage overheads. This approach also considers the inter-dependency between items such that caching of an item may affect the gain of items that are not cached yet.We experimentally evaluate all our methods using a real query log and document collections. We provide comparisons to corresponding baseline methods in the literature and we present improvements in terms of throughput, number of cache misses, and storage overhead of query results.
Web arama motorları için cevap önbelleği tazeleme yöntemi
The result cache is a vital component for the efficiency of large-scale web search engines, and maintaining the freshness of cached query results is a current research challenge. As a remedy to this problem, our work proposes a new mechanism to identify queries whose cached results are stale. The basic idea behind our mechanism is to maintain and compare the generation time of query results with the update times of posting lists and documents to decide on staleness of query results. The proposed technique is evaluated using a Wikipedia document collection with real update information and a real-life query log. Throughout the experiments, we compare our approach with two baseline strategies from literature together with a detailed evaluation. We show that our technique has good prediction accuracy, relative to the baseline based on the time-to-live (TTL) mechanism. Moreover, it is easy to implement and it incurs less processing overhead on the system relative to a recently proposed, more sophisticated invalidation mechanism.
Arama motoru sorgu kayıtlarının uzun süreli analizi: Zaman boyutlu kapsam
The internet is growing day-by-day and the usage of web search engines is continuously increasing. Main page of browsers started by internet users is typically the home page of a search engine. To navigate a certain web site, most of the people prefer to type web sites? name to search engine interface instead of using internet browsers? address bar. Considering this important role of search engines as the main entry point to the web, we need to understand Web searching trends that are emerging over time. We believe that temporal analysis of returned query results by search engines reveals important insights for the current situation and future directions of web searching.In this thesis, we provide a large-scale analysis of the evolution of query results obtained from a real search engine at two distant points in time, namely, in 2007 and 2010, for a set of 630000 real queries. Our analyses in this work attempt to find answers to several critical questions regarding the evolution of Web search results. We believe that this work, being a large-scale longitudinal analysis of query results, would shed some light on those questions.
Transqlate: Zenginleştirilmiş doğal dil cümlelerini transformerler kullanarak sql sorgularına çevirmek
A large amount of the structured data owned by different enterprises is typically stored in Relational Database Management Systems, and a decent knowledge of Structured Language Query (SQL) is required to extract desired information from the relational databases. Many naive users need to access the information from databases, and they do not have the necessary skills or knowledge. Additionally, even some expert users might find it challenging to provide complex SQL queries when they do not know the schema underlying the database. To this end, a considerable amount of research has been conducted recently for the translation of queries formulated by users in a natural language to SQL queries to be processed by database systems. In this thesis, we provide some deep intelligent strategies to be used in natural language to SQL translation. We propose TranSQLate, a novel method to enrich the input sequences and provide more effective Natural Language Interface to Database (NLIDB) systems. We apply our strategies to the Vanilla transformer and T5 transformer models in three different ways. With enriched inputs, we achieve up to 16.7% improvement in translation accuracy, 6.5 points in SacreBLEU score, and 18 points in the n-gram precision, compared to not enriched versions. Our method surpasses the strategies used in the state-of-the-art systems NALIR, TEMPLAR, and DBTagger, in terms of translation accuracy over IMDB, scholar, and Yelp datasets.