使用者對標籤資源進行查詢時，大多給予簡短的查詢字，搜尋出包含查詢字為標籤的資料物件。當查詢字為涵義較廣的字時，常造成查詢結果回傳大量資料物件，導致使用者需要費時對龐大的物件一一瀏覽，才能找到真正需要的資料。因此，本論文對社交標籤系統，探討如何由使用者給定的查詢字提供進一步的查詢標籤推薦，使能快速篩選找到所需資料。我們從包含查詢字為標籤的物件，以這些物件包含的所有標籤為候選標籤，評估與查詢字間的相關程度及和已推薦標籤的相異程度來決定一個標籤的關聯代表分數，再選擇分數值最高的前k個標籤為推薦查詢標籤。我們採用面相查詢的概念呈現推薦標籤，當使用者選擇特定推薦標籤後，系統將根據所選擇標籤推薦下一層可進一步篩選結果的查詢標籤，幫助使用者逐步縮小查詢結果涵蓋範圍。此外，本論文提出一個雙層式索引結構來加速社交標籤系統的查詢處理，而此索引結構也可支援可容錯的集合包含查詢處理。實驗結果顯示本研究方法可有效減少使用者搜尋資料所需的瀏覽成本，而所提出的索引結構亦可有效增進容錯集合包含查詢的處理效率，且對於關鍵字個數較多的查詢字效果越佳。

Most users are used to giving brief keywords to query a social-tagging system for getting the objects whose tag sets contain the given query keywords. When the query keyword is a general term, the system usually returns a lot of objects as the query result. Accordingly, the users have to spend much time to browse all the returned objects to get the data he needs. For solving this problem, this thesis proposes a query recommendation method for social tagging systems. According to the given query keyword, we study how to provide some more tags as additional query terms for helping the user to effectively filter the dataset to find the required data quickly. At first, we find out the query result which consists of all the objects whose tag sets contain the query keyword. All the tags of these objects are called candidate tags. Next, for each candidate tag, we consider the relatedness with the query and the diversity with the selected recommendation tags to decide its representation score. According to the representation scores, the top-k tags are chosen to be recommendation tags. Then we adopt the concept of facet search to present the recommended tags. After users choose a specific recommended tag, the system will add the chosen tag into the query and perform tag recommendation recursively. Furthermore, this thesis proposes a two-level index structure, which aggregate similar tag sets into clusters according to the similarity between tag sets. A two-level bounding mechanism is proposed to deal with query processing of tag set containment queries. Besides, the Jaccard Containment function is used to evaluate the degree of set containment for supporting set containment search with error tolerant allowed. The experimental results show that the proposed method of query recommendation can effectively reduce the cost of user-browsing. Moreover, the proposed two-level index structure and query processing strategies provide better performance on execution time for tag set containment queries, especially for queries consisting of many tags.

