Efficient Query Processing Over Spatial-Social Networks

Efficient Query Processing Over Spatial-Social Networks
Author: Ahmed Al-Baghdadi
Publisher:
Total Pages: 0
Release: 2022
Genre:
ISBN:

Recently, location-based social networks, that involve both social and spatial information, have received much attention in many real-world applications such as location-based services (LBS), map utilities, business planning, and so on. User's location is one of the most important components of user context that implies extensive knowledge about an individual's interests and behavior, thereby providing researchers with opportunities to better understand users in a social structure according to not only online user behavior but also the user mobility and activities in the physical world. In this dissertation, we have an initial study of query processing over spatial-social networks and propose suitable solutions of query processing over spatial-social networks by proposing new novel queries that are Community Search (CS), Group Planning (GP), and Community Detection (CD) over the spatial-social network settings. For each proposed query over spatial-social networks, we have designed effective pruning strategies to reduce the search space by filtering false alarms, proposed effective indexing mechanisms to facilitate the query processing, and develop efficient query answering algorithms via index traversals. Extensive experiments have been conducted to evaluate the efficiency and effectiveness of our proposed queries processing approaches.

Efficient Query Processing Over Large Road-Network Graphs

Efficient Query Processing Over Large Road-Network Graphs
Author: Niranjan Rai
Publisher:
Total Pages: 0
Release: 2022
Genre:
ISBN:

Many systems take the form of networks, sets of nodes or vertices joining together links or edges to form networks. Some examples include social networks, biological networks, collaboration networks, road networks, etc. Study of these networks is important for different purposes in each area. The community search or detection problem is also an important problem that has been widely studied in many of these networks. Community detection is essential in the study areas such as sociology, biology, and computer science, where data are often represented as graphs. Given a community definition, the community detection problem aims to find all the communities in the given graph network, whereas the community search problem aims to obtain all the communities that contain a query vertex provided by a user. The community search and detection problem are useful in many types of real-world applications such as social network analysis, online marketing and advertising over geo-social networks, and many others. While prior works on the community search/detection, usually considered user communities with strong social/spatial relationships in geo-social networks, in this dissertation, I will conduct a study on finding similar communities in road-network graphs which have not been done before. Specifically, I study a novel problem of retrieving top-k spatial communities on road-network graphs, which are quite useful and important for urban/city planning or community recommendations by real estate agencies.

Query Processing on Temporally Evolving Social Data

Query Processing on Temporally Evolving Social Data
Author: Wenyu Huo
Publisher:
Total Pages: 127
Release: 2013
Genre: Computer algorithms
ISBN: 9781303291968

The continuous growth of the internet and the popularity of social networks have created a huge amount of social media data. This includes social networks like users' friendships, as well as users' contributed content such as tags, blogs, posts, tweets, and etc. In addition, other collaborating applications also generate large data, such as the versioned textual documents created in a collaborative authoring environment like Wikipedia. In a dynamic world, the social media data is continuously evolving with time. In December 2004, Facebook had about 1 million users; but by October 2012, Facebook has over 1 billion active users. The dynamically changing and rapidly growing data bring us critical challenges: how to store, how to query, and how to use it in different application domains. This dissertation examines four related problems. First, we consider the large historical evolving graphs created from a social network, and examined various temporal shortest-path queries (e.g., find the shortest-path between two nodes as of certain time in the past). For this environment we proposed an efficient storage model, and fast query processing algorithms that take advantage of appropriate speed-up indexing techniques. For second problem examined, deals with social tagging websites, where users post and share items like bookmarks, videos, photos etc., along with comments and tags. Within this environment, we presented a study of top-k search that utilizes the temporal information as well as a user's participation in multiple social networks; our results show an improved search performance. Third, we examined the problem of temporal top-k keyword search in versioned textual collections; we compared different approaches and proposed novel methods that utilize multi-version access methods to improve the search. Finally, we considered applications that support multi-version schema evolutions; we explored scenarios for branching and merging, and proposed efficient indexing structures along with query processing optimizations.

Efficient Social Network Data Query Processing on MapReduce

Efficient Social Network Data Query Processing on MapReduce
Author: Liu Liu
Publisher:
Total Pages: 59
Release: 2013
Genre: Cloud computing
ISBN:

Social network data analysis becomes increasingly important today. In order to improve the integration and reuse of their data, many social networks start to apply RDF to present the data. Accordingly, one common approach for social network data analysis is to employ SPARQL to query RDF data. As the sizes of social networks expand rapidly, queries need to be executed in parallel such as using the MapReduce framework. However, the state-of-the-art translation from SPARQL queries to MapReduce jobs mainly follows a two layer rule, in which SPARQL is first translated to SQL join, is not efficient. In this thesis, we introduce two primitives to enable automatic translation from SPARQL to MapReduce, and to enable efficient execution of the SPARQL queries. We use multiple-join-with-filter to substitute traditional SQL multiple join when feasible, and merge different stages in the MapReduce query workflow. The evaluation on social network benchmarks shows that these two primitives can achieve up to 2x speedup in query running time compared with the original two layer scheme.

