User preference space partition and product filters for reverse top-k queries

Zong Hua Yang, Hung-Yu Kao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Top-k queries have been studied mainly from the perspective of the user. Many researchers have focused on improving the efficiency of top-k problems. However, few studies have focused on the essential factors required for manufacturers to assess the potential market. A novel query type, namely, the reverse top-k, is used to assess the potential market and help manufacturers calculate the impact of their products. Given a potential product, reverse top-k will find the user preferences for which this product is in the top-k query result set. Although several algorithms can solve the reverse top-k problem, none that are available can solve the reverse top-k problem when the number of products or users is large. In this paper, we formally define our algorithm as FSP (filtering and space partition) and explain how FSP solves the reverse top-k problem. The main idea of FSP is to use the partition of the candidate space to reduce the searching of space for products. In our experimental results, FSP can find the same results as other algorithms, but FSP reduces the time cost from 231 msec to 32 msec.

Original languageEnglish
Title of host publicationDSAA 2014 - Proceedings of the 2014 IEEE International Conference on Data Science and Advanced Analytics
EditorsGeorge Karypis, Longbing Cao, Wei Wang, Irwin King
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages498-504
Number of pages7
ISBN (Electronic)9781479969913
DOIs
Publication statusPublished - 2014 Mar 10
Event2014 IEEE International Conference on Data Science and Advanced Analytics, DSAA 2014 - Shanghai, China
Duration: 2014 Oct 302014 Nov 1

Publication series

NameDSAA 2014 - Proceedings of the 2014 IEEE International Conference on Data Science and Advanced Analytics

Other

Other2014 IEEE International Conference on Data Science and Advanced Analytics, DSAA 2014
CountryChina
CityShanghai
Period14-10-3014-11-01

Fingerprint

Query
Filter
Top-k
User preferences
Costs
Market potential
Factors
Time costs

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Information Systems
  • Information Systems and Management

Cite this

Yang, Z. H., & Kao, H-Y. (2014). User preference space partition and product filters for reverse top-k queries. In G. Karypis, L. Cao, W. Wang, & I. King (Eds.), DSAA 2014 - Proceedings of the 2014 IEEE International Conference on Data Science and Advanced Analytics (pp. 498-504). [7058118] (DSAA 2014 - Proceedings of the 2014 IEEE International Conference on Data Science and Advanced Analytics). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/DSAA.2014.7058118
Yang, Zong Hua ; Kao, Hung-Yu. / User preference space partition and product filters for reverse top-k queries. DSAA 2014 - Proceedings of the 2014 IEEE International Conference on Data Science and Advanced Analytics. editor / George Karypis ; Longbing Cao ; Wei Wang ; Irwin King. Institute of Electrical and Electronics Engineers Inc., 2014. pp. 498-504 (DSAA 2014 - Proceedings of the 2014 IEEE International Conference on Data Science and Advanced Analytics).
@inproceedings{480bbf6f86b94a89a4d9cd65af56c36f,
title = "User preference space partition and product filters for reverse top-k queries",
abstract = "Top-k queries have been studied mainly from the perspective of the user. Many researchers have focused on improving the efficiency of top-k problems. However, few studies have focused on the essential factors required for manufacturers to assess the potential market. A novel query type, namely, the reverse top-k, is used to assess the potential market and help manufacturers calculate the impact of their products. Given a potential product, reverse top-k will find the user preferences for which this product is in the top-k query result set. Although several algorithms can solve the reverse top-k problem, none that are available can solve the reverse top-k problem when the number of products or users is large. In this paper, we formally define our algorithm as FSP (filtering and space partition) and explain how FSP solves the reverse top-k problem. The main idea of FSP is to use the partition of the candidate space to reduce the searching of space for products. In our experimental results, FSP can find the same results as other algorithms, but FSP reduces the time cost from 231 msec to 32 msec.",
author = "Yang, {Zong Hua} and Hung-Yu Kao",
year = "2014",
month = "3",
day = "10",
doi = "10.1109/DSAA.2014.7058118",
language = "English",
series = "DSAA 2014 - Proceedings of the 2014 IEEE International Conference on Data Science and Advanced Analytics",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "498--504",
editor = "George Karypis and Longbing Cao and Wei Wang and Irwin King",
booktitle = "DSAA 2014 - Proceedings of the 2014 IEEE International Conference on Data Science and Advanced Analytics",
address = "United States",

}

