Inverted Linear Quadtree: Efficient Top K Spatial Keyword Search

Inverted Linear Quadtree: Efficient Top K

Spatial Keyword Search

ABSTRACT:

In this paper, With advances in geo-positioning technologies and geo-location services, there are a rapidly growing amount of spatiotextual objects collected in many applications such as location based services and social networks, in which an object is described by its spatial location and a set of keywords (terms). Consequently, the study of spatial keyword search which explores both location and textual description of the objects has attracted great attention from the commercial organizations and research communities. In the paper, we study two fundamental problems in the spatial keyword queries: top k spatial keyword search (TOPK-SK), and batch top k spatial keyword search (BTOPK-SK). Given a set of spatio-textual objects, a query location and a set of query keywords, the TOPK-SK retrieves the closest k objects each of which contains all keywords in the query. BTOPK-SK is the batch processing of sets of TOPK-SK queries. Based on the inverted index and the linear quadtree, we propose a novel index structure, called inverted linear quadtree (IL- Quadtree), which is carefully designed to exploit both spatial and keyword based pruning techniques to effectively reduce the search space. An efficient algorithm is then developed to tackle top k spatial keyword search. To further enhance the filtering capability of the signature of linear quadtree, we propose a partition based method. In addition, to deal with BTOPK-SK, we design a new computing paradigm which partition the queries into groups based on both spatial proximity and the textual relevance between queries. We show that the IL-Quadtree technique can also efficiently support BTOPK-SK. Comprehensive experiments on real and synthetic data clearly demonstrate the efficiency of our methods.

EXISITING SYSTEMS:

          The Existing Techniques for the problem of TOPK-SK query as well as some other variants of top k spatial keyword search. Then other spatial keyword related queries are introduced. Considering the indexing scheme used in existing works, we classify the indexes into two categories, namely Keyword First Index and Spatial First Index. we describe the shortcomings of the existing indexing approaches. the system throughout is poor if a large number of queries are processed one by one. Motivated by this, a large body of existing work  have been devoted to investigate how to improve the system throughout with the batch query processing techniques such that a large number of queries in the queue can be processed with a reasonable delay.

Disadvantages:

          In the GPS navigation system, a POI (point of interest) is a geographically anchored pushpin that someone may find useful or interesting, which is usually annotated with texture information (e.g., descriptions and users’ reviews). Moreover, in many social network services (e.g., Facebook, Flickr), a huge number of geo-tagged photographs are accu- mulated everyday, which can be geo-tagged by users, GPS- enabled smartphones or cameras with a built-in GPS receiver .

          These uploaded pho- tographs are usually associated with multiple text labels. As a result, in recent years various spatial keyword query models and techniques

PROPOSED SYSTEMS:

          we propose a novel index structure, called inverted linear quadtree (IL- Quadtree), which is carefully designed to exploit both spatial and keyword based pruning techniques to effectively reduce the search space. An efficient algorithm is then developed to tackle top k spatial keyword search. the spatial keyword rank- ing query is proposed to rank objects based on a scoring function which considers the distance to the query location as well as the textual relevance to the query keywords. In the paper, we adopt the linear quadtree structure because the quadtree is more flexible in the sense that the index is adaptive to the distribution of the objects and we may prune the objects at high levels of the quadtree. Clearly, the new structure proposed satisfies the above-mentioned three important criteria of the spatial keyword indexing method.

Advantages:

An efficient algorithm is developed to support the top k spatial keyword search by taking advantage of the IL-Quadtree. We further propose a partition based method to enhance the effectiveness of the signature of linear quadtree.

The main difference is that the construction of WIBR-tree takes advantage of the term frequencies of the keywords to facilitate the joint TOPK-SK queries.

IMPLEMENTATION

Implementation is the stage of the project when the theoretical design is turned out into a working system. Thus it can be considered to be the most critical stage in achieving a successful new system and in giving the user, confidence that the new system will work and be effective.

MODULES DESCRIPTION:

          In this project, Inverted Linear Quadtree: Efficient Top k Spatial Keyword Search there following  modules  such as given below:

Spatial Keyword

Batch Processing

