The widespread deployment of machine learning systems in critical real-world decision-making applications has highlighted the urgent need for counterfactual explainability methods that operate effectively. Global counterfactual explanations, expressed as actions to offer recourse, aim to provide succinct explanations and insights applicable to large population subgroups. High effectiveness, measured by the fraction of the population that is provided recourse, ensures that the actions benefit as many individuals as possible. Keeping the cost of actions low ensures the proposed recourse actions remain practical and actionable. Limiting the number of actions that provide global counterfactuals is essential to maximize interpretability. The primary challenge, therefore, is to balance these trade-offs—maximizing effectiveness, minimizing cost, while maintaining a small number of actions. We introduce GLANCE, a versatile and adaptive algorithm that employs a novel agglomerative approach, jointly considering both the feature space and the space of counterfactual actions, thereby accounting for the distribution of points in a way that aligns with the model's structure. This design enables the careful balancing of the trade-offs among the three key objectives, with the size objective functioning as a tunable parameter to keep the actions few and easy to interpret. Our extensive experimental evaluation demonstrates that GLANCE consistently shows greater robustness and performance compared to existing methods across various datasets and models.

This paper investigates the trade-offs between effectiveness, fairness, and privacy in job recommender systems that suggest job seekers for specific job postings. We assume that the system cannot be trusted with sensitive attributes of job seekers (e.g., nationality, gender), yet it must still ensure fair representation of all sensitive groups in the recommendation list. This creates a fundamental tension between fairness and privacy. To address this, we propose a novel framework that enhances fairness even when sensitive attributes are perturbed using a local differential privacy mechanism. Extensive experiments on real-world job platform data demonstrate that our framework can maintain fairness, even under strong privacy constraints.

The rapid integration of machine learning (ML) into critical decisionmaking systems has heightened concerns over fairness, particularly regarding spatial biases often tied to sensitive socioeconomic factors. In response, we propose a model-agnostic post-processing method for spatial bias mitigation that operates without access to the original training data. Our approach formulates an optimization problem that minimizes a fairness measure robust to gerrymandering, subject to a constraint specifying the allowable deviation from the original model's performance ensuring spatial fairness while preserving accuracy. This measure has a 0–1 scale, offering an intuitive way to quantify spatial bias. Comprehensive evaluations on real-world datasets show that our framework effectively reduces spatial bias and achieves fairer outcomes with minimal performance loss, outperforming other state-of-the-art post-processing methods. This work advances spatial fairness methodologies, offering practitioners an efficient, interpretable, and adaptable post-processing solution to mitigate location-based discrimination in ML applications.

For many use-cases, it is often important to explain the prediction of a black-box model by identifying the most influential training data samples. Existing approaches lack customization for user intent and often provide a homogeneous set of explanation samples, failing to reveal the model's reasoning from different angles. In this paper, we propose AIDE, an approach for providing antithetical (i.e., contrastive), intent-based, diverse explanations for opaque and complex models. AIDE distinguishes three types of explainability intents: interpreting a correct, investigating a wrong, and clarifying an ambiguous prediction. For each intent, AIDE selects an appropriate set of influential training samples that support or oppose the prediction either directly or by contrast. To provide a succinct summary, AIDE uses diversity-aware sampling to avoid redundancy and increase coverage of the training data. We demonstrate the effectiveness of AIDE on image and text classification tasks, in three ways: quantitatively, assessing correctness and continuity; qualitatively, comparing anecdotal evidence from AIDE and other example-based approaches; and via a user study, evaluating multiple aspects of AIDE. The results show that AIDE addresses the limitations of existing methods and exhibits desirable traits for an explainability method.

