Volatility, as a measure of uncertainty, plays a crucial role in numerous financial activities such as risk management. The Econometrics and Machine Learning communities have developed two distinct approaches for financial volatility forecasting: the stochastic approach and the neural network (NN) approach. Despite their individual strengths, these methodologies have conventionally evolved in separate research trajectories with little interaction between them. This study endeavors to bridge this gap by establishing an equivalence relationship between models of the GARCH family and their corresponding NN counterparts. With the equivalence relationship established, we introduce an innovative approach, named GARCH-NN, for constructing NN-based volatility models. It obtains the NN counterparts of GARCH models and integrates them as components into an established NN architecture, thereby seamlessly infusing volatility stylized facts (SFs) inherent in the GARCH models into the neural network. We develop the GARCH-LSTM model to showcase the power of GARCH-NN approach. Experiment results validate that amalgamating the NN counterparts of the GARCH family models into established NN models leads to enhanced outcomes compared to employing the stochastic and NN models in isolation.

Traditional recommender systems are typically passive in that they try to adapt their recommendations to the user’s historical interests. However, it is highly desirable for commercial applications, such as e-commerce, advertisement placement, and news portals, to be able to expand the users’ interests so that they would accept items that they were not originally aware of or interested in to increase customer interactions. In this paper, we present Influential Recommender System (IRS), a new recommendation paradigm that aims to proactively lead a user to like a given objective item by progressively recommending to the user a sequence of carefully selected items (called an influence path). We propose the Influential Recommender Network (IRN), which is a Transformer-based sequential model to encode the items’ sequential dependencies. Since different people react to external influences differently, we introduce the Personalized Impressionability Mask (PIM) to model how receptive a user is to external influence to generate the most effective influence path for the user. To evaluate IRN, we design several performance metrics to measure whether or not the influence path can smoothly expand the user interest to include the objective item while maintaining the user’s satisfaction with the recommendation. Experimental results show that IRN significantly outperforms the baseline recommenders and demonstrates its capability of influencing users’ interests.

Financial assets exhibit dependence structures, i.e., movements of their prices or returns show various correlations. Knowledge of assets’ price dependencies can help investors to create a diversified portfolio, aiming to reduce portfolio risk due to the high volatility of the financial market. Since asset dependency changes with time in complex patterns, asset dependency forecast is an essential problem in finance. In this paper, we organize pairwise assets dependencies in an Asset Dependency Matrix (ADM) and formulate the problem of assets dependencies forecast to predict the future ADM given a sequence of past ADMs. We propose a novel idea viewing a sequence of ADMs as a sequence of images to capture the spatial and temporal dependencies among the assets. Inspired by video prediction tasks, we develop a novel Asset Dependency Neural Network (ADNN) to tackle the ADM prediction problem. Experiments show that our proposed framework consistently outperforms baselines on both future ADM prediction and portfolio risk reduction tasks.

Breast cancer has become the leading cause of women cancer death worldwide. Despite the consensus that breast cancer early detection can significantly reduce treatment difficulty and cancer mortality, people still are reluctant to go to hospital for regular checkups due to the high costs incurred. A timely, private, affordable, and effective household breast cancer early detection solution is badly needed. In this paper, we propose a household solution that utilizes pairs of sensors embedded in the bra to measure the thermal and moisture time series data (BTMTSD) of the breast surface and conduct time series classification (TSC) to diagnose breast cancer. Three main challenges are encountered when doing BTMTSD classification, (1) small supervised dataset, which is a common limitation of medical research, (2) noisy time series with unique noise patterns, and (3) complex interplay patterns across multiple time series dimensions. To mitigate these problems, we incorporate multiple data augmentation and transformation techniques with various deep learning TSC approaches and compare their performances for the BTMTSD classification task. Experimental results validate the effectiveness of our framework in providing reliable breast cancer early detection.

Collaborative filtering (CF) has been one of the most important and popular recommendation methods, which aims at predicting users’ preferences (ratings) based on their past behaviors. Recently, various types of side information beyond the explicit ratings users give to items, such as social connections among users and metadata of items, have been introduced into CF and shown to be useful for improving recommendation performance. However, previous works process different types of information separately, thus failing to capture the correlations that might exist across them. To address this problem, in this work, we study the application of heterogeneous information network (HIN), which offers a unifying and flexible representation of different types of side information, to enhance CF-based recommendation methods. However, we face challenging issues in HIN-based recommendation, i.e., how to capture similarities of complex semantics between users and items in a HIN, and how to effectively fuse these similarities to improve final recommendation performance. To address these issues, we apply metagraph to similarity computation and solve the information fusion problem with a “matrix factorization (MF) + factorization machine (FM)” framework. For the MF part, we obtain the user-item similarity matrix from each metagraph and then apply low-rank matrix approximation to obtain latent features for both users and items. For the FM part, we apply FM with Group lasso (FMG) on the features obtained from the MF part to train the recommending model and, at the same time, identify the useful metagraphs. Besides FMG, a two-stage method, we further propose an end-to-end method, hierarchical attention fusing, to fuse metagraph-based similarities for the final recommendation. Experimental results on four large real-world datasets show that the two proposed frameworks significantly outperform existing state-of-the-art methods in terms of recommendation performance.

PageRank has been widely used to measure the authority or the influence of a user in social networks. However, conventional PageRank only makes use of edge-based relations, which represent first-order relations between two connected nodes. It ignores higher-order relations that may exist between nodes. In this article, we propose a novel framework, motif-based PageRank (MPR), to incorporate higher-order relations into the conventional PageRank computation. Motifs are subgraphs consisting of a small number of nodes. We use motifs to capture higher-order relations between nodes in a network and introduce two methods, one linear and one non-linear, to combine first-order and higher-order relations in PageRank computation. We conduct extensive experiments on three real-world networks, namely, DBLP, Epinions, and Ciao. We study different types of motifs, including 3-node simple and anchor motifs, 4-node and 5-node motifs. Besides using single motif, we also run MPR with ensemble of multiple motifs. We also design a learning task to evaluate the abilities of authority prediction with motif-based features. All experimental results demonstrate that MPR can significantly improve the performance of user ranking in social networks compared to the baseline methods.

In recent years, embedding models based on skip-gram algorithm have been widely applied to real-world recommendation systems (RSs). When designing embedding-based methods for recommendation at Taobao, there are three main challenges: scalability, sparsity and cold start. The first problem is inherently caused by the extremely large numbers of users and items (in the order of billions), while the remaining two problems are caused by the fact that most items have only very few (or none at all) user interactions. To address these challenges, in this work, we present a flexible and highly scalable Side Information (SI) enhanced Skip-Gram (SISG) framework, which is deployed at Taobao. SISG overcomes the drawbacks of existing embedding-based models by modeling user metadata and capturing asymmetries of user behavior. Furthermore, as training SISG can be performed using any SGNS implementation, we present our production deployment of SISG on a custom-built word2vec engine, which allows us to compute item and SI embedding vectors for billion-scale sets of products in a join semantic space on a daily basis. Finally, using offline and online experiments we demonstrate the significant superiority of SISG over our previously deployed framework, EGES, and a well-tuned CF, as well as present evidence supporting our scalability claims.

Industrial recommender systems have embraced deep learning algorithms for building intelligent systems to make accurate recommendations. At its core, deep learning offers powerful ability for learning representations from data, especially for user and item representations. Existing deep learning-based models usually represent a user by one representation vector, which is usually insufficient to capture diverse interests for large-scale users in practice. In this paper, we approach the learning of user representations from a different view, by representing a user with multiple representation vectors encoding the different aspects of the user's interests. To this end, we propose the Multi-Interest Network with Dynamic routing (MIND) for learning user representations in recommender systems. Specifically, we design a multi-interest extractor layer based on the recently proposed dynamic routing mechanism, which is applicable for modeling and extracting diverse interests from user's behaviors. Furthermore, a technique named label-aware attention is proposed to help the learning process of user representations. Through extensive experiments on several public benchmarks and one large-scale industrial dataset from Tmall, we demonstrate that MIND can achieve superior performance than state-of-the-art methods in terms of recommendation accuracy. Currently, MIND has been deployed for handling major online traffic at the homepage on Mobile Tmall App.

Heterogeneous Information Networks (HIN) has been widely used in recommender systems (RSs). In previous HIN-based RSs, meta-path is used to compute the similarity between users and items. However, existing meta-path based methods only consider first-order relations, ignoring higher-order relations among the nodes ofsame type, captured bymotifs. In this paper, we propose to use motifs to capture higher-order relations among nodes of same type in a HIN and develop the motif-enhanced meta-path (MEMP) to combine motif-based higher-order relations with edge-based first-order relations. With MEMP-based similarities between users and items, we design a recommending model MoHINRec, and experimental results on two real-world datasets, Epinions and CiaoDVD, demonstrate its superiority over existing HIN-based RS methods.