Linear Quadtree

Spatial Keyword:

          Spatial keyword search which explores both location and textual description of the objects has attracted great attention from the commercial organizations and research communities. These uploaded photographs are usually associated with multiple text labels. As a result, in recent years various spatial keyword query models and techniques have emerged such that users can effectively exploit both spatial and textual information of these spatio- textual objects. We have implemented this alogrrithm the problem of conducting top k spatial keyword search (TOPK-SK)  that is, given a set of spatio-textual objects, a query location q and a set of keywords, we aim to retrieve the k closest objects each of which contains all keywords in the query. The top k spatial keyword search is fundamental in spatial keyword queries and has a wide spectrum of applications.A large number of fake spatial keyword searches may be issued in order to protect the users privacy. This may lead to dramatic degrade of the system throughout if queries are processed individually.

Batch Processing:

          BTOPK-SK is the batch processing of sets of TOPK-SK queries. Based on the inverted index and the linear quadtree, we propose a novel index structure, called inverted linear quadtree (IL- Quadtree), which is carefully designed to exploit both spatial and keyword based pruning techniques to effectively reduce the search space. An efficient algorithm is then developed to tackle top k spatial keyword search. we also investigate the problem of batch spatial keyword query (BTOPK-SK) which aims to efficiently support a large number of spatial keyword queries at the same time. we devise efficient batch processing algorithm to support BTOPK-SK queries. Efficient batch spatial keyword query processing tech- niques are developed to improve the throughout of the system when there are a large amount of spatial keyword queries. an important role in batch query processing because it can significantly reduce the processing time by grouping similar queries so that the CPU and I/O costs can be shared between queries in the same group.

Linear Quadtree:

          Based on the inverted index and the linear quadtree, we propose a novel index structure, called inverted linear quadtree (IL- Quadtree), which is carefully designed to exploit both spatial and keyword based pruning techniques to effectively reduce the search space. An efficient algorithm is then developed to tackle top k spatial keyword search. We show that the IL-Quadtree technique can also efficiently support BTOPK-SK. the inverted linear quadtree (IL- Quadtree) indexing technique which naturally combines the spatial and textual features of the objects. Specifically, for each keyword we build a linear quadtree for the related objects so that the objects which do not contain any query keyword can be immediately excluded from computation.  we introduce a new indexing mechanism called inverted linear quadtree (IL-Quadtree) for the top k spatial keyword search. In Section 3.1 we describe the shortcomings of the existing indexing approaches. the linear quadtree structure because the quadtree is more flexible in the sense that the index is adaptive to the distribution of the objects and we may prune the objects at high levels of the quadtree. Clearly, the new structure proposed satisfies the above-mentioned three important criteria of the spatial keyword indexing method.

         

 

System Configuration:

HARDWARE REQUIREMENTS:

         Hardware                             -     Pentium

         Speed                                   -     1.1 GHz

         RAM                                   -    1GB

         Hard Disk                           -    20 GB

         Floppy Drive                       -    1.44 MB

         Key Board                          -    Standard Windows Keyboard

         Mouse                                 -    Two or Three Button Mouse

         Monitor                               -    SVGA

SOFTWARE REQUIREMENTS:

          Operating System                   : Windows

          Technology                    : Java and J2EE

          Web Technologies                   : Html, JavaScript, CSS

           IDE                               : My Eclipse

           Web Server                            : Tomcat

           Tool kit                        : Android Phone

           Database                      : My SQL

           Java Version                : J2SDK1.5                 

Conclusion:

                The problem of top k spatial keyword search is important due to the increasing amount of spatio-textual objects collected in a wide spectrum of applications. In the paper, we propose a novel index structure, namely IL-Quadtree, to organize the spatio-textual objects. An efficient algorithm is developed to support the top k spatial keyword search by taking advantage of the IL-Quadtree. We further propose a partition based method to enhance the effectiveness of the signature of linear quadtree. To facilitate a large amount of spatial keyword queries, we propose a BTOPK-SK algorithm as well as a query group algorithm to enhance the performance of the system. Our comprehensive experiments convincingly demonstrate the efficiency of our techniques.