Context- and content-aware node embeddings seek to represent graph nodes as dense vectors by modeling graph structure, node attributes, and neighborhood information. In textual attributed graphs, where nodes are paired with textual data, existing node embedding methods can face scalability challenges when large and noisy node contents are given as input. Prior work has mainly focused on proposing new node embedding methods, paying limited attention to the role of content preprocessing and the characteristics of large, real-world graphs. This work investigates the use of keyword and keyphrase extraction to simplify node content in textual graphs and evaluates its impact on established node embedding methods. Using a large, unprocessed citation graph, we show that keyword-based representations significantly reduce computational time while improving performance for the link prediction and node classification tasks. Furthermore, a graph augmentation strategy amplifies these efficiency gains as graph size increases, demonstrating the scalability advantages of content-aware preprocessing for node embeddings.

Graph Representation Learning (GRL) has become a key paradigm in network analysis, with a plethora of interdis-ciplinary applications. As the scale of networks increases, most of the widely used learning-based graph representation models also face computational challenges. While there is a recent effort toward designing algorithms that solely deal with scalability issues, most of them behave poorly in terms of accuracy on downstream tasks. In this paper, we aim to study models that balance the trade-off between efficiency and accuracy. In particular, we propose Nodesig, a scalable model that computes binary node representations. Nodesig exploits random walk diffusion probabilities via stable random projections towards efficiently computing embeddings in the Hamming space. Our extensive experimental evaluation on various networks has demonstrated that the proposed model achieves a good balance between accuracy and efficiency compared to well-known baseline models on the node classification and link prediction tasks.

Modern techniques in intrusion and DoS (Denial of Service) detection tend to be either supervised or semi-supervised, i.e., they require training and labelled data. In this work, we study the problem of correlating security attacks with anomalies reported at runtime by a fully unsupervised outlier detection module, i.e., a component that does not require any training at all. Through a concrete proof-of-concept case study, we demonstrate that unsupervised anomaly detection is both efficient and effective, but still, it needs to be combined with additional mechanisms to yield a complete intrusion detection and prevention solution.

The concept of network communities has been studied thoroughly in the network science literature since it has many important applications in diverse fields. Recently, the community concept has been combined with the concept of influence. The aim of this combination is to allow for the detection of communities that have also a high degree of influence. To achieve this, there is a need to guarantee that communities are good with respect to their structure and also influential with respect to attribute values of the nodes participating in the community. In the literature, there are two main directions to attack the problem: i) the online approach, which computes influential communities in increasing influence value order, and ii) the index-based approach, which pre-computes influential communities and stores appropriate information in a tree-based index structure. Based on these two directions, we propose a new technique with the following properties: i) there is no need to process the graph each time a new query arrives, and ii) there is no need to waste computational resources to maintain parts of the index that users are not interested in. This is achieved by starting without any index in memory. Then, using online algorithms, as new queries arrive, we incrementally build parts of the index that help answering similar future queries. Extensive experimental results, on real world graphs, demonstrate the efficiency of our method against existing approaches in most realistic cases.

The discovery of drug-target interactions (DTIs) is a very promising area of research with great potential. The accurate identification of reliable interactions among drugs and proteins via computational methods, which typically leverage heterogeneous information retrieved from diverse data sources, can boost the development of effective pharmaceuticals. Although random walk and matrix factorization techniques are widely used in DTI prediction, they have several limitations. Random walk-based embedding generation is usually conducted in an unsupervised manner, while the linear similarity combination in matrix factorization distorts individual insights offered by different views. To tackle these issues, we take a multi-layered network approach to handle diverse drug and target similarities, and propose a novel optimization framework, called Multiple similarity DeepWalk-based Matrix Factorization (MDMF), for DTI prediction. The framework unifies embedding generation and interaction prediction, learning vector representations of drugs and targets that not only retain higher order proximity across all hyper-layers and layer-specific local invariance, but also approximate the interactions with their inner product. Furthermore, we develop an ensemble method (MDMF2A) that integrates two instantiations of the MDMF model, optimizing the area under the precision-recall curve (AUPR) and the area under the receiver operating characteristic curve (AUC), respectively. The empirical study on real-world DTI datasets shows that our method achieves statistically significant improvement over current state-of-the-art approaches in four different settings. Moreover, the validation of highly ranked non-interacting pairs also demonstrates the potential of MDMF2A to discover novel DTIs.