As an ensemble model that consists of many independent decision trees, random forests generate predictions by feeding the input to internal trees and summarizing their outputs. The ensemble nature of the model helps random forests outperform any individual decision tree. However, it also leads to a poor model interpretability, which significantly hinders the model from being used in fields that require transparent and explainable predictions, such as medical diagnosis and financial fraud detection. The interpretation challenges stem from the variety and complexity of the contained decision trees. Each decision tree has its unique structure and properties, such as the features used in the tree and the feature threshold in each tree node. Thus, a data input may lead to a variety of decision paths. To understand how a final prediction is achieved, it is desired to understand and compare all decision paths in the context of all tree structures, which is a huge challenge for any users. In this paper, we propose a visual analytic system aiming at interpreting random forest models and predictions. In addition to providing users with all the tree information, we summarize the decision paths in random forests, which eventually reflects the working mechanism of the model and reduces users' mental burden of interpretation. To demonstrate the effectiveness of our system, two usage scenarios and a qualitative user study are conducted.

PageRank has been widely used to measure the authority or the influence of a user in social networks. However, conventional PageRank only makes use of edge-based relations, ignoring higher-order structures captured by motifs, subgraphs consisting of a small number of nodes in complex networks. In this paper, we propose a novel framework, motif-based PageRank (MPR), to incorporate higher-order structures into conventional PageRank computation. We conduct extensive experiments in three real-world networks, i.e., DBLP, Epinions, and Ciao, to show that MPR can significantly improve the effectiveness of PageRank for ranking users in social networks. In addition to numerical results, we also provide detailed analysis for MPR to show how and why incorporating higher-order information works better than PageRank in ranking users in social networks.

Recommender systems (RSs) have been the most important technology for increasing the business in Taobao, the largest online consumer-to-consumer (C2C) platform in China. There are three major challenges facing RS in Taobao: scalability, sparsity and cold start. In this paper, we present our technical solutions to address these three challenges. The methods are based on a well-known graph embedding framework. We first construct an item graph from users' behavior history, and learn the embeddings of all items in the graph. The item embeddings are employed to compute pairwise similarities between all items, which are then used in the recommendation process. To alleviate the sparsity and cold start problems, side information is incorporated into the graph embedding framework. We propose two aggregation methods to integrate the embeddings of items and the corresponding side information. Experimental results from offline experiments show that methods incorporating side information are superior to those that do not. Further, we describe the platform upon which the embedding methods are deployed and the workflow to process the billion-scale data in Taobao. Using A/B test, we show that the online Click-Through-Rates (CTRs) are improved comparing to the previous collaborative filtering based methods widely used in Taobao, further demonstrating the effectiveness and feasibility of our proposed methods in Taobao's live production environment.

Skyline queries have wide-ranging applications in fields that involve multi-criteria decision making, including tourism, retail industry, and human resources. By automatically removing incompetent candidates, skyline queries allow users to focus on a subset of superior data items (i.e., the skyline), thus reducing the decision-making overhead. However, users are still required to interpret and compare these superior items manually before making a successful choice. This task is challenging because of two issues. First, people usually have fuzzy, unstable, and inconsistent preferences when presented with multiple candidates. Second, skyline queries do not reveal the reasons for the superiority of certain skyline points in a multi-dimensional space. To address these issues, we propose SkyLens, a visual analytic system aiming at revealing the superiority of skyline points from different perspectives and at different scales to aid users in their decision making. Two scenarios demonstrate the usefulness of SkyLens on two datasets with a dozen of attributes. A qualitative study is also conducted to show that users can efficiently accomplish skyline understanding and comparison tasks with SkyLens.

Matrix Factorization (MF) is a very popular method for recommendation systems. It assumes that the underneath rating matrix is low-rank. However, this assumption can be too restrictive to capture complex relationships and interactions among users and items. Recently, Local LOw-Rank Matrix Approximation (LLORMA) has been shown to be very successful in addressing this issue. It just assumes the rating matrix is composed of a number of low-rank submatrices constructed from subsets of similar users and items. Although LLORMA outperforms MF, how to construct such submatrices remains a big problem. Motivated by the availability of rich social connections in today's recommendation systems, we propose a novel framework, i.e., Social LOcal low-rank Matrix Approximation (SLOMA), to address this problem. To the best of our knowledge, SLOMA is the first work to incorporate social connections into the local low-rank framework. Furthermore, we enhance SLOMA by applying social regularization to submatrices factorization, denoted as SLOMA++. Therefore, the proposed model can benefit from both social recommendation and the local low-rank assumption. Experimental results from two real-world datasets, Yelp and Douban, demonstrate the superiority of the proposed models over LLORMA and MF.

Heterogeneous Information Network (HIN) is a natural and general representation of data in modern large commercial recommender systems which involve heterogeneous types of data. HIN based recommenders face two problems: how to represent the high-level semantics of recommendations and how to fuse the heterogeneous information to make recommendations. In this paper, we solve the two problems by first introducing the concept of meta-graph to HIN-based recommendation, and then solving the information fusion problem with a "matrix factorization (MF) + factorization machine (FM)" approach. For the similarities generated by each meta-graph, we perform standard MF to generate latent features for both users and items. With different meta-graph based features, we propose to use FM with Group lasso (FMG) to automatically learn from the observed ratings to effectively select useful meta-graph based features. Experimental results on two real-world datasets, Amazon and Yelp, show the effectiveness of our approach compared to state-of-the-art FM and other HIN-based recommendation algorithms.

Traditional recommendation systems (RS's) aim to recommend items that are relevant to the user's interest. Unfortunately, the recommended items will soon become too familiar to the user and hence fail to arouse her interest. Discovery-oriented recommendation systems (DORS's) complement accuracy with "discover utilities" (DU's) such as novelty and diversity and optimize the tradeoff between the DU's and accuracy of the recommendations. Unfortunately, DORS's ignore an important fact that different users have different appetites for DU's. That is, highly curious users can accept highly novel and diversified recommendations whereas conservative users would behave in the opposite manner. In this paper, we propose a curiosity-based recommendation system (CBRS) framework which generates recommendations with a personalized amount of DU's to fit the user's curiosity level. The major contribution of this paper is a computational model of user curiosity, called Probabilistic Curiosity Model (PCM), which is based on the curiosity arousal theory and Wundt curve in psychology research. In PCM, we model a user's curiosity with a curiosity distribution function learnt from the user's access history and compute a curiousness score for each item representing how curious the user is about the item. CBRS then selects items which are both relevant and have high curiousness score, bounded by the constraint that the amount of DU's fits the user's DU appetite. We use joint optimization and co-factorization approaches to incorporate the curiosity signal into the recommendations. Extensive experiments have been performed to evaluate the performance of CBRS against the baselines using a music dataset from last.fm. The results show that compared to the baselines CBRS not only provides more personalized recommendations that adapt to the user's curiosity level but also improves the recommendation accuracy.

The semantic network is a form of knowledge that represents various relationships between concepts with ambiguity. The knowledge can be employed to identify semantically related objects. It helps, for example, a recommender system to generate effective recommendations to the users. We propose to study a new semantic network, namely, the Concept Relation Network (CRN) , which is efficiently constructed and maintained using existing web search engines. CRN tackles the uncertainty and dynamics of web content, and thus is optimized for many important web applications, such as social networks and search engines. It is a large semantic network for the collection, analysis, and interpretation of web content, and serves as a cornerstone for applications such as web search engines, recommendation systems, and social networks that can benefit from a large-scale knowledge base. In this article, we present two applications for CRN: (1) search engine and web analytic and (2) semantic information retrieval. Experimental results show that CRN effectively enhances these applications by considering the heterogenous and polysemous nature of web content.

This paper studies the problem of querying Bounded Spatial Datasets (BSDs). A BSD contains i) objects with known locations, and ii) unknown regions, each of which bounds an unknown number of objects, within a coverage area. We consider applications where each BSD is hosted on a server or site connected to a communication network and the BSDs overlap in their coverage areas. The challenge is to query the distributed BSDs to retrieve all objects and to minimize the unknown regions which may contain objects satisfying the query, while minimizing the data transmission volume and number of interactions between the query client and the sites. We develop query processing algorithms for two important types of spatial queries, namely, range and k-nearest-neighbor (kNN) queries. We develop the site-based approach and the area-based approach for efficiently processing range and kNN queries on distributed BSDs. They aim to process only a subset of the sites to obtain the full answer for a query. Thus, optimal site selection and the corresponding site querying methods are important problems studied in this paper. In the area-based approach, we prove an optimal division and derive a practical heuristic to partition a query and select the best processing site for each partition, hence achieving even better efficiency than the site-based approach. Simulation results based on three real spatial datasets show that our proposed approaches significantly outperform the baseline that uses a centralized approach in terms of data transmission volume and the number of interactions between the query client and the distributed sites.

We propose a personalized mobile search engine (PMSE) that captures the users' preferences in the form of concepts by mining their clickthrough data. Due to the importance of location information in mobile search, PMSE classifies these concepts into content concepts and location concepts. In addition, users' locations (positioned by GPS) are used to supplement the location concepts in PMSE. The user preferences are organized in an ontology-based, multifacet user profile, which are used to adapt a personalized ranking function for rank adaptation of future search results. To characterize the diversity of the concepts associated with a query and their relevances to the user's need, four entropies are introduced to balance the weights between the content and location facets. Based on the client-server model, we also present a detailed architecture and design for implementation of PMSE. In our design, the client collects and stores locally the clickthrough data to protect privacy, whereas heavy tasks such as concept extraction, training, and reranking are performed at the PMSE server. Moreover, we address the privacy issue by restricting the information in the user profile exposed to the PMSE server with two privacy parameters. We prototype PMSE on the Google Android platform. Experimental results show that PMSE significantly improves the precision comparing to the baseline.