We present HYPPO, a novel system to optimize pipelines encountered in exploratory machine learning. HYPPO exploits alternative computational paths of artifacts from past executions to derive better execution plans while reusing materialized artifacts. Adding alternative computations introduces new challenges for exploratory machine learning regarding workload representation, system architecture, and optimal execution plan generation. To this end, we present a novel workload representation based on directed hypergraphs, and we formulate the problem of discovering the optimal execution plan as a search problem over directed hypergraphs and that of selecting artifacts to materialize as an optimization problem. A thorough experimental evaluation shows that HYPPO results in plans that are typically one order (up to two orders) of magnitude faster and cheaper than the non-optimized pipeline and considerably (up to one order of magnitude) faster and cheaper than plans generated by the state of the art when materializing artifacts is possible. Lastly, our evaluation reveals that HYPPO reduces the cost by 3–4× even when materialization cannot be exploited.

We study the data sparsity problem for data generated from an integration system. We approach the problem from a textual information extraction perspective and propose to conceptualize external documents using the concepts in the integrated schema. We present THOR, a novel system that, unlike related approaches, neither relies on complex rules nor models trained with large annotated corpus, but on the integrated data and its schema without the need for human annotations. An extensive evaluation on the text conceptualization task demonstrates the superiority of our approach in terms of F1-score, effort and use of resources over the state-of-the-art language models.

In this study, we examine how to improve the Spatial Fairness of a classifier by selecting suitable modifications, flips, to its output. When Machine Learning algorithms are evaluated for Spatial Fairness and found to be unfair, it is important to make corrections to prevent the development of products and services that discriminate against individuals based on their location. We compared five different strategies for improving the Spatial Fairness of a classifier by computing observations' features. Among these strategies, an ensemble approach proved to be the most effective by modifying points among the recommendations made by simpler strategies.

In this work, we present Fairness Aware Counterfactuals for Subgroups (FACTS), a framework for auditing subgroup fairness through counterfactual explanations. We start with revisiting (and generalizing) existing notions and introducing new, more refined notions of subgroup fairness. We aim to (a) formulate different aspects of the difficulty of individuals in certain subgroups to achieve recourse, i.e. receive the desired outcome, either at the micro level, considering members of the subgroup individually, or at the macro level, considering the subgroup as a whole, and (b) introduce notions of subgroup fairness that are robust, if not totally oblivious, to the cost of achieving recourse. We accompany these notions with an efficient, model-agnostic, highly parameterizable, and explainable framework for evaluating subgroup fairness. We demonstrate the advantages, the wide applicability, and the efficiency of our approach through a thorough experimental evaluation on different benchmark datasets.

Set similarity join is an important problem with many applications in data discovery, cleaning and integration. To increase robustness, fuzzy set similarity join calculates the similarity of two sets based on maximum weighted bipartite matching instead of set overlap. This allows pairs of elements, represented as sets or strings, to also match approximately rather than exactly, e.g., based on Jaccard similarity or edit distance. However, this significantly increases the verification cost, making even more important the need for efficient and effective filtering techniques to reduce the number of candidate pairs. The current state-of-the-art algorithm relies on similarity computations between pairs of elements to filter candidates. In this paper, we propose token-based instead of element-based filtering, showing that it is significantly more lightweight, while offering similar or even better pruning effectiveness. Moreover, we address the top- k variant of the problem, alleviating the need for a user-specified similarity threshold. We also propose early termination to reduce the cost of verification. Our experimental results on six real-world datasets show that our approach always outperforms the state of the art, being an order of magnitude faster on average.

Given a collection of geospatial points of different types, mixture-based best region search aims at discovering spatial regions exhibiting either very high or very low mixture with respect to the types of enclosed points. Existing works detect fixed-shape regions, such as circles or rectangles, thus often missing interesting regions occurring in real-world data that may have arbitrary shapes. In this paper, we formulate the problem of mixture-based best region search for arbitrarily shaped regions, introducing certain desired properties to ensure their cohesiveness and completeness. Since computing exact solutions to this problem has exponential cost with respect to the number of points, we propose anytime algorithms that efficiently search the space of candidate solutions to produce high-scoring regions under any given time budget. Our experiments on several real-world datasets show that our algorithms can produce high-quality results even within tight time constraints.

