Search

With the proliferation of social sharing platforms (e.g., Foursquare and Yelp) and online social media (e.g., Twitter, Facebook and Instagram), large collections of geospatial data are becoming available, such as geo-tagged photos and geo-textual posts. The availability of substantial amount of such geospatial objects gives prominence to the spatial keyword query, which is to find the geo-textual objects that best match the query arguments exploiting both locations and textual descriptions. As an important type of spatial keyword query, the m-closest keywords (mCK) query is useful in many applications such as detecting locations of web resources. However, the existing work does not study the intractability of this problem and only provides exact algorithms, which are computationally expensive. Since the volume of geospatial data keeps growing rapidly, an emerging challenge is how to explore and understand the data before we analyze it. Presenting geospatial data through a visualization system is no doubt the most efficient way for end users, however, a remaining challenge is how to read the oversize data effectively. We aim at solving the challenge from two perspectives. On the one hand, the users may be exhausted and distracted if too many results are displayed at the same time. Following the rule of “Less is more”, we can show a small set of representative objects to users instead of the whole collection. Thus, the challenge in this problem is how to build such a map rendering system that efficiently selects a small set of representative objects from the current region of user’s interest. On the other hand, as the characteristics of geospatial data, the objects of similar types or functions may tend to appear together. Such circumstance is common in real-life, for example, there are more shopping malls grouping in the downtown area of a city than the living zones. To this end, we can explore the geo-spatial data by dividing the whole space into several functional regions according to the utilities of the geo-spatial objects. First, we study the m-closest keywords (mCK) query, finding a group of objects such that they cover all query keywords and have the smallest diameter, which is defined as the largest distance between any pair of objects in the group. We prove that the problem of answering mCK queries is NP-hard. We first devise a greedy algorithm that has an approximation ratio of 2. Then, we observe that an mCK query can be approximately answered by finding the circle with the smallest diameter that encloses a group of objects together covering all query keywords. We prove that the group enclosed in the circle can answer the mCK query with an approximation ratio of 2/√3. Based on this, we develop an algorithm for finding such a circle exactly, which has a high time complexity. To improve efficiency, we propose another two algorithms that find such a circle approximately, with a ratio of ( 2/√3+ ϵ). Finally, we propose an exact algorithm that utilizes the group found by the ( 2/√3+ϵ)-approximation algorithm to obtain the optimal group. We conduct extensive experiments using real-life datasets. The experimental results offer insights into both efficiency and accuracy of the proposed approximation algorithms, and the results also demonstrate that our exact algorithm outperforms the best known algorithm by an order of magnitude. Next, we study how to develop an interactive visualization map exploration system. We propose that such system should support the following desirable features: representativeness, visibility constraint, zooming consistency, and panning consistency. The first two constraints are fundamental challenges to a map exploration system, which aims to efficiently select a small set of representative objects from the current region of user’s interest, and any two selected objects should not be too close to each other for users to distinguish in the limited space of a screen. We formalize it as the Spatial Object Selection (sos) problem, prove that it is an NP-hard problem, and develop a novel approximation algorithm with performance guarantees. To further support interactive exploration of geospatial data on maps, we propose the Interactive sos (isos) problem, in which we enrich the sos problem with the zooming consistency and panning consistency constraints. The objective of isos is to provide seamless experience for end-users to interactively explore the data by navigating the map. We extend our algorithm for the sos problem to solve the isos problem, and propose a new strategy based on pre-fetching to significantly enhance the efficiency. Finally we have conducted extensive experiments to show the efficiency and scalability of our approach. Last but not least, we study how to partition the geospatial objects into functional regions according to the utilities and spatial distributions. It aims to aggregate similar and adjacent objects into enclosed regions that indicate certain functions. During this process, since the attributes distribution of the geospatial objects are aggregated, some information is lost during this process. We define the information loss to measure how much information is lost when merging two sets of objects. To reduce the possibilities of generated regions, we exploit the existing road networks to limit the boundaries of the separated regions to be roads, since it is the natural partition of cities and people live in these roads-segmented regions and POIs (points of interests) fall in these regions. We formulate this problem as Functional Region Segmentation (frs) problem, and prove that it is an NP-hard problem. We develop a bottom-up greedy algorithm to solve the frs problem, which terminates in limited steps. Results of empirical studies show that our proposed algorithm is able to solve frs problem efficiently and effectively. Doctor of Philosophy (IGS)