In this paper, we introduce the notion of sufficient set and necessary set for distributed processing of probabilistic top-k queries in cluster-based wireless sensor networks. These two concepts have very nice properties that can facilitate localized data pruning in clusters. Accordingly, we develop a suite of algorithms, namely, sufficient set-based (SSB), necessary set-based (NSB), and boundary-based (BB), for intercluster query processing with bounded rounds of communications. Moreover, in responding to dynamic changes of data distribution in the network, we develop an adaptive algorithm that dynamically switches among the three proposed algorithms to minimize the transmission cost. We show the applicability of sufficient set and necessary set to wireless sensor networks with both two-tier hierarchical and tree-structured network topologies. Experimental results show that the proposed algorithms reduce data transmissions significantly and incur only small constant rounds of data communications. The experimental results also demonstrate the superiority of the adaptive algorithm, which achieves a near-optimal performance under various conditions.

Personalized search is an important means to improve the performance of a search engine. In this article, we propose a framework that supports mining a user's conceptual preferences from users' clickthrough data resulting from Web search. The discovered preferences are utilized to adapt a search engine's ranking function. In this framework, an extended set of conceptual preferences was derived for a user based on the concepts extracted from the search results and the clickthrough data. Then, a concept-based user profile (CUP) representing the user profile as a concept ontology tree is generated. Finally, the CUP is input to a support vector machine (SVM) to learn a concept preference vector for adapting a personalized ranking function that reranks the search results. In order to achieve more flexible personalization, the framework allows a user to control the amount of specific CUP ontology information to be exposed to the personalized search engine. We study various parameters, such as conceptual relationships and concept features, arising from CUP that affect the ranking quality. Experiments confirm that our approach is able to significantly improve the retrieval effectiveness for the user. Further, our proposed control parameters of CUP information can adjust the exposed user information more smoothly and maintain better ranking quality than the existing methods.

Search engines are very effective in finding relevant pages for a query. When a query is ambiguous, the search engine returns a mix of results for different semantic interpretations of the query. This paper proposes a method to extract concepts from the search results of a query, and, treating each retrieved concept as a query, it recursively constructs a network of concepts related to different semantic interpretations of the query. By connecting networks of concepts obtained from different queries, a large integrated network, called Concept Relation Network (CRN), is formed. CRN is a semantic network that can be automatically constructed and maintained using existing search engines (e.g., Google) on the web. Taking advantage of large scale commercial search engines, CRN is able to derive a large number of highly coherent, highly related concepts. We study several ways to weight the connections between the concepts in CRN. By distinguishing between location concepts and content concepts, we analyze the ambiguity of each type of concepts individually. We also propose to extract concept clusters from CRN based on different graph topology. We observe that complete subgraphs in CRN can be used to effectively determine semantically related concepts. Finally, we apply CRN to search engine personalization. Experimental results show that the application of CRN to a concept-based personalization algorithm significantly improves precision comparing to the baseline.

We propose a novel collaborative caching framework to support spatial query processing in Mobile Peer-to-Peer Networks (MP2PNs). To maximize cache sharing among clients, each client caches not only data objects but also parts of the index structure built on the spatial objects. Thus, we call the proposed method structure-embedded collaborative caching (SECC). By introducing a novel index structure called Signature Augment Tree (SAT), we address two crucial issues in SECC. First, we propose a cost-efficient collaborative query processing method in MP2PNs, including peer selection and result merge from multiple peers. Second, we develop a novel collaborative cache replacement policy which maximizes cache effectiveness by considering not only the peer itself but also its neighbors. We implement two SECC schemes, namely, the periodical and adaptive SAT-based schemes, with different SAT maintenance policies. Simulation results show that our SECC schemes significantly outperform other collaborative caching methods which are based on existing spatial caching schemes in a number of metrics, including traffic volume, query latency and power consumption.

GPS data tracked on mobile devices contains rich information about human activities and preferences. In this paper, GPS data is used in location-based services (LBSs) to provide collaborative location recommendations. We observe that most existing LBSs provide location recommendations by clustering the User-Location matrix. Since the User-Location matrix created based on GPS data is huge, there are two major problems with these methods. First, the number of similar locations that need to be considered in computing the recommendations can be numerous. As a result, the identification of truly relevant locations from numerous candidates is challenging. Second, the clustering process on large matrix is time consuming. Thus, when new GPS data arrives, complete re-clustering of the whole matrix is infeasible. To tackle these two problems, we propose the Collaborative Location Recommendation (CLR) framework for location recommendation. By considering activities (i.e., temporal preferences) and different user classes (i.e., Pattern Users, Normal Users, and Travelers) in the recommendation process, CLR is capable of generating more precise and refined recommendations to the users compared to the existing methods. Moreover, CLR employs a dynamic clustering algorithm CADC to cluster the trajectory data into groups of similar users, similar activities and similar locations efficiently by supporting incremental update of the groups when new GPS trajectory data arrives. We evaluate CLR with a real-world GPS dataset, and confirm that the CLR framework provides more accurate location recommendations compared to the existing methods.

In this paper, we aim to provide a point-of-interests (POI) recommendation service for the rapid growing location-based social networks (LBSNs), e.g., Foursquare, Whrrl, etc. Our idea is to explore user preference, social influence and geographical influence for POI recommendations. In addition to deriving user preference based on user-based collaborative filtering and exploring social influence from friends, we put a special emphasis on geographical influence due to the spatial clustering phenomenon exhibited in user check-in activities of LBSNs. We argue that the geographical influence among POIs plays an important role in user check-in behaviors and model it by power law distribution. Accordingly, we develop a collaborative recommendation algorithm based on geographical influence based on naive Bayesian. Furthermore, we propose a unified POI recommendation framework, which fuses user preference to a POI with social influence and geographical influence. Finally, we conduct a comprehensive performance evaluation over two large-scale datasets collected from Foursquare and Whrrl. Experimental results with these real datasets show that the unified collaborative recommendation approach significantly outperforms a wide spectrum of alternative recommendation approaches.

Given a geographic query that is composed of query keywords and a location, a geographic search engine retrieves documents that are the most textually and spatially relevant to the query keywords and the location, respectively, and ranks the retrieved documents according to their joint textual and spatial relevances to the query. The lack of an efficient index that can simultaneously handle both the textual and spatial aspects of the documents makes existing geographic search engines inefficient in answering geographic queries. In this paper, we propose an efficient index, called IR-tree, that together with a top-k document search algorithm facilitates four major tasks in document searches, namely, 1) spatial filtering, 2) textual filtering, 3) relevance computation, and 4) document ranking in a fully integrated manner. In addition, IR-tree allows searches to adopt different weights on textual and spatial relevance of documents at the runtime and thus caters for a wide variety of applications. A set of comprehensive experiments over a wide range of scenarios has been conducted and the experiment results demonstrate that IR-tree outperforms the state-of-the-art approaches for geographic document searches.

As the amount of Web information grows rapidly, search engines must be able to retrieve information according to the user's preference. In this paper, we propose a new web search personalization approach that captures the user's interests and preferences in the form of concepts by mining search results and their clickthroughs. Due to the important role location information plays in mobile search, we separate concepts into content concepts and location concepts, and organize them into ontologies to create an ontology-based, multi-facet (OMF) profile to precisely capture the user's content and location interests and hence improve the search accuracy. Moreover, recognizing the fact that different users and queries may have different emphases on content and location information, we introduce the notion of content and location entropies to measure the amount of content and location information associated with a query, and click content and location entropies to measure how much the user is interested in the content and location information in the results. Accordingly, we propose to define personalization effectiveness based on the entropies and use it to balance the weights between the content and location facets. Finally, based on the derived ontologies and personalization effectiveness, we train an SVM to adapt a personalized ranking function for re-ranking of future search. We conduct extensive experiments to compare the precision produced by our OMF profiles and that of a baseline method. Experimental results show that OMF improves the precision significantly compared to the baseline.

In this paper, we propose the notion of sufficient set for distributed processing of probabilistic Top-k queries in cluster-based wireless sensor networks. Through the derivation of sufficient boundary, we show that data items ranked lower than sufficient boundary are not required for answering the probabilistic top-k queries, thus are subject to local pruning. Accordingly, we develop the sufficient set-based (SSB) algorithm for inter-cluster query processing. Experimental results show that the proposed algorithm reduces data transmissions significantly.

Abstract We studied the effectiveness of a new class of context‐dependent term weights for information retrieval. Unlike the traditional term frequency–inverse document frequency (TF–IDF), the new weighting of a term t in a document d depends not only on the occurrence statistics of t alone but also on the terms found within a text window (or “document‐context”) centered on t. We introduce a Boost and Discount (B&D) procedure which utilizes partial relevance information to compute the context‐dependent term weights of query terms according to a logistic regression model. We investigate the effectiveness of the new term weights compared with the context‐independent BM25 weights in the setting of relevance feedback. We performed experiments with title queries of the TREC‐6, ‐7, ‐8, and 2005 collections, comparing the residual Mean Average Precision (MAP) measures obtained using B&D term weights and those obtained by a baseline using BM25 weights. Given either 10 or 20 relevance judgments of the top retrieved documents, using the new term weights yields improvement over the baseline for all collections tested. The MAP obtained with the new weights has relative improvement over the baseline by 3.3 to 15.2%, with statistical significance at the 95% confidence level across all four collections.