We introduce PROUD, standing for PaRallel OUtlier Detection for streams, which is an extensible engine for continuous multi-parameter parallel distance-based outlier (or anomaly) detection tailored to big data streams. PROUD is built on top of Flink. It defines a simple API for data ingestion. It supports a variety of parallel techniques, including novel ones, for continuous outlier detection that can be easily configured. In addition, it graphically reports metrics of interest and stores main results into a permanent store to enable future analysis. It can be easily extended to support additional techniques. Finally, it is publicly provided in open-source.

Range queries are important in many diverse applications. In its simplest one-dimensional form, a range query is expressed by an interval [a, b] on the real line, whereas the answer consists of all elements e ∈ [a, b]. In this work, we focus on efficient range query processing techniques in the Apache Spark engine, which is the state-of-the-art solution for big data management and analytics. We aim at developing a Spark-based indexing scheme that supports range queries in such large-scale decentralized environments and scale well w.r.t. the number of nodes and the data items stored. Towards this goal, there have been solutions in the last few years, which however turn out to be inadequate at the envisaged scale, since the classic linear or even the logarithmic complexity (for point queries) is still too expensive, whereas range query processing is even more demanding. In this paper, we go one step further and present a solution with sub-logarithmic complexity. In particular, we present SPIS (SPark-based Interpolation Search), a tree structure that outperforms the existing Spark built-in lookup techniques. We carry out an experimental evaluation by using synthetic data sets. Our experimental results demonstrate the efficiency and scalability of the proposed approach.

The representation of real-life problems by using k-partite graphs introduced a new era in Machine Learning. Moreover, the merge of virtual and physical layers through Location Based Social Networks (LBSN s) offers a different meaning into the constructed graphs. To this point, multiple models introduced in literature that aim to support users with personalized recommendations. These approaches represent the mathematical models that aim to understand users' behaviour by finding patterns on users' check-ins, reviews, ratings, friendships, etc. With this paper we describe and compare 20 of those state-of-the-art deep learning models to bring into the surface some of their strengths and shortcomings. First, we categorize them according to: data factors or features they use, data representation, methodologies used and recommendation types they support. Then, we highlight the existing limitations that tackles their performance. Finally, we introduce research trends and future directions.

The range skyline query retrieves the dynamic skyline for every individual query point in a range by generalizing the point-based dynamic skyline query. Its wide-ranging applications enable users to submit their preferences within an interval of 'ideally sought' values across every dimension, instead of being limited to submit their preference in relation to a single sought value. This paper considers the query as a hyper-rectangle iso-oriented towards the axes of the multi-dimensional space and proposes: (i) main-memory algorithmic strategies, which are simple to implement and (ii) secondary-memory pruning mechanisms for processing range skyline queries efficiently. The proposed approach is progressive and I/O optimal. A performance evaluation of the proposed technique demonstrates its robustness and practicability.

The rapid growth of Location-based Social Networks (LBSNs) has lead to the generation of massive datasets which are collected in an exponential rate. The collected information may be used to facilitate users' needs with recommendations related to their past preferences. Many recommendation models were introduced in the literature, which learn by the history of users and provide recommendations for Points-of-Interest. Unfortunately, most of them ignore the relation existing among the temporal properties, the spatial attributes and the periodicity of the check-ins. In this work, we present a novel methodology, named JLGE, that combines all aforementioned factors into one unified approach which facilitates POI recommendations. In particular, the model jointly learns the embeddings of six informational graphs i.e., two unipartite (user-user and POIPOI) and four bipartite (user-location, user-time, location-user, and location-time) into the same latent space and personalize the recommendations based on these embeddings. We have experimentally evaluated the accuracy of our model using two real-world datasets in terms of the top-n POIs recommendations. The performance evaluation results indicate a significant improvement in accuracy, in comparison to another state-of-theart graph-based approach.

