Deep neural networks (DNNs), in addition to great power, exhibit significant weaknesses, with one of the most notable being the susceptibility to adversarial attacks by carefully crafted, minimally perturbed, adversarial examples. Despite numerous efforts towards creating reliable detectors and defense mechanisms, the underlying factors that make such attacks possible have not yet been fully understood. In this paper, we further explore the use of local intrinsic dimensionality (LID), and, for the first time, hubness, as indicators for detection of adversarial examples. Furthermore, we involve neural tangent kernels (NTKs) in this task, showing that NTK-induced distance measures offer more information on how to detect adversarial examples, through both LID and hubness, than distances computed on raw input data or one network layer. Furthermore, we combine LID and hubness as features into a well-performing classifier that exhibits better detection accuracy than any of the two features used on their own. Finally, we combine the LID and hubness features with state-of-the-art adversarial attack detectors, demonstrating their general usefulness for the task. Our findings offer insight into the properties and nature of adversarial examples of various types, paving the way to the construction of better detectors and, possibly, the construction of models that are more robust to such attacks.

Abstract We examine the problem of handling uncertainty in the predictions for out-of-distribution data (OOD) when classifying time series with distortions, such as gaps, that can occur due to operating conditions in production environments. This problem can find several application domains, including predictive maintenance. We focus on Conformal Prediction (CP) as a framework for handling the uncertainty in predictions for OOD time series that occurs due to distortions. Our study focuses on the potential impact of OOD time series on the performance of CP, by assessing the size and coverage of the resulting prediction sets. The motivation for this study is that neural networks, which are widely used for time-series classification, may suffer from overconfidence. This fact negatively impacts CP when faced with OOD data, because incorrect predictions with high confidence can have catastrophic consequences in high-risk applications. To alleviate this problem, we propose two model-agnostic methods: the use of various forms of label smoothing as well as the use of hybrid classifiers. Our experimental findings in the context of prominent time-series classifiers demonstrate that the coverage of CP may be maintained around a desirable level without needlessly expanding the size of the prediction sets.

In recommender systems user preferences can be fairly dynamic, as users tend to exploit a wide range of items and modify their tastes accordingly over time. In this paper, we model user-item interactions over time using a tensor that has time as a dimension (mode). To account for the fact that user preferences change individually, we propose a new measure of user-preference dynamics (UPD) that captures the rate with which the current preferences of each user have been shifted. UPD shows the variability in how users interact with items in recommender systems. We generate recommendations based on a tensor factorization technique, where the importance of past user preferences are weighted according to their UPD values, that is, higher UPD values downweigh more past user preferences. Additionally, we exploit users' side data, such as demographics, which improve the accuracy of recommendations based on a coupled tensor-matrix factorization scheme. Our empirical evaluation uses two real benchmark datasets from the social media platforms Last.fm and MovieLens, containing users' history records pertaining to listening to songs and viewing movies, respectively. We demonstrate that in both datasets, there are users with a varying level of dynamics, expressed by the UPD metric. Our experimental results show that the proposed method outperforms several baselines, by taking into account both dynamics and side data of users.

Outlier detection in high-dimensional data presents various challenges resulting from the “curse of dimensionality.” A prevailing view is that distance concentration, i.e., the tendency of distances in high-dimensional data to become indiscernible, hinders the detection of outliers by making distance-based methods label all points as almost equally good outliers. In this paper, we provide evidence supporting the opinion that such a view is too simple, by demonstrating that distance-based methods can produce more contrasting outlier scores in high-dimensional settings. Furthermore, we show that high dimensionality can have a different impact, by reexamining the notion of reverse nearest neighbors in the unsupervised outlier-detection context. Namely, it was recently observed that the distribution of points' reverse-neighbor counts becomes skewed in high dimensions, resulting in the phenomenon known as hubness. We provide insight into how some points (antihubs) appear very infrequently in k-NN lists of other points, and explain the connection between antihubs, outliers, and existing unsupervised outlier-detection methods. By evaluating the classic k-NN method, the angle-based technique designed for high-dimensional data, the density-based local outlier factor and influenced outlierness methods, and antihub-based methods on various synthetic and real-world data sets, we offer novel insight into the usefulness of reverse neighbor counts in unsupervised outlier detection.

