成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	楊宗樺 Yang, Zong-Hua
論文名稱：	基於高維度空間分割法之反向式Top-k查詢 User preference space partition and product filtering for reverse Top-k queries
指導教授：	高宏宇 Kao, Hong-Yu
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 資訊工程學系 Department of Computer Science and Information Engineering
論文出版年：	2014
畢業學年度：	102
語文別：	英文
論文頁數：	41
中文關鍵詞：	前k個、反前k個、空間分割
外文關鍵詞：	Space partition, filtering, top-k, reverse top-k
相關次數：	點閱：85 下載：2
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

前k筆資料查詢一直是廣為人探討的問題，大部份的問題著重在改善前ｋ筆查詢的效能。然而，卻很少研究針對產品的優缺進行市場的評估。與前k筆相似的問題被稱為反前k個查詢，這個問題著重於市場分析並協助產品製造商評估他們的產品在市場上所站的位置。指定一個產品，反前k筆查詢將找出所有將該產品列為前k個喜好的所有使用者，雖然目前存在一些方法能解決反前k筆查詢的問題，但這些方法在大量的使用者或大量的產品上都顯得較為不足。在這篇研究中我們提出了FSP模型，FSP模型包含兩個部份，首先，它將過濾掉在大量產品中相對不具有競爭性的產品，另一方面，FSP運用空間模組分割的方式，將大量的使用者進行分組，當我們進行反前k筆查詢時僅需針對各組的使用者進行查詢，而不是將所有的使用者進行查詢。最後我們將對我們提出的FSP進行評估，我們實做了BBR以及RTA兩個方法並進行比較。結果是，不同的方法在不同的環境下有不一樣的優勢，而FSP在擁有大量使用者及產品的購物網站上擁有較好的表現。

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.

CONTENT
中文摘要	III
ABSTRACT	IV
TABLE LISTING	VIII
FIGURE LISTING	IX
1.	INTRODUCTION	1
1.1	Background	1
1.2	Motivation	2
1.3	Our approach	3
1.4	Paper structure	4
2.	RELATED WORK	6
2.1	Related Search	6
2.2	Preliminaries	9
3.	METHOD	11
3.1	Preliminary	11
3.2	Filtering Based on Limit Point	12
3.3	Product Space Partitioning	15
3.4	Top-down algorithm	18
3.5	Space of the User Preference	23
3.6	Filtering and Space Partitioning algorithm	23
4.	Experiments	26
4.1	Experiment Setup	26
4.2	Experimental Result	28
4.3	Different Data Type	32
4.4	Different Units and Real Data	34
5.	CONCLUSIONS	37
6.	REFERENCES	39

TABLE LISTING	
Table 1:Overview of symbols	9
Table 2. Parameters	26

FIGURE LISTING
Figure 1. Example of reverse top-k queries	2
Figure 2 Example of RTA	7
Figure 3 Minimum bounding rectangle of BBR	8
Figure 4 Example of a top-k query and reverse top-k query	11
Figure 5 Process of FSP	12
Figure 6 Example of the limit point	14
Figure 7 Example of space partition	18
Figure 8 Top-down space partition	19
Figure 9 Example of finding candidates using thresholds	20
Figure 10 Example of finding candidates	21
Figure 11 Example of query processing	25
Figure 12 Comparative performance of all algorithms for UN dataset in varying n	28
Figure 13 Comparative performance of all algorithms for UN dataset in varying |P|	29
Figure 14 Comparative performance of all algorithms for UN dataset in varying |W|	30
Figure 15 Comparative performance of all algorithms for UN dataset in varying k	31
Figure 16 Comparative performance of all algorithms for UN dataset in varying |Q|	32
Figure 17 Comparative performance of all algorithms for correlated dataset S	32
Figure 18 Comparative performance of all algorithms for Anti-Correlated dataset S	33
Figure 19 Comparative performance of all algorithms for k-skyband queries Q	34
Figure 20 Top-k evaluations of RTA for varying dimensions d	35
Figure 21 INTop-k evaluations of BBR for varying dimensions d	35
Figure 22 Candidates size of the space in FSP for varying dimensions d	36
Figure 24 Performance of the NBA dataset	36

                                    