Due to the prosperity of social networks and smart phones, huge amounts of data with both spatial and textual information, e.g., geo-tagged tweets, is generated continuously, which can be modelled as data streams. Such spatio-textual data stream contains valuable information for millions of users with various interests on different keywords and locations. There has been increasing demand for efficiently exploring and processing spatio-textual data streams, which calls for systems that can provide real-time analytical results over the spatio-textual data. Publish/subscribe systems enable efficient and effective information distribution by allowing users to register continuous queries with both spatial and textual constraints. However, most existing publish/subscribe systems are centralized systems, which run on a single machine to process all the incoming data. The explosive growth of data scale and user base has posed challenges to the existing centralized publish/subscribe systems for spatio-textual data streams. To overcome these, we propose a distributed publish/subscribe system, called PS2Stream, which digests a massive spatio-textual data stream and directs the stream to target users with registered interests. Compared with existing systems, PS2Stream achieves a better workload distribution in terms of both minimizing the total amount of workload and balancing the load of workers. To achieve this, we propose a new workload distribution algorithm considering both space and text properties of the data. Additionally, PS2Stream supports dynamic load adjustments to adapt to the change of the workload, which makes PS2Stream adaptive. Extensive empirical evaluation, on commercial cloud computing platform with real data, validates the superiority of our system design and advantages of our techniques on system performance improvement. Publish/subscribe systems provide efficient ways to analyze the spatio-textual data at the tuple level, which return a set of spatio-textual objects satisfying the continuous queries in real time. However, in some scenarios, users are more interested in the higher level knowledge that can be extracted from the data. For instance, a marketing manager wants to know the popularity of some product in different regions, so that he or she can decide whether need to adjust the advertising strategy. A data stream warehouse system (DSWS) has the features of e cient data ingestion and enabling online analytical processing (OLAP) over streaming data. Unfortunately, existing DSWSs are not tailored for spatio-textual data and it requires a significant amount of efforts to address this. We develop a DSWS called STAR (Spatio-Textual Data Stream Warehouse). STAR is a distributed in-memory stream warehouse system, which can provide low-latency and up-to-date analytical results over a fast arriving spatio-textual data stream. STAR facilitates processing of ad-hoc aggregation queries with spatial or textual constraints by implementing a distributed view materialization algorithm. STAR adopts an effective workload partitioning strategy, which well partitions the workload composed of object processing, query processing and view maintaining. Additionally, STAR supports dynamic load adjustments, which make STAR scalable and adaptive. Extensive experiments over real data sets demonstrate the superior performance of STAR over existing systems. Doctor of Philosophy

With the wide-spread usage of social media such as Facebook and Twitter, large amount of data with both spatial and temporal information has become available. Topic modelling has been a useful tool to uncover latent information from such data. This thesis considers a specific type of topic model computational problem called topic-range queries, where the topic model of interest is restricted to the data records that fall within a dynamically specified geographic region and time period. To achieve this purpose, one naive approach is to directly apply a range query to retrieve the data items falling within the specified spatio-temporal range, then derive the topic model from the retrieved data by using a known algorithm such as LDA (Latent Dirichlet Allocation). When dealing with large volume of data, however, the two-step naive approach could each incur substantial amount of time. Novel algorithms for expediting the topic-range queries have been designed, including the fast topic combining algorithm FSS (Fast Set Sampling) which indexes the dataset with a tree, and pre-compute the topic model of the subset of data associated with each node of the tree. To answer a topic-range query, the tree nodes covered by the range query are identified, and the pre-computed topic models associated with these tree nodes are merged to produce an approximate result. Compared to the nave approach, this approximation of topic model substantially can reduce runtime. In the original design of the FSS algorithm, Cube trees are used as the indexing structure to support spatio-temporal range queries. In the literature, however, Range Trees offer a better worst-case query time guarantee for a range query. This master thesis thus considers a new combination of Range Trees and FSS (called Topic Ranger) to support the topic-range queries. The thesis presents the design, implementation of several versions of Topic Ranger for trade-offs between execution time and memory space. It also documents the experiments and comparisons of the execution time and the quality of the resulting approximate topic models against that of the original FSS scheme. Master of Engineering