In this paper we extend the current state-of-the-art matrix factorization method for recommendations to general probability distributions. As shown in previous work, the standard method called "Probabilistic Matrix Factorization" is based on a normal distribution assumption. While there exists work in which this method is extended to other distributions, these extensions are restrictive and we experimentally show on the basis of a real data set that it is worthwhile considering more general distributions which have not been used in the literature. Our contribution lies in providing a flexible and easy-to-use framework for matrix factorization with almost no limitation on the form of the distribution used. Our approach is based on maximum likelihood estimation and a key ingredient of our proposed method is automatic differentiation. This allows for the automatic derivation of the corresponding optimization algorithm, without the need to derive it manually for each distributional assumption while simultaneously being computationally efficient. Thus, with our method it is very easy to use a wide range of even complicated distributions for any data set.

In several applications, user preferences can be fairly dynamic, since users tend to exploit a wide range of items and modify their tastes accordingly over time. In this paper, we model continuous user-item interactions over time using a tensor that has time as a dimension (mode). To account for the fact that user preferences are dynamic and change individually, we propose a new measure of user-preference dynamics (UPD) that captures the rate with which the current preferences of each user have been shifted. We generate recommendations based on factorizing the tensor, by weighting the importance of past user preferences according to their UPD values. We additionally exploit users' side data, such as demographics, which can help improving the accuracy of recommendations based on a coupled, tensor-matrix factorization scheme. Our empirical evaluation uses a real data set from last.fm, which allows us to demonstrate that user preferences can become very dynamic. Our experimental results show that the proposed method, by taking into account these dynamics, outperforms several baselines.

A key challenge in recommender systems is how to profile new users. A well-known solution for this problem is to use active learning techniques and ask the new user to rate a few items to reveal her preferences. The sequence of queries should not be static, i.e in each step the best query depends on the responses of the new user to the previous queries. Decision trees have been proposed to capture the dynamic aspect of this process. In this paper we improve decision trees in two ways. First, we propose the Most Popular Sampling (MPS) method to increase the speed of the tree construction. In each node, instead of checking all candidate items, only those which are popular among users associated with the node are examined. Second, we develop a new algorithm to build decision trees. It is called Factorized Decision Trees (FDT) and exploits matrix factorization to predict the ratings at nodes of the tree. The experimental results on the Netflix dataset show that both contributions are successful. The MPS increases the speed of the tree construction without harming the accuracy. And FDT improves the accuracy of rating predictions especially in the last queries.

Data sparsity is an emerging real-world problem observed in a various domains ranging from sensor networks to medical diagnosis. Consecutively, numerous machine learning methods were modeled to treat missing values. Nevertheless, sparsity, defined as missing segments, has not been thoroughly investigated in the context of time series classification. We propose a novel principle for classifying time series, which in contrast to existing approaches, avoids reconstructing the missing segments in time series and operates solely on the observed ones. Based on the proposed principle, we develop a method that prevents adding noise that incurs during the reconstruction of the original time series. Ourmethod adapts supervised matrix factorization by projecting time series in a latent space through stochasticlearning. Furthermore the projected data is built in a supervised fashion via a logistic regression. Abundant experiments on a large collection of 37 data sets demonstrate the superiority of our method, which in the majority of cases outperforms a set of baselines that do not follow our proposed principle.

Recommender systems help web users to address information overload. However their performance depends on the number of provided ratings by users. This problem is amplified for a new user because he/she has not provided any rating. To address this problem, active learning methods have been proposed to acquire those ratings from users, that will help most in determining their interests. However, different from the classic active learning, users (the "oracle") are not always able to provide an answer for queries. The easiest way to solve this problem is to ask most popular items, i.e items which have received many ratings from training users. But it is static and presents the same items to all users regardless of the ratings they have provided so far. In this paper we propose a method that improves the most popular selection strategy using the characteristics of matrix factorization. It finds similar users to the new user in the latent space and then selects item which is most popular among the similar users. The experimental results show the proposed method outperforms the most popular method both in terms of error and the number of received ratings.

Due to its various applications, time-series classification is a prominent research topic in data mining and computational intelligence. The simple k-NN classifier using dynamic time warping (DTW) distance had been shown to be competitive to other state-of-the art time-series classifiers. In our research, however, we observed that a single fixed choice for the number of nearest neighbors k may lead to suboptimal performance. This is due to the complexity of time-series data, especially because the characteristic of the data may vary from region to region. Therefore, local adaptations of the classification algorithm is required. In order to address this problem in a principled way by, in this paper we introduce individual quality (IQ) estimation. This refers to estimating the expected classification accuracy for each time series and each k individually. Based on the IQ estimations we combine the classification results of several k-NN classifiers as final prediction. In our framework of IQ, we develop two time-series classification algorithms, IQ-MAX and IQ-WV. In our experiments on 35 commonly used benchmark data sets, we show that both IQ-MAX and IQ-WV outperform two baselines.

