Abstract

Sponsored search has emerged as one of the most dominant forms for advertising on the Web. In sponsored search, advertisers create ad campaigns and bid on the keywords of potential search queries related to a given product or service. It has been observed that search queries follow a long-tail distribution of a small yet fat head of frequent queries and a long and thin tail of infrequent queries. Normally, the advertisers tend to bid on frequent keywords related to search queries. As a result, the ad space of the tail portion of search queries is harder to exploit. In this paper, we have proposed an improved allocation approach to utilize the ad space of the tail keywords related to search queries based on the knowledge of coverage patterns extracted from the transactions formed from search query logs. The advertisers bid on potential concepts represented by coverage patterns which consist of a combination of head and tail keywords. By facilitating the advertisers to bid on the concepts, the proposed approach improves the ad space utilization of tail queries. Experiments on the real-world dataset of search query logs demonstrate that the proposed approach indeed improves the performance of search engine advertising by improving ad space utilization of tail queries.

Abstract

Visibility computation is critical in spatial databases for realizing various interesting and diverse applications such as defence-related surveillance, identifying interesting spots in tourist places and online warcraft games. Existing works address the problem of identifying individual locations for maximizing the visibility of a given target object. However, in case of many applications, a set of locations may be more effective than just individual locations towards maximizing the visibility of the given target object. In this paper, we introduce the Multi-Location Visibility (MLV) query. An MLV query determines the top-k query locations from which the visibility of a given target object can be maximized. We propose a portion-based transactional framework and coverage pattern mining based algorithm to process MLV queries. Our performance evaluation with real datasets demonstrates the effectiveness of the proposed scheme in terms of query processing time, pruning efficiency and target object visibility w.r.t. a recent existing scheme.

Abstract

Pattern mining is an important task of data mining and involves the extraction of interesting associations from large databases. Typically, pattern mining is carried out from huge databases, which tend to get updated several times. Consequently, as a given database is updated, some of the patterns discovered may become invalid, while some new patterns may emerge. This has motivated significant research efforts in the area of Incremental Mining. The goal of incremental mining is to efficiently and incrementally mine patterns when a database is updated as opposed to mining all of the patterns from scratch from the complete database. Incidentally, research efforts are being made to develop incremental pattern mining algorithms for extracting different kinds of patterns such as frequent patterns, sequential patterns and utility patterns. However, none of the existing works addresses incremental mining in the context of coverage patterns, which has important applications in areas such as banner advertising, search engine advertising and graph mining. In this regard, the main contributions of this work are three-fold. First, we introduce the problem of incremental mining in the context of coverage patterns. Second, we propose the IncCMine algorithm for efficiently extracting the knowledge of coverage patterns when incremental database is added to the existing database. Third, we performed extensive experiments using two real-world click stream datasets and one synthetic dataset. The results of our performance evaluation demonstrate that our proposed IncCMine algorithm indeed improves the performance significantly w.r.t. the existing CMine algorithm. Index Terms—Data mining, Coverage patterns, Incremental mining, Knowledge discovery

Abstract

Finding (partial) periodic patterns in time series data is a challenging problem of great importance in many applications. Due to computational reasons, most previous studies in this area have focused on the efficient discovery of periodic patterns in regular time series data. Unfortunately, these studies have limited applicability because real-world data naturally exists as an irregular time series. This paper proposes a more flexible model of periodic pattern that may be present in irregular time series. Two measures, period and period-support, were employed to determine the interestingness of a pattern in a series. The former measure captures the inter-arrival times of a pattern in a series, while the latter captures the number of periodic occurrences of a pattern in a series. A novel tree structure, called Periodic Pattern tree (PP-tree), has been introduced to record the irregular occurrences of items within the series. A pattern-growth algorithm has also been presented to find all periodic patterns from PP-tree. Experimental results demonstrate that the proposed model can find useful information, and the algorithm is efficient.

Abstract