Abstract The Basic Vector Space Model (BVSM) is well known in information retrieval. Unfortunately, its retrieval effectiveness is limited because it is based on literal term matching. The Generalized Vector Space Model (GVSM) and Latent Semantic Indexing (LSI) are two prominent semantic retrieval methods, both of which assume there is some underlying latent semantic structure in a dataset that can be used to improve retrieval performance. However, while this structure may be derived from both the term space and the document space, GVSM exploits only the former and LSI the latter. In this article, the latent semantic structure of a dataset is examined from a dual perspective; namely, we consider the term space and the document space simultaneously. This new viewpoint has a natural connection to the notion of kernels. Specifically, a unified kernel function can be derived for a class of vector space models. The dual perspective provides a deeper understanding of the semantic space and makes transparent the geometrical meaning of the unified kernel function. New semantic analysis methods based on the unified kernel function are developed, which combine the advantages of LSI and GVSM. We also prove that the new methods are stable because although the selected rank of the truncated Singular Value Decomposition (SVD) is far from the optimum, the retrieval performance will not be degraded significantly. Experiments performed on standard test collections show that our methods are promising.

Efficiency and privacy are two fundamental issues in moving object monitoring. This paper proposes a privacy-aware monitoring (PAM) framework that addresses both issues. The framework distinguishes itself from the existing work by being the first to holistically address the issues of location updating in terms of monitoring accuracy, efficiency, and privacy, particularly, when and how mobile clients should send location updates to the server. Based on the notions of safe region and most probable result, PAM performs location updates only when they would likely alter the query results. Furthermore, by designing various client update strategies, the framework is flexible and able to optimize accuracy, privacy, or efficiency. We develop efficient query evaluation/reevaluation and safe region computation algorithms in the framework. The experimental results show that PAM substantially outperforms traditional schemes in terms of monitoring accuracy, CPU cost, and scalability while achieving close-to-optimal communication cost.

The eight papers in this special section were selected from the 93 long papers presented at the 25th IEEE International Conference on Data Engineering (ICDE 2009), held in Shanghai, China, on 29 March-2 April 2009.

User profiling is a fundamental component of any personalization applications. Most existing user profiling strategies are based on objects that users are interested in (i.e., positive preferences), but not the objects that users dislike (i.e., negative preferences). In this paper, we focus on search engine personalization and develop several concept-based user profiling methods that are based on both positive and negative preferences. We evaluate the proposed methods against our previously proposed personalized query clustering method. Experimental results show that profiles which capture and utilize both of the user's positive and negative preferences perform the best. An important result from the experiments is that profiles with negative preferences can increase the separation between similar and dissimilar queries. The separation provides a clear threshold for an agglomerative clustering algorithm to terminate and improve the overall quality of the resulting query clusters.

To bring data services through low-cost Internet access to remote rural areas, several projects proposed to use ferries, such as buses and cars,equipped with short-range WiFi to deliver messages between the Internet and remote villages. In such store-and-forward, ferry-based delay tolerant networks (DTNs), the messaging capacity on the ferries becomes a critical resource and thus needs to be used properly in order to reduce the overall transit delay. However, simply optimizing the overall transit delay may result in prolonged delays for certain individual villages. In this paper, we aim at ensuring a "fair" message ferrying service (in terms of transit delay) amongst the served villages while optimizing the overall performance of the whole system. To achieve our goal, we develop an application layer switch for message/ferry scheduling. Our scheduling is based on the notion of benefit that measures the advantages of ferry scheduling selections in a relative fashion. This approach allows us to properly model the delay minimization problem and fairness goal as mathematical constraints of a schedule optimization problem. Furthermore, we transform the two conflicting goals of this complex optimization problem into two interacting components, namely, performance optimization block and fairness assurance block, and treat them with bipartite matching and stochastic approximation techniques, respectively. Through simulations, we validate our proposal and show that the overall system performance is optimized, together with the ensured fairness in terms of benefit and queuing time.

It has been observed that many queries submitted to search engines are location-sensitive. Traditional search techniques fail to interpret the significance of such geographical clues and as such are unable to return highly relevant search results. Although there have been efforts in the literature to support location-aware information retrieval, critical challenges still remain in terms of search result quality and data scalability. In this paper, we propose an innovative probabilistic ranking framework for domain information retrieval where users are interested in a set of location-sensitive topics. Our proposed method recognizes the geographical distribution of topic influence in the process of ranking documents and models it accurately using probabilistic Gaussian Process classifiers. Additionally, we demonstrate the effectiveness of the proposed ranking framework by implementing it in a Web search service for NBA news. Extensive performance evaluation is performed on real Web document collections, which confirms that our proposed mechanism works significantly better (around 29.7% averagely using DCG20 measure) than other popular location-aware information retrieval techniques in ranking quality.

Given a set of clusters, we consider an optimization problem which seeks a subset of clusters that maximizes the microaverage F-measure. This optimal value can be used as an evaluation measure of the goodness of clustering. For arbitrarily overlapping clusters, finding the optimal value is NP-hard. We claim that a greedy approximation algorithm yields the global optimal solution for clusters that overlap only by nesting. We present a mathematical proof of this claim by induction. For a family of n clusters containing a total of N objects, this algorithm has an {\rm O}(n;{2}) time complexity and O(N) space complexity.

In this paper, we investigate the trade off between performance and confidentiality in signature-based air indexing schemes for wireless data broadcast. Two metrics, namely, false drop probability and false guess probability, are defined to quantify the filtering efficiency and confidentiality loss of a signature scheme. Our analysis reveals that false drop probability and false guess probability share a similar trend as the tuning parameters of a signature scheme change and it is impossible to achieve a low false drop probability and a high false guess probability simultaneously. In order to balance the performance and confidentiality, we perform an analysis to provide a guidance for parameter settings of the signature schemes to meet different system requirements. In addition, we propose the jump pointer technique and the XOR signature scheme to further improve the performance and confidentiality. A comprehensive simulation has been conducted to validate our findings.

The rule-based localization methods proposed in this paper are based on two important observations. First, although the absolute RSS values change with time, the relative RSS (RRSS) values between several Access Points (APs) are more stable than the absolute RSSs. Thus, we can use RRSSs as rules for inferring a client's location. Second, when a unique location cannot be obtained based on RRSS rules, the localization process can backtrack to the previous observed client location. By analyzing the accessible paths on the floor plan, locations that are not reacheable from the previous location can be disqualified. Based on these two key observations, we propose several localization methods, implement them in a life environment and conduct extensive experiments to measure the localization accuracy of the proposed methods. We found that our methods achieve much higher accuracy than the state-of-the-art localization methods, namely, RADAR, LOCADIO and WHAM!.

Location-based services (LBSs) play more and more important roles in our daily life with the prevalence of mobile devices and the internet. Location modeling is a significant research topic in LBSs, which is needed to provide a well-defined representation of location knowledge for location browsing, navigation and query processing. In this paper, we propose that a topological structure can be attached to an exit-location space model, which can preserve the topology and distance semantics between locations (exits). The Q-analysis developed by R. H. Atkin is used to analyze the semantic information of the model. Compared with those existing models which only reveal the relationships between two entities, this novel model can provide the analysis of n-ary relationships (i.e., the relations among n entities) from both local and global viewpoints. Moreover, by using the rich structures obtained from the topological analysis, we define a semantic distance which can support more meaningful navigation and queries on complicated indoor environments. Examples are described in detail to demonstrate the effectiveness of our model.

Location models play an important role in location- based services (LBSs), because LBSs require a well-defined representation of location knowledge to support location browsing, navigation and query processing. Current location models can be divided into two categories: symbolic and geometric. Symbolic models try to represent the semantic relationships between entities, and geometric models are based on geometric coordinates and Euclidean distance. In this paper, we propose a lattice-based semantic location model (LSLM) for the indoor environment. LSLM is based on the exit-location model and the theory of "formal concept analysis." The model can provide an explicit representation of the basic relationships between two entities such as containment and overlap. The nearest neighbor relationship on the concept lattice is used to define the optimal distance between two entities. Furthermore, the dual (location/exit) property of the model can cater for different navigation needs. We provide examples to show the effectiveness of our model.

Abstract We propose a new optimal clustering effectiveness measure, called CS1, based on a combination of clusters rather than selecting a single optimal cluster as in the traditional MK1 measure. For hierarchical clustering, we present an algorithm to compute CS1, defined by seeking the optimal combinations of disjoint clusters obtained by cutting the hierarchical structure at a certain similarity level. By reformulating the optimization to a 0‐1 linear fractional programming problem, we demonstrate that an exact solution can be obtained by a linear time algorithm. We further discuss how our approach can be generalized to more general problems involving overlapping clusters, and we show how optimal estimates can be obtained by greedy algorithms.

The exponential growth of information on the Web has introduced new challenges for building effective search engines. A major problem of Web search is that search queries are usually short and ambiguous, and thus are insufficient for specifying the precise user needs. To alleviate this problem, some search engines suggest terms that are semantically related to the submitted queries so that users can choose from the suggestions the ones that reflect their information needs. In this paper, we introduce an effective approach that captures the user's conceptual preferences in order to provide personalized query suggestions. We achieve this goal with two new strategies. First, we develop online techniques that extract concepts from the Web-snippets of the search result returned from a query and use the concepts to identify related queries for that query. Second, we propose a new two-phase personalized agglomerative clustering algorithm that is able to generate personalized query clusters. To the best of the authors' knowledge, no previous work has addressed personalization for query suggestions. To evaluate the effectiveness of our technique, a Google middleware was developed for collecting clickthrough data to conduct experimental evaluation. Experimental results show that our approach has better precision and recall than the existing query clustering methods.