Recommender systems help Web users to address information overload. Their performance, however, depends on the amount of information that users provide about their preferences. Users are not willing to provide information for a large amount of items, thus the quality of recommendations is affected specially for new users. Active learning has been proposed in the past, to acquire preference information from users. Based on an underlying prediction model, these approaches determine the most informative item for querying the new user to provide a rating. In this paper, we propose a new active learning method which is developed specially based on aspect model features. There is a difference between classic active learning and active learning for recommender system. In the recommender system context, each item has already been rated by training users while in classic active learning there is not training user. We take into account this difference and develop a new method which competes with a complicated bayesian approach in accuracy while results in drastically reduced (one order of magnitude) user waiting times, i.e., the time that the users wait before being asked a new query.

Measuring similarity of two musical pieces is an ill-defined problem for which recent research on contextual information, assigned as free-form text (tags) in social networking services, has shown to be highly effective. Nevertheless, approaches based on contextual information require adequate amount of tags per musical datum in order to be effective. In the case of the so called "cold-start" problem, this assumption is not valid for several music data. In this paper, we address this problem by proposing a combination of the audio and the tag feature space of musical data. The application of the proposed combination for musical data lacking contextual information is shown, through experimental results with real musical data, to evaluate more accurately their similarity than the use of solely audio-based similarity.

Similarity measurement between musical pieces is a hard problem. Recent research on contextual information assigned (tags) in social networking services has shown to be highly effective in measuring musical similarity. Nevertheless, such an approach requires adequate amount of tags assigned to each musical datum. In the case of the so called “cold-start” problem, this assumption is not valid for several music data. Herein, we address this problem by proposing the utilisation of a learning mechanism that maps musical data from audio feature space to tag feature space. The developed mapping can be applied to musical data with no or limited contextual information, in order to more accurately evaluate similarity and avoid the sole use of audio-based similarity measures that may affect the similarity measurement quality. Experimental results with real musical data illustrate the substantial gains of the proposed method.

Recommender systems help web users to address information overload. However their performance depends on the number of provided ratings by users. This problem is amplified for a new user because he/she has not provided any rating. To address this problem, active learning methods have been proposed to acquire those ratings from users, that will help most in determining their interests. The optimal active learning selects a query that directly optimizes the expected error for the test data. This approach is applicable for prediction models in which this question can be answered in closed-form given the distribution of test data is known. Unfortunately, there are many tasks and models for which the optimal selection cannot efficiently be found in closed-form. Therefore, most of the active learning methods optimize different, non-optimal criteria, such as uncertainty. Nevertheless, in this paper we exploit the characteristics of matrix factorization, which leads to a closed-form solution and by being inspired from existing optimal active learning for the regression task, develop a method that approximates the optimal solution for recommender systems. Our results demonstrate that the proposed method improves the prediction accuracy of MF.

Along with the new opportunities introduced by Web 2.0 and collaborative tagging systems, several challenges have to be addressed too, notably, the problem of information overload. Recommender systems are among the most successful approaches for increasing the level of relevant content over the “noise.” Traditional recommender systems fail to address the requirements presented in collaborative tagging systems. This paper considers the problem of item recommendation in collaborative tagging systems. It is proposed to model data from collaborative tagging systems with three-mode tensors, in order to capture the three-way correlations between users, tags, and items. By applying multiway analysis, latent correlations are revealed, which help to improve the quality of recommendations. Moreover, a hybrid scheme is proposed that additionally considers content-based information that is extracted from items. Experimental comparison, using data from a real collaborative tagging system (Last.fm), against both recent tag-aware and traditional (non tag aware) item recommendation algorithms indicates significant improvements in recommendation quality. Moreover, the experimental results illustrate the advantage of the proposed hybrid scheme.