The constantly increasing rate at which scientific papers are published makes it difficult for researchers to identify papers that currently impact the research field of their interest. In this work, we present a method that ranks papers based on their estimated short-term impact, as measured by the number of citations received in the near future. Our method models a researcher exploring the paper citation network, and introduces an attention-based mechanism, akin to a time-restricted version of preferential attachment, that explicitly captures the researcher's preference to read papers which received a lot of attention recently. A detailed experimental evaluation on real citation datasets across disciplines, shows that our approach is more effective than previous work.

Explanations for algorithmically generated recommendations is an important requirement for transparent and trustworthy recommender systems. When the internal recommendation model is not inherently interpretable (e.g., most contemporary systems are complex and opaque), or when access to the system is not available (e.g., recommendation as a service), explanations have to be generated post-hoc, i.e., after the system is trained. In this common setting, the standard approach is to provide plausible interpretations of the observed outputs of the system, e.g., by building a simple surrogate model that is inherently interpretable, and explaining that model. This however has several drawbacks. First, such explanations are not truthful, as they are rationalizations of the observed inputs and outputs constructed by another system. Second, there are privacy concerns, as to train a surrogate model, one has to know the interactions from users other than the one who seeks an explanation. Third, such explanations may not be scrutable and actionable, as they typically return weights for items or other users that are difficult to comprehend, and hard to act upon so to improve the quality of one’s recommendations.

As the rate at which scientific work is published continues to increase, so does the need to discern high-impact publications. In recent years, there have been several approaches that seek to rank publications based on their expected citation-based impact. Despite this level of attention, this research area has not been systematically studied. Past literature often fails to distinguish between short-term impact, the current popularity of an article, and long-term impact, the overall influence of an article. Moreover, the evaluation methodologies applied vary widely and are inconsistent. In this work, we aim to fill these gaps, studying impact-based ranking theoretically and experimentally. First, we provide explicit definitions for short-term and long-term impact, and introduce the associated ranking problems. Then, we identify and classify the most important ideas employed by state-of-the-art methods. After studying various evaluation methodologies of the literature, we propose a specific benchmark framework that can help us better differentiate effectiveness across impact aspects. Using this framework we investigate: (1) the practical difference between ranking by short- and long-term impact, and (2) the effectiveness and efficiency of ranking methods in different settings. To avoid reporting results that are discipline-dependent, we perform our experiments using four datasets from different scientific disciplines.

Service selection is a challenging task, and a lot of effort has been devoted to tools that assist the user in choosing the service whose non-functional parameters better match her/his preferences. In many practical situations, the responsibility to decide which is the appropriate service is shared among multiple parties. A standard approach to this service selection problem is to discard services that are unanimously considered inappropriate and focus on the rest. However, as the involved parties may have colliding interests, only a few services may be eliminated. This work addresses this shortcoming and enables users to reach a “democratic” decision by means of a majority vote: a service is eliminated if the majority of the parties find it inappropriate. We formulate the problem using dominance relationships, and propose algorithms that return an appropriate subset of services for the parties, while being more efficient than standard techniques. Moreover, we consider the problem of defining an appropriate ranking for the non eliminated services, and formulate it as an instance of a group recommendation problem. Finally, we demonstrate the effectiveness and the efficiency of our approach through extensive experimental evaluation on real-based and synthetic datasets.

Social-based recommenders seek to exploit the mechanisms of homophily and influence observed in social networks in order to provide more accurate recommendations. The way they achieve this is by enforcing similar preferences among users that are socially connected. It is thus reasonable to question whether such approaches lead to the formation of echo chambers, i.e., social groups with a narrow set of preferences and which receive recommendations with low diversity and novelty. This work studies this research question and quantifies the diversity and novelty of existing methods. An important finding is that it is possible to increase accuracy without sacrificing diversity and novelty.