In this work, we focus on distance-based outliers in a metric space, where the status of an entity as to whether it is an outlier is based on the number of other entities in its neighborhood. In the recent years, several solutions have tackled the problem of distance-based outliers in data streams, where outliers must be mined continuously as new elements become available. An interesting research problem is to combine the streaming environment with massively parallel systems to provide scalable stream-based algorithms. However, none of the previously proposed techniques refer to a massively parallel setting. Our proposal fills this gap and studies transferring state-of-the-art techniques in Apache Flink, a modern platform for intensive streaming analytics. We thoroughly present the technical challenges encountered and the alternatives that may be applied. We show speed-ups up to 117 (resp. 2076) times over a naive parallel (resp. non-parallel) solution in Flink, by using just an ordinary 4-core machine and a real-world dataset. Our results demonstrate that oulier mining can be achieved in an efficient and scalable manner. The resulting techniques have been made publicly available in open-source.

Graph mining is an important research area with a plethora of practical applications. Core decomposition in networks, is a fundamental operation strongly related to more complex mining tasks such as community detection, dense subgraph discovery, identification of influential nodes, network visualization, text mining, just to name a few. In this tutorial, we present in detail the concept and properties of core decomposition in graphs, the associated algorithms for its efficient computation and some of its most important applications.

Top - k dominating queries combine the natural idea of selecting the k best items with a comprehensive “goodness” criterion based on dominance. A point p 1 dominates p 2 if p 1 is as good as p 2 in all attributes and is strictly better in at least one. Existing works address the problem in settings where data objects are multidimensional points. However, there are domains where we only have access to the distance between two objects. In cases like these, attributes reflect distances from a set of input objects and are dynamically generated as the input objects change. Consequently, prior works from the literature cannot be applied, despite the fact that the dominance relation is still meaningful and valid. For this reason, in this work, we present the first study for processing top- k dominating queries over distance-based dynamic attribute vectors, defined over a metric space . We propose four progressive algorithms that utilize the properties of the underlying metric space to efficiently solve the problem and present an extensive, comparative evaluation on both synthetic and real-world datasets.

Top-k dominating queries combine the natural idea of se-lecting the k best items with a comprehensive \\goodness" criterion based on dominance. A point p1 dominates p2 if p1 is as good as p2 in all attributes and is strictly better in at least one. Existing works address the problem in settings where data objects are multidimensional points. However, there are domains where we only have access to the dis-tance between two objects. In cases like these, attributes re ect distances from a set of input objects and are dynam-ically generated as the input objects change. Consequently, prior works from the literature can not be applied, despite the fact that the dominance relation is still meaningful and valid. For this reason, in this work, we present the rst study for processing top-k dominating queries over distance-based dynamic asttribute vectors, dened over a metric space. We propose four progressive algorithms that utilize the proper-ties of the underlying metric space to eciently solve the problem, and present an extensive, comparative evaluation on both synthetic and real world data sets.

The top-k dominating query returns the k database objects with the highest score with respect to their dominance score. The dominance score of an object p is simply the number of objects dominated by p, based on minimization or max-imization preferences on the attribute values. Each object (tuple) is represented as a point in a multidimensional space, and therefore, the number of attributes equals the number of dimensions. The top-k dominating query combines the dominance concept of skyline queries with the ranking func-tion of top-k queries and can be used as an important tool in multi-criteria decision making systems. In this work, we focus on the 2-dimensional space and present, for the first time, novel algorithms for top-k dominating query process-ing in main memory with non-trivial asymptotic guarantees.