With the prevalence of online social media (e.g, Facebook, Twitter), location-based services (e.g., Foursquare, Yelp, Flickr), and GPS-enabled devices, a huge number of documents with spatial information are being generated. Such documents are associated with either points of interest (e.g., restaurants) or latitude-longitude coordinates. We call these documents geo-textual documents. Geo-textual documents often contain information that indicates public/individual views and interests. It is of great interest to mine and explore topics from geo-textual documents to help various practical tasks, e.g., business analytics, point-of-interest (POI) recommendation, user recommendation, topic exploration, etc. There are two types of studies on mining topics from geo-textual data — (1) discovering topics of individuals from POI-associated posts (e.g., check-ins); and (2) mining and exploring topics of regions from geo-tagged microblogs. However, both types of studies have several limitations. Firstly, the topics of individuals that are mined from geo-textual data are successfully applied to POI recommendation, location prediction, etc. However, most of the existing methods mine topics from check-in datasets from Foursquare. Because each check-in often consists of limited textual information, and most of the users only shared few check-ins, it is difficult to discover meaningful topics of individuals from the check-in data. Moreover, the existing methods cannot capture topical aspects, e.g., the “environment” of a restaurant, thus failing to tell users why a POI is recommended to the user. Worse still, the existing methods are frequency-based (the more a topic is mentioned, the more likely a user prefers the topic), while ignoring the user’s sentiment. A user may hold negative opinions on some topics even though he/she mentions them many times. Secondly, the existing studies on learning topics of regions only allow users to explore the topics in predefined regions and time spans. A user may want to query topics within a specified region and time span. For example, a social scientist may want to find out breaking events by submitting regions and time spans in an exploratory manner. Some studies propose to learn geographical topic models to uncover latent regions and geographical topics. However, training these models is time consuming. It often takes months to train a model of moderate size (e.g., thousands of topics and thousands of regions) on millions of documents. However, there exists no distributed solution for training geographical topic models. To overcome the limitations in mining topics of individuals, we address two research challenges. First, we propose an approach to associating POIs with geo-tagged microblogs to compose a complementary “check-in” data source for topic mining of individuals. Second, we propose a unified model for learning topical aspects and regions of individuals with consideration of sentiment. The proposed model is able to improve the effectiveness of many downstream applications, e.g., POI recommendation, user recommendation, aspect satisfaction analysis, etc. To overcome the limitations in mining topics of regions, we consider two research problems. First, we develop a framework for exploring topics within a user specified region and time span. The framework can return topics fall in the spatio-temporal query to a user within seconds. Second, to allow efficient training of geographical topic models, we propose a distributed solution that supports learning large geographical topic models with millions of parameters from tens of gigabytes of geo-textual documents within 20 hours on a small cluster of 20 machines. Doctor of Philosophy (SCE)