Spatial High Utility Itemset Mining (SHUIM) aims to discover all itemsets in a spatiotemporal database that satisfy the userspecified minimum utility (minU til) and maximum distance (maxDist) constraints. The popular adoption and successful industrial application of SHUIM suffers from the following two limitations: (i) Since SHUIM determines the interestingness of an itemset without taking into account its support with in the data, it is sensitive to the random noise and length of the transactions within the data. Consequently, SHUIM facilitates sporadic itemsets with high utility to be generated as SHUIs. For instance, items in long transactions can combine with each other and be generated as SHUIs. (ii) SHUIM is a computationally expensive process because the generated itemsets do not satisfy the downward closure property. This paper introduces Spatial High Utility Frequent Itemset Mining (SHUFIM) to address these two issues. A SHUI in a spatiotemporal database is said to be a SHUFI if and only if its support is no less than the user-specified minimum support (minSup) constraint. The usage of minSup not only facilitates the proposed model to be tolerant to the random noise within the data, but also facilitate us to employ additional pruning techniques to reduce the computational cost. A single scan fast algorithm has also been proposed to discover all SHUFIs in a spatiotemporal database. Experimental results demonstrate that the proposed algorithm is efficient. We also demonstrate the usefulness of the proposed model with two real-world applications.

Abstract

t. In addition to maximizing the revenue, retailers also aim at diversifying product offerings for facilitating sustainable revenue generation in the long run. Thus, it becomes a necessity for retailers to place appropriate itemsets in a limited k number of premium slots in retail stores for achieving the goals of revenue maximization and itemset diversification. In this regard, research efforts are being made to extract itemsets with high utility for maximizing the revenue, but they do not consider itemset diversification i.e., there could be duplicate (repetitive) items in the selected top-utility itemsets. Furthermore, given utility and support thresholds, the number of candidate itemsets of all sizes generated by existing utility mining approaches typically explodes. This leads to issues of memory and itemset retrieval times. In this paper, we present a framework and schemes for efficiently retrieving the top-utility itemsets of any given itemset size based on both revenue as well as the degree of diversification. Here, higher degree of diversification implies less duplicate items in the selected top-utility itemsets. The proposed schemes are based on efficiently determining and indexing the topλ high-utility and diversified itemsets. Experiments with a real dataset show the overall effectiveness and scalability of the proposed schemes in terms of execution time, revenue and degree of diversification w.r.t. a recent existing scheme.

Abstract

Many domain specific decisions of our day-to-day lives are dependent on weather. Weather and its variables have a significant impact on crop gro wth stages and crop producti vity.Weather forecast service has been started by In dia Meteorological Department (IMD) from the year 1945. To help the farming community, IMD has started pro viding district level agro-meteorological advisory based on the district-level Medium Range Forecast (MRF) f rom the year2008 fo r all districts through 130 agro-meteorological field units (AMFUs). Based on the MRF for five days, each AMFU is providing crop-s pecific agromet advice for the districts covered by that AMFU. To impro ve the effectiveness, IMD has started block level MRF on an experimental basis from the year 2015. Based on block level MRF, IMD is planning to provide block-level agromet advisory based on the block-level MRF. In such a situation, agromet scientisst haveto prepare agromet advisory for several blocks and crops at the earliest after receiving the block level MRF which will be disseminated to the farmers and stakeholders. In this context, research efforts have to be made to develop efficient system to enable agromet scientists to prepare the block-level agromet advice based on the block-level MRF. Normally, it can be observed that the weather and cro ps of nearby blocks may not vary significantly. S o, there is an opportunity to reuse the agromet advice prepared for one block to the nearby blocks. In this paper, we have pro posed an IT- based framewo rk to enable the agromet scientists to prepare the block level agromet advisoryby exploitingthe fact that the agromet advice which has been prepared for one block can be reused for another block if the weather condition and the crop is the same. The proposed framework pro vides the scope to exploit the reuse of agromet advisory prepared for one block toother blocks and could improve the efficiency of agromet scientists for the preparation of block-level agromet advisory based on the MRF

Abstract