Skyline queries have attracted considerable attention by the database community during the last decade, due to their applicability in a series of domains. However, most existing works tackle the problem from an efficiency standpoint, i.e., returning the skyline as quickly as possible. The user is then presented with the entire skyline set, which may be in several cases overwhelming, therefore requiring manual inspection to come up with the most informative data points. To overcome this shortcoming, we propose a novel approach in selecting the k most diverse skyline points, i.e., the ones that best capture the different aspects of both the skyline and the dataset they belong to. We present a novel formulation of diversification which, in contrast to previous proposals, is intuitive, because it is based solely on the domination relationships among points. Consequently, additional artificial distance measures (e.g., Lp norms) among skyline points are not required. We present efficient approaches in solving this problem and demonstrate the efficiency and effectiveness of our approach through an extensive experimental evaluation with both real-life and synthetic data sets.

Anomaly detection is an important data mining task, aiming at the discovery of elements that show significant diversion from the expected behavior; such elements are termed as outliers. One of the most widely employed criteria for determining whether an element is an outlier is based on the number of neighboring elements within a fixed distance (R), against a fixed threshold (k). Such outliers are referred to as distance-based outliers and are the focus of this work. In this demo, we show both an extendible framework for outlier detection algorithms and specific outlier detection algorithms for the demanding case where outlier detection is continuously performed over a data stream. More specifically: i) first we demonstrate a novel flavor of an open-source publicly available tool for Massive Online Analysis (MOA) that is endowed with capabilities to encapsulate algorithms that continuously detect outliers and ii) second, we present four online outlier detection algorithms. Two of these algorithms have been designed by the authors of this demo, with a view to improving on key aspects related to outlier mining, such as running time, flexibility and space requirements.

Top-k dominating queries use an intuitive scoring function which ranks multidimensional points with respect to their dominance power, i.e., the number of points that a point dominates. The k points with the best (e.g., highest) scores are returned to the user. Both top-k and skyline queries have been studied in a streaming environment, where changes to the data set are very frequent. In such an environment, continuous query processing techniques are required toward efficient monitoring of query results, since periodic query re-execution is computationally intensive, and therefore, prohibitive. This work contains the first study of continuous top-k dominating queries over data streams. In comparison to continuous top-k and skyline queries, continuous top-k dominating queries pose additional challenges. Three exact algorithms (BFA, EVA, ADA) are studied, and among them ADA, which is enhanced with additional optimization techniques, shows the best overall performance. In some cases, we are willing to trade accuracy for speed. Toward this direction, two approximate algorithms are proposed (AHBA and AMSA). AHBA offers probabilistic guarantees regarding the accuracy of the result based on the Hoeffding bound, whereas AMSA performs a more aggressive computation resulting in more efficient processing. Evaluation results, based on real-life and synthetic data sets, show the efficiency and scalability of our techniques.

A fundamental and very useful operation in graphs is the computation of the proximity between nodes, i.e., the degree of dissimilarity (or similarity) between two nodes v and u. This is an important tool both in graph databases and graph mining applications, because it provides the base to support more complex tasks such as graph partitioning, clustering, classification, to name a few. All methods proposed in the literature assume that proximity is computed on a single graph by using a single distance measure. In addition, most of them focus on the proximity between node pairs. In this work, we present for the first time, scalable algorithms that: (i) they support proximity computation in multiple graph instances, (ii) they enable the utilization of several distance measures, (iii) they support proximity queries around a source node without limiting to node pairs and (iv) they support extensions for metric-based and skyline query processing. The main result of our work is the design of Threshold Algorithms for Graphs (denoted as TAGs), which are studied and evaluated experimentally by using real-life as well as synthetic graphs, based on both the G(n, p) Erdõs-Rényi model and power law degree distributions.

Anomaly detection is considered an important data mining task, aiming at the discovery of elements (also known as outliers) that show significant diversion from the expected case. More specifically, given a set of objects the problem is to return the suspicious objects that deviate significantly from the typical behavior. As in the case of clustering, the application of different criteria lead to different definitions for an outlier. In this work, we focus on distance-based outliers: an object x is an outlier if there are less than k objects lying at distance at most R from x. The problem offers significant challenges when a stream-based environment is considered, where data arrive continuously and outliers must be detected on-the-fly. There are a few research works studying the problem of continuous outlier detection. However, none of these proposals meets the requirements of modern stream-based applications for the following reasons: (i) they demand a significant storage overhead, (ii) their efficiency is limited and (iii) they lack flexibility. In this work, we propose new algorithms for continuous outlier monitoring in data streams, based on sliding windows. Our techniques are able to reduce the required storage overhead, run faster than previously proposed techniques and offer significant flexibility. Experiments performed on real-life as well as synthetic data sets verify our theoretical study.