With the prominence of GPS-enabled mobile devices, people can easily acquire their locations and access online services anywhere. The spatial information bridges the gap between the offline world and the online social networks, which leads to the germination of the location-based social networks (LBSNs) and event-based social networks (EBSNs). For instance, users can share their feelings and locations with their friends through LBSNs like Foursquare, and post a review of a restaurant through Yelp. As another example, people can find interesting local events to attend, or organize their own events through Meetup. We refer to the geo-tagged data (e.g. posts, check-ins, reviews, POIs) and the users in the social networks as objects. The availability of large scale social data paves the way to design data-driven approaches for various applications and tasks. We are interested in one type of queries called the group optimization query. Specifically, the group optimization query aims to select a group of objects which together satisfy a specified constraint such that the pre-defined score function of the group is optimized. In this dissertation, we define and investigate novel group optimization queries on spatial data and social networks. Specifically, for group optimization queries on spatial data, we define an axis-aligned rectangular region of a given size as the spatial constraint. Given a size of a rectangle, all the selected spatial objects should be close enough such that they can be covered by a rectangle of the given size. On the other hand, for group optimization queries in social networks, we define a set of attributes as the attribute constraint. All the selected nodes should together cover the specified set of attributes. With the spatial constraint and the attribute constraint, we define and investigate group optimization queries on spatial data and social networks by adopting different functions to measure the quality of the selected objects. We conduct three studies on spatial data, namely best aggregation region detection, bursty region detection and attribute-based similar region detection. We also conduct a study on social networks, namely influential organizers detection. In our study of best aggregation region detection, we propose the best region search (BRS) problem. Specifically, given a set O of spatial objects, the size a * b of a query rectangle, and a submodular monotone aggregate score function, the BRS problem aims at identifying a rectangular region of size a * b such that the aggregate score of the spatial objects inside the region is maximized. We then propose an algorithm to find the exact location of the region with the maximum score. By assuming that slight imprecision to the solution is acceptable, we further propose an algorithm which can find an approximate answer to the BRS problem bounded by a constant. In our study of bursty region detection, we propose a problem which utilizes such spatial object stream to detect and maintain bursty region of a given size in a specified geographic area in real time. We adopt two sliding windows to model the burstiness of a region. To handle spatial streams with high arrival rates, we design several pruning techniques to avoid frequent recomputation. In addition, we propose two approximate algorithms with better efficiency. We also extend the proposed solutions to support continuous detection of top-k bursty regions. In our study of attribute-based similar region detection, we propose the attribute-based similar region search (ASRS) problem, which aims at finding a region of the same size as the query rectangle such that the attribute distance between the two regions is minimized. We propose a grid-based method to address the ASRS problem efficiently. In our study of influential organizers detection, we formulate the influential cover set problem, which aims to select k users who can together cover a set of required skills and their influence is maximized. We adopt the independent cascade model to evaluate the influence of users. We first propose two heuristic greedy algorithms which are very efficient. The third algorithm has an approximation ratio of 2. It guarantees to find a feasible solution if any. Doctor of Philosophy (IGS)

With the increasing popularity of online social media applications, a large amount of data has been generated by users. Based on the user generated data, many research problems have been studied, such as the location-based recommendation and social influence analysis. In this thesis, we investigate the problem of user sequential mobility and the problem of social influence propagation. The main challenge of both problems lies in the difficulty to effectively learn the sequential transition. However, due to the data sparsity, it is hard to model the sequential information by conventional methods. To this end, we resort to the latent representation approach, which is to represent items in a low-dimensional latent space, such that the relations between items are captured by their representations. In addition, based on the social influence propagation in social networks, we study the problem of finding a set of influential users. Doctor of Philosophy (IGS)

Effective land use planning is essential for countries where land is scarce. In Singapore, land use planning is managed by the Urban Redevelopment Authority (URA). A revised land use plan is released by the URA every four to five years with the goal to create self-sufficient neighbourhoods and reduce commute time between places. Identifying identical land zones can assist city planners to draft out similar development objectives, reducing the time required to produce the land use plan. For business owners, identifying similar land zones can allow them to find the next potential area of expansion that fits their first success case. This work provides an analysis and a framework to the problem of similar urban region query. In particular, the analysis and the proposed query framework investigate the use of urban and social media data to find regions that are topically consistent and exhibits similar demographics. To achieve this, an Urban Region Similarity Analysis System (URSAS) is developed. This work shows that social media data can help to improve the quality of the query result as opposed to only considering urban information. Additionally, this work shows that the proposed query framework can recognize the type of function for a given zone based on urban and social media data. Master of Engineering (SCE)

