Top-K Query Processing in Edge-Labeled Graph Data

Edge-labeled graphs have proliferated rapidly over the last decade due to the increased popularity of social networks and the Semantic Web. In social networks, relationships between people are represented by edges and each edge is labeled with a semantic annotation. Hence, a huge single graph can express many different relationships between entities. The Semantic Web represents each single fragment of knowledge as a triple (subject, predicate, object), which is conceptually identical to an edge from subject to object labeled with predicates. A set of triples constitutes an edge-labeled graph on which knowledge inference is performed. Subgraph matching has been extensively used as a query language for patterns in the context of edge-labeled graphs. For example, in social networks, users can specify a subgraph matching query to find all people that have certain neighborhood relationships. Heavily used fragments of the SPARQL query language for the Semantic Web and graph queries of other graph DBMS can also be viewed as subgraph matching over large graphs. Though subgraph matching has been extensively studied as a query paradigm in the Semantic Web and in social networks, a user can get a large number of answers in response to a query. These answers can be shown to the user in accordance with an importance ranking. In this thesis proposal, we present four different scoring models along with scalable algorithms to find the top-k answers via a suite of intelligent pruning techniques. The suggested models consist of a practically important subset of the SPARQL query language augmented with some additional useful features. The first model called Substitution Importance Query (SIQ) identifies the top-k answers whose scores are calculated from matched vertices' properties in each answer in accordance with a user-specified notion of importance. The second model called Vertex Importance Query (VIQ) identifies important vertices in accordance with a user-defined scoring method that builds on top of various subgraphs articulated by the user. Approximate Importance Query (AIQ), our third model, allows partial and inexact matchings and returns top-k of them with a user-specified approximation terms and scoring functions. In the fourth model called Probabilistic Importance Query (PIQ), a query consists of several sub-blocks: one mandatory block that must be mapped and other blocks that can be opportunistically mapped. The probability is calculated from various aspects of answers such as the number of mapped blocks, vertices' properties in each block and so on and the most top-k probable answers are returned. An important distinguishing feature of our work is that we allow the user a huge amount of freedom in specifying: (i) what pattern and approximation he considers important, (ii) how to score answers - irrespective of whether they are vertices or substitution, and (iii) how to combine and aggregate scores generated by multiple patterns and/or multiple substitutions. Because so much power is given to the user, indexing is more challenging than in situations where additional restrictions are imposed on the queries the user can ask. The proposed algorithms for the first model can also be used for answering SPARQL queries with ORDER BY and LIMIT, and the method for the second model also works for SPARQL queries with GROUP BY, ORDER BY and LIMIT. We test our algorithms on multiple real-world graph databases, showing that our algorithms are far more efficient than popular triple stores.

RICH AND EFFICIENT VISUAL DATA REPRESENTATION

Increasing the size of training data in many computer vision tasks has shown to be very effective. Using large scale image datasets (e.g. ImageNet) with simple learning techniques (e.g. linear classifiers) one can achieve state-of-the-art performance in object recognition compared to sophisticated learning techniques on smaller image sets. Semantic search on visual data has become very popular. There are billions of images on the internet and the number is increasing every day. Dealing with large scale image sets is intense per se. They take a significant amount of memory that makes it impossible to process the images with complex algorithms on single CPU machines. Finding an efficient image representation can be a key to attack this problem. A representation being efficient is not enough for image understanding. It should be comprehensive and rich in carrying semantic information. In this proposal we develop an approach to computing binary codes that provide a rich and efficient image representation. We demonstrate several tasks in which binary features can be very effective. We show how binary features can speed up large scale image classification. We present learning techniques to learn the binary features from supervised image set (With different types of semantic supervision; class labels, textual descriptions). We propose several problems that are very important in finding and using efficient image representation.

When Love Becomes Hate(?): The Interplay Between Consumer-Brand Relationships and Crisis Situations

This study had three purposes. First, it aimed to re-conceptualize organization-public relationships (OPRs) in public relations and crisis communication. This OPR re-conceptualization helps find out when the OPR buffering effect or the OPR love-becomes-hate effect happens. Second, it aimed to examine how consumer emotions are influenced by OPRs and influence consumer behavioral intentions. Third, it aimed to address the current problematic operationalization of the concept of consumer. Three pilot studies and one main study were conducted. Apple and Whole Foods were the two brands examined. One crisis that undermined the self-defining attributes shared between the brand and its consumers and another crisis that did not were examined for each brand. Almost 500 Apple consumers and 400 Whole Foods consumers provided usable questionnaires. This study had several major findings. First, non-identifying relationship and identifying relationship were different constructs. Moreover, trust, satisfaction, and commitment were not conceptually separate dimensions of OPRs. Second, the non-identifying relationships offered buffering effects by increasing positive attitudes and tempering anger and disappointment. The identifying relationships primarily offered the love-becomes-hate effects by increasing anger and disappointment. Third, if the crisis was relevant to consumers’ daily lives, brand response strategies were less effective at mitigating consumer negative reactions. Moreover, apology-compensation-reminder strategy was more effective compared to no-comment strategy. However, the apology-compensation-reminder strategy was no more effective than other strategies as long as brands compensate to the victims. Identifying relationships increased the effectiveness of response strategies. If the crisis did not undermine the self-defining attributes shared between consumers and brands, the response strategies worked even better. This study contributes to crisis communication research in multiple ways. First, it advances the OPR conceptualization by demonstrating that non-identifying relationship and identifying relationship are different concepts. More importantly, it advances the theory building of OPRs’ influences on crises by finding out when the buffering effect and the love-becomes-hate effect happen. Second, it adds to emotion research by demonstrating that strong OPRs can lead to negative emotions and positive emotions can have negative behavioral consequences on organizations. Third, the precise operationalization of the concept of consumer gives more insights about consumer reactions to crises.