University of Macau / Faculty of Science and Technology. / Department of Computer and Information Science

Nowadays we are living in an era of rich data, not only in the sense of the amount of data, but also in the sense of various sources and content of data. Efficient search, management, and exploitation of data have, over decades, been a major direction of database research. In this thesis, three challenging problems are proposed and studied, targeting (i) time series data, (ii) user preference data, and (iii) location-based social network data, respectively, providing efficient solutions to corresponding real-life applications. First, durability queries are studied in historical time series databases, which identify objects that have durable quality over time. For example, a sociologist may be interested in the top 10 web search terms during the period of some historical events; the police may seek for vehicles that move close to a suspect 70% of the time during a certain time, etc. Such durable top-k (DTop-k) and durable k-nearest neighbor (DkNN) queries can be viewed as natural extensions of the standard snapshot top-k and NN queries to timestamped sequences of values or locations. Although their snapshot counterparts have been studied extensively, there is little prior work that addresses this new class of durability queries. Efficient and scalable algorithms are proposed based on novel indexing techniques. Next, an efficient solution to k-nearest neighbor search over top-m lists is investigated. A top-m list is a ranking of m items, typically representing some user’s preference over these items. For example, a user may have a list of her 10 most favourite books; the result from a search engine is typically a list of webpages ranked according to their relevance to some keywords. The search problem aims at extracting k top-m lists from the database that are the “closest” to some query list where the closeness is evaluated using commonly used measures such as the Fagin’s intersection metric, Spearman’s footrule, Kendall’s tau, etc. Despite of the importance of such queries, there’s little prior work suggesting any efficient solution. In this thesis, a unified framework is proposed to answer such queries efficiently. Finally, the problem of top-N venue recommendation in location-based social networks (LBSNs) is studied, which recommends new venues to users. As an increasingly larger number of users partake in LBSNs, the recommendation problem in this setting has attracted significant attention in research and in practical applications. The detailed information about past user behavior that is traced by the LBSN differentiates the problem significantly from its traditional settings. The spatial nature in the past user behavior and also the information about the user social interaction with other users, provide a richer background to build a more accurate and expressive recommendation model. Although there have been extensive studies on recommender systems working with user-item ratings, GPS trajectories, and other types of data, there are very few approaches that exploit the unique properties of the LBSN user check-in data. In this thesis, effective and efficient algorithms that create recommendations are proposed based on such properties. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

This thesis concerns Social Network Analysis as a mechanism for exploring Community Dynamics. To be able to use the Social Network methodologies, relationships existing between the modeling entities are required. In this thesis, we use two different kinds of relationships: e-mails exchanged and co-authorship of papers. The e-mails exchanged, as an indicator of information exchange in an organization, is used to facilitate the emergence of structure within the organization. In this thesis we demonstrate the effectiveness of using e-mail communication patterns for crisis detection in a hierarchically set organization. We compare the performance of a Social Network based Classifier with some of the traditional classifiers from the data mining framework for inferring this hierarchy. A generic framework for studying dynamic group transformations is presented and the co-authorship of papers, as an indicator of collaboration in an academic institution, is used to study the community behavioral patterns evolving over time. Enron e-mail corpus and the IISc Co-authorship Dataset are utilized for illustrative purposes.