Given a set of geospatial objects, the Best Region Search problem finds the optimal placement of a fixed-size rectangle so that the value of a user-defined utility function over the enclosed objects is maximized. The existing algorithm for this problem computes only the top result. However, this is often quite restrictive in practice and falls short in providing sufficient insight about the dataset. In this paper, we introduce the k-BRS problem, and we present a method for efficiently and progressively computing the next best result for any number k of results requested by the user. We show that our approach can accommodate additional constraints. In particular, we consider the requirement of computing the next best rectangle that has no or little overlap with the already retrieved ones, which reduces the repetition and redundancy in the results presented to the user. Our experimental evaluation demonstrates that our algorithms are efficient and scalable to large real-world datasets.

Thousands of posts are generated constantly by millions of users in social media, with an increasing portion of this content being geotagged. Keeping track of the whole stream of this spatio-textual content can easily become overwhelming for the user. In this paper, we address the problem of selecting a small, representative and diversified subset of posts, which is continuously updated over a sliding window. Each such subset can be considered as a concise summary of the stream's contents within the respective time interval, being dynamically updated every time the window slides to reflect newly arrived and expired posts. We define the criteria for selecting the contents of each summary, and we present several alternative strategies for summary construction and maintenance that provide different trade-offs between information quality and performance. Furthermore, we optimize the performance of our methods by partitioning the newly arriving posts spatio-textually and computing bounds for the coverage and diversity of the posts in each partition. The proposed methods are evaluated experimentally using real-world datasets containing geotagged tweets and photos.

S.558-561

An increasing amount of user-generated content on the Web is geotagged. This often results in the formation of user trails, e.g., sequences of photos, check-ins, or text messages, that users generate while visiting various locations. In this paper, we introduce and study the problem of identifying sets of locations that are strongly associated under social and textual criteria. We say that a location set is associated with a set of keywords if there exists a user with posts around these locations whose textual descriptions cover all keywords. We measure the strength of this association by the number of users with posts that support it. Although the problem reminisces frequent itemset mining, we show that our support measure does not satisfy the necessary anti-monotonicity property, which is used to effectively prune the search space. Nonetheless, by studying the characteristics of the support measure, we are able to devise an efficient approach. We present a basic and two optimized algorithms, exploiting an inverted or a spatio-textual index to increase efficiency. Finally, we conduct an experimental evaluation using geotagged Flickr photos in three major cities. From a qualitative perspective, the results indicate that the introduced type of query returns meaningful and interesting location sets, which are not discovered by other existing approaches. Furthermore, the proposed optimizations and the use of appropriate indexes significantly reduce computation time.

Digital location traces can help build insights about how citizens experience their cities, but also offer personalized products and experiences to them. Even as data abound, though, building an accurate picture about citizen whereabouts is not always straightforward, due to noisy or incomplete data.

Consider a road network, and let the preferred subnet consist of the roads a driver is more acquainted to and hence tends to follow. In this paper, we study the problem of finding the most preferred path between two network nodes; we consider two variants of this problem. We first target the Most Preferred Unrestricted Path (MPUP) that has the lowest traveling time in the non-preferred subnet; this problem was introduced in the literature as identifying the safest path though safe zones. As MPUP imposes no constraints on the total traveling time, we then introduce the Most Preferred Near Shortest Path (MPNSP) that has the lowest traveling time in the non-preferred subnet among all paths which are not much slower than the shortest path. We focus on the efficient evaluation of both problems by proposing solutions with simple pre-processing steps. An extensive evaluation demonstrates the efficiency of our techniques compared to the existing method for MPUP and to the state-of-the-art on computing multi-criteria shortest paths for MPNSP.

In this paper, we address the problem of continuously maintaining a concise, diversified summary of the contents of a sliding window over a stream of geotagged posts. Selecting posts to include in the summary takes into account both the criteria of coverage and diversity, and the summary is updated dynamically when the window slides. Our proposed strategy provides a trade-off between information quality and performance. An experimental evaluation of our method is presented using two real-world datasets containing spatio-textual posts from Twitter and Flickr.

In many domains, it is often required to provide recommendations for groups, instead of individual users. Existing approaches try to compensate for the lack of group profiles, by either merging individual profiles, or treating users separately and then fusing the recommendations. Both paradigms thus fail to account for the different roles and behaviors people assume when making group decisions. In this work, we propose two novel group recommendation models that explicitly try to model the behavior of group members and distinguish it from that when they act alone. A detailed evaluation has shown that our models consistently provide significantly better recommendations. In addition, useful conclusions are drawn regarding the favorable settings of existing techniques.