The integration of OLAP with web-search technologies is a promising research topic. Recommender systems are popular web-search mechanisms, because they can address information overload and provide personalization of results. Nevertheless, the evaluation of recommender systems is a challenging task. In this paper, we propose a novel framework for evaluating recommender systems, which is multidimensional and takes into account for the multiple facets of the recommendation algorithms, data sets and performance measures. Emphasis is placed on supporting business applications of recommender systems, notably e-commerce, by allowing analysts to perform ad-hoc analysis and use popular online analytical processing (OLAP) operations. Combined with support for visual analysis, action such as drill-down or slice/dice allow assessment of the performance of recommendations in terms of business objectives. We describe a detailed methodology for designing and developing the proposed multidimensional framework, and provide insights about its applications. Our experimental results, using a research prototype, demonstrate the ability of the proposed framework to comprise an effective way for evaluating recommender systems.

In the context of many data mining tasks, high dimensionality was shown to be able to pose significant problems, commonly referred to as different aspects of the curse of dimensionality. In this paper, we investigate in the time-series domain one aspect of the dimensionality curse called hubness, which refers to the tendency of some instances in a data set to become hubs by being included in unexpectedly many k-nearest neighbor lists of other instances. Through empirical measurements on a large collection of time-series data sets we demonstrate that the hubness phenomenon is caused by high intrinsic dimensionality of time-series data, and shed light on the mechanism through which hubs emerge, focusing on the popular and successful dynamic time warping (DTW) distance. Also, the interaction between hubness and the information provided by class labels is investigated, by considering label matches and mismatches between neighboring time series. Following our findings we formulate a framework for categorizing time-series data sets based on measurements that reflect hubness and the diversity of class labels among nearest neighbors. The framework allows one to assess whether hubness can be successfully used to improve the performance of k-NN classification. Finally, the merits of the framework are demonstrated through experimental evaluation of 1-NN and k-NN classifiers, including a proposed weighting scheme that is designed to make use of hubness information. Our experimental results show that the examined framework, in the majority of cases, is able to correctly reflect the circumstances in which hubness information can effectively be employed in k-NN time-series classification.

The vector space model (VSM) is a popular and widely applied model in information retrieval (IR). VSM creates vector spaces whose dimensionality is usually high (e.g., tens of thousands of terms). This may cause various problems, such as susceptibility to noise and difficulty in capturing the underlying semantic structure, which are commonly recognized as different aspects of the "curse of dimensionality." In this paper, we investigate a novel aspect of the dimensionality curse, which is referred to as hubness and manifested by the tendency of some documents (called hubs) to be included in unexpectedly many search result lists. Hubness may impact VSM considerably since hubs can become obstinate results, irrelevant to a large number of queries, thus harming the performance of an IR system and the experience of its users. We analyze the origins of hubness, showing it is primarily a consequence of high (intrinsic) dimensionality of data, and not a result of other factors such as sparsity and skewness of the distribution of term frequencies. We describe the mechanisms through which hubness emerges by exploring the behavior of similarity measures in high-dimensional vector spaces. Our consideration begins with the classical VSM (tf-idf term weighting and cosine similarity), but the conclusions generalize to more advanced variations, such as Okapi BM25. Moreover, we explain why hubness may not be easily mitigated by dimensionality reduction, and propose a similarity adjustment scheme that takes into account the existence of hubs. Experimental results over real data indicate that significant improvement can be obtained through consideration of hubness.

Social tagging is becoming increasingly popular in music information retrieval (MIR). It allows users to tag music items like songs, albums, or artists. Social tags are valuable to MIR, because they comprise a multifaced source of information about genre, style, mood, users' opinion, or instrumentation. In this paper, we examine the problem of personalized music recommendation based on social tags. We propose the modeling of social tagging data with three-order tensors, which capture cubic (three-way) correlations between users-tags-music items. The discovery of latent structure in this model is performed with the Higher Order Singular Value Decomposition (HOSVD), which helps to provide accurate and personalized recommendations, i.e., adapted to the particular users' preferences. To address the sparsity that incurs in social tagging data and further improve the quality of recommendation, we propose to enhance the model with a tag-propagation scheme that uses similarity values computed between the music items based on audio features. As a result, the proposed model effectively combines both information about social tags and audio features. The performance of the proposed method is examined experimentally with real data from Last.fm. Our results indicate the superiority of the proposed approach compared to existing methods that suppress the cubic relationships that are inherent in social tagging data. Additionally, our results suggest that the combination of social tagging data with audio features is preferable than the sole use of the former.