Advanced Spatial Queries with Textual and Social Components

Advanced Spatial Queries with Textual and Social Components
Author: Jing Li
Publisher: Open Dissertation Press
Total Pages:
Release: 2017-01-26
Genre:
ISBN: 9781361305379

This dissertation, "Advanced Spatial Queries With Textual and Social Components" by Jing, Li, 李晶, was obtained from The University of Hong Kong (Pokfulam, Hong Kong) and is being sold pursuant to Creative Commons: Attribution 3.0 Hong Kong License. The content of this dissertation has not been altered in any way. We have altered the formatting in order to facilitate the ease of printing and reading of the dissertation. All rights not granted by the above license are retained by the author. Abstract: The emerging new services for GPS and mobile users have developed applications that access and exploit spatial objects with new components (e.g. text and social network). Web objects, including blogs, tweets, photos and videos, are embedded into a map by the APIs of map service providers, where textual messages are associated with geographic information. Location-based social networking services, arising from Facebook and Foursquare, allow users to browse and share their traces of locations among the social networks. Among this class of applications, the highlight is that the retrieved spatial objects (e.g. points of interest and moving users) are featured with new components. Integrating such new components into the spatial query processing has produced large amounts of promising results. However, handling new components along with the retrieval of spatial objects increases the complexity of such joint query processing significantly. Thus, management over data from such multiple domains has been received considerable attention from database research community. In this thesis, we introduce three interesting problems and study their sophisticated solutions for processing spatial objects with new components: (i) category-aware optimal route query (CORQ), (ii) social and spatial ranking query (SSRQ), and (iii) efficient notification of meeting point (ENMP) query. Our results for (i) and (ii) facilitate the retrieval of spatial objects from multiple domains while our solutions for (iii) provide effective tools for synchronous management of multiple moving users from a social network. Category-aware optimal route queries (CORQ) are generalized from the traveling salesman problem and enable users to retrieve shortest routes covering selected categories. Social and spatial ranking queries (SSRQ) are relevant to spatial object recommendations using social information and allow users to obtain the spatial objects that not only are near their locations but also impress them with high social influence. Efficient notification of meeting point (ENMP) queries are variants of aggregate nearest neighbor queries and provide real-time rearrangement for multiple moving users according to their locations. Query processing in such multiple domains is complicated due to the mixture of domain information and their integration within one search. Naive algorithms for these problems incur either numerous expensive evaluations or massive communication cost, which render them inapplicable to large datasets. Our main research purpose is to design efficient and effective solutions for the proposed problems, that avoid the aforementioned shortcomings of naive algorithms. DOI: 10.5353/th_b4961783 Subjects: Querying (Computer science)

Community Search over Big Graphs

Community Search over Big Graphs
Author: Xin Huang
Publisher: Springer Nature
Total Pages: 188
Release: 2022-05-31
Genre: Computers
ISBN: 3031018745

Communities serve as basic structural building blocks for understanding the organization of many real-world networks, including social, biological, collaboration, and communication networks. Recently, community search over graphs has attracted significantly increasing attention, from small, simple, and static graphs to big, evolving, attributed, and location-based graphs. In this book, we first review the basic concepts of networks, communities, and various kinds of dense subgraph models. We then survey the state of the art in community search techniques on various kinds of networks across different application areas. Specifically, we discuss cohesive community search, attributed community search, social circle discovery, and geo-social group search. We highlight the challenges posed by different community search problems. We present their motivations, principles, methodologies, algorithms, and applications, and provide a comprehensive comparison of the existing techniques. This book finally concludes by listing publicly available real-world datasets and useful tools for facilitating further research, and by offering further readings and future directions of research in this important and growing area.

Advanced Query Processing on Spatial Networks

Advanced Query Processing on Spatial Networks
Author: MAN-LUNG. YIU
Publisher:
Total Pages:
Release: 2017-01-27
Genre:
ISBN: 9781361418345