The amount of crowdsourced geospatial content on the Web is constantly increasing, providing a wealth of information for a variety of location-based services and applications. This content can be analyzed to discover interesting locations in large urban environments which people choose for different purposes, such as for entertainment, shopping, business or culture. In this paper, we focus on the problem of identifying and describing Streets of Interest. Given the road network in a specified area, and a collection of geolocated Points of Interest and photos in this area, our goal is to identify the most interesting streets for a specified category or keyword set, and to allow their visual exploration by selecting a small and spatio-textually diverse set of relevant photos. We formally define the problem and we present efficient algorithms, based on spatiotextual indices and filter and refinement strategies. The proposed methods are evaluated experimentally regarding their effectiveness and efficiency, using three real-world datasets containing road networks, POIs and photos collected from several Web sources.

Large amounts of user-generated content are posted daily on the Web, including textual, spatial and temporal information. Exploiting this content to detect, analyze and monitor events and topics that have a potentially large span in space and time requires efficient retrieval and ranking based on criteria including all three dimensions. In this paper, we introduce a novel type of spatial-temporal-keyword query that combines keyword search with the task of maximizing the spatio-temporal coverage and diversity of the returned top-f results. We first describe a baseline algorithm based on related search results diversification problems. Then, we develop an efficient approach which exploits a hybrid spatial-temporal-keyword index to drastically reduce query execution time. To that end, we extend two state-of-the- art indices for top-f spatio-textual queries and describe how our proposed approach can be applied on top of them. We evaluate the efficiency of our algorithms by conducting experiments on two large, real-world datasets containing geotagged tweets and photos.

Given a set of attractors and repellers, the cohesion query returns the point in database that is as close to the attractors and as far from the repellers as possible. Cohesion queries find applications in various settings, such as facility location problems, location-based services. For example, when attractors represent favorable plases, e.g., tourist attractions, and repellers denote undesirable locations, e.g., competitor stores, the cohesion query would return the ideal location, among a database of possible options, to open a new store. These queries are not trivial to process as the best location, unlike aggregate nearest or farthest neighbor queries, may be far from the optimal point in space. Therefore, to achieve sub-linear performance in practice, we employ novel best-first search and branch and bound paradigms that take advantage of the geometrical interpretation of the problem. Our methods are up to orders of magnitude faster than linear scan and adaptations of existing aggregate nearest/farthest neighbor algorithms.

We introduce a generic framework, termed RIPPLE, for processing rank queries in decentralized systems. Rank queries are particularly challenging, since the search area (i.e., which tuples qualify) cannot be determined by any peer individually. While our proposed framework is generic enough to apply to all decentralized structured systems, we show that when coupled with a particular distributed hash table (DHT) topology, it offers guaranteed worst-case performance. Specifically, rank query processing in our framework exhibits tunable polylogarithmic latency, in terms of the network size. Additionally we provide a means to trade-off latency for communication and processing cost. As a proof of concept, we apply RIPPLE for top-k query processing. Then, we consider skyline queries, and demonstrate that our framework results in a method that has better latency and lower overall communication cost than existing approaches over DHTs. Finally, we provide a RIPPLEbased approach for constructing a k-diversified set, which, to the best of our knowledge, is the first distributed solution for this problem. Extensive experiments with real and synthetic datasets validate the effectiveness of our framework.

The ubiquity of mobile location aware devices and the proliferation of social networks have given rise to Location-Aware Social Networks (LASN), where users form social connections and make geo-referenced posts. The goal of this paper is to identify users that can influence a large number of important other users, within a given spatial region. Returning a ranked list of regionally influential LASN users is useful in viral marketing and in other per-region analytical scenarios. We show that under a general influence propagation model, the problem is #P-hard, while it becomes solvable in polynomial time in a more restricted model. Under the more restrictive model, we then show that the problem can be translated to computing a variant of the so-called closeness centrality of users in the social network, and devise an evaluation method.

