Abstract
Reverse k-rank queries, for a given query item, extract the top-k users whose ranking of the item (based on individual user’s preferences) is best among all the users. Such queries have recently received significant interest in diverse applications like market analysis, product placement, sales and e-commerce. Current approaches employ efficient high-dimensional data indexing techniques to prune input data points for improving query run-time. However, they fail to provide practical run-time characteristics for online and streaming scenarios, typical in such applications. This paper proposes the RADAR algorithm to efficiently compute, in real-time, approximate reverse k-rank queries. RADAR sorts the input data on each dimension (i.e., item aspects), and utilizes the ranking of a query in each of the dimensions to approximate the final ranking of the query by users based on their preferences. Empirical evaluations on real datasets demonstrates upto 50\(\times \) run-time improvements over existing approaches, with a high accuracy of around \(90\%\). Further, experiments on synthetic datasets showcase the scalability and efficacy of our algorithm for large scale and high-dimensional datasets.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Chang, Y., Bergman, L.D., Castelli, V., Li, C., Lo, M., Smith, J.R.: The onion technique: indexing for linear optimization queries. In: SIGMOD, pp. 391–402 (2000)
Chester, S., Thomo, A., Venkatesh, S., Whitesides, S.: Indexing reverse top-k queries in two dimensions. In: DASFAA, pp. 201–208 (2013)
Dong, Y., Chen, H., Furuse, K., Kitagawa, H.: Aggregate reverse rank queries. In: DEXA, pp. 87–101 (2016)
Dong, Y., Chen, H., Furuse, K., Kitagawa, H.: Efficient processing of aggregate reverse rank queries. In: DEXA, pp. 159–166 (2017)
Dong, Y., Chen, H., Yu, J.X., Furuse, K., Kitagawa, H.: Grid-index algorithm for reverse rank queries. In: EDBT, pp. 306–317 (2017)
Fagin, R., Lotem, A., Naor, M.: Optimal aggregation algorithms for middleware. J. Comput. Syst. Sci. 66(4), 614–656 (2003)
Gao, Y., Miao, X., Chen, G., Zheng, B., Cai, D., Cui, H.: On efficiently finding reverse k-nearest neighbors over uncertain graphs. VLDB J. 26, 467–492 (2017)
Ge, S., U, L.H., Mamoulis, N., Cheung, D.: Efficient all top-k computation - a unified solution for all top-k, reverse top-k and top-m influential queries. TKDE 25(5), 1015–1027 (2012)
Hjaltason, G.R., Samet, H.: Distance browsing in spatial databases. TODS 24(2), 265–318 (1999)
Hristidis, V., Koudas, N., Papakonstantinou, Y.: PREFER: a system for the efficient execution of multi-parametric ranked queries. In: SIGMOD, pp. 259–270 (2001)
Ilyas, I.F., Beskales, G., Soliman, M.A.: A survey of top-k query processing techniques in relational database systems. ACM Comput. Surv. (CSUR) 40(4), 11:1–11:58 (2008)
Korn, F., Muthukrishnan, S.: Influence sets based on reverse nearest neighbor queries. In: SIGMOD, pp. 201–212 (2000)
Mamoulis, N., Yiu, M.L., Cheng, K.H., Cheung, D.W.: Efficient top-k aggregation of ranked inputs. TODS 32(3), 19 (2007)
Qian, Y., Li, H., Mamoulis, N., Liu, Y., Cheung, D.W.: Reverse k-ranks queries on large graphs. In: EDBT, pp. 37–48 (2017)
Vlachou, A., Doulkeridis, C., Kotidis, Y., Nørvåg, K.: Reverse top-k queries. In: ICDE, pp. 365–376 (2010)
Vlachou, A., Doulkeridis, C., Kotidis, Y., Nørvåg, K.: Monochromatic and bichromatic reverse top-k queries. TKDE 23(8), 1215–1229 (2011)
Vlachou, A., Doulkeridis, C., Nørvåg, K., Kotidis, Y.: Branch-and-bound algorithm for reverse top-k queries. In: SIGMOD, pp. 481–492 (2013)
Xin, D., Chen, C., Han, J.: Towards robust indexing for ranked queries. In: VLDB, pp. 235–246 (2006)
Yang, S., Cheema, M.A., Lin, X., Zhang, Y.: SLICE: reviving regions-based pruning for reverse-k nearest neighbors queries. In: ICDE, pp. 760–771 (2014)
Yu, A.W., Mamoulis, N., Su, H.: Reverse top-k search using random walk with restart. PVLDB 7(5), 401–412 (2014)
Zhang, Z., Jin, C., Kang, Q.: Reverse k-rank query. PVLDB 7(10), 785–796 (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Dutta, S. (2021). RADAR: Fast Approximate Reverse Rank Queries. In: Arai, K., Kapoor, S., Bhatia, R. (eds) Intelligent Systems and Applications. IntelliSys 2020. Advances in Intelligent Systems and Computing, vol 1252. Springer, Cham. https://doi.org/10.1007/978-3-030-55190-2_63
Download citation
DOI: https://doi.org/10.1007/978-3-030-55190-2_63
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-55189-6
Online ISBN: 978-3-030-55190-2
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)