Social tagging is the process by which many users add metadata in the form of keywords, to annotate and categorize items (songs, pictures, Web links, products, etc.). Social tagging systems (STSs) can provide three different types of recommendations: They can recommend 1) tags to users, based on what tags other users have used for the same items, 2) items to users, based on tags they have in common with other similar users, and 3) users with common social interest, based on common tags on similar items. However, users may have different interests for an item, and items may have multiple facets. In contrast to the current recommendation algorithms, our approach develops a unified framework to model the three types of entities that exist in a social tagging system: users, items, and tags. These data are modeled by a 3-order tensor, on which multiway latent semantic analysis and dimensionality reduction is performed using both the higher order singular value decomposition (HOSVD) method and the kernel-SVD smoothing technique. We perform experimental comparison of the proposed method against state-of-the-art recommendation algorithms with two real data sets (Last.fm and BibSonomy). Our results show significant improvements in terms of effectiveness measured through recall/precision.

Music expresses emotion. A number of audio extracted features have influence on the perceived emotional expression of music. These audio features generate a high-dimensional space, on which music similarity retrieval can be performed effectively, with respect to human perception of the music-emotion. However, the real-time systems that retrieve music over large music databases, can achieve order of magnitude performance increase, if applying multidimensional indexing over a dimensionally reduced audio feature space. To meet this performance achievement, in this paper, extensive studies are conducted on a number of dimensionality reduction algorithms, including both classic and novel approaches. The paper clearly envisages which dimensionality reduction techniques on the considered audio feature space, can preserve in average the accuracy of the emotion-based music retrieval.

High dimensionality can pose severe difficulties, widely recognized as different aspects of the curse of dimensionality. In this paper we study a new aspect of the curse pertaining to the distribution of k-occurrences, i.e., the number of times a point appears among the k nearest neighbors of other points in a data set. We show that, as dimensionality increases, this distribution becomes considerably skewed and hub points emerge (points with very high k-occurrences). We examine the origin of this phenomenon, showing that it is an inherent property of high-dimensional vector space, and explore its influence on applications based on measuring distances in vector spaces, notably classification, clustering, and information retrieval.

Tag recommendation is the task of predicting a personalized list of tags for a user given an item. This is important for many websites with tagging capabilities like last.fm or delicious. In this paper, we propose a method for tag recommendation based on tensor factorization (TF). In contrast to other TF methods like higher order singular value decomposition (HOSVD), our method RTF ('ranking with tensor factorization') directly optimizes the factorization model for the best personalized ranking. RTF handles missing values and learns from pairwise ranking constraints. Our optimization criterion for TF is motivated by a detailed analysis of the problem and of interpretation schemes for the observed data in tagging systems. In all, RTF directly optimizes for the actual problem using a correct interpretation of the data. We provide a gradient descent algorithm to solve our optimization problem. We also provide an improved learning and prediction method with runtime complexity analysis for RTF. The prediction runtime of RTF is independent of the number of observations and only depends on the factorization dimensions. Besides the theoretical analysis, we empirically show that our method outperforms other state-of-the-art tag recommendation methods like FolkRank, PageRank and HOSVD both in quality and prediction runtime.

A crucial operation in memory-based collaborative filtering (CF) is determining nearest neighbors (NNs) of users/items. This paper addresses two phenomena that emerge when CF algorithms perform NN search in high-dimensional spaces that are typical in CF applications. The first is similarity concentration and the second is the appearance of hubs (i.e. points which appear in $k$-NN lists of many other points). Through theoretical analysis and experimental evaluation we show that these phenomena are inherent properties of high-dimensional space, unrelated to other data properties like sparsity, and that they can impact CF algorithms by questioning the meaning and representativeness of discovered NNs. Moreover, we show that it is not easy to mitigate the phenomena using dimensionality reduction. Studying these phenomena aims to provide a better understanding of the limitations of memory-based CF and motivate the development of new algorithms that would overcome them.

Providing justification to a recommendation gives credibility to a recommender system. Some recommender systems (Amazon.com etc.) try to explain their recommendations, in an effort to regain customer acceptance and trust. But their explanations are poor, because they are based solely on rating data, ignoring the content data. Our prototype system MoviExplain is a movie recommender system that provides both accurate and justifiable recommendations.