Analyzing tracking data of various types of moving objects is an interesting research problem with numerous real-world applications. Several works have focused on continuously monitoring the nearest neighbors of a moving object, while others have proposed similarity measures for finding similar trajectories in databases containing historical tracking data. In this work, we introduce the problem of continuously monitoring nearest trajectories. In contrast to other similar approaches, we are interested in monitoring moving objects taking into account at each timestamp not only their current positions but their recent trajectory in a defined time window. We first describe a generic baseline algorithm for this problem, which applies for any aggregate function used to compute trajectory distances between objects, and without any restrictions on the movement of the objects. Using this as a framework, we continue to derive an optimized algorithm for the cases where the distance between two moving objects in a time window is determined by their maximum or minimum distance in all contained timestamps. Furthermore, we propose additional optimizations for the case that an upper bound on the velocities of the objects exists. Finally, we evaluate the efficiency of our proposed algorithms by conducting experiments on three real-world datasets.

MicroRNAs (miRNAs) are small RNA molecules that inhibit the expression of particular genes, a function that makes them useful towards the treatment of many diseases. Computational methods that predict which genes are targeted by particular miRNA molecules are known as target prediction methods. In this paper, we present a MapReduce-based system, termed MR-microT, for one of the most popular and accurate, but computational intensive, prediction methods. MR-microT offers the highly requested by life scientists feature of predicting the targets of ad-hoc miRNA molecules in near-real time through an intuitive Web interface.

The problem of providing meaningful routing directions over road networks is of great importance. In many real-life cases, the fastest route may not be the ideal choice for providing directions in written/spoken text, or for an unfamiliar neighborhood, or in cases of emergency. Rather, it is often more preferable to offer "simple" directions that are easy to memorize, explain, understand or follow. However, there exist cases where the simplest route is considerably longer than the fastest. This paper tries to address this issue, by finding near-simplest routes which are as short as possible and near-fastest routes which are as simple as possible. Particularly, we focus on efficiency, and propose novel algorithms, which are theoretically and experimentally shown to be significantly faster than existing approaches.

The recent advances in the infrastructure of Geographic Information Systems (GIS), and the proliferation of GPS technology, have resulted in the abundance of geodata in the form of sequences of points of interest (POIs), waypoints, etc. We refer to sets of such sequences as route collections. In this work, we consider path queries on frequently updated route collections: given a route collection and two points nsand nt, a path query returns a path, i.e., a sequence of points, that connects nsto nt. We introduce two path query evaluation paradigms that enjoy the benefits of search algorithms (i.e., fast index maintenance) while utilizing transitivity information to terminate the search sooner. Efficient indexing schemes and appropriate updating procedures are introduced. An extensive experimental evaluation verifies the advantages of our methods compared to conventional graph-based search.

This work presents MIDAS-RDF, a distributed P2P RDF/S repository that is built on top of a distributed multi-dimensional index structure. MIDAS-RDF features fast retrieval of RDF triples satisfying various pattern queries by translating them into multi-dimensional range queries, which can be processed by the underlying index in hops logarithmic to the number of peers. More importantly, MIDAS-RDF utilizes a labeling scheme to handle expensive transitive closure computations efficiently. This allows for distributed RDFS reasoning in a more scalable way compared to existing methods, as also demonstrated by our extensive experimental study. Furthermore, MIDAS-RDF supports a publish-subscribe model that enables remote peers to selectively subscribe to RDF content.

The skyline query returns the most interesting tuples according to a set of explicitly defined preferences among attribute values. This work relaxes this requirement, and allows users to pose meaningful skyline queries without stating their choices. To compensate for missing knowledge, we first determine a set of uncertain preferences based on user profiles, i.e., information collected for previous contexts. Then, we define a probabilistic contextual skyline query (p-CSQ) that returns the tuples which are interesting with high probability. We emphasize that, unlike past work, uncertainty lies within the query and not the data, i.e., it is in the relationships among tuples rather than in their attribute values. Furthermore, due to the nature of this uncertainty, popular skyline methods, which rely on a particular tuple visit order, do not apply for p-CSQs. Therefore, we present novel non-indexed and index-based algorithms for answering p-CSQs. Our experimental evaluation concludes that the proposed techniques are significantly more efficient compared to a standard block nested loops approach.