This dissertation, "Advanced Query Processing on Spatial Networks" by Man-lung, Yiu, 姚文龍, was obtained from The University of Hong Kong (Pokfulam, Hong Kong) and is being sold pursuant to Creative Commons: Attribution 3.0 Hong Kong License. The content of this dissertation has not been altered in any way. We have altered the formatting in order to facilitate the ease of printing and reading of the dissertation. All rights not granted by the above license are retained by the author. Abstract: Abstract of thesis entitled "Advanced Query Processing on Spatial Networks" Submitted by Man Lung Yiu for the degree of Doctor of Philosophy at the University of Hong Kong in February 2006 Recent advances in GPS and mobile communication technologies have al- lowedapplicationstoemergethatcanaccessandexploitlocationinformation about (moving) objects on road networks. Location-based services enable car drivers to search for facilities such as restaurants, shops, and car-parks close to their route. Logistic services monitor the status of delivery vehi- cles and ensure the timely delivery of goods. In this class of applications, both the accessibility and location of objects (e.g., vehicles and facilities) are constrained by the underlying network. The actual distance between two objects is defined by their shortest path distance on the network rather than their Euclidean distance. These network constraints significantly increase the complexity of retrieving spatial query results. Thus, query processing on spatial networks (i.e., road networks) has received considerable attention from database researchers in recent years. In this thesis, we identify three interesting problems and study their eval- uation in the context of spatial networks: (i) aggregate nearest neighbor (ANN) query, (ii) reverse nearest neighbor (RNN) query, and (iii) cluster- ing. Our findings for (i) and (ii) provide meaningful results for end-users, while our results for (iii) provide effective data exploration tools for data analysts. Aggregate nearest neighbor (ANN) queries are generalized from the nearest neighbor problem, allowing a group of mobile users to express individual preferences for reaching the best overall facility (e.g., a restau- rant). Reverse nearest neighbor (RNN) queries are relevant to applications in decision support and resource allocation, enabling users to retrieve data objects locationally influenced by a query object. Clustering can be applied to discover dense collections of data objects, indicating regions of special interest. The process of computing results for these problems on spatial networks is complicated by the shortest path definition of the distance between two ob- jects. Naive evaluation methods may lead to numerous expensive network distance computations, and may not scale well for large networks and large datasets. Our main research objective is the design of appropriate opti- mization techniques for the proposed problems, that incur low I/O cost ofaccessing the spatial network. We also investigate several variants of these problems in order to expand the application scope of our proposed techniques. Variants of ANN queries include aggregate center queries and weighted queries. RNN queries have bichromatic and continuous variants. Clustering is also applicable with sev- eral grouping criteria. An abstract of exactly 388 words Signed Man Lung Yiu DOI: 10.5353/th_b3627936 Subjects: Nearest neighbor analysis (Statistics) Database management Cluster analysis

Queries and Analysis Tasks on Semantically Rich Spatial Data

Queries and Analysis Tasks on Semantically Rich Spatial Data
Author: Jieming Shi
Publisher:
Total Pages:
Release: 2017-01-26
Genre:
ISBN: 9781361024942

This dissertation, "Queries and Analysis Tasks on Semantically Rich Spatial Data" by Jieming, Shi, 石杰明, was obtained from The University of Hong Kong (Pokfulam, Hong Kong) and is being sold pursuant to Creative Commons: Attribution 3.0 Hong Kong License. The content of this dissertation has not been altered in any way. We have altered the formatting in order to facilitate the ease of printing and reading of the dissertation. All rights not granted by the above license are retained by the author. Abstract: Semantically rich spatial data are big and ubiquitous, raising challenges with respect to their effective and efficient querying and analysis. In particular, traditional spatial analysis and querying methods are not readily applicable due to the increased data complexity. Toward addressing these challenges and supporting real-life applications that manage such data, in this thesis, three problems on the querying and analysis of (i) geo-social network data, (ii) spatio-textual data, and (iii) spatial RDF data are proposed and studied. First, we study the problem of Density-based Clustering of Places in Geo-Social networks (DCPGS). Current spatial clustering models disregard information about the people who are related to the clustered places. We extend the density-based clustering paradigm to apply on places in geo-social networks, considering both the spatial information between places and the social relationships between users who visit the places. After formally defining our model and the distance measure it relies on, we present efficient index-based algorithms for its implementation. We evaluate the effectiveness of our model via a case study and two quantitative measures, called social entropy and community score, which indicate that geo-social clusters have special properties and cannot be found by applying simple spatial clustering approaches. The efficiency of our algorithms is also evaluated experimentally. Next, we study the modeling and evaluation of a Spatio-Textual Skyline (STS) query, in which the skyline points are selected based on not only their distances to a set of query locations, but also on their relevance to a set of query keywords. STS is especially relevant to modern applications, where points of interest are typically augmented with textual descriptions. We investigate three models for integrating textual relevance into the spatial skyline. Among them, model STD, combining spatial distance with textual relevance in a derived dimensional space, is the most effective one. STD computes a skyline satisfying the intent of STS, and having a small and easy-to-interpret size. We propose an IR-tree based algorithm for computing STD-based skylines. The effectiveness of our STD model and the efficiency of the algorithm are evaluated experimentally. Finally, we propose the problem of top-k relevant Semantic Place retrieval (kSP) on spatial RDF data, which finds applications in domains such as journalism, health, business, and tourism. Traditionally, RDF data is accessed by structured query languages, e.g., SPARQL. This requires users to understand both the language and the RDF schema. Recent research on keyword search over RDF data aims at reducing such requirements, but still ignores the spatial dimension of RDF data. Our kSP seeks for RDF subgraphs, rooted at spatial entities close to the query location and containing a set of query keywords. Compared to existing work, kSP queries are independent to structured query languages and they are location-aware. We devise a basic method for processing kSP queries. Two pruning approaches and a preprocessing technique are proposed to further improve efficiency. Experiments on real datasets demonstrate the superior and robust performance of our proposals compared to the basic method. Subjects: Spatial analysis (Statistics)