A continuous nearest neighbor (CNN) search, which retrieves the nearest neighbors corresponding to every point in a given query line segment, is important for location-based services such as vehicular navigation and tourist guides. It is infeasible to answer a CNN search by issuing a traditional nearest neighbor query at every point of the line segment due to the large number of queries generated and the overhead on bandwidth. Algorithms have been proposed recently to support CNN search in the traditional client- server systems but not in the environment of wireless data broadcast, where uplink communication channels from mobile devices to the server are not available. In this paper, we develop a generalized search algorithm for continuous k-nearest neighbors based on Hilbert Curve Index in wireless data broadcast systems. A performance evaluation is conducted to compare the proposed search algorithms with an algorithm based on R-tree Air Index. The result shows that the Hilbert Curve Index-based algorithm is more energy efficient than the R-tree-based algorithm.

This article addresses search engine personalization. We present a new approach to mining a user's preferences on the search results from clickthrough data and using the discovered preferences to adapt the search engine's ranking function for improving search quality. We develop a new preference mining technique called SpyNB , which is based on the practical assumption that the search results clicked on by the user reflect the user's preferences but does not draw any conclusions about the results that the user did not click on. As such, SpyNB is still valid even if the user does not follow any order in reading the search results or does not click on all relevant results. Our extensive offline experiments demonstrate that SpyNB discovers many more accurate preferences than existing algorithms do. The interactive online experiments further confirm that SpyNB and our personalization approach are effective in practice. We also show that the efficiency of SpyNB is comparable to existing simple preference mining algorithms.

This paper presents a pilot study of query-specific clustering that uses our novel document-context based similarity scores as compared with document similarity scores. Clustering is applied to the top 1000 retrieved documents for a given query. Clustering effectiveness is evaluated based on the MK1 score for TREC-2, TREC-6 and TREC-7 test collections. Encouraging results were obtained whereby document-context clustering produces better MK1 scores than document clustering with a 95% confidence level if precision and recall are equally important.

k-closest pair query is a useful type of query in many practical applications involving spatial data for decision making. The traditional techniques to handle k-closest pair queries generally assume that the objects are static. In this paper, we study the problem of k-closest pair monitoring (kCPM) over moving objects. Aiming at reducing communication cost for location updates between the clients and the server, our proposed kCPM approach achieves high monitoring accuracy with less CPU utilization compared to existing periodical location update schemes.

The vector space model (VSM) is one of the most widely used information retrieval (IR) models in both academia and industry. It was less effective at the Chinese ad hoc retrieval tasks than other retrieval models in the NTCIR-3 evaluation workshop, but comparable to those in the NTCIR-4 and NTCIR-5 workshops. We do not know whether the lower level performance was due to the VSM's inherent deficiencies or to a less effective normalization of document length. Hence we evaluated the VSM with various pivoted normalizations of document length using the NTCIR-3 collection for confirmation. We found that VSM's retrieval effectiveness with pivoted normalization was comparable to other competitive retrieval models (for example, 2-Poisson), and that VSM's retrieval speed with pivoted normalization was similar to competitive retrieval models (2-Poisson). We proposed a novel adaptive scheme that automatically estimates the (near) best parameters for pivoted document-length normalization based on query size; the new normalization is called adaptive pivoted document-length normalization . This scheme achieved good retrieval effectiveness, sometimes for short (title) queries and sometimes for long queries, without manually adjusting parameter values. We found that unique, adaptive pivoted normalization can enhance fixed pivoted normalizations for different test collections (TREC-5 and TREC-6). We also evaluated the VSM with the adaptive pivoted normalization using the pseudo-relevance feedback (PRF) and found that this type of VSM performs similarly to the competitive retrieval models (2-Poisson) with PRF. Hence, we conclude that the VSM with unique (adaptive) pivoted document-length normalization is effective for Chinese IR and that its retrieval effectiveness is comparable to that of other competitive retrieval models with or without PRF for the reference test collections used in this evaluation.

A range nearest-neighbor (RNN) query retrieves the nearest neighbor (NN) for every point in a range. It is a natural generalization of point and continuous nearest-neighbor queries and has many applications. In this paper, we consider the ranges as (hyper)rectangles and propose efficient in-memory processing and secondary memory pruning techniques for RNN queries in both 2D and high-dimensional spaces. These techniques are generalized for kRNN queries, which return the k nearest neighbors for every point in the range. In addition, we devise an auxiliary solution-based index EXO-tree to speed up any type of NN query. EXO-tree is orthogonal to any existing NN processing algorithm and, thus, can be transparently integrated. An extensive empirical study was conducted to evaluate the CPU and I/O performance of these techniques, and the study showed that they are efficient and robust under various data sets, query ranges, numbers of nearest neighbors, dimensions, and cache sizes.

Studies on the performance issues (i.e., access latency and energy conservation) of wireless data broadcast have appeared in the literature. However, the important security issues have not been well addressed. This paper investigates the tradeoff between performance and security of signature-based air index schemes in wireless data broadcast. From the performance perspective, keeping low false drop probability helps clients retrieve the information from a broadcast channel efficiently. Meanwhile, from the security perspective, achieving high false guess probability prevents the hacker from guessing the information easily. There is a tradeoff between these two aspects. An administrator of the wireless broadcast system may balance this tradeoff by carefully configuring the signatures used in broadcast. This study provides a guidance for parameter settings of the signature schemes in order to meet the performance and security requirements. Experiments are performed to validate the analytical results and to obtain optimal signature configuration corresponding to different application criteria.

More and more applications require peer-to-peer (P2P) systems to support complex queries over multi-dimensional data. For example, a P2P auction network for real estate frequently needs to answer queries such as "select five available buildings closest to the airport". Such queries are not efficiently supported in current P2P systems. Towards an efficient and scalable P2P system capable of processing complex multi-dimensional queries, we first propose a comprehensive framework for sharing, indexing, and querying multi-dimensional data, where (i) peers with more computational power coordinate indexing and query processing, and (ii) other peers participate in part of the computation in order to achieve scalability and load-balance. Based on this framework, we propose Network-R-tree (NR-tree), a P2P adaptation of the dominant spatial index - R*-tree. NR-tree, indexing spatial data at clustered peers, is capable of processing complex queries such as range queries and k-nearest neighbor queries. We propose query processing algorithms for range and k-nearest neighbor queries and experimentally prove the effectiveness of proposed techniques with real data.

Semantic caching enables mobile clients to answer spatial queries locally by storing the query descriptions together with the results. However, it supports only a limited number of query types, and sharing results among these types is difficult. To address these issues, we propose a proactive caching model which caches the result objects as well as the index that supports these objects as the results. The cached index enables the objects to be reused for all common types of queries. We also propose an adaptive scheme to cache such an index, which further optimizes the query response time for the best user experience. Simulation results show that proactive caching achieves a significant performance gain over page caching and semantic caching in mobile environments where wireless bandwidth and battery are precious resources.

Caching has been an important technique for saving network traffic and reducing response time, especially in mobile environments where bandwidth is often a scarce resource. In this paper, we propose a novel approach for caching multidimensional data in a cluster of mobile devices. In particular, we focus on the most common types of multi-dimensional queries, namely range and k-nearest neighbor queries, by computing a cacheable region for every query, caching the result at the client, and indexing it in an R*-tree at the cluster gateway. Subsequent queries are first issued to the R*-tree and only remainder queries or queries that cannot be guaranteed exact answers are sent to the remote data server. To the best of our knowledge, our work is the first to study caching results from complex multi-dimensional queries (e.g., kNN query) and propose to build an R*-tree on previously fetched query results in a cluster of mobile devices. Rigorous experiments show that our approach significantly reduces network traffic and response time.

Wireless broadcast is very suitable for delivering information to a large user population. In this paper, we concentrate on data allocation methods for multiple broadcast channels. To the best of our knowledge, this is the first allocation model that takes into the consideration of items' access frequencies, items' lengths. and bandwidth of different channels. We first derive the optimal average expected delay for multiple channels for the general case where data access frequencies, data sizes, and channel bandwidths can all be non-uniform. Second, we develop TOSA, a multi-channel allocation method that does not assume a uniform broadcast schedule for data items on the same channel. TOSA is based on the idea of two-level data allocation, i.e., a high-level optimization step for allocating data to the channels, followed by a low-level optimization step to schedule data within a channel. We show that TOSA achieves near-optimal performance in terms of average waiting time and significantly outperforms the existing algorithms.

This paper proposes a generic framework for monitoring continuous spatial queries over moving objects. The framework distinguishes itself from existing work by being the first to address the location update issue and to provide a common interface for monitoring mixed types of queries. Based on the notion of safe region, the client location update strategy is developed based on the queries being monitored. Thus, it significantly reduces the wireless communication and query reevaluation costs required to maintain the up-to-date query results. We propose algorithms for query evaluation/reevaluation and for safe region computation in this framework. Enhancements are also proposed to take advantage of two practical mobility assumptions: maximum speed and steady movement. The experimental results show that our framework substantially outperforms the traditional periodic monitoring scheme in terms of monitoring accuracy and CPU time while achieving a close-to-optimal wireless communication cost. The framework also can scale up to a large monitoring system and is robust under various object mobility patterns.