Yang, ZH & Kao, H-Y 2014, User preference space partition and product filters for reverse top-k queries. in G Karypis, L Cao, W Wang & I King (eds), DSAA 2014 - Proceedings of the 2014 IEEE International Conference on Data Science and Advanced Analytics., 7058118, DSAA 2014 - Proceedings of the 2014 IEEE International Conference on Data Science and Advanced Analytics, Institute of Electrical and Electronics Engineers Inc., pp. 498-504, 2014 IEEE International Conference on Data Science and Advanced Analytics, DSAA 2014, Shanghai, China, 14-10-30. https://doi.org/10.1109/DSAA.2014.7058118

User preference space partition and product filters for reverse top-k queries. / Yang, Zong Hua; Kao, Hung-Yu.

DSAA 2014 - Proceedings of the 2014 IEEE International Conference on Data Science and Advanced Analytics. ed. / George Karypis; Longbing Cao; Wei Wang; Irwin King. Institute of Electrical and Electronics Engineers Inc., 2014. p. 498-504 7058118 (DSAA 2014 - Proceedings of the 2014 IEEE International Conference on Data Science and Advanced Analytics).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - User preference space partition and product filters for reverse top-k queries

AU - Yang, Zong Hua

AU - Kao, Hung-Yu

PY - 2014/3/10

Y1 - 2014/3/10

N2 - Top-k queries have been studied mainly from the perspective of the user. Many researchers have focused on improving the efficiency of top-k problems. However, few studies have focused on the essential factors required for manufacturers to assess the potential market. A novel query type, namely, the reverse top-k, is used to assess the potential market and help manufacturers calculate the impact of their products. Given a potential product, reverse top-k will find the user preferences for which this product is in the top-k query result set. Although several algorithms can solve the reverse top-k problem, none that are available can solve the reverse top-k problem when the number of products or users is large. In this paper, we formally define our algorithm as FSP (filtering and space partition) and explain how FSP solves the reverse top-k problem. The main idea of FSP is to use the partition of the candidate space to reduce the searching of space for products. In our experimental results, FSP can find the same results as other algorithms, but FSP reduces the time cost from 231 msec to 32 msec.

AB - Top-k queries have been studied mainly from the perspective of the user. Many researchers have focused on improving the efficiency of top-k problems. However, few studies have focused on the essential factors required for manufacturers to assess the potential market. A novel query type, namely, the reverse top-k, is used to assess the potential market and help manufacturers calculate the impact of their products. Given a potential product, reverse top-k will find the user preferences for which this product is in the top-k query result set. Although several algorithms can solve the reverse top-k problem, none that are available can solve the reverse top-k problem when the number of products or users is large. In this paper, we formally define our algorithm as FSP (filtering and space partition) and explain how FSP solves the reverse top-k problem. The main idea of FSP is to use the partition of the candidate space to reduce the searching of space for products. In our experimental results, FSP can find the same results as other algorithms, but FSP reduces the time cost from 231 msec to 32 msec.

UR - http://www.scopus.com/inward/record.url?scp=84946693547&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84946693547&partnerID=8YFLogxK

U2 - 10.1109/DSAA.2014.7058118

DO - 10.1109/DSAA.2014.7058118

M3 - Conference contribution

AN - SCOPUS:84946693547

T3 - DSAA 2014 - Proceedings of the 2014 IEEE International Conference on Data Science and Advanced Analytics

SP - 498

EP - 504

BT - DSAA 2014 - Proceedings of the 2014 IEEE International Conference on Data Science and Advanced Analytics

A2 - Karypis, George

A2 - Cao, Longbing

A2 - Wang, Wei

A2 - King, Irwin

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

Yang ZH, Kao H-Y. User preference space partition and product filters for reverse top-k queries. In Karypis G, Cao L, Wang W, King I, editors, DSAA 2014 - Proceedings of the 2014 IEEE International Conference on Data Science and Advanced Analytics. Institute of Electrical and Electronics Engineers Inc. 2014. p. 498-504. 7058118. (DSAA 2014 - Proceedings of the 2014 IEEE International Conference on Data Science and Advanced Analytics). https://doi.org/10.1109/DSAA.2014.7058118