With the proliferation of geo-positioning techniques and mobile devices such as smart-phones and tablet computers, the web is increasingly being used by mobile users and accurate user positioning is increasingly available. As a result, a spatial, or geographical web is emerging where contents and users are associated with locations. This leads to the fact that massive amounts of objects are available on the web that possess both a geographical location and a textual description. Such geo-textual objects include stores, tourist attractions, hotels, restaurants, businesses, entertainment services, public transport, etc. The availability of substantial amounts of geo-textual objects gives prominence to spatial keyword queries that target these objects. Such queries exploit both locations and textual descriptions and occur in many types of mobile and traditional web services and applications, e.g., Yellow Pages and Maps services, which greatly facilitate our everyday life. For example, in Google Maps the functionality “search nearby” allows users to retrieve points of interest around a specified location. Spatial keyword querying has attracted significant industrial and academic interests. There exist many proposals on studying spatial keyword queries, which retrieve lists of geo-textual objects that are both textually relevant to the query and satisfy a spatial query predicate. However, most existing work on spatial keyword querying treats the geo-textual objects as independent. This thesis focuses on efficiently processing the spatial keyword queries beyond the single geo-textual object granularity. First, we believe that a relevant result geo-textual object with nearby objects that are also relevant to the query is likely to be preferable over a relevant object without relevant nearby objects. We propose the concept of prestige-based relevance to capture both the textual relevance of an object to a query and the effects of nearby objects. Based on this, a new type of query, the top-k Prestige-based Spatial Keyword (kPSK) query, is proposed that retrieves the top-k geo-textual objects ranked according to both prestige-based relevance and location proximity. Two algorithms are devised to answer kPSK queries. Empirical studies with real-world datasets demonstrate that kPSK queries are more effective in retrieving geo-textual objects than is a previous approach without the consideration of the effects of nearby objects; the experimental results also show that the proposed algorithms are scalable and outperform a baseline approach significantly. Next, proposals for spatial keyword search so far generally focus on finding individual objects rather than finding groups of objects where the objects in a group collectively satisfy the requirements. We define another new type of query named the Spatial Group Keyword (SGK) query, which retrieves a group of geo-textual objects such that the group’s keywords cover the query’s keywords and such that objects are nearest to the query location and have the lowest inter-object distances. Specifically, we study two variants of this problem, both of which are NP-hard. We devise exact solutions as well as approximate solutions with provable approximation bounds to the problems. We present empirical studies that offer insight into the efficiency and accuracy of the solutions. Third, we consider a spatial keyword query over road networks that retrieves routes that are formed by a sequence of geo-textual objects. Identifying a preferable route is an important problem that finds applications in map services. When a user plans a trip within a city, the user may want to find “a most popular route such that it passes by shopping mall, restaurant, and pub, and the travel time to and from my hotel is within 4 hours.” However, no existing algorithms can be used to answer such queries. Motivated by this, we define the Keyword-aware Optimal Route query, denoted by KOR, which finds a route such that it covers a set of user-specified keywords, a specified budget constraint is satisfied, and an objective score of the route is optimal. The problem of answering KOR queries is NP-hard. We first devise an approximation algorithm with provable approximation bounds. Based on this algorithm, a more efficient approximation algorithm is proposed. We also design a greedy approximation algorithm. Results of empirical studies show that all the proposed algorithms are capable of answering KOR queries efficiently. The empirical studies also evaluate the accuracy of the proposed algorithms. DOCTOR OF PHILOSOPHY (SCE)

Online reviews are immensely valuable for customers to make informed decisions on product purchase, hotel booking, etc., and for businesses to improve the quality of their products and services. However, customer reviews grow very rapidly in quantity, while varying largely in quality. It is practically impossible for users to read through all the reviews for good decision-making. Opinion mining, also known as sentiment analysis, has been employed to automatically discover and summarize online reviews. In this thesis, we focus on the problem of aspect-based opinion mining of customer reviews. Our goal is to study and develop computational opinion mining techniques to support users to digest the huge amount of review data. In particular, we study three closely related problems as described below. The first problem deals with extracting aspect terms and opinion words that appear in customer reviews. We propose a generalized corpus statistics association based bootstrapping approach (ABOOT). ABOOT starts with a small list of annotated aspect seeds, and then iteratively extracts a large number of domain-specific aspect terms and opinion words from a given review corpus. ABOOT is able to work properly with only one seed, which can be simply domain word, e.g., "hotel" for hotel reviews. Our second problem focuses on identifying implicit aspects for the opinion words devoid of explicit aspects. Implicit aspects refer to the aspects that do not appear but are implied by opinion words in reviews. In opinion mining, very little work has been done on this problem. We propose a cooccurrence association rule mining method (coARM). coARM first discovers a significant set of association rules from a review corpus, and then it applies the rules to the opinion words devoid of explicit aspects for implicit aspect identification. The third part of this thesis deals with modeling customer reviews with aims at identifying semantic aspects and opinions as well as predicting overall review ratings in a unified framework. We introduce a new supervised joint topic model named supervised joint aspect and opinion model (SJAOM). SJAOM incorporates the overall ratings as supervision data, and simultaneously models the pairwise aspect terms and opinion words in each review. One key advantage of SJAOM is its ability to jointly identify the semantic aspects and opinions that are predictive of the overall ratings of reviews. Experimental results on real-world customer reviews demonstrate the benefits of our proposed methods for opinion mining problems, notably the SJAOM model. DOCTOR OF PHILOSOPHY (SCE)