Given two spatial data sets A and B, a top-k spatial join retrieves the k objects from A or B that intersect the largest number of objects from the other data set. Depending on the application requirements, there exist several variations of the problem. For instance, B may be a point data set, and the goal may be to retrieve the regions of A that contain the maximum number of points. The processing of such queries with conventional spatial join algorithms is expensive. However, several improvements are possible based on the fact that we only require a small subset of the result (instead of all intersection/containments pairs). In this paper, we propose output-sensitive algorithms for top-k spatial joins that utilize a variety of optimizations for reducing the overhead.

Finding informative genes from microarray data is an important research problem in bioinformatics research and applications. Most of the existing methods rank features according to their discriminative capability and then find a subset of discriminative genes (usually top k genes). In particular, t-statistic criterion and its variants have been adopted extensively. This kind of methods rely on the statistics principle of t-test, which requires that the data follows a normal distribution. However, according to our investigation, the normality condition often cannot be met in real data sets.To avoid the assumption of the normality condition, in this paper, we propose a rank sum test method for informative gene discovery. The method uses a rank-sum statistic as the ranking criterion. Moreover, we propose using the significance level threshold, instead of the number of informative genes, as the parameter. The significance level threshold as a parameter carries the quality specification in statistics. We follow the Pitman efficiency theory to show that the rank sum method is more accurate and more robust than the t-statistic method in theory.To verify the effectiveness of the rank sum method, we use support vector machine (SVM) to construct classifiers based on the identified informative genes on two well known data sets, namely colon data and leukemia data. The prediction accuracy reaches 96.2% on the colon data and 100% on the leukemia data. The results are clearly better than those from the previous feature ranking methods. By experiments, we also verify that using significance level threshold is more effective than directly specifying an arbitrary k.

This paper studies a heterogeneous multiple channel environment (HMCE), in which the channels are controlled by different wireless operators. To the best of our knowledge, there is no previous research on this scenario. In this paper, we first present the architecture for HMCE which makes use of a centralized index server to broadcast index information about the broadcast data on a dedicated index channel. An analog can be drawn between HMCE and WWW: the wireless operators are Web sites and the index channel is Google; Google indexes Web pages so that users can find the Web pages they want, whereas in HMCE the index channel indexes the data channels to help mobile users to find the data on the air. We propose three indexing methods to reduce the time and energy used to search for data in HMCE. Simulation results are obtained to evaluate the performance of the proposed methods.

Location-based applications require a well-formed representation of spatial knowledge. Current location models can be classified into symbolic or geometric models. The former attempts to represent logical entities and their semantics, but requires a large amount of manual effort for describing them. On the other hand, the latter represents the geometric coordinates but not the semantics. In this paper, we present a semantic location model which preserves topology and distance semantics to support location navigation but at the same time facilitates programmatic model construction and maintenance. The model is based on a sound location theory. It is mainly composed of two hierarchies: a location hierarchy and an exit hierarchy, which can be derived from spatial maps, such as floor plans, without manual intervention. Through a series of model construction algorithms and a real example, we show that our model is simple but powerful enough to capture spatial connectivity and hierarchical relationship to support location-based applications. Furthermore, the location and exit hierarchies are easy to understand by human users.

A continuous nearest neighbor (CNN) search retrieves the nearest neighbors corresponding to every point in a given query line segment. It is important for location-based services such as vehicular navigation tools and tourist guides. It is infeasible to answer a CNN search by issuing a traditional nearest neighbor query at every point of the line segment due to the large number of queries generated and the large overhead on bandwidth. Algorithms have been proposed recently to support CNN search in the traditional client-server service model. In this paper, we conduct a pioneering study on CNN search in wireless data broadcast environments. We propose two air indexing techniques, namely, R-tree air index and Hilbert curve air index, and develop algorithms based on these two techniques to search CNNs on the air. A simulation is conducted to compare the proposed air indexing techniques with a naive broadcast approach. The result shows that both of the proposed methods outperform the naive approach significantly. The Hilbert Curve air index is superior for uniform data distributions, while the R-tree air index is a better choice for skewed data distributions.

Data caching at mobile clients is an important technique for improving the performance of wireless data dissemination systems. However, variable data sizes, data updates, limited client resources, and frequent client disconnections make cache management a challenge. We propose a gain-based cache replacement policy, Min-SAUD, for wireless data dissemination when cache consistency must be enforced before a cached item is used. Min-SAUD considers several factors that affect cache performance, namely, access probability, update frequency, data size, retrieval delay, and cache validation cost. The paper employs stretch as the major performance metric since it accounts for the data service time and, thus, is fair when items have different sizes. We prove that Min-SAUD achieves optimal stretch under some standard assumptions. Moreover, a series of simulation experiments have been conducted to thoroughly evaluate the performance of Min-SAUD under various system configurations. The simulation results show that, in most cases, the Min-SAUD replacement policy substantially outperforms two existing policies, namely, LRU and SAIU.

Location-based services (LBSs), considered as a killer application in the wireless data market, provide information based on locations specified in the queries. In this paper, we examine the indexing issue for querying location-dependent data in wireless LBSs; in particular, we focus on an important class of queries, planar point queries. To address the issues of responsiveness, energy consumption, and bandwidth contention in wireless communications, an index has to minimize the search time and maintain a small storage overhead. It is shown that the traditional point-location algorithms and spatial index structures fail to achieve either objective or both. This paper proposes a new index structure, called D-tree, which indexes spatial regions based on the divisions that form the boundaries of the regions. We describe how to construct a binary D-tree index, how to process queries based on the D-tree, and how to page the binary D-tree. Moreover, two parameterized methods for partitioning the original space, called fixed grid assignment (FGA) and adaptive grid assignment (AGA), are proposed to enhance the D-tree. The performance of the D-tree is evaluated using both synthetic and real data sets. Experimental results show that the proposed D-tree outperforms the well-known indexes such as the R/sup */-tree, and that both the FGA and AGA approaches can achieve different performance trade-offs between the index search time and storage overhead by fine-tuning their algorithmic parameters.

We are witnessing in recent years growing interest for location-dependent information services among mobile users. We examine the issue of processing location-dependent queries in a mobile broadcast environment. Different from a traditional environment, mobile users are concerned with not only access latencies but also power conservation. The planar point location algorithms and conventional spatial index structures are shown inefficient. We propose a new index data structure, called D-tree, for querying location-dependent data in mobile broadcast environments. The basic idea is to index data regions based on the divisions between them. We describe how to construct the binary D-tree index, how to process location-dependent queries based on this index structure, and how to page the D-tree to fit the packet capacity. The performance of the D-tree is evaluated using both synthetic and real datasets. Experimental results show that the proposed D-tree provides a much better overall performance than the well-known existing schemes such as the R*-tree.

Spatial databases are entering an era of mass deployment in various real-life applications, especially mobile and location-based services. The real-time processing of spatial queries to meet different performance goals poses new problems to the real-time and parallel processing communities. We investigate how multiple window queries can be parallelized, decomposed, scheduled and processed in real time workloads to optimize system performance, such as I/O cost, response time and miss rate. We devise in-memory R-trees to decompose queries into independent jobs. Jobs from different queries can be combined according to their spatial locality to eliminate redundant I/Os. Runtime job schedulers are elaborately devised to optimize response time or miss rate for various systems. Empirical results show a significant performance improvement over the sequential, unparalleled approach

With the advent of wireless networking and personal digital devices, the population of mobile users will increase significantly. Broadcasting is particularly suitable for environments having a large number of clients. In this paper, we study the query processing of some typical location-dependent queries, such as window queries and kNN queries, in a broadcast system. To reduce clients' power consumption and provide efficient services, a transformation of the objects is applied based on Hilbert curve. Furthermore, a linear index structure is constructed and several algorithms are devised to answer spatial queries. Experiments are conducted to evaluate the performance of the proposed transformation and related algorithms. Results show that the proposed schemes outperform existing algorithms significantly.

In this paper we propose an approach that enables mobile clients to determine the validity of previous queries based on their current locations. In order to make this possible, the server returns in addition to the query result, a validity region around the client's location within which the result remains the same. We focus on two of the most common spatial query types, namely nearest neighbor and window queries, define the validity region in each case and propose the corresponding query processing algorithms. In addition, we provide analytical models for estimating the expected size of the validity region. Our techniques can significantly reduce the number of queries issued to the server, while introducing minimal computational and network overhead compared to traditional spatial queries.

Mobile location-dependent information services are gaining increasing interest in both academic and industrial communities. In these services, data values depend on their locations. Caching frequently accessed data on mobile clients can help save wireless bandwidth and improve system performance. However, since client location changes constantly, location-dependent data may become obsolete not only due to updates performed on data items but also because of client movements across the network. To the best of the authors' knowledge, previous work on cache invalidation issues focused on data updates only. This paper considers data inconsistency caused by client movements and proposes three location-dependent cache invalidation schemes. The performance for the proposed schemes is investigated by both analytical study and simulation experiments in a scenario where temporal- and location-dependent updates coexist. Both analytical and experimental results show that, in most cases, the proposed methods substantially outperform the NSI scheme, which drops the entire cache contents when hand-off is performed.