The concept of k-anonymity has received considerable attention due to the need of several organizations to release microdata without revealing the identity of individuals. Although all previous k-anonymity techniques assume the existence of a public database (PD) that can be used to breach privacy, none utilizes PD during the anonymization process. Specifically, existing generalization algorithms create anonymous tables using only the microdata table (MT) to be published, independently of the external knowledge available. This omission leads to high information loss. Motivated by this observation, we first introduce the concept of k-join-anonymity (KJA), which permits more effective generalization to reduce the information loss. Briefly, KJA anonymizes a superset of MT, which includes selected records from PD. We propose two methodologies for adapting k-anonymity algorithms to their KJA counterparts. The first generalizes the combination of MT and PD, under the constraint that each group should contain at least 1 tuple of MT (otherwise, the group is useless and discarded). The second anonymizes MT, and then, refines the resulting groups using PD. Finally, we evaluate the effectiveness of our contributions with an extensive experimental evaluation using real and synthetic data sets.

As the web is increasingly used not only to find answers to specific information needs but also to carry out various tasks, enhancing the capabilities of current web search engines with effective and efficient techniques for web service retrieval and selection becomes an important issue. Existing service matchmakers typically determine the relevance between a web service advertisement and a service request by computing an overall score that aggregates individual matching scores among the various parameters in their descriptions. Two main drawbacks characterize such approaches. First, there is no single matching criterion that is optimal for determining the similarity between parameters. Instead, there are numerous approaches ranging from Information Retrieval similarity measures up to semantic logic-based inference rules. Second, the reduction of individual scores to an overall similarity leads to significant information loss. Determining appropriate weights for these intermediate scores requires knowledge of user preferences, which is often not possible or easy to acquire. Instead, using a typical aggregation function, such as the average or the minimum of the degrees of match across the service parameters, introduces undesired bias, which often reduces the accuracy of the retrieval process. Consequently, several services, e.g., those having a single unmatched parameter, may be excluded from the result set, while being potentially good candidates. In this work, we present two complementary approaches that overcome the aforementioned deficiencies. First, we propose a methodology for ranking the relevant services for a given request, introducing objective measures based on dominance relationships defined among the services. Second, we investigate methods for clustering the relevant services in a way that reveals and reflects the different trade-offs between the matched parameters. We demonstrate the effectiveness and the efficiency of our proposed techniques and algorithms through extensive experimental evaluation on both real requests and relevance sets, as well as on synthetic scenarios.

As we move from a Web of data to a Web of services, enhancing the capabilities of the current Web search engines with effective and efficient techniques for Web services retrieval and selection becomes an important issue. Traditionally, the relevance of a Web service advertisement to a service request is determined by computing an overall score that aggregates individual matching scores among the various parameters in their descriptions. Two drawbacks characterize such approaches. First, there is no single matching criterion that is optimal for determining the similarity between parameters. Instead, there are numerous approaches ranging from using Information Retrieval similarity metrics up to semantic logic-based inference rules. Second, the reduction of individual scores to an overall similarity leads to significant information loss. Since there is no consensus on how to weight these scores, existing methods are typically pessimistic, adopting a worst-case scenario. As a consequence, several services, e.g., those having a single unrelated parameter, can be excluded from the result set, even though they are potentially good alternatives. In this work, we present a methodology that overcomes both deficiencies. Given a request, we introduce an objective measure that assigns a dominance score to each advertised Web service. This score takes into consideration all the available criteria for each parameter in the request. We investigate three distinct definitions of dominance score, and we devise efficient algorithms that retrieve the top-k most dominant Web services in each case. Extensive experimental evaluation on real requests and relevance sets, as well as on synthetically generated scenarios, demonstrates both the effectiveness of the proposed technique and the efficiency of the algorithms.

