Xin Cao
Christian S. Jensen
Abstract
The location-aware keyword query returns ranked objects that are near a query location and that have textual descriptions that match query keywords. This query occurs inherently in many types of mobile and traditional web services and applications, e.g., Yellow Pages and Maps services. Previous work considers the potential results of such a query as being independent when ranking them. However, a relevant result object with nearby objects that are also relevant to the query is likely to be preferable over a relevant object without relevant nearby objects.
The paper proposes 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 Location-aware top-k Prestige-based Text retrieval (LkPT) query, is proposed that retrieves the top-k spatial web objects ranked according to both prestige-based relevance and location proximity.
We propose two algorithms that compute LkPT queries. Empirical studies with real-world spatial data demonstrate that LkPT queries are more effective in retrieving web objects than a previous approach that does not consider the effects of nearby objects; and they show that the proposed algorithms are scalable and outperform a baseline approach significantly.
- A. Balmin, V. Hristidis, and Y. Papakonstantinou. Objectrank: authority-based keyword search in databases. In VLDB, pp. 564--575, 2004. Google Scholar
Digital Library
- Z. Bar-Yossef and L.-T. Mashiach. Local approximation of pagerank and reverse PageRank. In CIKM, pp. 279--288, 2008. Google ScholarDigital Library
- N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R*-tree: an efficient and robust access method for points and rectangles. In SIGMOD, pp. 322--331, 1990. Google ScholarDigital Library
- P. Berkhin. Bookmark-coloring algorithm for personalized PageRank computing. Internet Math., 3(1):41--62, 2006.Google ScholarCross Ref
- S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. Comput. Netw. ISDN Syst., 30(1--7), 1998. Google ScholarDigital Library
- S. Chakrabarti. Dynamic personalized PageRank in entity-relation graphs. In www, pp. 571--580, 2007. Google ScholarDigital Library
- Y.-Y. Chen, T. Suel, and A. Markowetz. Efficient query processing in geographic web search engines. In SIGMOD, pp. 277--288, 2006. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- G. Cong, L. Wang, C.-Y. Lin, Y.-I. Song, and Y. Sun. Finding question-answer pairs from online forums. In SIGIR, pp. 467--474, 2008. Google ScholarDigital Library
- I. De Felipe, V. Hristidis, and N. Rishe. Keyword search on spatial databases. In ICDE, pp. 656--665, 2008. Google ScholarDigital Library
- R. Fagin, A. Lotem, and M. Naor. Optimal aggregation algorithms for middleware. J. Comput. Syst. Sci., 66(4):614--656, 2003. Google ScholarDigital Library
- D. Fogaras, B. Rácz, K. Csalogány, and T. Sarlós. Towards scaling fully personalized pagerank: Algorithms, lower bounds, and experiments. Internet Math., 2(3):333--358, 2005.Google ScholarCross Ref
- M. Gupta, A. Pathak, and S. Chakrabarti. Fast algorithms for top-k personalized PageRank queries. In WWW, pp. 1225--1226, 2008. Google ScholarDigital Library
- G. R. Hjaltason and H. Samet. Distance browsing in spatial databases. ACM TODS, 24(2):265--318, 1999. Google ScholarDigital Library
- K. Järvelin and J. Kekäläinen. Cumulated gain-based evaluation of IR techniques. ACM TOIS, 20(4):422--446, 2002. Google ScholarDigital Library
- G. Jeh and J. Widom. Scaling personalized web search. In WWW, pp. 271--279, 2003. Google ScholarDigital Library
- S. D. Kamvar, T. H. Haveliwala, C. D. Manning, and G. H. Golub. Exploiting the block structure of theweb for computing PageRank. Stanford University Technical Report 2003--17.Google Scholar
- O. Kurland and L. Lee. Pagerank without hyperlinks: structural re-ranking using links induced by language models. In SIGIR, pp. 306--313, 2005. Google ScholarDigital Library
- A. Langville and C. Meyer. Deeper inside PageRank. Internet Math., 1(3):335--380, 2004.Google ScholarCross Ref
- B. Martins, M. J. Silva, and L. Andrade. Indexing and ranking in Geo-IR systems. In GIR, pp. 31--34, 2005. Google ScholarDigital Library
- D. Zhang, Y. M. Chee, A. Mondal, A. K. H. Tung, and M. Kitsuregawa. Keyword search in spatial databases: Towards searching by document. In ICDE, pp. 688--699, 2009. Google ScholarDigital Library
- Y. Zhou, X. Xie, C. Wang, Y. Gong, and W.-Y. Ma. Hybrid index structures for location-based web search. In CIKM, pp. 155--162, 2005. Google ScholarDigital Library
- J. Zobel and A. Moffat. Inverted files for text search engines. ACM Comp. Surv., 38(2):6, 2006. Google ScholarDigital Library
Index Terms
- Retrieving top-k prestige-based relevant spatial web objects
Recommendations
Efficient retrieval of the top-k most relevant spatial web objects
The conventional Internet is acquiring a geo-spatial dimension. Web documents are being geo-tagged, and geo-referenced objects such as points of interest are being associated with descriptive text documents. The resulting fusion of geo-location and ...
Finding top-k relevant groups of spatial web objects
The web is increasingly being accessed from geo-positioned devices such as smartphones, and rapidly increasing volumes of web content are geo-tagged. In addition, studies show that a substantial fraction of all web queries has local intent. This ...
Retrieving multimedia web objects based on PageRank algorithm
WWW '05: Special interest tracks and posters of the 14th international conference on World Wide WebHyperlink analysis has been widely investigated to support the retrieval of Web documents in Internet search engines. It has been proven that the hyperlink analysis significantly improves the relevance of the search results and these techniques have ...
Comments