SKY R-tree: An Index Structure for Distance-Based Top-k Query

详细信息    查看全文

• 作者：Yuya Sasaki (22)
  Wang-Chien Lee (23)
  Takahiro Hara (22)
  Shojiro Nishio (22)
  
• 关键词：Top ; k query ; Spatial database ; R ; tree ; Skyline ; Location ; based service
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：8421
• 期：1
• 页码：220-235
• 参考文献：1. Akbarinia, R., Pacitti, E., Valduriez, P.: Best position algorithms for top-k queries. In: VLDB, pp. 495鈥?06 (2007)
  2. Borzsony, S., Kossmann, D., Stocker, K.: The skyline operator. In: ICDE, pp. 421鈥?30 (2001)
  3. Cong, G., Jensen, C.S., Wu, D.: Efficient retrieval of the top-k most relevant spatial web objects. VLDB Journal聽2(1), 337鈥?48 (2009)
  4. Fagin, R., Lotem, A., Naor, M.: Optimal aggregation algorithms for middleware. Journal of Computer and System Sciences聽66(4), 614鈥?56 (2003) CrossRef
  5. Guttman, A.: R-trees: a dynamic index structure for spatial searching. SIGMOD聽14, 47鈥?7 (1984) CrossRef
  6. Ilyas, I.F., Beskales, G., Soliman, M.A.: A survey of top-k query processing techniques in relational database systems. ACM CSUR聽40(4), 11 (2008)
  7. Lazaridis, I., Mehrotra, S.: Progressive approximate aggregate queries with a multi-resolution tree structure. ACM SIGMOD Record聽30(2), 401鈥?12 (2001) CrossRef
  8. Roussopoulos, N., Kelley, S., Vincent, F.: Nearest neighbor queries. ACM SIGMOD Record聽24(2), 71鈥?9 (1995) CrossRef
  9. Tao, Y., Hristidis, V., Papadias, D., Papakonstantinou, Y.: Branch-and-bound processing of ranked queries. Information Systems聽32(3), 424鈥?45 (2007) CrossRef
  10. Vlachou, A., Doulkeridis, C., N酶rv氓g, K.: Monitoring reverse top-k queries over mobile devices. In: MobiDE, pp. 17鈥?4 (2011)
  11. Vlachou, A., Doulkeridis, C., N酶rv氓g, K.: Distributed top-k query processing by exploiting skyline summaries. IEEE Tran. on Distributed and Parallel Databases聽30(3-4), 239鈥?71 (2012) CrossRef
  12. Vlachou, A., Doulkeridis, C., N酶rv氓g, K., Vazirgiannis, M.: On efficient top-k query processing in highly distributed environments. In: ACM SIGMOD, pp. 753鈥?64 (2008)
  
• 作者单位：Yuya Sasaki (22)
  Wang-Chien Lee (23)
  Takahiro Hara (22)
  Shojiro Nishio (22)
  
  22. Osaka University, Osaka, Japan
  23. The Pennsylvania State University, PA, USA
  
• ISSN：1611-3349

文摘

Searches for objects associated with location information and non-spatial attributes have increased significantly over the years. To address this need, a top-k query may be issued by taking into account both the location information and non-spatial attributes. This paper focuses on a distance-based top-k query which retrieves the best objects based on distance from candidate objects to a query point as well as other non-spatial attributes. In this paper, we propose a new index structure and query processing algorithms for distance-based top-k queries. This new index, called SKY R-tree, drives on the strengths of R-tree and Skyline algorithm to efficiently prune the search space by exploring both the spatial proximity and non-spatial attributes. Moreover, we propose a variant of SKY R-tree, called S2KY R-tree which incorporates a similarity measure of non-spatial attributes. We demonstrate, through extensive experimentation, that our proposals perform very well in terms of I/O costs and CPU time.