The vast majority of work on skyline queries considers totally ordered domains, whereas in many applications some attributes are partially ordered, as for instance, domains of set values, hierarchies, intervals and preferences. The only work addressing this issue has limited progressiveness and pruning ability, and it is only applicable to static skylines. This paper overcomes these problems with the following contributions: (i) we introduce a generic framework, termed TSS, for handling partially ordered domains using topological sorting. (ii) We propose a novel dominance check that eliminates false hits/misses, further enhancing progressiveness and pruning ability. (iii) We extend our methodology to dynamic skylines with respect to an input query. In this case, the dominance relationships change according to the query specification, and their computation is rather complex. We perform an extensive experimental evaluation demonstrating that TSS is up to 9 times and up to 2 orders of magnitude faster than existing methods in the static and the dynamic case, respectively.

We consider an environment of numerous moving objects, equipped with location-sensing devices and capable of communicating with a central coordinator. In this setting, we investigate the problem of maintaining hot motion paths, i.e., routes frequently followed by multiple objects over the recent past. Motion paths approximate portions of objects' movement within a tolerance margin that depends on the uncertainty inherent in positional measurements. Discovery of hot motion paths is important to applications requiring classification/profiling based on monitored movement patterns, such as targeted advertising, resource allocation, etc. To achieve this goal, we delegate part of the path extraction process to objects, by assigning to them adaptive lightweight filters that dynamically suppress unnecessary location updates and, thus, help reducing the communication overhead. We demonstrate the benefits of our methods and their efficiency through extensive experiments on synthetic data sets.

Summarization is an important task in data mining. A major challenge over the past years has been the efficient construction of fixed-space synopses that provide a deterministic quality guarantee, often expressed in terms of a maximum-error metric. Histograms and several hierarchical techniques have been proposed for this problem. However, their time and/or space complexities remain impractically high and depend not only on the data set size n, but also on the space budget B. These handicaps stem from a requirement to tabulate all allocations of synopsis space to different regions of the data. In this paper we develop an alternative methodology that dispels these deficiencies, thanks to a fruitful application of the solution to the dual problem: given a maximum allowed error, determine the minimum-space synopsis that achieves it. Compared to the state-of-the-art, our histogram construction algorithm reduces time complexity by (at least) a Blog2n over logε* factor and our hierarchical synopsis algorithm reduces the complexity by (at least) a factor of log2B over logε* + logn in time and B(1-log B over log n) in space, where ε* is the optimal error. These complexity advantages offer both a space-efficiency and a scalability that previous approaches lacked. We verify the benefits of our approach in practice by experimentation.

In this paper we perform an extensive theoretical and experimental study on common synopsis construction algorithms, with emphasis on wavelet based techniques, that take under consideration query workload statistics. Our goal is to compare, "expensive" quadratic time algorithms with "cheap" near-linear time algorithms, particularly when the latter are not optimal and/or not workload-aware for the problem at hand. Further, we present the first known algorithm for constructing wavelet synopses for a special class of range-sum query workloads. Our experimental results, clearly justify the necessity for designing workload-aware algorithms, especially in the case of range-sum queries.

The Discrete Wavelet Transform is a proven tool for a wide range of database applications. However, despite broad acceptance, some of its properties have not been fully explored and thus not exploited, particularly for two common forms of multidimensional decomposition. We introduce two novel operations for wavelet transformed data, termed SHIFT and SPLIT, based on the properties of wavelet trees, which work directly in the wavelet domain. We demonstrate their significance and usefulness by analytically proving six important results in four common data maintenance scenarios, i.e., transformation of massive datasets, appending data, approximation of data streams and partial data reconstruction, leading to significant I/O cost reduction in all cases. Furthermore, we show how these operations can be further improved in combination with the optimal coefficient-to-disk-block allocation strategy. Our exhaustive set of empirical experiments with real-world datasets verifies our claims.