Contact Project Developer Ashish D. Tiwari [astiwz@gmail.com]
Download Synopsis Abstract

Inverted Linear Quadtree: Efficient Top K Spatial Keyword Search

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 s
Abstract-Synopsis-Documentation

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.

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.



Comment is Only Available for registered users! Create Account or Login Now!