A distributed search system consists of a large number of autonomous search servers logically connected in a peer-to-peer network. Each search server maintains a local index of a collection of documents available at the server or on other peer machines. When a query is received by any server in the network, a distributed search process determines the most relevant search servers and redirects the query to them for processing. We model the distributed search process as Markov decision processes (MDPs). The estimated relevance of a server to a query is regarded as the reward in the MDP model. Once the MDP policies representing the global knowledge are obtained at each server through asynchronous value iteration, the most relevant servers to a given query can be efficiently identified despite the lack of centralized control and global knowledge at each autonomous server. We discuss the implementation and complexity of the asynchronous value iteration and how we extend the traditional MDP to handle the multiple-access policy (i.e., more than one optimal server is returned) and queries with multiple terms. Finally, experiments are conducted using the TREC collection. We show that the MDP-based distributed search can achieve results very close to that of a centralized search.

Transparent data replication has been considered a promising technique for improving system performance for a large distributed network. In this paper, a hybrid transparent replication model is presented. We address the problems of replication proxy placement in the network and data replica placement on the installed proxies given that a maximum of M proxies are allowed. Both reads and writes are considered in these problems. The performance objective is to minimize the total data transfer cost. To address the placement problems, we first present the optimal solutions for a single object in a tree network without/with constraint on the number of replicas. Based on that, two schemes, namely, aggregate access (AGGA) and weighted popularity (WPOP), are proposed for the replication proxy placement problem. An optimal solution is described for the replica placement problem. The performance of the proposed placement schemes is evaluated with a set of carefully designed simulation experiments over a wide range of system parameters. The results give us several helpful intuitions in deploying transparent replication proxies in a practical system.

Mobile location-dependent information services (LDISs) have become increasingly popular in recent years. However, data caching strategies for LDISs have thus far received little attention. In this paper, we study the issues of cache invalidation and cache replacement for location-dependent data under a geometric location model. We introduce a new performance criterion, called caching efficiency, and propose a generic method for location-dependent cache invalidation strategies. In addition, two cache replacement policies, PA and PAID, are proposed. Unlike the conventional replacement policies, PA and PAID take into consideration the valid scope area of a data value. We conduct a series of simulation experiments to study the performance of the proposed caching schemes. The experimental results show that the proposed location-dependent invalidation scheme is very effective and the PA and PAID policies significantly outperform the conventional replacement policies.

A good cache management method for mobile wireless environments has to handle problems associated with limited client resources and frequent client disconnections, in addition to standard problems found in wired environments, such as variable data sizes and data updates. In this paper we propose a gain-based cache replacement policy, Min-SAUD, for wireless data dissemination when cache consistency must be enforced before a cached item is used. Min-SAUD considers several factors that affect cache performance, namely access probability, update frequency, data size, retrieval delay, and cache validation cost. Min-SAUD is optimal in terms of the stretch performance measure. Preliminary experimental results show that in most cases the Min-SAUD replacement policy substantially outperforms two existing policies, namely LRU and SAIU.

A meta-search engine acts as an agent for the participant search engines. It receives queries from users and redirects them to one or more of the participant search engines for processing. A meta-search engine incorporating many participant search engines is better than a single global search engine in terms of the number of pages indexed and the freshness of the indexes. The meta-search engine stores descriptive data (i.e., descriptors) about the index maintained by each participant search engine so that it can estimate the relevance of each search engine when a query is received. The ability for the meta-search engine to select the most relevant search engines determines the quality of the final result. To facilitate the selection process, the document space covered by each search engine must be described not only concisely but also precisely. Existing methods tend to focus on the conciseness of the descriptors by keeping a descriptor for a search engine's entire index. This paper proposes to cluster a search engine's document space into clusters and keep a descriptor for each cluster. We show that cluster descriptors can provide a finer and more accurate representation of the document space, and hence enable the meta-search engine to improve the selection of relevant search engines. Two cluster-based search engine selection scenarios (i.e., independent and high-correlation) are discussed in this paper. Experiments verify that the cluster-based search engine selection can effectively identify the most relevant search engines and improve the quality of the search results consequently.

Abstract not available.

The combination of broadcast and on-demand data delivery services is an economic way to build a highly scalable wireless information system with limited bandwidth. The use of data broadcasting should be adaptive so that the system response time can always be minimised. A traditional approach requires the development of a system response time equation in order to find the optimal solution. However, obtaining such an equation is not always possible. We observe that by maintaining a certain level of on-demand request arrival rate, a close approximation to the optimal solution can be obtained. Using this approach, a real-time adaptive data delivery algorithm is developed. Our algorithm does not require the access information of the data items to be known exactly, which is needed normally for this kind of optimization problems. A simple and low overhead bit vector mechanism is able to capture the relative popularities of the data items. With this information, our algorithm can give a performance comparable to the ideal case in which the access information for each data item is known exactly.

Studies power conservation techniques for multi-attribute queries on wireless data broadcast channels. Indexing data on broadcast channels can improve the client filtering capability, while clustering and scheduling can reduce both the access time and the tune-in time. Thus, indexing techniques should be coupled with clustering and scheduling methods to reduce the battery power consumption of mobile computers. In this study, three indexing schemes for multi-attribute queries, namely the index tree, signature and hybrid index, are discussed. We develop cost models for these three indexing schemes and evaluate their performance based on multi-attribute queries on wireless data broadcast channels.

This paper investigates power conserving indexing techniques for data disseminated on a broadcast channel. A hybrid indexing method combining strengths of the signature and the index tree techniques is presented. Different from previous studies, our research takes into consideration two important data organization factors, namely, clustering and scheduling. Cost models for index, signature and hybrid methods are derived by taking into account various data organizations accommodating these two factors. Based on our analytical comparisons, the signature and the hybrid indexing techniques are the best choices for power conserving indexing of various data organizations on wireless broadcast channels.

In a text categorization model using an artificial neural network as the text classifier scalability is poor if the neural network is trained using the raw feature space since textural data has a very high-dimension feature space. We proposed and compared four dimensionality reduction techniques to reduce the feature space into an input space of much lower dimension for the neural network classifier. To test the effectiveness of the proposed model, experiments were conducted using a subset of the Reuters-22173 test collection for text categorization. The results showed that the proposed model was able to achieve high categorization effectiveness as measured by precision and recall. Among the four dimensionality reduction techniques proposed, principal component analysis was found to be the most effective in reducing the dimensionality of the feature space.

Various techniques have been developed to improve the performance of wireless information services. Techniques such as information broadcasting, caching of frequently accessed data, and point-to-point channels for pull-based data requests are often used to reduce data access time. To efficiently utilize information broadcast, indexing and scheduling schemes are employed for the organization of data broadcast. Most of the studies in the literature focused either on individual technique or a combination of them with some restrictive assumptions. There is no study considering these techniques working together in an integrated manner. In this paper, we propose a dynamic data delivery model for wireless communication environments. An important feature of our model is that data are disseminated through various storage mediums according to the dynamically collected data access patterns. Various results are presented in a set of simulation studies, which give some of the intuitions behind the design of a wireless data delivery system. 1

We discuss the wireless channel allocation problem for data dissemination in mobile computing systems. Methods for accessing data through broadcast and on-demand channels are described. We provide analytical models and cost formulae for the exclusive broadcast channels and the exclusive on-demand channels and propose a dynamic channel allocation algorithm for optimizing system performance. Our performance evaluation shows that dynamic channel allocation significantly improves system performance and the channel allocation algorithm gives us the optimal solution for various system parameter settings.

We present a new access method, called the path dictionary index (PDI) method, for supporting nested queries on object-oriented databases. PDI supports object traversal and associative search, respectively, with a path dictionary and a set of attribute indexes built on top of the path dictionary. We discuss issues on indexing and query processing in object-oriented databases; describe the operations of the new mechanism; develop cost models for its storage overhead and query and update costs; and compare the new mechanism to the path index method. The result shows that the path dictionary index method is significantly better than the path index method over a wide range of parameters in terms of retrieval and update costs and that the storage overhead grows slowly with the number of indexed attributes.

Caching of frequently accessed data items can reduce the bandwidth requirement in a mobile wireless computing environment. Periodically broadcast of invalidation reports is an efficient cache invalidation strategy. However, this strategy is severely affected by the disconnection and mobility of the clients. In this paper, we present two adaptive cache invalidation report methods, in which the server broadcasts different invalidation reports according to the update and query rates/patterns and client disconnection time while spending little uplink cost. Simulation results show that the adaptive invalidation methods are efficient in improving mobile caching and reducing the uplink and downlink costs without degrading the system throughput.

We discuss several channel allocation methods for data dissemination in mobile computing systems. We suggest that the broadcast and on-demand channels have different access performance under different system parameters and that a mobile cell should use a combination of both to obtain optimal access time for a given workload and system parameters. We study the data access efficiency of three channel configurations: all channels are used as on-demand channels (exclusive on-demand); all channels are used for broadcast (exclusive broadcast); and some channels are on-demand channels and some are broadcast channels (hybrid). Simulations on obtaining the optimal channel allocation for lightly-loaded, medium-loaded, and heavy-loaded conditions is conducted and the result shows that an optimal channel allocation significantly improves the system performance.