[1]. G. Das, et al., "Answering top-k queries using views," presented at the Proceedings of the 32nd international conference on Very large data bases, Seoul, Korea, 2006.
[2]. G. Das, et al., "Ad-hoc top-k query answering for data streams," presented at the Proceedings of the 33rd international conference on Very large data bases, Vienna, Austria, 2007.
[3]. A. Vlachou, et al., "Reverse top-k queries," Data Engineering (ICDE), 2010 IEEE 26th International Conference on. IEEE, pp. 365-376, 2010.
[4]. A. Vlachou, et al., "Branch-and-bound algorithm for reverse top-k queries," presented at the Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, New York, New York, USA, 2013.
[5]. V. Hristidis, et al., "PREFER: a system for the efficient execution of multi-parametric ranked queries," SIGMOD Rec., vol. 30, pp. 259-270, 2001.
[6]. Y.-C. Chang, et al., "The onion technique: indexing for linear optimization queries," SIGMOD Rec., vol. 29, pp. 391-402, 2000.
[7]. D. Xin, et al., "Towards robust indexing for ranked queries," presented at the Proceedings of the 32nd international conference on Very large data bases, Seoul, Korea, 2006.
[8]. R. Fagin, et al., "Optimal aggregation algorithms for middleware," presented at the Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, Santa Barbara, California, USA, 2001.
[9]. Y. Tao, et al., "Branch-and-bound processing of ranked queries," Inf. Syst., vol. 32, pp. 424-445, 2007.
[10]. A. Yu, et al., "Processing a large number of continuous preference top-<i>k</i> queries," presented at the Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, Scottsdale, Arizona, USA, 2012.
[11]. A. Vlachou, et al., "Monochromatic and Bichromatic Reverse Top-k Queries," IEEE Trans. on Knowl. and Data Eng., vol. 23, pp. 1215-1229, 2011.
[12]. A. Vlachou, et al., "Monitoring reverse top-k queries over mobile devices," presented at the Proceedings of the 10th ACM International Workshop on Data Engineering for Wireless and Mobile Access, Athens, Greece, 2011.
[13]. A. Vlachou, et al., "Identifying the most influential data objects with reverse top-k queries," Proc. VLDB Endow., vol. 3, pp. 364-372, 2010.
[14]. A. Arvanitis, et al., "Efficient influence-based processing of market research queries," presented at the Proceedings of the 21st ACM international conference on Information and knowledge management, Maui, Hawaii, USA, 2012.
[15]. O. Gkorgkas, et al., "Discovering influential data objects over time," presented at the Proceedings of the 13th international conference on Advances in Spatial and Temporal Databases, Munich, Germany, 2013.
[16]. T. Bernecker, et al., "Inverse queries for multidimensional spaces," presented at the Proceedings of the 12th international conference on Advances in spatial and temporal databases, Minneapolis, MN, 2011.
[17]. S. Ge, et al., "Efficient All Top-$(k)$ Computation—A Unified Solution for All Top-$(k)$, Reverse Top-$(k)$ and Top-$(m)$ Influential Queries," IEEE Trans. on Knowl. and Data Eng., vol. 25, pp. 1015-1027, 2013.
[18]. F. Korn and S. Muthukrishnan, "Influence sets based on reverse nearest neighbor queries," presented at the Proceedings of the 2000 ACM SIGMOD international conference on Management of data, Dallas, Texas, USA, 2000.
[19]. B. Yao, et al., "Reverse Furthest Neighbors in Spatial Databases," presented at the Proceedings of the 2009 IEEE International Conference on Data Engineering, 2009.
[20]. E. Dellis and B. Seeger, "Efficient computation of reverse skyline queries," presented at the Proceedings of the 33rd international conference on Very large data bases, Vienna, Austria, 2007.
[21]. X. Lian and L. Chen, "Monochromatic and bichromatic reverse skyline search over uncertain databases," presented at the Proceedings of the 2008 ACM SIGMOD international conference on Management of data, Vancouver, Canada, 2008

校內：2019-08-28公開
校外：2019-08-28公開

簡易檢索 / 詳目顯示

相關論文