[1] J. Gemmell, A. Shepitsen, B. Mobasher and R. Burke , “Personalization in Folksonomies Based on Tag Clustering,” in Proceedings of the 23rd Association for the Advancement of Artificial Intelligence(AAAI), 2008.
[2] M. Gupta, R. Li, Z. Yin and J. Han , “Survey on Social Tagging Techniques,” in Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining(KDD), 2010.
[3] L. von Ahn and L. Dabbish , “Labeling Images with a Computer Game,” in Proceedings of the SIGCHI conference on Human factors in computing systems(CHI), 2004.
[4] H. Ma, R. Chandrasekar, C. Quirk and A. Gupta , “Improving Sea ch Engines Using Human Computation Games, ” in Proceedings of the 18th ACM conference on Information and knowledge management(CIKM), 2009.
[5] J. Chuang, C. Cho, A. Chen , “Similarity Search in Transaction Databases with a Two Level Bounding Mechanism,” in Proceedings of the 11th International Conference of Database Systems for Advanced Applications (DASFAA), 2006.
[6] N. Shongwe, “A Multi-level Hierarchical Index Structure for Supporting Efficient Similarity Search of Tagsets,” 國立臺灣師範大學, 碩士論文, 2011.
[7] P. Agrawal, A. Arasu and R. Kaushik, “On Indexing Error-Tolerant Set Containment,” in Proceedings of the ACM International Conference on Management of Data (SIGMOD), 2010.
[8] S. Golder and B. Huberman, “The Structure of Collaborative Tagging Systems,” in Proceedings of the 32nd International Journal of Information Science (IS), 2006.
[9] D. Lu and Q. Li, “Personalized Search on Flickr based on Searcher’s Preference Prediction,” in Proceedings of the 20th international conference companion on World wide web(WWW), 2011.
[10] J. Peng, D. D. Zeng, H. Zhao and F. Wang, “Collaborative filtering in social tagging systems based on joint item-tag recommendations,” in Proceedings of the 19th ACM international conference on Information and knowledge management(CIKM), 2010.
[11] D. Vandic, J.-W. v. Dam and F. Hogenboom, “A Semantic Clustering-Based Approach for Searching and Browsing Tag Spaces,” in Proceedings of the 26th ACM Symposium on Applied Computing(SAC), 2011.
[12] A. Sun, S. S. Bhowmick and J.-A. Chong, “Social image tag recommendation by concept matching,” in Proceedings of the 19th ACM international conference on Multimedia(MM), 2011.
[13] P. Venetis, G. Koutrika and H G-M, “On the selection of tags for tag clouds ,” in Proceedings of the fourth ACM international conference on Web search and data mining (WSDM), 2011.
[14] D. Skoutas and M. Alrifai, “Tag Clouds Revisited,” in Proceedings of the 20th ACM international conference on Information and knowledge management(CIKM), 2011.
[15] A.W. Rivadeneira, D. M. Gruen, M. J. Muller and D. R. Millen, “Getting Our Head in the Clouds Toward Evaluation Studies of Tagclouds,” in Proceedings of the SIGCHI conference on Human factors in computing systems(CHI), 2007.
[16] C. Li , N. Yan , S. B. Roy , L. Lisham and G. Das, “Facetedpedia: Dynamic Generation of Query-Dependent Faceted Interfaces for Wikipedia,” in Proceedings of the 19th international conference on World wide web(WWW), 2010.
[17] C. David, R. Haggai and Y. Elad, “Social bookmark weighting for search and recommendation,” in Proceedings of the 19th International Journal on Very Large Data Bases (VLDB), 2010.
[18] J. Fokker, J. Pouwelse and W. Buntine, “Tag-Based Navigation for Peer-to-Peer Wikipedia,” in Proceedings of the 15th international conference on World wide web(WWW), 2006.
[19] C. S. Mesnage and M. J. Carman, “Tag Navigation,” in Proceedings of the 2nd international workshop on Social software engineering and applications, 2009.
[20] T.-S. Chua, J. Tang, R. Hong, H. Li, Z. Luo, and Y.-T. Zheng. "NUS-WIDE: A Real-World Web Image Database from National University of Singapore", ACM International Conference on Image and Video Retrieval, 2009.
[21] J.-Y. Pan, H.-J. Yang, C. Faloutsos and P. Duygulu. “Automatic Multimedia Cross-modal Correlation Discovery,” in Proceedings of the 10th ACM SIGKDD international conference on Knowledge discovery and data mining(KDD), 2004.
[22] D. Dash, J. Rao, N. Megiddo, A. Ailamaki and Guy Lohman. Dynamic Faceted Search for Discovery-driven Analysis,” in Proceedings of the 17th ACM international conference on Information and knowledge management(CIKM), 2008.
[23] B. Zhao, X. Lin, B. Ding and J. Han. “TEXplorer: Keyword-based Object Search and Exploration in Multidimensional Text Databases,” in Proceedings of the 20th ACM international conference on Information and knowledge management(CIKM), 2011.
[24] Y. Cai and Q. Li. “Personalized Search by Tag-based User Profile and Resource Profile in Collaborative Tagging Systems,” in Proceedings of the 19th ACM international conference on Information and knowledge management(CIKM), 2010.
[25] X. Wu, L. Zhang and Yong Yu, “Exploring Social Annotations for the Semantic Web,” in Proceedings of the 15th international conference on World wide web(WWW), 2006.