Applying information retrieval techniques to the World Wide Web (WWW) environment is a challenge, mostly because of its hypertext/hypermedia nature and the richness of the meta-information it provides. We present four keyword-based search and ranking algorithms for locating relevant WWW pages with respect to user queries. The first algorithm, Boolean Spreading Activation, extends the notion of word occurrence in the Boolean retrieval model by propagating the occurrence of a query word in a page to other pages linked to it. The second algorithm, Most-cited, uses the number of citing hyperlinks between potentially relevant WWW pages to increase the relevance scores of the referenced pages over the referencing pages. The third algorithm, TFxIDF vector space model, is based on word distribution statistics. The last algorithm, Vector Spreading Activation, combines TFxIDF with the spreading activation model. We conducted an experiment to evaluate the retrieval effectiveness of these algorithms. From the results of the experiment, we draw conclusions regarding the nature of the WWW environment with respect to document ranking strategies.

The paper describes the World Wide Web Index and Search Engine (WISE) for Internet resource discovery. The system is designed around a resource database containing meta information about WWW resources and is automatically built using an indexer robot, a special WWW client agent. The resource database allows users to search for resources based on keywords, and to learn about potentially relevant resources without having to directly access them. Such capabilities can significantly reduce the amount of time that a user needs to spend in order to find the information of his/her interest. We discuss WISE's main components: the resource database, the indexer robot, the search engine, and the user interface, and through the technical discussions, we highlight the research issues involved in the design, the implementation and the evaluation of such a system.

A signature file organization, called the weight-partitioned signature file, for supporting document ranking is proposed. It employs multiple signature files, each of which corresponds to one term frequency, to represent terms with different term frequencies. Words with the same term frequency in a document are grouped together and hashed into the signature file corresponding to that term frequency. This eliminates the need to record the term frequency explicitly for each word. We investigate the effect of false drops on retrieval effectiveness if they are not eliminated in the search process. We have shown that false drops introduce insignificant degradation on precision and recall when the false-drop probability is below a certain threshold. This is an important result since false-drop elimination could become the bottleneck in systems using fast signature file search techniques. We perform an analytical study on the performance of the weight-partitioned signature file under different search strategies and configurations. An optimal formula is obtained to determine for a fixed total storage overhead the storage to be allocated to each partition in order to minimize the effect of false drops on document ranks. Experiments were performed using a document collection to support the analytical results.

Signature files have been studied extensively, as an access method for textual databases. Many approaches have been proposed for searching signatures files efficiently. However, different methods make different assumptions and use different performance measures, making it difficult to compare their performance. In this paper, we study three basic methods proposed in the literature, namely, the indexed descriptor file, the two-level superimposed coding scheme, and the partitioned signature file approach. The contribution of this paper is two-fold. First, we present a uniform analytical performance model so that the methods can be compared fairly and consistently. The analysis shows that the two-level superimposed coding scheme, if stored in a transposed file, has the best performance. Second, we extend the two-level superimposed coding method into a multilevel superimposed coding method, we obtain the optimal number of levels for the multilevel method and show that for databases with reasonable size the optimal value is much larger than 2, which is assumed in the two-level method. The accuracy of the analytical formula is demonstrated by simulation.>

This paper argues that most queries in object-oriented databases require traversing from one object to another in the aggregation hierarchy. Thus, the connections between objects through object identifiers are essential to the efficiency of query processing and should be represented separately from the database. We introduce the concept of path dictionary and describe how it supports queries of different types. We evaluate the storage overhead, query and update costs of the path dictionary. Compared to the path index, the path dictionary has better overall query and update performance and lower storage overhead.

The results of modeling the performance of searching large text databases (>10 gigabytes) via various parallel hardware architectures and search algorithms are discussed. The performance under load and the cost of each configuration are compared. Strengths, weaknesses, performance sensitivities, and search features supported for each configuration are also addressed. In addition, a common search workload used in the modeling is described. The search workload is derived from a set of searches run against the Chemical Abstracts (CA) file of bibliographic and abstract text available on STN International®. This common workload is applied to all configurations modeled to provide a common basis of comparison. © 1994 John Wiley & Sons, Inc.

We study a general class of single linear recursions and the properties of their expansions by analyzing the structures of the recursions. We show that the expansions of a linear recursion of this class are very regular in that the variable connections are heavily shared and change periodically with respect to the expansions. The variable connections can be precisely characterized as static bindings and chain connections. We conclude that a single linear recursion under our assumptions either is bounded or can be expressed as chain recursions. This study contributes to query processing, because it provides the basis for rule compilation as a general and powerful technique for query processing. Combined with query information, the expansion properties of the recursion provide optimized query-processing plans.>

A composition requires three operations: join, project, and duplicate elimination. A hot-spot composition algorithm is proposed in an attempt to achieve savings on both join and external sort operations. The proposed algorithm reduces the effort of performing the join operation by using a novel hot-spot technique. Several experiments have been conducted, and it is shown that the hot-spot composition algorithm outperforms other algorithms under almost every condition. The composition operation is implemented as a primitive operation in the algorithm.>

Previous work on superimposed coding has been characterized by two aspects. First, it is generally assumed that signatures are generated from logical text blocks of the same size; that is, each block contains the same number of unique terms after stopword and duplicate removal. We call this approach the fixed-size block (FSB) method, since each text block has the same size, as measured by the number of unique terms contained in it. Second, with only a few exceptions [6,7,8,9,17], most previous work has assumed that each term in the text contributes the same number of ones to the signature (i.e., the weight of the term signatures is fixed). The main objective of this paper is to derive an optimal weight assignment that assigns weights to document terms according to their occurrence and query frequencies in order to minimize the false-drop probability. The optimal scheme can account for both uniform and nonuniform occurence and query frequencies, and the signature generation method is still based on hashing rather than on table lookup. Furthermore, a new way of generating signatures, the fixed-weight block (FWB) method, is introduced. FWB controls the weight of every signature to a constant, whereas in FSB, only the expected signature weight is constant. We have shown that FWB has a lower false-drop probability than that of the FSB method, but its storage overhead is slightly higher. Other advantages of FWB are that the optimal weight assignment can be obtained analytically without making unrealistic assumptions and that the formula for computing the term signature weights is simple and efficient.

A partitioning method is introduced for reducing the search space required on the signature file. A partitioned signature file is better than the multilevel signature file and the S-tree in that it has an extremely small storage and processing overhead. Three partitioning schemes are outlined and their performance discussed. A description is given of the data structure necessary to support the partitioning schemes and the algorithms for signature insertion, deletion, and retrieval.>

The design of a text-retrieval machine, called HYTREM (hybrid text-retrieval machine), for the support of large unformatted text databases is described. A signature file is used as an access method to reduce the amount of data that need to be searched directly. Therefore, HYTREM consists of two major subsystems: a signature processor and a text processor. The signature processor is based on a world-parallel, bit-serial organization which is faster, more efficient, and more flexible than a word-serial, bit-parallel organization proposed by S.R. Ahuja and C.S. Roberts (1980). The text processor, called ALTEP (associative linear text processor), is a linear array of logic cells capable of matching regular expressions at a much higher speed than that of previous designs. Since both the signature processor and ALTEP are highly parallel processors, a high-speed multiple-response resolver is provided to facilitate data transfer between the processors and the controllers over a single common bus. Issues about th design of a cost-effective mass-storage system are also discussed. Performance and implementation issues for HYTREM are discussed.>

A signature file acts as a filtering mechanism to reduce the amount of text that needs to be searched for a query. Unfortunately, the signature file itself must be exhaustively searched, resulting in degraded performance for a large file size. We propose to use a deterministic algorithm to divide a signature file into partitions, each of which contains signatures with the same “key.” The signature keys in a partition can be extracted and represented as the partition's key. The search can then be confined to the subset of partitions whose keys match the query key. Our main concern here is to study methods for obtaining the keys and their performance in terms of their ability to reduce the search space. Owing to the reduction of search space, partitioning a signature file has a direct benefit in a sequential search (single-processor) environment. In a parallel environment, search can be conducted in parallel effectively by allocating one or more partitions to a processor. Partitioning the signature tile with a deterministic method (as opposed to a random partitioning scheme) provides intraquery parallelism as well as interquery parallelism. In this paper, we outline the criteria for evaluating partitioning schemes. Three algorithms are described and studied. An analytical study of the performance of the algorithms is provided and the results are verified with simulation.

The design of a word-parallel, bit-serial (WPBS) signature processor for searching superimposed codes is presented. The WPBS signature processor is based on a transposed file organization and is optimal in the sense that the smallest possible amount of data is read. As such, it performs much faster than the word-serial, bit-parallel (WSBP) signature processor proposed in the literature. In addition, it can easily accommodate signatures of different lengths in the same signature store. This feature is important in utilizing the signature store efficiently but difficult to implement with a WSBP architecture. We also discuss the implementation of the processor with magnetic bubble memory.

ABSTRACrThe design and analysis of a distributed multiple-response resolver for value-ordered retrieval is presented.It is similar to the design proposed by Ramamoorthy et.at., the fastest scheme to date in its class, but has a number of improvements over it.We present the detailed algorithm and the logic design of our scheme.Its performance is evaluated by simulation.Approximate analytical results are given as well.We also compare our design with previous designs to illustrate its superiority.The most important feature of our design is to terminate the selection process as soon as the responder set contains only one responder or the largest responder includes all the other responders in the active responder set, and to retain the history of the selection process so that succeeding retrievals do not have to start from the first bit slice.