With the prevalence of 3G & 4G services, people can easily share their opinions, moods, and activities with others via smartphones and tablets. As mobile devices are often GPS-enabled, a great quantity of user-generated content (UGC) with geographic locations has been accumulated, such as check-ins in location-based social networks (LBSNs), event-records in event-based social networks (EBSNs), and geo-annotated tweets on Twitter. Besides geographic location, UGC is often associated with timestamp and contains text content. The spatial, temporal and semantic information embedded in geo-annotated UGC can be exploited for a number of appealing applications and research problems. Point-of-interest (POI) recommendation is a representative one, which aims at recommending places that a target user has not visited before. Obviously, POI recommendation can help people explore new places and know their cities better. In addition, merchants can also benefit from it to deliver location-based advertisements and attract more customers. In recent years, a number of POI recommendation methods have been proposed, but most of them neglect contextual information, and make recommendations only based on user-POI check-in matrix. In real life, however, a user's preference to POIs is often influenced by her surroundings or context, such as time, companions, etc. For example, a user may prefer shopping malls to pubs in the afternoon, but may prefer pubs at night. Therefore, contextual information should be an important consideration for POI recommendation. In addition, a user may have specific requirement for recommendations sometimes, which directly reveals the user's preference. Thus, in this dissertation, we exploit the contextual information and requirements to recommend POIs for users. Specifically, we study three recommendation tasks that are relevant to the spatial, temporal, and semantic information of users. First, as human mobility is greatly influenced by time, we believe temporal influence is an important consideration for POI recommendation. We define a new problem, namely, time-aware POI recommendation, which aims to return a list of POIs for a user to visit at a specific time. In addition to temporal influence, human mobility is also influenced by geographic distance, e.g., people often visit their nearby places. To exploit both the temporal and spatial influences, we propose two algorithms, namely, User-based Collaborative Filtering with Temporal preference and smoothing Enhancement + Spatial influence with popularity Enhancement (UTE+SE) and Geographical-Temporal influences Aware Graph+Breadth-first Preference Propagation (GTAG-BPP), both of which are effective in making time-aware POI recommendations. We evaluate the performance of the proposed methods on two datasets, and the results show that the proposed methods outperform the state-of-the-art baselines significantly. Second, we observe that people often participate in activities and visit places together with others, e.g., watching movies with friends, and having dinner with colleagues. Thus, group POI recommendation is a realistic and important task, which aims at recommending POIs for a group of people. However, group recommendation is a challenging task, since group members may have different preferences, and how to balance their preferences is still an open problem. Furthermore, groups are often ad hoc, and the number of history records of a group may be very limited. The cold-start problem caused by ad hoc groups makes group recommendations even harder. To this end, we propose a Latent Dirichlet Allocation (LDA) based COnsensus Model (COM) to simulate the generative process of group activities and make POI recommendations for a group of users. Extensive experimental results on four real-world datasets validate that our model COM achieves superior recommendation accuracy comparing with five baselines. Third, when submitting recommendation requests, users may have clear requirements, e.g., dining or shopping, and the requirements can be formulated as short text. To make use of such information, we define a new task, namely, requirement-aware POI recommendation that generates a list of POIs for a target user based on her specific requirements. In addition, when target time is available, the recommendation results could be also time-aware. However, making time-aware and requirement-aware POI recommendations is non-trivial, as it calls for a model that can take into account the user, time, POI and words factors simultaneously. To solve this problem, we propose two frameworks, namely, a probabilistic Latent Semantic Analysis (pLSA) based model Who+Where+When+What (W4) and a Hierarchical Dirichlet Process (HDP) based model Enhanced W4 (EW^4), to model the complex interactions among the four factors, and make time-aware and requirement-aware POI recommendations. Empirical studies on two real-world datasets demonstrate our proposals outperform state-of-the-art approaches substantially. In summary, in this dissertation, we exploit spatial, temporal, and semantic information to recommend POIs to users, which is a natural but novel extension of exiting proposals on POI recommendation. DOCTOR OF PHILOSOPHY (SCE)