Due to the rapidly increasing availability of audio files on the Web, it is relevant to augment search engines with advanced audio search functionality. In this context, the ranking of the retrieved music is an important issue. This paper proposes a music ranking method capable of flexibly fusing the music based on its relevance and importance. The fusion is controlled by a single parameter, which can be intuitively tuned by the user. The notion of authoritative music among relevant music is introduced, and social media mined from the Web is used in an innovative manner to determine both the relevance and importance of music. The proposed method may support users with diverse needs when searching for music.

Social tagging is the process by which many users add metadata in the form of keywords, to annotate and categorize information items (songs, pictures, web links, products etc.). Collaborative tagging systems recommend tags to users based on what tags other users have used for the same items, aiming to develop a common consensus about which tags best describe an item. However, they fail to provide appropriate tag recommendations, because: (i) users may have different interests for an information item and (ii) information items may have multiple facets. In contrast to the current tag recommendation algorithms, our approach develops a unified framework to model the three types of entities that exist in a social tagging system: users, items and tags. These data is represented by a 3-order tensor, on which latent semantic analysis and dimensionality reduction is performed using the Higher Order Singular Value Decomposition (HOSVD) technique. We perform experimental comparison of the proposed method against two state-of-the-art tag recommendations algorithms with two real data sets (Last.fm and BibSonomy). Our results show significant improvements in terms of effectiveness measured through recall/precision.

Wireless networks introduce new opportunities for music delivery. The trend of using mobile devices on wireless networks can significantly extent the recent change of paradigm in the model of music distribution by allowing mobile clients to search for audio music in a network of wireless mobile hosts. This paper introduces the application of content-based music information retrieval (CBMIR) in wireless ad-hoc networks. We investigate, for the first time in the literature, the challenges posed by the wireless medium and recognize the factors that require optimization. We propose novel techniques that attain a significant reduction in both response time and network traffic, compared to naive approaches. Extensive experimental results illustrate the appropriateness, effectiveness, and efficiency of the proposed method to this bandwidth-starving and volatility due to mobility and environment.

Recommender systems are gaining widespread acceptance in e-commerce applications to confront the ldquoinformation overloadrdquo problem. Providing justification to a recommendation gives credibility to a recommender system. Some recommender systems (Amazon.com, etc.) try to explain their recommendations, in an effort to regain customer acceptance and trust. However, their explanations are not sufficient, because they are based solely on rating or navigational data, ignoring the content data. Several systems have proposed the combination of content data with rating data to provide more accurate recommendations, but they cannot provide qualitative justifications. In this paper, we propose a novel approach that attains both accurate and justifiable recommendations. We construct a feature profile for the users to reveal their favorite features. Moreover, we group users into biclusters (i.e., groups of users which exhibit highly correlated ratings on groups of items) to exploit partial matching between the preferences of the target user and each group of users. We have evaluated the quality of our justifications with an objective metric in two real data sets (Reuters and MovieLens), showing the superiority of the proposed method over existing approaches.

Server-initiated broadcast, compared to unicast transmission, presents excellent scalability to requests by multiple clients in wireless networks. In a wireless network, many mobile clients may have overlapping interests about the same visual information, thus image broadcasting is expected to find acceptance in wireless broadcast networks (WBNs). In this paper, we examine for the first time, to our knowledge, the problem of image broadcasting in WBNs. We propose a novel method that significantly reduces the time latency perceived by clients that request images. We also consider the issue of energy consumption, since portable devices operate with batteries and therefore energy limitations are posed. Experimental results verify the superiority of the proposed method against existing techniques from other domains.

Collaborative filtering (CF) systems are gaining widespread acceptance in recommender systems and e-commerce applications. These systems combine information retrieval and data mining techniques to provide recommendations for products, based on suggestions of users with similar preferences. Nearest-neighbor CF process is influenced by several factors, which were not examined carefully in past work. In this paper, we bring to surface these factors in order to identify existing false beliefs. Moreover, by being able to view the "big picture" from the CF process, we propose new approaches that substantially improve the performance of CF algorithms. For instance, we obtain more than 40% percent increase in precision in comparison to widely-used CF algorithms. We perform an extensive experimental evaluation, with several real data sets, and produce results that invalidate some existing beliefs and illustrate the superiority of the proposed extensions

In several applications, data objects are assumed to move on predefined spatial networks such as road segments, railways, and invisible air routes. Moving objects may exhibit similarity with respect to their traversed paths, and therefore two objects can be correlated based on their path similarity. In this paper, we study similarity search for moving object trajectories for spatial networks. The problem poses some important challenges, since it is quite different from the case where objects are allowed to move without motion restrictions. Experimental results performed on real-life spatial networks show that trajectory similarity can be supported in an effective and efficient manner by using metric-based access methods