This work studies the problem of 2-dimensional searching for the 3-sided range query of the form [a, b] x (-∞, c] in both main and external memory, by considering a variety of input distributions. A dynamic linear main memory solution is proposed, which answers 3-sided queries in O(log n + t) worst case time and scales with O (log log n) expected with high probability update time, under continuous μ-random distributions of the x and y coordinates, where n is the current number of stored points and t is the size of the query output. Our expected update bound constitutes a considerable improvement over the O(log n) update time bound achieved by the classic Priority Search Tree of McCreight [23], as well as over the Fusion Priority Search Tree of Willard [30], which requires O(log n/log log n) time for all operations. Moreover, we externalize this solution, gaining O(logB n + t/B) worst case and O(logBlogn) amortized expected with high probability I/Os for query and update operations respectively, where B is the disk block size. Then, combining the Modified Priority Search Tree [27] with the Priority Search Tree [23], we achieve a query time of O(log log n + t) expected with high probability and an update time of O(log log n) expected with high probability, under the assumption that the x-coordinates are continuously drawn from a smooth distribution and the y-coordinates are continuously drawn from a more restricted class of distributions. The total space is linear. Finally, we externalize this solution, obtaining a dynamic data structure that answers 3-sided queries in O(logB log n + t/B) I/Os expected with high probability, and it can be updated in O(logB log n) I/Os amortized expected with high probability and consumes O(n/B) space, under the same assumptions.

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.

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.

Performing data mining tasks in streaming data is considered a challenging research direction, due to the continuous data evolution. In this work, we focus on the problem of clustering streaming time series, based on the sliding window paradigm. More specifically, we use the concept of alpha-clusters in each time instance separately. A subspace alpha-cluster consists of a set of streams, whose value difference is less than a in a consecutive number of time instances (dimensions). The clusters can be continuously and incrementally updated as the streaming time series evolve. The proposed technique is based on a careful examination of pair-wise stream similarities for a subset of dimensions and then, it is generalized for more streams per cluster. Performance evaluation results show that the proposed pruning criteria are important for search space reduction, and that the cost of incremental cluster monitoring is computationally more efficient than reclustering

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.

Similarity queries are fundamental operations that are used extensively in many modern applications, whereas disk arrays are powerful storage media of increasing importance. The basic trade-off in similarity query processing in such a system is that increased parallelism leads to higher resource consumptions and low throughput, whereas low parallelism leads to higher response times. Here, we propose a technique which is based on a careful investigation of the currently available data in order to exploit parallelism up to a point, retaining low response times during query processing. The underlying access method is a variation of the R*-tree, which is distributed among the components of a disk array, whereas the system is simulated using event-driven simulation. The performance results conducted, demonstrate that the proposed approach outperforms by factors a previous branch-and-bound algorithm and a greedy algorithm which maximizes parallelism as much as possible. Moreover, the comparison of the proposed algorithm to a hypothetical (non-existing) optimal one (with respect to the number of disk accesses) shows that the former is on average two times slower than the latter.

A new issue that arises in modern applications involves the efficient manipulation of (static or moving) spatial objects, and the relationships among them. As a result, modern database systems should be able to efficiently support that type of data. Towards this goal, appropriate extensions of multidimensional access methods can be exploited in order to index and retrieve spatiotemporal objects, satisfying users' demands. This paper introduces the basic specifications such a spatiotemporal index structure should follow, evaluates existing proposals with respect to the above specifications, and illustrates issues of interest involving object representation, query processing, and index maintenance.