The author wants to answer the question: how Data Mining techniques can be utilised to improve the efficiency of room rental search? With this, the first objective of this study is to develop a clustering method in the context of Singapore Room Rental listing retrieval, called Relevance-based Clustering. The proposed clustering method adds geographical relationship among the textual relevance search results. The second objective is to develop a Rental Property Search Engine to demonstrate the result of applying Relevance-based Clustering to achieve efficient room rental search in Singapore. The essential part of this process is the ability to extract geographical information from webpages. The author narrows the scope of the study down to Singapore property websites, whereby the geographical information can be easily extracted from the map latitude and longitude information available in all of the major property websites in Singapore. The rental property search engine is custom-coded by the author using Python 2.7 programming language and is being deployed on Google App Engine (GAE) cloud hosting platform. The search engine consists of a property content web crawler that crawls rental section of Singapore property websites, and downloads content from each URL into the Listing table. Next, Data Pre-processing process is used to cleanse and tokenize the downloaded content to create and update into Inverted Index. Processed URLs are recorded into the Done-Process table to prevent duplicate effort. Upon receiving user query input, the query text will be cleansed and tokenized by Query Parsing process before passing over to Scoring and Ranking process to convert into vector form for Cosine Similarity score computation. The scoring will be ranked and the top K number of listings will form the Top K List. The Top K List is used to compute the URL Spherical Distance Matrix and clustering is performed on the URL Spherical Distance Matrix to discover geographical relationship among the top K textual relevance listings. The clustered result is converted into HTML format and returned to the user. The Information Retrieval (IR) effectiveness of the search engine based on K value = 100 has a low average F-Measure of 26%. Whereas, IR effectiveness based on K value = 20 has a better average F-Measure of 78%. Master of Science (Information Studies)

Subspace clustering overcomes the curse of dimensionality that traditional clustering suffered, by finding groups of objects that are homogeneous in subspaces of the data, instead of the full space. Research on basic subspace clustering over the past decade primary focuses on finding groups of objects that are closed together in subspaces of 2D data. Recently, the proliferation of non-traditional data and the need for higher quality clustering results have shifted the research paradigm to enhanced subspace clustering, which focuses on problems that cannot be handled or solved effectively through basic subspace clustering. The problems of enhanced subspace clustering can be categorized into two main groups, handling non-traditional data and improving clustering results. We give a survey on the enhanced subspace clustering problems, desired properties that these problems sought in their solutions, and the existing solutions. We study three main problems of enhanced subspace clustering on 2D and 3D datasets: mining subspace clusters in noisy data, mining significant subspace clusters and mining semi-supervised subspace clusters. For mining subspace clusters in noisy data, we found several problems of existing approaches, such as mining incomplete and unstable results, lacking the ability to handle 3D data, and mining clusters that are non-maximal and that contain skewed noise. We propose subspace clusters that are maximal and do not contain skewed noise. We also develop algorithms which exploit the anti-monotone property of the clusters to efficiently mine the complete and stable set of results. We show the effectiveness of our solution in mining biologically significant protein clusters in protein-protein interaction data, which is notoriously noisy in nature. For mining significant subspace clusters, we formulate an information theory concept known as correlation information, to measure the significance of the subspace clusters. We propose mining subspace clusters with high correlation information, and we develop an algorithm which uses the concept of rarity to mine significant 3D subspace clusters in a parameter-insensitive way. We show the effectiveness of our solution in finding significant (1) groups of proteins in protein-protein interaction data, (2) clusters of words and documents in word-document data and (3) in classifying an insurance data, where significant clusters are used as rules of the classifier. For mining semi-supervised subspace clusters, we propose actionable subspace clusters, which are semi-supervised subspace clusters that allow incorporation of user's knowledge, and can suggest beneficial actions to the users. We develop algorithms that use augmented Lagrangian multiplier method coupled with frequent itemset mining algorithm to efficiently mine the actionable clusters in a parameter-insensitive way. We show the effectiveness of our solution in finding actionable groups of residues in protein structural data, which are potential binding sites for drug molecules. Lastly, we present a financial data mining application on value investing, and show that our proposed algorithms outperform a famous value investment strategy in 70% of the experiments. Doctor of Philosophy