Distance join queries are used in many modern applications, such as spatial databases, spatiotemporal databases and data mining. One of the most common distance join queries is the closest-pair query (CPQ). Given two datasets DA and DB the CPQ retrieves the pair (a, b), where a ∈ DA and b ∈ DB⁠, having the smallest distance between all pairs of objects. An extension to this problem is to generate the k closest pairs of objects (k-CPQ). In several cases spatial constraints are applied, and object pairs that are retrieved must also satisfy these constraints. Although the application of spatial constraints seems natural towards a more focused search, only recently they have been studied for the CPQ problem with the restriction that DA = DB⁠. In this work, we focus on constrained closest-pair queries, between two distinct datasets DA and DB⁠, where objects from DA must be enclosed by a spatial region R. Several algorithms are presented and evaluated using real-life and synthetic datasets. Among them, a heap-based method enhanced with batch capabilities outperforms the other approaches as it is demonstrated by an extensive performance evaluation.

This paper presents an algorithm that efficiently retrieves audio data similar to an audio query. The proposed method utilises a feature extraction method for acoustical music sequences. The extracted features are grouped by Minimum Bounding Rectangles (MBRs) and indexed by means of a spatial access method. We also present a novel false alarm resolution method that utilises a reverse order schema while calculating the distance of the query and results, in order to avoid costly operations. Performance evaluation results show that the proposed technique achieves considerable performance improvement in comparison to an existing method.

Since its introduction in 1984, R-tree has been proven to be one of the most practical and well-behaved data structures for accommodating dynamic massive sets of geometric objects and conducting a very diverse set of queries on such datasets in real-world applications. This success has led to a variety of versions, each one trying to tune the performance parameters of the original proposal. Among them, the most prominent one is R*-tree, which employs a number of carefully designed heuristics and is widely ccepted as achieving the best performance in most cases. However, in the presence of actively changing datasets, R*-tree still does not avoid performance tuning with forced reinsertion, i.e. a process that performs a kind of local rebuilding. The latter fact has motivated the investigation of the adaptation of a known dynamization technique, based on carefully triggered local rebuildings, for converting static or semi-dynamic, main memory data structures to dynamic ones onto R*-trees. In this paper, we present LR-trees, a new efficient scheme for dynamic manipulation of large datasets, which combines the search performance of the bulk-loaded R-trees with the updated performance of R*-trees. Experimental results provide evidence on the latter statement and illustrate the superiority of the proposed method.

Predictive Web prefetching refers to the mechanism of deducing the forthcoming page accesses of a client based on its past accesses. In this paper, we present a new context for the interpretation of Web prefetching algorithms as Markov predictors. We identify the factors that affect the performance of Web prefetching algorithms. We propose a new algorithm called WM,,, which is based on data mining and is proven to be a generalization of existing ones. It was designed to address their specific limitations and its characteristics include all the above factors. It compares favorably with previously proposed algorithms. Further, the algorithm efficiently addresses the increased number of candidates. We present a detailed performance evaluation of WM, with synthetic and real data. The experimental results show that WM/sub o/ can provide significant improvements over previously proposed Web prefetching algorithms.

In this paper we describe a new density-biased sampling algorithm. It exploits spatial indexes and the local density information they preserve, to provide improved quality of sampling result and fast access to elements of the dataset. It attains improved sampling quality, with respect to factors like skew, noise or dimensionality. Moreover, it has the advantage of efficiently handling dynamic updates, and it requires low execution times. The performance of the proposed method is examined experimentally. The comparative results illustrate its superiority over existing methods.

Signature-based tree structures which have been proposed in the past do not perform well for large databases. The problem arises from the fact that they are incapable of pruning searching, especially at the upper tree levels, and thus they have decreased selectivities. In this paper, we locate a number of reasons for this problem and propose several methods for node splitting and partial-tree restructuring, which lead to improved query-response times. We have implemented all methods and we present experimental results, which indicate that the proposed methods are superior in all cases to the standard one and up to 5–10 times better for medium and higher weights in inclusive (partial-match) queries. Additionally, we have developed new functions for the performance estimation of signature trees which, in contrast to a previous estimation function, are able to take into account the outcome of different split methods and to provide more accurate estimation.