Weather-based decision support systems (DSSs) are being built to improve the efficiency of the production systems in the domains of healthcare, agriculture, transport, governance and so on. Normally, a weather con-dition (WC) is represented by the statistical values of weather variables for a given duration (e.g. a day or a week). In a weather-based DSS, given a WC, the domain experts prepare the appropriate suggestions to improve the efficiency of the stakeholders. Normally, once the domain experts prepare a suggestion for a given WC that belongs to certain period (e.g. year or season), there is a scope to reuse the same suggestion for the similar WCs of other period(s). As a result, the performance of the DSS could be improved. In this paper, to improve reuse, we have proposed a notion of category-based WC (CWC) which is formed by using the categories of weather variables in the respective domain. By considering the context of agromet advisory service operated by India Meteorological Department (IMD) and the corresponding weather categories provided by IMD, we have ana-lyzed the extent of reuse among CWCs by conducting the experiments on 30 years of weather data collected at Rajendranagar, Hyderabad, Telangana state. The experiments are conducted by considering two types of CWCs with the duration equal to one day and five days. By varying the number of weather variables in CWC from one to five, we have computed the extent of reuse among CWCs of different periods of the following period types: year, season, and phenophases (i.e., growth stages) of the Rice crop. The results show that there is a significant similarity among the CWCs of the given period and the CWCs of the preceding periods of each period type. For any domain including agriculture, the results provide an opportunity to improve the efficiency of weather-based agricultural DSSs by improving the reuse of the weather-based suggestions

Abstract

Preablative stimulated thyroglobulin (ps‑Tg) is an important investigation in the follow‑up of patients with Differentiated thyroid cancer(DTC) after surgery. Levels of ps‑Tg >2–10 ng/ml have been suggested to predict metastasis to cervical and extracervical sites. There is still debate on the need for routine iodine whole‑body scan (131I WBS) in the management of low‑to‑intermediate‑risk DTC patients. Objective: We analyzed our data of patients with DTC who underwent total thyroidectomy to discuss the predictability of ps‑Tg on metastatic disease on the 131I WBS. Materials and Methods: Retrospective analysis of patient records. Results: One hundred and seventeen patients with DTC (95 papillary thyroid cancer [71 had classic histology, 8 had tall cell variant, 16 had follicular variant] and 22 follicular thyroid cancer [18 minimally invasive, 2 hurtle cell, and 2 widely invasive cancers]) had undergone total thyroidectomy. All these patients underwent ps‑Tg assessment and an 131I WBS. About 65% of them went on to have radioiodine ablation along with a posttherapy 131I WBS. We divided the cohort into four groups based on their ps‑Tg levels: Group 1 (ps‑Tg <1), Group 2 (ps‑Tg 1–1.9), Group 3 (ps‑Tg 2–5), and Group 4 (ps‑Tg >5). None of the patients in Group 1, 7% of those combined in Groups 2 and 3 (2 out of 28 patients), and 26% (12 out of 47) of those in Group 4 had either cervical or extracervical metastasis. Those with extracervical metastatic disease to lungs and bones had a mean (standard deviation) ps‑Tg value of 436 (130) and median of 500 ng/ml and those with cervical metastatic disease had a mean Tg value of 31 (64) and median 6.6 ng/ml. Conclusions: A ps‑Tg value in the absence of anti‑Tgantibodies <1 ng/ml reliably excludes metastatic disease in DTC, while a value >5 ng/ml has a 26% risk of having either cervical or extracervical metastasis.

Abstract

Efficient discovery of interesting patterns using parallel algorithms is an actively studied topic in data mining. A key research issue related to this topic is data segmentation, which influences the overall computational requirements of an algorithm. This paper makes an effort to address this issue in correlated pattern mining. Two novel data segmentation techniques, ‘database segmentation’ and ‘transaction segmentation,’ have been introduced to discover the patterns efficiently. The former technique involves segmenting the database into multiple sub-databases such that each sub-database can be mined independently. The latter technique involves segmenting a transaction into multiple sub-transactions such that each sub-transaction can be processed as an individual transaction. The proposed techniques are algorithm independent, and therefore, can be incorporated into any parallel algorithm to find correlated patterns effectively. In this paper, we introduce map-reduce based pattern-growth algorithm by incorporating the above mentioned techniques. Experimental results demonstrate that the proposed algorithm is memory and runtime efficient and highly scalable as well.