Research Paper Computer Science E-ISSN : 2454-9916 | Volume : 2 | Issue : 1 | Jan 2016 FAST
NEAREST
NEIGHBOR
SEARCH
WITH
KEYWORDS
USING
ANDROID Nikhil Gadekar 1 | Dhiraj Jadhav 2 | Srinivas D 3 1 BE [Computer], G S Moze College of Emginerring, Pune-411045. 2 Professor, G S Moze College of Emginerring, Pune-411045. 3 Department of Physiological Sciences, Piracicaba Dental School - University of Campinas - UNICAMP, Piracicaba, SP, Brazil. ABSTRACT There are many modern applications that used to find out objects satisfying both spatial predicate and a predicate on their associated texts. In this paper, for finding nearest hotel a simple solution is introduced which based on IR2 (Information Retrieval R-Tree) tree. IR2 tree includes few deficiencies that affect its efficiency. To increase the efficiency a new method called spatial inverted index is introduced 'SI Index' extends the standard inverted index to address multidimensional information. This new SI index method comes with algo- rithms which will answer nearest neighbor queries with keywords in real time. Keywords: Information Retrieval Tree, Keyword Search, Spatial Inverted Index. Introduction recently that attention was diverted to multidimensional data. An increasing number of applications require an efficient execu- Existing works mainly focus on finding top-k Nearest Neighbors, tion of nearest neighbor (NN) queries constrained by the proper- where each node has to match the whole querying keywords .It ties of the spatial objects. Due to the popularity of keyword search, does not consider the density of data objects in the spatial space. particularly on the Internet, many of these applications allow the Also these methods are low efficient for incremental query. users to provide keywords that the spatial objects should contain description of spatial keyword query. A spatial database manages Disadvantages of the Existing System: multidimensional objects (such as points, rectangles, etc.) and pro- Ÿ Fail to provide real time answers on difficult inputs. vides fast access to those objects based on different selection crite- ria. The importance of spatial databases is, the real entities are rep- Ÿ The real nearest Neighbors lies quite far away from the query resented in a geometric manner. For example, locations of restau- point, while all the closer neighbours are missing at least one of rants, hotels, so on are represented as points in a map, while larger the query keywords. areas such as parks, lakes and landscapes as a combination of rect- angles. Queries focus on objects' geometric properties only, such as Proposed System: whether a point is in a rectangle or how close two points are from To overcome the drawbacks of previous applications, we proposed each other. Some modern applications that call for the ability to an application for android users. In our system we are mainly deal- select objects based on both of their geometric coordinates and ing with searching and nearer location issues and database man- their associated texts. age multidimensional objects which resulted in failure of previous systems. To deal with spatial index as searching the entered key- For example if user wants nearest hotel then he can find it with its word and from that find the nearest location having that keyword famous dish. Means if user wants “Paneer” only then he can enter available and showing the location of restaurant having menus Paneer as keyword then it will return nearest hotels which has available in map. So easier to find the location of nearer restaurant Paneer menu. Currently the best solution to such queries is based in map having the available keyword. A spatial database manages on the IR2-tree, which is used in this paper. This algorithm is very dimensional objects (such as points, rectangles, etc.) and provides efficient to search location with given keywords. Also there is a quick access to those objects. method called spatial inverted index that is used with multidi- mensional data and that comes with nearest neighbor search with Advantages of the Proposed System: given keywords. Ÿ Improves the search experience of the data search service. Existing System: Ÿ Distance browsing is easy with IR-trees. In the previous system, real nearest neighbor lies quite far away from the query point, while all the closer neighbors are missing at Ÿ It is straight forward to extend our compression scheme to any least one of the query keywords. As its fail to find the nearer loca- dimensional space. tion of restaurant having with all the keywords or menus available in restaurant. Existing system mainly focus on finding the nearest Mathematical Model: top neighbor where each node have to match whole query keyword. Let W be a set such that Spatial queries with keywords have not been extensively explored. W = {S, E, I,O, F, DD, NDD, Success, Failure} In the past years, the community has sparked enthusiasm in studying keyword search in relational databases. It is until International Education & Research Journal [IERJ] 47 Research Paper E-ISSN : 2454-9916 | Volume : 2 | Issue : 1 | Jan 2016 Where, Design Model: S=initial state where user register, login E =end state where user get the expected result I= input of the system. O=output of the system. F= set of functions DD- deterministic data it helps identifying the load store functions or assignment functions. NDD- Non deterministic data of the system S to be solved. Success-Desired outcome generated. Fig. USE CASE Diagram with Relationship Fig: State Diagram Goal and Objective: States: S0, S1, S2, S3, S4, S5 In this Paper we will develop new concept as per existing project. In that we will provide extra facilities like as hotel, PG, lodge res- S0: Initial State (User Logged in) taurants. For example when we will search information about any one facility in that will show the full information about the S1: Registration searched thing. S2: Login When people search the hotel information in that it will show the hotel name, location, distance from your location to hotel, road S3: Search Techniques line, hotel facilities also showing like as menu, rate as per hotel menu, available item food as per cultural. S4: Final State (Search Result Displayed) Expected Outcome: S5: Final State (Nearest Query/Result shown) In this system, when user enters the keyword to search in specific category, than it will show the nearest locations on map related to Modules: entered keywords. 1. Registration: In this module a User have to register first, and then only he/she has to access the data base. Future Scope: In future, we can use this system in different search engine appli- 2. Login: In this module, any of the above mentioned users have cation which will help the user to find the nearest object in faster to login, they should login by giving their email id and password. way by searching keyword. It can useful in location based apps which will help to find the nearest route for source to destination. 3. Hotel Registration: In this module Admin registers the hotel Also it provides the quick response for the keyword which will along with its famous dish. Also he measures the distance of the describes the input keyword related details. corresponding hotel from the corresponding source place by using spatial distance of Google map Conclusions: Our Paper is extremely effective for searching nearest restaurant 4. Search Techniques : Here we are using two techniques for from user location with expected menus. It does this by IR2 tree searching the document algorithm- Compression, Merging and Distance Browsing, and GPS System. In this we can add features like after selecting Hotel I. Restaurant Search: It means that the user can give the key in it will display menu card of that Hotel Implement this application which dish that the restaurant is famous for .This results in the for mobile user. list of menu items displayed. We have many applications that can be used as search engine II. Key Search: It means that the user can have the list of restau- which is able to efficiently support novel forms of spatial queries rants which are located very near. List came from the database. that are integrated with keyword search. In this paper we have developed an access method called the Spatial Inverted Index (SI 5. Map view : The User can see the view of their locality by Google Index). This method is very effective to perform keyword aug- Map(such as map view, satellite view) mented nearest neighbor search in real time. Acknowledgment: We are profoundly grateful to Prof. Srinivas.D, Project Co- Coordinator for their expert guidance and continuous encourage- ment throughout to see that this project rights its target since its commencement to its completion. We are also grateful for his sup- 48 International Education & Research Journal [IERJ] Research Paper E-ISSN : 2454-9916 | Volume : 2 | Issue : 1 | Jan 2016 port and guidance that have helped us to expand our horizons of thought and expression. We would like to express our deepest appreciation towards Prof. J. Ratnarajkumar, Head of the Department, Computer Engineering Department whose invaluable guidance supported us in complet- ing this project. We are particularly grateful to Mr. Pravin Lalge CEO (eis- ePersistence India Software, Pune) who allows us for the intern- ship in ePersistence India Software. At last we must express our sincere heartfelt gratitude to all staff members of Computer Engineering Department who helped us directly or indirectly during this course of work. REFERENCES: [1 ] N. Beckmann, H. Kriegel, R. Schneider, and B. Seeger. The R*-tree: An efficient and robust access method for points and rectangles. In Proc. of ACM Management of Data (SIGMOD), pages 322–331,1990. [2 ] S. Agrawal, S. Chaudhuri, and G. Das. Dbxplorer: A system for keyword-based search over relational databases. In Proc. of International Conference on Data Engineering (ICDE), pages 5–16, 2002. [3 ] G. Bhalotia, A. Hulgeri, C. Nakhe, S. Chakrabarti, and S. Sudar- shan. Keyword searching and browsing in databases using banks. In Proc. of International Conference on Data ngineering (ICDE), pages 431–440, 2002. [4 ] X. Cao, L. Chen, G. Cong, C. S. Jensen, Q. Qu, A. Skovsgaard, D. Wu, and M. L. Yiu. Spatial keyword querying. In ER, pages 16–29, 2012. [5 ] X. Cao, G. Cong, and C. S. Jensen. Retrieving top-k prestige- based relevant spatial web objects. PVLDB, 3(1):373–384, 2010. [6 ] X. Cao, G. Cong, C. S. Jensen, and B. C. Ooi. Collective spatial keyword querying. In Proc. of ACM Management of Data (SIG-MOD), pages 373–384, 2011. [7 ] B. Chazelle, J. Kilian, R. Rubinfeld, and A. Tal. The bloomier filter: an efficient data structure for static support lookup tables. In Proc. of the Annual ACM-SIAM Symposium on Dis- crete Algorithms (SODA), pages 30–39, 2004. [8] Yufei Tao And Cheng Sheng : Fast Nearest Neighbor Search With Keywords, IEEE Transactions On Knowledge And Data Engineering, Vol. 26, No. 4, April 2014. [9] Y.-Y. Chen, T. Suel, and A. Markowetz. Efficient query pro- cessing in geographic web search engines. In Proc. Of ACM Management of Data (SIGMOD), pages 277–288, 2006. [10 E. Chu, A. Baid, X. Chai, A. Doan, and J. Naughton. Combin- ing keyword search and forms for ad hocquerying of data- bases. In Proc. of ACM Management of Data (SIGMOD), 2009. [11] G. Cong, C. S. Jensen, and D. Wu. Efficient retrieval of the top- k most relevant spatial web objects. PVLDB,2(1):337–348, 2009. [11] C. Faloutsos and S. Christodoulakis. Signature files: An access method for documents and its analytical performanceevaluation. ACM Trans- actions on Information Systems (TOIS), 2(4):267–288, 1984. International Education & Research Journal [IERJ] 49