Cited By
View all- Le SDong YChen HFuruse K(2019)Balanced Nearest Neighborhood Query in Spatial Database2019 IEEE International Conference on Big Data and Smart Computing (BigComp)10.1109/BIGCOMP.2019.8679425(1-4)Online publication date: Feb-2019
Weighted Aggregate Reverse Rank Queries
Authors: 
Yuyang Dong, Hanxiong Chen, 
Jeffrey Xu Yu, Kazutaka Furuse, Hiroyuki KitagawaAuthors Info & Claims
Article No.: 5, Pages 1 - 23
Abstract
In marketing, helping manufacturers to find the matching preferences of potential customers for their products is an essential work, especially in e-commerce analyzing with big data. The aggregate reverse rank query has been proposed to return top-k customers who have more potential to buy a given product bundling than other customers, where the potential is evaluated by the aggregate rank, which is defined as the sum of each product’s rank. This query correctly reflects the request only when the customers consider the products in the product bundling equally. Unfortunately, rather than thinking products equally, in most cases, people buy a product bundling because they appreciate a special part of the bundling. Manufacturers, such as video games companies and cable television industries, are also willing to bundle some attractive products with less popular products for the purpose of maximum benefits or inventory liquidation.
Inspired by the necessity of general aggregate reverse rank query for unequal thinking, we propose a weighted aggregate reverse rank query, which treats the elements in product bundling with different weights to target customers from all aspects of thought. To solve this query efficiently, we first try a straightforward extension. Then, we rebuild the bound-and-filter framework for the weighted aggregate reverse rank query. We prove, theoretically, that the new approach finds the optimal bounds, and we develop the highly efficient algorithm based on these bounds. The theoretical analysis and experimental results demonstrated the efficacy of the proposed methods.
References
[1]
Reza Akbarinia, Esther Pacitti, and Patrick Valduriez. 2007. Best position algorithms for top-k queries. In Proceedings of the 33rd International Conference on Very Large Data Bases. 495--506.
[2]
Yuan-Chi Chang, Lawrence D. Bergman, Vittorio Castelli, Chung-Sheng Li, Ming-Ling Lo, and John R. Smith. 2000. The onion technique: Indexing for linear optimization queries. In Proceedings of the SIGMOD Conference. 391--402.
[3]
Surajit Chaudhuri and Luis Gravano. 1999. Evaluating top-k selection queries. In Proceedings of 25th International Conference on Very Large Data Bases(VLDB’99). 397--410.
[4]
Muhammad Aamir Cheema, Xuemin Lin, Wenjie Zhang, and Ying Zhang. 2011. Influence zone: Efficiently processing reverse k nearest neighbors queries. In Proceedings of the 27th ICDE. 577--588.
[5]
Evangelos Dellis and Bernhard Seeger. 2007. Efficient computation of reverse skyline queries. In Proceedings of the 33rd International Conference on VLDB. 291--302.
[6]
Yuyang Dong, Hanxiong Chen, Kazutaka Furuse, and Hiroyuki Kitagawa. 2016. Aggregate reverse rank queries. In Proceedings of the 27th International Conference on Database and Expert Systems Applications, Part II. 87--101.
[7]
Yuyang Dong, Hanxiong Chen, Jeffrey Xu Yu, Kazutaka Furuse, and Hiroyuki Kitagawa. 2017. Grid-index algorithm for reverse rank queries. In Proceedings of the 20th International Conference on Extending Database Technology (EDBT’17). 306--317.
[8]
Ronald Fagin. 1999. Combining fuzzy information from multiple systems. J. Comput. Syst. Sci. 58, 1 (1999), 83--99.
[9]
Ronald Fagin, Amnon Lotem, and Moni Naor. 2003. Optimal aggregation algorithms for middleware. J. Comput. Syst. Sci. 66, 4 (2003), 614--656.
[10]
Vagelis Hristidis, Nick Koudas, and Yannis Papakonstantinou. 2001. PREFER: A System for the efficient execution of multi-parametric ranked queries. In Proceedings of the 2001 ACM SIGMOD. 259--270.
[11]
Ihab F. Ilyas, George Beskales, and Mohamed A. Soliman. 2008. A survey of top-k query processing techniques in relational database systems. ACM Comput. Surv. 40, 4 (2008), 11:1--11:58.
[12]
Flip Korn and S. Muthukrishnan. 2000. Influence sets based on reverse nearest neighbor queries. In Proceedings of the 2000 ACM SIGMOD. 201--212.
[13]
Xiang Lian and Lei Chen. 2008. Monochromatic and bichromatic reverse skyline search over uncertain databases. In Proceedings of the ACM SIGMOD. 213--226.
[14]
Amélie Marian, Nicolas Bruno, and Luis Gravano. 2004. Evaluating top-k queries over web-accessible databases. ACM Trans. Database Syst. 29, 2 (2004), 319--362.
[15]
Julian J. McAuley, Rahul Pandey, and Jure Leskovec. 2015. Inferring networks of substitutable and complementary products. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 785--794.
[16]
Julian J. McAuley, Christopher Targett, Qinfeng Shi, and Anton van den Hengel. 2015. Image-based recommendations on styles and substitutes. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval. 43--52.
[17]
Dimitris Papadias, Qiongmao Shen, Yufei Tao, and Kyriakos Mouratidis. 2004. Group nearest neighbor queries. In Proceedings of the 20th International Conference on Data Engineering(ICDE’04). 301--312.
[18]
Dimitris Papadias, Yufei Tao, Kyriakos Mouratidis, and Chun Kit Hui. 2005. Aggregate nearest neighbor queries in spatial databases. ACM Trans. Database Syst. 30, 2 (2005), 529--576.
[19]
Ioana Stanoi, Divyakant Agrawal, and Amr El Abbadi. 2000. Reverse nearest neighbor queries for dynamic databases. In Proceedings of the ACM SIGMOD Workshop. 44--53.
[20]
Yufei Tao, Vagelis Hristidis, Dimitris Papadias, and Yannis Papakonstantinou. 2007. Branch-and-bound processing of ranked queries. Inf. Syst. 32, 3 (2007), 424--445.
[21]
Yufei Tao, Dimitris Papadias, and Xiang Lian. 2004. Reverse kNN search in arbitrary dimensionality. In Proceedings of the 13th International Conference on VLDB. 744--755.
[22]
Yufei Tao, Dimitris Papadias, Xiang Lian, and Xiaokui Xiao. 2007. Multidimensional reverse k NN search. VLDB J. 16, 3 (2007), 293--316.
[23]
Akrivi Vlachou, Christos Doulkeridis, and Yannis Kotidis. 2010. Identifying the most influential data objects with reverse top-k queries. PVLDB (2010), 364--372.
[24]
Akrivi Vlachou, Christos Doulkeridis, Yannis Kotidis, and Kjetil Nørvåg. 2010. Reverse top-k queries. In Proceedings of the 26th International Conference on Data Engineering (ICDE’10). 365--376.
[25]
Akrivi Vlachou, Christos Doulkeridis, Yannis Kotidis, and Kjetil Nørvåg. 2011. Monochromatic and bichromatic reverse top-k queries. IEEE Trans. Knowl. Data Eng. (2011), 1215--1229.
[26]
Akrivi Vlachou, Christos Doulkeridis, Yannis Kotidis, and Kjetil Nørvåg. 2013. Branch-and-bound algorithm for reverse top-k queries. In Proceedings of the SIGMOD Conference. 481--492.
[27]
Akrivi Vlachou, Christos Doulkeridis, and Kjetil Nørvåg. 2011. Monitoring reverse top-k queries over mobile devices. In MobiDE. 17--24.
[28]
Shenlu Wang, Muhammad Aamir Cheema, Xuemin Lin, Ying Zhang, and Dongxi Liu. 2016. Efficiently computing reverse k furthest neighbors. In Proceedings of the 32nd IEEE International Conference on Data Engineering (ICDE’16). 1110--1121.
[29]
Shiyu Yang, Muhammad Aamir Cheema, Xuemin Lin, and Wei Wang. 2015. Reverse k nearest neighbors query processing: Experiments and analysis. PVLDB 8, 5 (2015), 605--616.
[30]
Shiyu Yang, Muhammad Aamir Cheema, Xuemin Lin, and Ying Zhang. 2014. SLICE: Reviving regions-based pruning for reverse k nearest neighbors queries. In Proceedings of the IEEE 30th International Conference on Data Engineering, ICDE. 760--771.
[31]
Bin Yao, Feifei Li, and Piyush Kumar. 2009. Reverse furthest neighbors in spatial databases. In Proceedings of the 25th ICDE. 664--675.
[32]
Zhao Zhang, Cheqing Jin, and Qiangqiang Kang. 2014. Reverse k-ranks query. PVLDB 7, 10 (2014), 785--796.
Recommendations
Processing Aggregate Queries with Materialized Views in Data Warehouse Environment
Materialized views, which are derived from base relations and stored in the database, offer opportunities for significant performance gain in query evaluation by providing quick access to the pre-computed data. A materialized view can be utilized in ...
Probabilistic top-k and ranking-aggregate queries
Ranking and aggregation queries are widely used in data exploration, data analysis, and decision-making scenarios. While most of the currently proposed ranking and aggregation techniques focus on deterministic data, several emerging applications involve ...
Efficient processing of monotonic linear progressive queries via dynamic materialized views
CASCON '10: Proceedings of the 2010 Conference of the Center for Advanced Studies on Collaborative ResearchThere is an increasing demand to process emerging types of queries, such as progressive queries (PQs), from numerous contemporary database applications including telematics, ecommerce, business intelligence, and decision support. Unlike a conventional ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2018
68 pages
Copyright © 2018 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 10 August 2018
Accepted: 01 May 2018
Revised: 01 January 2018
Received: 01 May 2017
Published in TSAS Volume 4, Issue 2
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed
Funding Sources
- “Research and Development on Real World Big Data Integration and Analysis” of RIKEN, Japan
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 171Total Downloads
- Downloads (Last 12 months)5
- Downloads (Last 6 weeks)2
Reflects downloads up to 17 Dec 2024
Other Metrics
Citations
Cited By
View all- Le SDong YChen HFuruse K(2019)Balanced Nearest Neighborhood Query in Spatial Database2019 IEEE International Conference on Big Data and Smart Computing (BigComp)10.1109/BIGCOMP.2019.8679425(1-4)Online publication date: Feb-2019
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in