Search

The semantics of UTop-kquery is based on the possible world model, and the greatest challenge in processing UTop-kqueries is the explosion of possible world space. In this direction, several optimized algorithms have been developed. However, uncertain databases are different in data distributions under different scoring functions, which has significant influence on the performance of the existing optimizing algorithms. In this paper, we propose two novel algorithms, MSSUTop-kand quick MSSUTop-k, for determining the minimum scan scope for UTop-kquery processing. This work is important because before UTop-kquery processing is started, users hope to know in advance how many and which tuples will be involved in UTop-kquery processing. Then, they can make a balance between result precision and processing cost. So, it should be the prerequisite for answering UTop-kqueries. MSSUTop-kcan achieve accurate results but is relatively more costly in time complexity. Oppositely, quick MSSUTop-kcan only achieve approximate results but performs better in time cost. We conduct comprehensive experiments to evaluate the performance of our proposed algorithms and analyze the relationship between the data distribution and the minimum scan scope of UTop-kqueries.

The result of U-Topk query simply consist of k tuples, which is not satisfactory in many cases mainly for the following two reasons: firstly, the probability of result is so small that it is hard for users to accept it, secondly, it abandons the relations between the tuples and the corresponding entities, accordingly it can't completely reflect the real state of monitored entities. Aiming at shortage of tuple-oriented semantic of U-Topk query, this paper proposes an entity-oriented U-Topk query named as EoU-Topk as well as query processing algorithm. The basic idea of the algorithm is converting tuple-oriented probabilistic database into entity-oriented probabilistic database. In this process, some exclusive tuples that meet the pre-defined rules will be merged. The algorithm of EoU-Topk query has two advantage: firstly, it can greatly reduce the size of probabilistic database, secondly, it can truly reflect whole state of entities, and avoid the one sidedness of the tuple-oriented U-Topk query. Finally, the efficiency and quality of the EoU-Topk query proposed in the paper are verified by experiments using real data.

Recently, Point of Interest Recommendation is widely used in LBS navigation systems. It makes use of the real-time GPS locations of users as well as their preferences to recommend POIs that mostly match these preferences and the paths leading to the POIs. Previous studies are focused on the following two issues: (1) Similarity measurement between POIs and the user preferences, and (2) Optimum path selection from the user location to the recommended POIs. However in most scenarios, users need not only some isolated POIs, but a combination of several POIs that covers the user preferences as well as the paths connecting them. Essentially, it is the schedule planning problem. Schedule planning is usually with strict time limits, and equivalent to Generalized Traveling Sales Man Problem (GTSP) which was proved a NP-hard problem. This imposes great challenge to its solution. In this paper, we formalize the problem of Schedule Planning with strict Time Constraint (SPwTC). Especially, we wrap the static paths between POIs into route activities, thus a globally unified model of user activity can be defined. Based on Genetic Algorithm, we propose the schedule recommendation algorithm to generate candidate route plans. Subsequently, we propose the recommendation function for sorting the recommended schedule plans so as to make the recommended result more in line with user expectation. At the end of this paper, we verify the efficiency of the algorithm as well as its rationality of the recommended result with real road network data.

The semantic of UTop-k query is based on the possible world model, and the greatest challenge in processing UTop-k queries is the explosion of possible world space. In this paper, we propose two novel algorithms, MSSUTop-k and Quick MSSUTop-k, for determining the minimum scan scope for UTop-k query processing. MSSUTop-k can achieve accurate results, but have more costly in time complexity. Oppositely, Quick MSSUTop-k achieve approximate results, and performs better in time cost. We conduct extensive experiments to evaluate the performance of our proposed algorithms, and analyze the relationship between score distribution and the minimum scan scope of UTop-k queries.

With the advances in technology of CPS (Cyper Physical System), it is found that uncertain data arises in many important domains, such as WSN, RFID, P2P system, and so on. It poses a great challenge on Top-k query processing, which is a very common and crucial application in data management. In this paper, we summarize several semantics of top-k queries on uncertain data and propose an optimized algorithm DMPUTop-k for processing most probable uncertain Top-k queries(MPUTop-k) in the distributed environment. In addition, we analyze the equivalence between MPUTop-k and UTop-k in some special cases. The experiments on real dataset show that our technique can greatly reduce the bandwidth consumption for processing Top-k queries in distributed uncertain dataset.

Web topic detection is a crucial prerequisite to web-based data integration and also a key component for Vertical Search Engine. So, it attracts much attention from not only the industry but also the literature. In this paper, we proposed a domain-lexicon-based framework for Web topic detection. In our framework, we extracted the topical features from the web page first. Next, we employed Vector Space Model(VSM) and Support Vector Machine (SVM) to compute the topical relevance between the Web page features and the domain that the user prefers so as to conclude whether the web page satisfies the user's request. Vector Space Model is suitable for the domains where the corresponding domain lexicons need to be updated frequently. Oppositely, Support Vector Machine is suitable for the domains where the corresponding domain lexicons are relatively unchangeable. Moreover, in this work we also explored the mechanism of domain lexicon updating, which can guarantee the accuracy and freshness of the domain lexicon. Finally, we conducted extensive experiment to test our framework and analyze how the domain lexicon affects the judgement result.